HashMap

1. 基本知识

• HashMap始于JDK 1.5，作者是大师Doug Lea。
• HashMap提供所有可选的映射操作，并允许使用null键和null值。
• HashMap由数组+链表+红黑树组成，链表的时间复杂度为O(n)，红黑树的时间复杂度为O(logn)。
• HashMap并非线程安全，当存在多个线程同时写入HashMap时，会导致数据覆盖和环。

2. 基本属性

/** 默认初始化容量 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/** 最大容量 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/** 默认负载因子 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** 树化阈值 */
static final int TREEIFY_THRESHOLD = 8;
/** 链化阈值 */
static final int UNTREEIFY_THRESHOLD = 6;
/** 最小的树化容量 */
static final int MIN_TREEIFY_CAPACITY = 64;
/** 哈希桶数组，第一次put时初始化，长度为2的次幂 */
transient Node<K,V>[] table;
/** 存储键值对集合 */
transient Set<Map.Entry<K,V>> entrySet;
/** 键值对数量 */
transient int size;
/** 修改次数 */
transient int modCount;
/** 树化阈值 */
int threshold;
/** 负载因子 */
final float loadFactor;

3. 构造方法

// 带初始化容量和负载因子的构造
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
// 带初始化容量的构造
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 无参构造
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

可以看到，在构造方法中，并没有进行任何的初始化，只是进行了一些简单的赋值处理。

4. hash方法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash计算方法：调用hashcode()进行位运算，将hashcode右移16位取得hashcode的高16位，与原hashcode的低16位进行异或运算。
index计算方法：将hash值与数组长度-1进行与运算得到数组下标，计算公式index = hash & (table.length - 1)。

5. tableSizeFor方法

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

返回一个大于等于给定目标容量的最小2的幂次方。
如果n = 0，则初始化结果为1。
第一次：n |= n >>> 1
右移1位：000001xxxxxx -> 0000001xxxxx
或运算：n = 0000011xxxxx
第二次：n |= n >>> 2
右移2位：000011xxxxx -> 000000011xxx
或运算：n = 000001111xxx
右移1位做或运算后，最高位有2个1；
右移2位做或运算后，最高位有4个1；
右移4位做或运算后，最高位有8个1；
右移8位做或运算后，最高位有16个1；
右移16位做或运算后，最高位有32个1。
int占32bit，最多就32个1，这时候已经大于MAXIMUM_CAPACITY(1 << 30 = 2147483647 / 2)，所以取值到了MAXIMUM_CAPACITY。

:::info 那么为什么必须为2的整数次幂呢？
为了提高计算与存储效率，同时减少哈希碰撞的几率。
确定数组下标采用的算法是 hash & (n - 1)，n为哈希桶数组的大小。n为2的整数次幂，n - 1的二进制形式为000..11111，这个二进制值与任何值进行与运算的结果都在指定区间[0, n-1]。
正例：n = 8，n - 1 = 7，二进制0111，任何与0111进行与运算的结果都会映射到[0，7]，即落入给定的8个哈希桶中，存储空间利用率100%。
反例：n = 7，n - 1 = 6，二进制0110，任何与0110进行与运算的结果都会映射到{0, 2, 4, 6}四个桶中，而不是[0, 6]区间，存储空间利用率只有 4 / 7 * 100%。 :::

6. put方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * @param hash  根据键计算的hash
 * @param key   键
 * @param value 值
 * @param onlyIfAbsent true只是在值为空的时候存储数据，false都存储数据
 * @param evict 不关心
 * @return 返回被覆盖的值，如果没有覆盖则返回null
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 第一次put值的时候会触发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<K,V> e; K k;
        // 首先，判断该位置的第一个数据和要插入的数据，key是不是相等
        // 如果是，取出这个结点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果该结点是代表红黑树的结点，调用红黑树的插值方法
        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) {
                    p.next = newNode(hash, key, value, null);
                    // TREEIFY_THRESHOLD = 8，
                    // 如果新插入的值是链表中的第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 != null 说明存在旧值的key与要插入的key相等
        // 进行值覆盖，然后返回旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 如果HashMap由于新插入这个值导致size查过阈值，则进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

过程总结：
（1）第一次put的时候，会触发resize方法，经典懒加载，数组初始化。
（2）计算数组长度和hash的与运算结果得到key在数组中的具体下标，从而得到数组该位置的第一节点。
（3）如果第一节点为空，那么直接新建一个节点并放在这个位置即可。
（4）如果第一节点非空， 那么判断第一节点key和当前key是否相等。
（5）如果相等，则取出这个节点。
（6）如果不相等，则判断这个节点的类型是红黑树节点还是链表节点。
（7）如果是红黑树节点，则调用红黑树的插值方法。
（8）如果是链表节点，则遍历整个链表，如果存在相同key，则取出这个节点并break，否则直接插入到链表最后面，如果链表长度超过树化阈值8，那么进行树化操作。
（9）判断取出的节点是否为空，非空则进行值覆盖，然后返回旧值。
（10）如果因为新插入值导致size超过阈值，则进行扩容，并返回null。

7. get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * @param hash  根据键计算的hash
 * @param key   键
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断第一个节点是不是就查找的
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            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;
}

过程总结：
（1）计算key的hash，根据hash值找到数组下标：hash & (length - 1)。
（2）判断该位置的第一个元素是否为所查找的，如果是直接返回。
（3）判断该元素类型是否为红黑树节点，如果是则调用红黑树的方法获取结点。
（4）到这里说明元素是链表节点，直接遍历链表，寻找key相同的结点。
（5）最后，表示没有找到，直接返回null。

8. 负载因子

负载因子 = 填入哈希表中元素数量 / 哈希桶的长度，负载因子决定HashMap的数据密度。

扩容阈值 = 哈希表当前容量 * 负载因子，负载因子决定HashMap的扩容阈值。

• 负载因子过大，产生数据碰撞的几率越高，数组中的链表也会越长，会造成查询和插入的比较增次数多。『降低空间开销，提高查找成本。』
• 负载因子过小，触发扩容的几率越高，产生数据碰撞的几率越小，查询和插入的比较次数少。『降低时间开销，提高空间成本。』
• 因此在负载因子的选择上，要做到时间和空间的折中。

举例：
当loadFactor= 1时，hash数组中的16个值全部填充的时候才会扩容，造成链表或者红黑树的长度变大，hash碰撞的次数变多；
当loadFactor= 0.5时，hash数组中的值填充一半开始扩容，造成空间利用率降低。

关于负载因子0.75的证明
通过预测桶是否为空，桶空与非空的概率为0.5。
设s表示哈希桶的长度，n表示已添加的元素个数，负载因子loadFactor = n / s；
对于每个元素，桶非空的概率为1/s，桶空的概率为1 - 1/s；
根据二项式定理，桶空的概率：

P(0) = C(n, 0) * [(1 / s) ^ 0] * [(1 - 1 / s) ^ (n - 0)] 
=> P(0) = (1 - 1 / s) ^ n

令这个概率值等于 1/2，那么：

(1 - 1 / s) ^ n = 1 / 2

然后进行极限变换求值：

(1 - 1 / s) ^ n
= [1 + 1/ (-s)] ^ [(-s) * (- n / s)]
= 1 / 2
当s -> +∞时，[1 + 1 / (-s)] ^ (-s) -> e
即 e ^ (- n / s) = 1 / 2
两边同时取对数，n / s = ln 2

从而，loadFactor = ln2 = 0.69314718056。
个人猜测，负载因子在[ln2, 0.75]这个区间内都可以保证良好的性能。

9. 树化阈值

在理想情况下，使用随机哈希码，节点出现的频率在哈希桶中遵循泊松分布，同时给出了桶中元素个数（链表长度）和命中概率的对照表：

• 0: 0.60653066
• 1: 0.30326533
• 2: 0.07581633
• 3: 0.01263606
• 4: 0.00157952
• 5: 0.00015795
• 6: 0.00001316
• 7: 0.00000094
• 8: 0.00000006
• more: 小于千万分之一

从上可以看出当桶中元素长度达到8的时候，每个碰撞位置的链表长度为8的概率为一千万分之六，超过8的概率小于一千万分之一。
也就是说，当哈希码分布均匀时，同一个位置上出现8个元素的概率为千万分之六，侧面说明如果链表长度达到了8，key的hashcode()出现了问题，这个时候需要红黑树来保证性能。

10. 扩容原理

JDK1.7扩容

源码分析

扩容，创建新的哈希桶数组，进行数据迁移。源码如下：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    //创建新的table
    Entry[] newTable = new Entry[newCapacity];
    // 判断新的table中的元素是否需要重新求hash值，源码在下面
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;//数组扩容赋值给table
    // 计算新的扩容阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

数据迁移，将旧元素重新计算hash值然后放入到新的table里面。源码如下：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    // 遍历桶
    for (Entry<K,V> e : table) {
        // 采用头插法
        while(null != e) {
            // 记录当前节点的下一个节点
            Entry<K,V> next = e.next; // sign A
            // 重新计算哈希
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 新的哈希值对应的数组下标
            int i = indexFor(e.hash, newCapacity);
            // 插入新的节点
            e.next = newTable[i];
            newTable[i] = e;
            // 迭代
            e = next;
        }
    }
}

总结：

1. 创建新的数组newTable；
2. 遍历桶，将table中的节点全部重新计算hash值，采用头插法插入到newTable中；
3. 将newTable赋值给table；
4. 重新计算扩容阈值 = 新的容量 * 负载因子。

并发问题

原始情况

死链情况
两个线程：线程A和线程B
（1）假设线程A指定到sign A，情况如下：

（2）此时，穿插线程B执行，执行完了整个迁移过程，结果如下：

（3）线程A继续执行，使用头插法插入5节点，那么就会导致5节点和6节点相互引用导致链表成环：

数据丢失
两个线程：线程A和线程B
（1）假设线程A指定到sign A，情况如下：

（2）此时，穿插线程B，执行完了整个迁移过程，结果如下：

（3）线程A继续执行，使用头插法插入5节点，然后继续插入next节点，由于6节点的next为null，会导致7节点丢失：

最后扩容结束，由于线程B先执行了table = newTable，线程A后执行，那么A丢失的newTable最终成为真正的哈希桶，丢失数据。

JDK1.8扩容

源码分析

扩容，创建新数组，数据迁移采用尾插法。源码如下：

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
    }
    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;
    if (oldTab != null) {
        // 遍历原始数组下标
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 如果原始数组下标对应位置有元素
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 当前节点是个独狼
                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
                   // 根据hash值和原始数组长度重新计算索引值
                    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;
                        }
                        // 如果索引值不为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;
}

总结：

1. 先判断当前table是否进行过初始化，如果没有则初始化默认值，已经初始化则扩容为原来的2倍。
2. 扩容后对原始table进行遍历，将数据迁移到新的table中：
   1. 如果当前位置节点是个独狼，那么直接重新计算数组下标并放在新的table中；
   2. 如果当前位置节点为红黑树节点，那么需要单独处理，进行重新拆分操作；
   3. 如果当前节点节点为链表节点，那么根据哈希值和原数组长度重新计算索引值，索引值为0则新数组下标与原数组下标相同，否则新数组下标为原数组下标+原数组长度。

并发问题

采用尾插法可以防止在多线程情况下链表成环的产生，但是依然非线程安全。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // ... 
}

在putVal的第六行代码中判断是否出现哈希碰撞，如果线程A和线程B都在进行put操作，并且hash函数计算出的插入下标是相同的的，当线程A执行完后被挂起，而线程B在该下标处插入了元素，完成了正常的插入，这样数据就悄无声息的覆盖掉了，从而线程不安全。

:::info JDK1.8中由头插法改为尾插法的变更原因：

1. 可以保证节点的有序性。（根据缓存的时间局部性原则，可以减少查找次数。）
2. 防止多线程下链表成环。

另外，JDK1.8中不需要为每个节点重新计算哈希，只需要根据原来的哈希值和原数组长度进行与运算得到新的索引值。 :::