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

让我们来看一下 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;
    }

执行过程大致是这样的：

1. 先对table的非空检查,为空就初始化

2. 对key的非空检查，如果key是null，会被存储到table[0]，因为null的hash值总是0

3. 对key的hashCode()做hash，然后再通过indexFor()计算index,这个就是table数组的索引;

4. 如果在刚才计算出来的索引位置中table没有元素，直接把Entry对象放在那个索引上

5. 如果索引上有元素，然后会进行迭代，在迭代的过程中，会调用equals()方法来检查key的相等性(key.equals(k))，如果这个方法返回true，它就会用当前Entry的value来替换之前的value。如果返回false就一直到Entry->next是null，把当前的Entry对象变成链表的下一个节点

6. 如果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的时候：

1. 对key进行null检查。如果key是null，table[0]这个位置的元素将被返回。

2. key的hashcode()方法被调用，然后计算hash值。

3. indexFor(hash,table.length)用来计算要获取的Entry对象在table数组中的精确的位置，使用刚才计算的hash值。在获取了table数组的索引之后，会迭代链表，调用equals()方法检查key的相等性，如果equals()方法返回true，get方法返回Entry对象的value，否则，返回null。

总结：

1. HashMap中数据是用一个叫table的数组来存的，table的索引在逻辑上叫做“桶”(bucket)，它存储了链表的第一个元素。
2. HashMap有一个叫做Entry的内部类，它用来存储key-value对。table数组存的就是它。Entry用一个next属性实现多个Entry以单向链表存放，插入元素时，如果两条Key落在同一个桶，并且这两条key不equals,后入桶的Entry将next指向桶当前的Entry，否则后入桶的会将前面的给覆盖（确保key的唯一性）;
3. 使用HashMap的时候最好使用泛型，如果key放的是自己的对象，最好重写equals()和hashcode()。

百度找了一张形象点的HashMap结构图（无耻）

由上图可以看出哈希表是一个数组+链表的存储结构。HashMap存储结构文字解释：

table[0] →[index=1,Entry<K,V>] 


 table[1] →[index=2,Entry<K,V>]

  ...

 依次类推