Java HashMap工作原理及实现
很多刚学Java的同学们都知道HashMap，平常一般使用，可能并不知道它的工作原理，前段时间有为刚毕业的同事在使用HashMap的时候碰到了个问题找我，问题大概是这样的：
Map map = new HashMap();
map.put(1l, "abc");
System.out.println(map.get(1));
明明有值啊，为什么是null呢？
下面我们一起来探讨一下HashMap的工作原理及实现，首先看个例子，带着问题去研究
public class TestMap {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<String, Integer>();
map.put(null, 0);
map.put("java", 1);
map.put("c++", 2);
map.put("python", 3);
map.put("php", 4);
map.put("nodejs", 5);
for(Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
System.out.println("php".hashCode() == "c++".hashCode());
}
}
运行结果是：
null: 0
php: 4
c++: 2
java: 1
nodejs: 5
false
20161001120548021.png
让我们来看一下 HashMap 中的几个参数的意义
- loadFactor : 负载因子 默认0.75
initialCapacity : 初始化容量16，最大是（1 << 30）1073741824
table : Entry<K,V>[] table 是用来存储数据的数组
Entry<K,V> 是HashMap的一个内部类，链表结构
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
...
}
既然table是用来存储数据的，那么例子中我们往map放了六条数据，table中应该就有六条数据对吧。细心的同学可能发现了上图table中只有四条，table[0]，table[7]，table[10]，table[12]数据，还有两条数据去哪了呢？而且打印结果也是六条数据。是不是eclipse有bug啊，还有两条数据没显示出来。 再仔细一看为什么“c++”这条数据跑到了table[7]的next去了，那null这条数据呢？看来不是eclipse的bug(尴尬的表情)，那原因是什么呢？
我们先来看看执行put()的时候到底做了什么？大概浏览一下源码
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
执行过程大致是这样的：
-
先对table的非空检查,为空就初始化
-
对key的非空检查，如果key是null，会被存储到table[0]，因为null的hash值总是0
-
对key的hashCode()做hash，然后再通过indexFor()计算index,这个就是table数组的索引;
-
如果在刚才计算出来的索引位置中table没有元素，直接把Entry对象放在那个索引上
-
如果索引上有元素，然后会进行迭代，在迭代的过程中，会调用equals()方法来检查key的相等性(key.equals(k))，如果这个方法返回true，它就会用当前Entry的value来替换之前的value。如果返回false就一直到Entry->next是null，把当前的Entry对象变成链表的下一个节点
-
如果table的长度超过了loadFactor *current capacity，就要重新resize一个原来长度两倍的HashMap
到这里就恍然大悟了，刚才“c++”为什么会跑到table[7]中了，原来“PHP”和“c++”的hashCode()做hash，然后再通过indexFor()计算出来的index都是7，但是“php”和“c++”并不equals，所以这两条数据就形成一个链表存在table[7]中。至于null那条数据去哪了，大家应该也知道了。
那get()方法呢？
当你理解了hashmap的put的工作原理，理解get的工作原理就非常简单了。当你传递一个key从hashmap总获取value的时候：
-
对key进行null检查。如果key是null，table[0]这个位置的元素将被返回。
-
key的hashcode()方法被调用，然后计算hash值。
-
indexFor(hash,table.length)用来计算要获取的Entry对象在table数组中的精确的位置，使用刚才计算的hash值。在获取了table数组的索引之后，会迭代链表，调用equals()方法检查key的相等性，如果equals()方法返回true，get方法返回Entry对象的value，否则，返回null。
总结：
- HashMap中数据是用一个叫table的数组来存的，table的索引在逻辑上叫做“桶”(bucket)，它存储了链表的第一个元素。
- HashMap有一个叫做Entry的内部类，它用来存储key-value对。table数组存的就是它。Entry用一个next属性实现多个Entry以单向链表存放，插入元素时，如果两条Key落在同一个桶，并且这两条key不equals,后入桶的Entry将next指向桶当前的Entry，否则后入桶的会将前面的给覆盖（确保key的唯一性）;
- 使用HashMap的时候最好使用泛型，如果key放的是自己的对象，最好重写equals()和hashcode()。
百度找了一张形象点的HashMap结构图（无耻）
20161001140638976.png
由上图可以看出哈希表是一个数组+链表的存储结构。HashMap存储结构文字解释：
table[0] →[index=1,Entry<K,V>]
table[1] →[index=2,Entry<K,V>]
...
依次类推
