HashMap

概述

HashMap 是由哈希表实现，是线程不安全的，允许 key 和 value 为 null。在遍历时是无序的。哈希表底层数据节后是数组，数组中每个节点存储着链表，链表中的每个节点 ，就是 HashMap 中存储的元素。当链表长度大于 8 时，会转化为红黑树，以提升查询、插入效率。

由于是由数组实现的，HashMap 在容量达到 threshold 以后会触发扩容函数 resize()。在扩容前后，数组的长度一定是 2 的次方。这样在根据 key 的 hash 值查找元素的时候，可以使用位运算代替取余操作，效率更高。

通过 key 的 hashCode() 和数组长度取余，来确定对应的元素放在数组的哪个位置。但是由于数组长度远远小于 hashCode() 的取值范围，而取余操作会忽略 hash 的高位。这样计算出得到 index 值相同的概率会很大，这种情况称为 hash 碰撞。扰动函数可以很好的减少 hash 碰撞的概率。

在 JDK 中用 hash & (table.length - 1) 代替 hash % table.length，以提升效率。

每一个节点的 hash 值，是将 key 的 hashCode 和 value 的 hashCode 异或得到的。

源码

HashMap 扩容

final Node<K,V>[] resize() {
    	//存放旧的数组
        Node<K,V>[] oldTab = table;
    	//得到旧的数组的容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
    	//旧数组的阈值
        int oldThr = threshold;
    	//初始化新的数组容量和阈值
        int newCap, newThr = 0;
    	//1. 如果旧的数组中存在节点
        if (oldCap > 0) {
            //1.1 如果旧的数组容量已经达到上限
            if (oldCap >= MAXIMUM_CAPACITY) {
                //设置阈值是 2 的 30-1 次方（最大值）
                threshold = Integer.MAX_VALUE;
                //数组已经到达最大容量，无法扩容，返回旧的数组。
                return oldTab;
            }
            //1.2 否则将新数组容量扩大为旧数组的两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 新的阈值也扩大两倍
                newThr = oldThr << 1; // double threshold
        }
    	//2. 当前数组是空的，但是有阈值（代表指定了初始化的容量和阈值）
        else if (oldThr > 0) 
            newCap = oldThr;//设置新的容量是旧的阈值
    	//3. 当前数组是空的，并且没有指定阈值。代表初始化没有指定阈值和容量
        else { 
            //指定新的容量是默认的容量 16
            newCap = DEFAULT_INITIAL_CAPACITY;
            //指定新的阈值是默认的装填因子*默认的初始容量
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
    	//如果新的阈值是0，对应2.的情况，数组是空的但是初始化了阈值
        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;
    	//如果扩容前数组是不为空的，需要将旧数组中的节点转移到新的数组中。
        if (oldTab != null) {
            //遍历旧的数组
            for (int j = 0; j < oldCap; ++j) {
                //取出当前的节点
                Node<K,V> e;
                //1. 当前节点不为空
                if ((e = oldTab[j]) != null) {
                    //指定旧的数组引用为空
                    oldTab[j] = null;
                    //当前链表中只有一个元素，没有发生哈希碰撞
                    if (e.next == null)
                       	//将这个链表节点放在新的数组中
                        newTab[e.hash & (newCap - 1)] = e;
                    //当前链表是红黑树，链表长度超过了8
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //当前链表发生了哈希碰撞，并且没有转换为红黑树。依次将链表上的节点放在新数组中
                    else {
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        //当前节点的下一个节点
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            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;
    }

上面的代码每一步都有详细的注释。只有最后一部分遍历数组，将所有的数组中链表依次放在新的数组中合适的位置的代表有点难以理解。下面就一步一步慢慢的分析：

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;

定义了四个 Node 节点。从命名上可以知道是定义了 lo 和 hi 两个链表。这个四个 Node 节点分别指向 lo 和 hi 的头结点和尾节点。

接下来是一个 do-while 循环。可以看出来是在按排序遍历链表上的所有节点。

do {
    next = e.next;
    ...
} while ((e = next) != null);

在循环中的 if-else 语句，是一个插入链表的实现

// 插入lo链表
if (loTail == null)
    loHead = e;
else
    loTail.next = e;
loTail = e;

// 插入hi链表
if (hiTail == null)
    hiHead = e;
else
    hiTail.next = e;
hiTail = e;

上面的的代码大概就是创建了两个链表，然后遍历原链表上所有的节点，如果 (e.hash & oldCap) == 0,就将节点放入 lo 链表中，否则就放入 hi 链表中。

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

最后这一段实现了：

• 如果 lo 链表非空，就将整个 lo 链表放在新 table 的 j 位置上。
• 如果 hi 链表非空，就将整个 hi 链表放在新 table 的 j + oldCap 位置上。

整个上面的代码实现了：就是将原来的连边拆分成为 lo 和 hi 两个链表。，并将这两个链表分别放在新 table 的 j 和 j + oldCap 的位置上。而将原 table 的拆分的依据就是：(e.hash & oldCap) == 0.

关于 (e.hash & oldCap) == 0 和 j 、 j + oldCap

虽然弄懂了是如何把旧数组的节点转换到新数组中，但是上述的拆分条件看起来确实很奇怪。

首先要明确三点：

• 数组的长度一定是 2 的整数次幂。
• newCap 是 oldCap 的两倍。
• hash 对数组大小取余 n - 1 & hash 其实就是取 hash 的低 m 位。

首先假设数组的大小是 16 。那么 16 - 1 = 15 二进制表示为0000 1111。可以发现除了低 4 位，其他的位置都是 0，则 (16 - 1) & hash 自然就是取 hash 值的低 4 位。假设它是 abcd

这样在数组扩容后，数组的大小是 32。这样原节点在新数组中的位置 index 就是 (32 - 1) & hash,也就是取 hash 的低5位。那么对于同一个 Node，index 的值就只有两种情况：1abcd 或者 0abcd。其中 0abcd 和在旧数组中的 index 一样 abcd。而 1abcd = 0abcd + 10000 = 0abcd + oldCap。

所以虽然新旧 table 容量相差了两倍，但是同一个 key 在新旧 table 中的 index 要么一致，要么相差 oldCap 。而上述例子中新旧 index 是否一致就体现在 hash 值的第 4 位，通过 hash & 0001 0000 = hash & 16 = hash & oldCap 这样的方式获得。如果是等于 0 就可以判断当前 key 对应的值在新旧 table 中是相同的，就放入 lo 链表中，否则就放在 hi 链表中。