我所理解的HashMap in Java8

Planeswalker23 2020年06月17日共5,608字 278次浏览

1. HashMap简述

HashMap是一个基于哈希表实现的无序的key-value容器，它键和值都允许设置为null，但是它是线程不安全的，同时在默认情况下如果HashMap元素超过默认容量的0.75时会进行扩容，将容量扩大为原来的两倍。

1.1 HashMap的底层数据结构

在JDK1.7以前HashMap底层是数组和链表实现的，但是为了防止同一个数组下标中的链表过于长导致查询效率过低的情况，从JDK1.8开始在HashMap容量大于64且链表长度大于8时会将链表转化为红黑树。

HashMap中每一个元素都以一个Node节点的形式存放在数组中。

HashMap底层结构

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // ...
}

hash属性是键的哈希值，key属性存放的是键，value属性存放的是值。

还有一个next属性，就是当两个key的哈希值相同时，这两个元素会被放在数组的同一个下标位置中，通过next属性指定一下个Node对象，从而会形成一个链表。

1.2 哈希碰撞

HashMap的底层数据结构首先是一个Node类型的数组，一个Node节点存放在数组中的位置（即数组下标）是由该Node节点key属性的哈希值（也就是hash属性）确定的，但是这就可能产生一种特殊情况——不同Node节点的哈希值相同。

如果存在两个Node节点的hash属性相同，那么它们都会存放在数组下标为hash的位置，同时会通过Node节点的next属性将这两个节点连接在一起，形成一个链表，这就解决了哈希冲突的问题。

举个例子，当我在Map中添加一个键为Java值为No1的元素时，Java字符串会通过hash方法来计算哈希值。假设Java字符串的哈希值为1，那么此时HashMap的结构就是下面这样。

放入键Java后的HashMap

假设这时再放入一个键为PHP值为No2的元素，刚好很不巧假设PHP作为键的哈希值结果也是1，那么这个Node节点也会放在数组下标为1的位置上，同时与Java键形成一个链表，如下图所示。

JDK1.7中是头插法，会引起死循环，在JDK1.8中改为使用尾插法。

放入键PHP后的HashMap

但是如果发生大量哈希值相同的特殊情况，导致链表很长，就会严重影响HashMap的性能，因为链表的查询效率需要遍历所有Node节点。

于是在JDK1.8引入了红黑树，当链表的长度大于8，且HashMap的容量大于64的时候，就会将链表转化为红黑树。

// JDK1.8 HashMap#putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 省略
    // binCount 是该链表的长度计数器，当链表长度大于等于8时，执行树化方法
    // TREEIFY_THRESHOLD = 8
    if (binCount >= TREEIFY_THRESHOLD - 1)
        treeifyBin(tab, hash);
    // 省略
}

// HashMap#treeifyBin    
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // MIN_TREEIFY_CAPACITY=64
    // 若 HashMap 的大小小于64，仅扩容，不会转化为红黑树
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 代码省略...
    }
}

1.3 如何计算键的哈希值

当一个键值对被放入HashMap时，会通过HashMap#hash(Object key)方法来计算该键的哈希值，作为它存放在HashMap数组中的索引下标值，hash方法的源码如下所示。

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

假如键为null的元素，它会被放在HashMap数组下标为0的位置。

当键不为null时，有hash值有如下的计算规则：

h被赋值为键的哈希值
进行h >>> 16运算
将上述两步的结果进行^运算

>>>符号表示无符号右移，右移后高位补0
^是异或运算符，当两者不同时结果为1，相同时结果为0

假设h=15，我们来计算一下hash方法的结果，先把15转化为二进制，也就是0000 1111。

h >>> 16的结果就是在15的32位二进制中取高半区，也就是0000 0000 0000 0000，最后对这两者做异或运算。

运算结果

所以最终h=15的键值对将被存放在HashMap数组下标为15的位置。

上面这段hash方法有一个专业术语叫做扰动函数，它的作用就是让元素充分的散列，减少发生哈希碰撞的可能性。

1.4 为什么HashMap是线程不安全的

CSDN上有一篇比较全面的回答：JDK1.7和JDK1.8中HashMap为什么是线程不安全的？

总结一下：

在JDK1.7中，并发执行扩容操作时会造成环形链和数据丢失的情况
在JDK1.8中，并发执行put操作时会发生数据覆盖的情况

2. 红黑树

红黑树是一棵特殊的二叉搜索树，除了根节点外，每个非根节点有且只有一个父节点，对于一个节点来说，它的左子树上所有节点的值都小于等于根节点的值，它的右子树上的值都大于等于根节点的值，同时从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

基于红黑树这样的结构特性，它的时间复杂度是O(logn)，所以会比链表的O(N)快，这也就是JDK1.8引入红黑树的原因。

红黑树

在此附上一篇博文，描述了红黑树维护的详情：聊一聊红黑树的左旋和右旋（结合JAVA中TreeMap红黑树实现），这里面那张动图可以说是十分形象了。

3. 加载因子

HashMap在进行扩容的时候有一定的条件，就是元素超过默认容量的0.75，这个0.75是HashMap的加载因子属性，它是用来进行扩容判断的。

假设加载因子是0.5，HashMap初始化容量是16，当HashMap中有16 * 0.5=8个元素时，HashMap就会进行扩容操作。

而HashMap中加载因子为0.75，是考虑到了性能和容量的平衡。

由加载因子的定义，可以知道它的取值范围是(0, 1]。

如果加载因子过小，那么扩容门槛低，扩容频繁，这虽然能使元素存储得更稀疏，有效避免了哈希冲突发生，同时操作性能较高，但是会占用更多的空间。
如果加载因子过大，那么扩容门槛高，扩容不频繁，虽然占用的空间降低了，但是这会导致元素存储密集，发生哈希冲突的概率大大提高，从而导致存储元素的数据结构更加复杂（用于解决哈希冲突），最终导致操作性能降低。
还有一个因素是为了提升扩容效率。因为HashMap的容量（size属性，构造函数中的initialCapacity变量）有一个要求：它一定是2的幂。所以加载因子选择了0.75就可以保证它与容量的乘积为整数。

// 构造函数
public HashMap(int initialCapacity, float loadFactor) {
    // ……
    this.loadFactor = loadFactor;// 加载因子
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 返回2的幂
 * Returns a power of two size for the given target capacity.
 * MAXIMUM_CAPACITY = 1 << 30
 */
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;
}

4. HashMap容量为什么规定为2的n次幂

原因一：与运算高效

与运算&，基于二进制数值，同时为1结果为1，否则就是0。如1&1=1,1&0=0,0&0=0。使用与运算的原因就是对于计算机来说，与运算十分高效。

原因二：有利于元素充分散列，减少 Hash 碰撞

在给HashMap添加元素的putVal函数中，有这样一段代码：

// n为容量，hash为该元素的hash值
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

它会在添加元素时，通过i = (n - 1) & hash计算该元素在HashMap中的位置。

当 HashMap 的容量为 2 的 n 次幂时，他的二进制值是100000……（n个0），所以n-1的值就是011111……（n个1），这样的话(n - 1) & hash的值才能够充分散列。

举个例子，假设容量为16，现在有哈希值为1111，1110，1011，1001四种将被添加，它们与n-1(15的二进制=01111)的哈希值分别为1111、1110、1110、1011，都不相同。

而假设容量不为2的n次幂，假设为10，那么它与上述四个哈希值进行与运算的结果分别是：0101、0100、0001、0001。

可以看到后两个值发生了碰撞，从中可以看出，非2的n次幂会加大哈希碰撞的概率。所以HashMap的容量设置为2的n次幂有利于元素的充分散列。

5. 死循环

上文在说到为什么HashMap是线程不安全的的时候提到过在JDK1.7中由于哈希碰撞，在同一个数组下标中进行链表元素的新增时是用头插法，会导致死循环，而在JDK1.8中改为使用尾插法，避免了死循环的情况的发生。

在此贴出网上比较详细的解释分析博客与视频：

6. 小结

回顾一下本文：

HashMap的底层数据结构是怎么样的？
哈希碰撞是什么？如何解决？
哈希值的计算过程？
为什么HashMap是线程不安全的？
简单说下红黑树的特性
HashMap加载因子为什么默认是0.75？
HashMap容量为什么设计成是2的n次幂？
HashMap死循环是怎么回事？

7. 参考资料

上一篇：如何找到链表的中间节点？下一篇：我所理解的String in Java8