Map即映射表：它存放的是键值对关联的对象。因此，可以通过键来查找值。
在了解Map之前，我们通过Map的概念，先思考几个问题：
- map如何存放键-值的？
- map如何确定键的唯一性？
- map如何通过键快速查找值？
- 自己如何实现一个简单的map？
抱着提出问题，解决问题的态度，让我们开始map之旅吧。
第一步：来实现一个能想到的最简单的Map
我能想到的最简单的map就是将key和value放入一个二维数组中，然后根据key去数组中循环查找value。
二话不说，开撸：
public class AssociativeArray<K, V> {
//定义pairs二维数组
private Object[][] pairs;
private int index;
/**
* 定义固定长度的数组
* */
public AssociativeArray(int length) {
//pairs二维数组的长度是length,宽度为2
pairs = new Object[length][2];
}
public void put(K key, V value) {
if (index >= pairs.length) {
throw new ArrayIndexOutOfBoundsException();
}
//将key和value放入数组
pairs[index++] = new Object[]{key, value};
}
/**
* 根据key来查询value的值
* */
public V get(K key) {
for (int i = 0; i < index; i++) {
if (key.equals(pairs[i][0])) return (V) pairs[i][1];
}
return null;
}
/**
* 重写toString方法，输出map中的数据
* */
public String toString() {
StringBuffer result = new StringBuffer();
for (int i = 0; i < index; i++) {
result.append(pairs[i][0].toString());
result.append(":");
result.append(pairs[i][1].toString());
if (i < index - 1) result.append("\n");
}
return result.toString();
}
public static void main(String[] args) {
//因为打算存5个元素，所以给数组固定一个长度为5
AssociativeArray<String,String> map = new AssociativeArray<>(5);
map.put("111","aaa");
map.put("222","bbb");
map.put("333","ccc");
map.put("444","ddd");
map.put("555","eee");
System.out.println(map);
System.out.println(map.get("333"));
}
}
上面的代码，输出结果符合预期，确实把对象对进去了，也取出来了。但是总感觉哪里不对？
- 首先，数组长度是固定的，我怎么可能每次都知道要传入的数组长度呢？
- 再有，每次根据key取value值，都要将数组循环一边，那要是这个数组很大，这性能差的要死啊。
- 最后，这个代码实在很low，一点也不高大上呀。
散列码和hashCode()
为了解决性能问题，HashMap使用了特殊值，散列码，来取代对键的缓慢搜索。
那什么是散列码呢？
散列码是：”相对唯一“的，用以代表对象的int值，它是通过将该对象的某些信息进行转换后由hashCode()生成的。
先来看一下不用散列码的例子：一个优秀的射击运动员在训练，向靶子射击10枪，设计完成后，想查看自己某一枪是否命中。
public class Shoot {
protected int number; //射击次数
public Shoot(int n){this.number = n;}
public String toString(){
return "Shoot # " + number;
}
}
public class Points {
private static Random ran = new Random();
//假设0-10环为命中，其他为脱靶
private boolean shadow = ran.nextInt(20) < 10 && ran.nextInt(20) > 0;
public String toString(){
if (shadow) return "命中！";
else return "脱靶！";
}
}
AssociativeArray类的main方法稍加改动
public static void main(String[] args) {
AssociativeArray<Groundhog,Prediction> map = new AssociativeArray<>(10);
for (int i = 0;i<10;i++){
map.put(new Shoot(i),new Points());
}
//打印map中的值
System.out.println(map);
//查看第三次射击是否命中，这时候发现输出是null
System.out.println(map.get(new Shoot(2)));
}
在打印map的值时，可以看到KEY中明明有2这个键，可为什么map.get(new Shoot(2))输出是null呢？
原因：问题出在Shoot自动地继承自基类Object，所以这里使用Object的
hashCode()方法生成散列码，而他默认是使用对象的地址计算散列码。因此，由new Shoot(2)生成的第一个实例的散列码与由new Shoot(2)生成的第二个实例的散列码是不同的，而我们正是使用后者进行查找的。
public class Shoot {
protected int number; //射击次数
public Shoot(int n){this.number = n;}
public String toString(){
return "Shoot # " + number;
}
//重写hashCode()方法,用number作为散列码
public int hashCode(){return number;}
//重写equles方法，默认的equals()只是比较对象的地址
public boolean equals(Object o){
return o instanceof Shoot && (number == ((Shoot)o).number);
}
}
在Shoot射击类中重写Object的hashCode()和equals(Object o)后，就可以正常查找射击是否命中了。
再写一个Map
我们知道了数组实现map的缺点，又了解了散列码和hashCode()，现在我们根据这些信息，让我们再实现一个更加完善的map吧。
public class SlowMap<K, V> extends AbstractMap<K, V> {
private List<K> keys = new ArrayList<K>();
private List<V> values = new ArrayList<V>();
public V put(K key, V value) {
V oldValue = get(key);
if (!keys.contains(key)) {
keys.add(key);
values.add(value);
} else values.set(keys.indexOf(key), value);
return oldValue;
}
public V get(Object key) {
if (keys.contains(key)) {
return values.get(keys.indexOf(key));
}
return null;
}
public V remove(Object key) {
if (keys.contains(key)) {
keys.remove(keys.indexOf(key));
}
return !keys.contains(key) ?
null : values.get(keys.indexOf(key));
}
public void clear() {
if(keys != null && keys.size() > 0){
keys = null;
values = null;
}
}
@Override
public Set<Entry<K, V>> entrySet() {
Set<Map.Entry<K,V>> set = new HashSet<>();
Iterator<K> ki = keys.iterator();
Iterator<V> vi = values.iterator();
while (ki.hasNext()) set.add(new MapEntry<>(ki.next(),vi.next()));
return set;
}
public static void main(String[] args) {
SlowMap<Integer ,String > map = new SlowMap<>();
String[] chars =
"A B C D E F G H I J K L M N O P Q R S T U V W X Y Z"
.split(" ");
for (int i = 0; i < chars.length; i++){
map.put(i,chars[i]);
}
System.out.println(map);
System.out.println("Map Size == " + map.size());
System.out.println(map.entrySet());
System.out.println(map.get(4));
System.out.println("删除元素: 【4】");
map.remove(4); //删除集合中的某个元素
System.out.println("Map Size == " + map.size());
//map.clear();//清空集合
System.out.println(map);
System.out.println(map.get(4));
}
}
public class MapEntry<K, V> implements Map.Entry<K, V> {
private K key;
private V value;
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V value) {
V reslut = value;
this.value = value;
return reslut;
}
public int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
public String toString(){return key + "=" + value;}
public MapEntry(K key, V value) {
this.key = key;
this.value = value;
}
}
分析代码：
SlowMap类继承了AbstractMap，又因为AbstractMap实现了Map接口，这样SlowMap就包含了Map借口的完整实现，继承AbstractMap需要实现entrySet()方法，entrySet()是返回此映射中包含的映射关系的 set 视图集合。
在entrySet()中使用的MapEntry类作用是保存和读取键值，在entrySet()中用来产生键值对的Set
这些代码看似很完美的模拟了map集合了，没毛病了～！
代码问题
- 问题出在Key和Value分别保存在了两个List集合中，整个类中
entrySet()方法只是提供了Map的副本，而不是视图。 - 再有List集合移除元素的速度也是很不理想的。
总之，这个比用单纯的数组是强多了，但是还是有很多可以优化的地方。
优化性能的自定义Map
public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
static final int SIZE = 997;
LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
public V put(K key, V value) {
V oldValue = null;
//计算散列码 abs(int a),返回a的绝对值
int index = Math.abs(key.hashCode()) % SIZE;
//如果集合数组中没有元素，则初始化一个数组元素
if (buckets[index] == null) buckets[index] = new LinkedList<>();
//获取元素
LinkedList<MapEntry<K, V>> bucket = buckets[index];
MapEntry<K, V> pair = new MapEntry<>(key, value); //将存入KEY,VALUE值存入pair
boolean found = false;
ListIterator<MapEntry<K, V>> it = bucket.listIterator();
while (it.hasNext()) {
MapEntry<K, V> iPair = it.next();
/**
* 对list中的值进行线性查询,解决冲突
* 既:当向数组集合中插入已经存在的key时,将会用新值的value替换原来的value值
* */
if (iPair.getKey().equals(key)) {
oldValue = iPair.getValue();
it.set(pair);
found = true;
break;
}
}
if (!found) buckets[index].add(pair);
return oldValue;
}
public V get(Object key) {
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets == null) return null;
for (MapEntry<K, V> iPair : buckets[index]) {
if (iPair.getKey().equals(key)) return iPair.getValue();
}
return null;
}
public V remove(Object key) {
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets == null) return null;
for (MapEntry<K, V> iPair : buckets[index]) {
if (iPair.getKey().equals(key)) {
//如果存在key的键值,则删除
buckets[index].remove(iPair);
} else{
return iPair.getValue();
}
}
return null;
}
public void clear() {
if (buckets != null && buckets.length > 0) {
buckets = null;
}
}
@Override
public Set<Entry<K, V>> entrySet() {
Set<Map.Entry<K, V>> set = new HashSet<>();
if(buckets != null && buckets.length > 0){
for (LinkedList<MapEntry<K, V>> bucket : buckets) {
if (bucket == null) continue;
set.addAll(bucket);
}
}
return set;
}
public static void main(String[] args) {
SimpleHashMap<Integer, String> map = new SimpleHashMap<>();
String[] chars =
"A B C D E F G H I J K L M N O P Q R S T U V W X Y Z"
.split(" ");
for (int i = 0; i < chars.length; i++) {
map.put(i, chars[i]);
}
System.out.println(map.entrySet());
System.out.println("map的长度是:" + map.size() + " ,第7个元素是: " + map.get(6));
map.remove(6);
System.out.println("map的长度是:" + map.size());
System.out.println(map.get(6));
map.clear();
System.out.println(map.entrySet());
}
}
虽然还存在一点小瑕疵（在解决冲突方面的性能还是略微欠缺），基本上可以表达map的原理了…
总结回顾
HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。既向Map中存入键值对时，实际上是初始化一个数组。使用散列码可以根据key找到对应的value，散列码是在hashCode()中计算。
转载请注明：R&M » JAVA集合——Map原理浅析
