最通俗易懂的 HashMap 源码分析解读

关注  “ 未读代码 ” ，不断 与你分享 原创文章 。

HashMap 作为最常用的集合类之一，有必要深入浅出的了解一下。这篇文章会深入到 HashMap 源码，刨析它的存储结构以及工作机制。

1. HashMap 的存储结构

HashMap 的数据存储结构是一个 Node<K,V> 数组，在（Java 7 中是 Entry<K,V> 数组，但结构相同）

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 数组
    transient Node<K,V>[] table;
	static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        // 链表
        Node<K,V> next;
        ....
	}
	.....
}

存储结构主要是 数组加链表 ，像下面的图。

2. HashMap 的 put()

在 Java 8 中 HashMap 的 put 方法如下，我已经详细注释了重要代码。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
// 计算哈希值 与（&）、非（~）、或（|）、异或（^）
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
   
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果数组为空，进行 resize() 初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果计算的位置上Node不存在，直接创建节点插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 如果计算的位置上Node 存在，链表处理
        Node<K,V> e; K k;
        // 如果 hash 值，k 值完全相同，直接覆盖
        if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果 index 位置元素已经存在，且是红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 如果这次要放入的值不存在
            for (int binCount = 0; ; ++binCount) {
                // 尾插法
                if ((e = p.next) == null) {
                    // 找到节点链表中next为空的节点，创建新的节点插入
                    p.next = newNode(hash, key, value, null);
                    // 如果节点链表中数量超过TREEIFY_THRESHOLD（8）个，转化为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果节点链表中有发现已有相同key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果节点 e 有值，放入数组 table[]
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
 
    ++modCount;
    // 当前大小大于临界大小，扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

举个例子，如果 put 的 key 为字母 a，当前 HashMap 容量是初始容量 16，计算出位置是 1。

# int hash = key.hashCode()
# hash = hash ^ (hash >>> 16)
# 公式 index = (n - 1) & hash // n 是容量
    
hash HEX(97)  = 0110 0001‬
n-1  HEX(15)  = 0000 1111
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1

总结 HashMap put 过程。

1. 计算 key 的 hash 值。

   计算方式是 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

2. 检查当前数组是否为空，为空需要进行初始化，初始化容量是 16 ，负载因子默认  0.75 。

3. 计算 key 在数组中的坐标。

   计算方式： (容量 - 1) & hash .

   因为容量总是2的次方，所以-1的值的二进制 总是全1 。方便与 hash 值进行 与 运算。

4. 如果计算出的坐标元素为空，创建节点加入，put 结束。

1. 如果当前数组容量大于负载因子设置的容量， 进行扩容 。

5. 如果计算出的坐标元素有值。

1. 如果 next 节点为空，把要加入的值和 key 加入 next 节点。

2. 如果 next 节点不为空，循环查看 next 节点。

   如果发现有 next 节点的 key 和要加入的 key 一样，对应的值替换为新值。

3. 如果循环 next 节点查找 超过8层 还不为空，把这个位置元素转换为 红黑树 。

4. 如果坐标上的元素值和要加入的值 key 完全一样，覆盖原有值。

5. 如果坐标上的元素是 红黑树 ，把要加入的值和 key 加入到红黑树。

6. 如果坐标上的元素和要加入的元素不同（ 尾插法 增加）。

3. HashMap 的 get()

在 Java 8 中 get 方法源码如下，我已经做了注释说明。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 只有在存储数组已经存在的情况下进入这个 if
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // first 是获取的坐标上元素
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            // key 相同，说明first是想要的元素，返回
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                // 如果是红黑树，从红黑树中查找结果
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 循环遍历查找
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
 }

get 方法流程总结。

1. 计算 key 的 hash 值。

2. 如果存储数组不为空，且计算得到的位置上的元素不为空。继续，否则，返回 Null。

3. 如果获取到的元素的 key 值相等，说明查找到了，返回元素。

4. 如果获取到的元素的 key 值不相等，查找 next 节点的元素。

1. 如果元素是红黑树，在红黑树中查找。

2. 不是红黑树，遍历 next 节点查找，找到则返回。

4. HashMap 的 Hash 规则

1. 计算 hash 值 int hash = key.hashCode()。

2. 与或上 hash 值无符号右移16 位。hash = hash ^ (hash >>> 16)。

3. 位置计算公式  index = (n - 1) & hash ，其中  n 是容量。

5. HashMap 的初始化大小

1. 初始化大小是 16，为什么是 16 呢？

   这可能是因为每次扩容都是 2 倍。而选择 2 的次方值 16 作为初始容量，有利于扩容时重新 Hash 计算位置。为什么是 16 我想是一个经验值，理论上说只要是 2 的次方都没有问题。

6. HashMap 的扩容方式

负载因子是多少？负载因子是 0.75 。

扩容方式是什么？看源码说明。

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        // 现有容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 现有扩容阀值
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            // 如果当前长度已经大于最大容量。结束扩容
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 如果扩大两倍之后小于最大容量，且现有容量大于等于初始容量，就扩大两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
               // 扩容阀值扩大为两倍
                newThr = oldThr << 1; // double threshold
        }
        // 当前容量 = 0 ，但是当前记录容量 > 0 ，获取当前记录容量。
       else if (oldThr > 0) // initial capacity was placed in threshold
            // 进入这里，说明是通过指定容量和负载因子的构造函数
            newCap = oldThr;
        else {    	           // zero initial threshold signifies using defaults
            // 进入这里说明是通过无参构造
            // 新的容量
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 新的阀值
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            // 计算扩容阀值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 如果 oldTab != null，说明是扩容，否则是初始化，直接返回
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 如果当前元素 next节点没有元素，当前元素重新计算位置直接放入
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // 如果当前节点是红黑树
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // == 0 ，位置不变
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // e.hash & oldCap != 0 ,位置变为：位置+扩容前容量
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

扩容时候怎么重新确定元素在数组中的位置，我们看到是由 if ((e.hash & oldCap) == 0) 确定的。

hash HEX(97)  = 0110 0001‬
n    HEX(16)  = 0001 0000
--------------------------
         结果  = 0000 0000
# e.hash & oldCap = 0 计算得到位置还是扩容前位置
    
hash HEX(17)  = 0001 0001‬
n    HEX(16)  = 0001 0000
--------------------------
         结果  = 0001 0000
#  e.hash & oldCap != 0 计算得到位置是扩容前位置+扩容前容量

通过上面的分析也可以看出，只有在每次容量都是2的次方的情况下才能使用 if ((e.hash & oldCap) == 0) 判断扩容后的位置。

7. HashMap 中的红黑树

HashMap 在 Java 8 中的实现增加了红黑树，当链表节点达到 8 个的时候，会把链表转换成红黑树，低于 6 个的时候，会退回链表。究其原因是因为当节点过多时，使用红黑树可以更高效的查找到节点。毕竟红黑树是一种二叉查找树。

1. 节点个数是多少的时候，链表会转变成红黑树。

   链表节点个数 大于等于 8 时 ，链表会转换成树结构。

2. 节点个数是多少的时候，红黑树会退回链表。

   节点个数 小于等于 6 时 ，树会转变成链表。

3. 为什么转变条件 8 和 6 有一个差值。

   如果没有差值，都是 8 ，那么如果频繁的插入删除元素，链表个数又刚好在 8 徘徊，那么就会频繁的发生链表转树，树转链表。

8. 为啥容量都是2的幂？

容量是2的幂时，key 的 hash 值然后 & (容量-1) 确定位置时 碰撞概率会比较低 ，因为容量为 2 的幂时，减 1 之后的二进制数为全1，这样与运算的结果就等于 hasｈ值后面与 1 进行与运算的几位。

下面是个例子。

hash HEX(97)  = 0110 0001‬
n-1  HEX(15)  = 0000 1111
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1
hash HEX(99)  = 0110 0011‬
n-1  HEX(15)  = 0000 1111
--------------------------
         结果  = 0000 0011
# 计算得到位置是 3
hash HEX(101)  = 0110 0101‬
n-1  HEX(15)   = 0000 1111
--------------------------
         结果   = 0000 0101
# 计算得到位置是 5

如果是其他的容量值，假设是9，进行与运算结果碰撞的概率就比较大。

hash HEX(97)  = 0110 0001‬
n-1  HEX(09)  = 0000 1001
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1
hash HEX(99)  = 0110 0011‬
n-1  HEX(09)  = 0000 1001
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1
hash HEX(101)  = 0110 0101‬
n-1  HEX(09)   = 0000 1001
--------------------------
         结果   = 0000 0001
# 计算得到位置是 1

另外，每次都是 2 的幂也可以让 HashMap 扩容时可以方便的 重新计算位置 。

hash HEX(97)  = 0110 0001‬
n-1  HEX(15)  = 0000 1111
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1
    
hash HEX(97)  = 0110 0001‬
n-1  HEX(31)  = 0001 1111
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1

9. 快速失败（fail—fast）

HashMap 遍历使用的是一种快速失败机制，它是 Java 非安全集合中的一种普遍机制，这种机制可以让集合在遍历时，如果有线程对集合进行了修改、删除、增加操作，会触发并发修改异常。

它的实现机制是在遍历前保存一份 modCount ，在每次获取下一个要遍历的元素时会对比当前的 modCount 和保存的 modCount 是否相等。

快速失败也可以看作是一种 安全机制 ，这样在多线程操作不安全的集合时，由于快速失败的机制，会抛出异常。

10. 线程安全的 Map

1. 使用 Collections.synchronizedMap(Map) 创建线程安全的 Map.

   实现原理：有一个变量 final Object mutex; ，操作方法都加了这个  synchronized (mutex) 排它锁。

2. 使用 Hashtable

3. 使用 ConcurrentHashMap

「朕已阅」 :point_down: