一文搞懂“HashMap底层实现原理”

哈希表

什么是哈希表

哈希表，也称为散列表，是一种根据关键码值进行快速访问的数据结构。它通过将关键码值映射到表中一个位置来访问记录，以提高查找速度。这个映射函数称为散列函数，存放记录的数组称为散列表。哈希表的基本思想是将记录的存储位置与它的关键字之间建立一个确定的关系$H$，使每个关键字和唯一的存储位置对应。这种关系H就是该哈希表的一个哈希函数。在查找时，只需要根据对应关系计算出给定的关键字值$H(k)$，就可以得到记录的存储位置。这样，不经过比较，一次存取就能得到所查元素的查找方法。

什么是哈希冲突

根据一定的规则放进存放哈希值的数组中，然后下标为1的数组已经有值了，后面根据规则，判定某个数也需要放到下标为1的数组中，这样就导致了只有一个位置两个人都要坐，就引起了冲突。(不同的key值产生的$H(key)$是一样的)。

解决哈希冲突的方法

开放定址法

开放地址发也称为再散列发，当我们插入一个元素时，若发生冲突，则存放元素需要尝试另外的单元，直到找到空的单元为止。

当发生冲突时，开放地址法按照下面的方法求得后继哈希地址：
$H(i)=(H(key)+F(i))\%m,i=1,2,3,\dots ,n(n<=m-1)$

• $H(i)$ 是在处理冲突中得到的地址序列。即在第 1 次冲突$（i=1）$时经过处理得到一个新地址 $H(1)$，如果在 $H(1)$ 处仍然发生冲突$（i=2）$时经过处理时得到另一个新地址 $H(2)$ …… 如此下去，直到求得的 $H(n)$ 不再发生冲突
• $H(key)$ 是哈希函数，$m$ 是哈希表表长，取余目的是为了使得到的下一个地址一定落在哈希表中
• $F(i)$ 是冲突解决方法，下面介绍几种常见的解决方法。

线性探查法

$F(i)=1,2,3,\dots ,m-1$，冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

二次探查法

$F(i)=1^2,-1^2,2^2,-2^2,\dots ,n^2,-n^2(n<=m/2)$，冲突发生时，在表的左右进行跳跃式探测，比较灵活。

随机探查法

$F(i)$是伪随机数序列，建立一个伪随机数发生器生成一个伪随机序列，每次冲突加上伪随机数。

再哈希法

有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。

链地址法

每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。
例如有两个元素22和33的哈希值都是1，节点为1的位置已经有元素了，那么这两个元素就放到了节点为1的链表中，如下图。

HashMap

温馨提示：以下对于HashMap的讲解都是基于jdk1.8，其他jdk版本不在本篇描述。

HashMap中的hash函数

hash函数代码如下

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

可能会有童鞋不懂为何h值要异或h值的后16位，我也是上网搜了下才搞明白。

我们设哈希表数组长度为16（HashMap初始不设置长度时默认为16），如果我们hash值不异或后16位，当我们对结果取余计算存储位置时，实际上只用到了二进制值的后四位。
例如某个key的哈希值为 ：1111 1111 1110 1111 0101 0101 0111 0101，如果没有 ^ (h >>> 16)，计算下标如下。

          1111 1111 1110 1111 0101 0101 0111 0101  //h = hashcode()
	   &  0000 0000 0000 0000 0000 0000 0000 1111  //数组长度 - 1 = 15 (15的二进制就是 1111)
	   ------------------------------------------
	      0000 0000 0000 0000 0000 0000 0000 0101  //key的储存下标为5

       由上面可知，只相当于取了后面几位进行运算，所以哈希冲突的可能大大增加。

1
2
3
4
5
6
7

而当hash值^ (h >>> 16)时，最终计算的hash值前16位保持不变，后16位与前16为异或，这样后16位值也掺杂了高位的一部分特性，这样就减少了哈希冲突。

还是用上面key的哈希值，以上条件不变，加上 异或h >>> 16，之后再进行下标计算，计算结果如下。

          1111 1111 1110 1111 0101 0101 0111 0101  //h = hashcode()
       ^  0000 0000 0000 0000 1111 1111 1110 1111  //h >>> 16
       ------------------------------------------
          1111 1111 1110 1111 1010 1010 1001 1010  //h = key.hashCode() ^ (h >>> 16) 
      &   0000 0000 0000 0000 0000 0000 0000 1111  //数组长度 - 1 = 15 (15的二进制就是 1111)
       ------------------------------------------
          0000 0000 0000 0000 0000 0000 0000 1010  //key的存储下标为10
          
        重要：由上可知，因为哈希值得高16位和低16位进行异或运算，混合之后的哈希值，低位也可能掺杂了高位的一部分特性(就是变化性增加了)，这样就减少了哈希冲突。
1
2
3
4
5
6
7
8
9

HashMap是怎么解决哈希冲突的

HashMap解决冲突采用的是链地址法。

可以看到hashMap在存储{key, value}对时，若发生冲突，则在对应数组结点的链表尾部插入元素，若插入元素后链表长度大于等于8时，则将链表调整为红黑树。

特别提示：其实这里还有一个小坑，当触发链表长度大于等于8的条件时，链表在转化为红黑树之前，会先检查哈希表的数组长度有没有到达64。若低于64，会对哈希表进行扩容，就不会走转化红黑树的条件分支了；只有数组长度不低于64，才会转化红黑树。

什么是红黑树

红黑树是一种平衡二叉查找树，是一种数据结构。除了具备二叉查找树特性以外，还具备以下特性。

1. 根节点是黑色
2. 节点是黑色或红色
3. 每个叶子节点是黑色
4. 红色节点的子节点都是黑色
5. 从任意节点到其叶子节点的所有路径都包含相同数目的黑色节点

以上性质强制了红黑树的关键性质从根到叶子的最长的路径不多于最短的路径的两倍长。保证了红黑树的高效。

HashMap为什么引入红黑树

因为当链表长度大于等于8时，链表遍历查询速度比较慢，所以引入红黑树。

为什么不一开始就使用红黑树

因为树相对链表维护成本更大，红黑树在插入新数据之后，可能会通过左旋、右旋、变色来保持平衡，造成维护成本过高，故链路较短时，不适合用红黑树。

HashMap扩容机制

HashMap的初始容量

HashMap根据构造函数设置初始容量，若传空在插入元素时设置初始容量为16。

若不传空，则初始容量设置为不小于该数字的最接近的2次幂。

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;
}
1
2
3
4
5
6
7
8
9

特别提醒：HashMap扩容时也是将原容量扩大为2倍。为何初始容量和扩容都是2次幂呢？这一点我会在扩容时单独讲解。

HashMap什么时候扩容

1. 当HashMap中数组的容量超过 扩载因子 * 数组最大容量 时，HashMap扩容为原来的两倍
2. 当某个数组结点链表长度到达8且数组容量低于64时，HashMap也会扩容
   

HashMap的数组容量为什么是2次幂，扩容为什么是2倍

一开始我也很疑惑，然后上网搜了下，基本都说是为了减少哈希冲突。如果是单纯减少哈希冲突，完全可以把初始容量设置的更大，扩容也设置的更大。我一直对这个解答抱有疑问，直到我看了HashMap的扩容源码，我才找到答案。

当HashMap扩容时，原哈希表中的元素会放到新哈希表中，那么必然会重新计算旧元素在新哈希表中的索引下标。如果我们设原哈希表的容量为16，某一个旧元素存储的下标位置为7，那么我们能知道扩容后该元素可能会存储到什么位置吗？

我现在可以告诉大家，该元素只能存储在下标为7或者23的位置。这是为什么呢？

我们可以看到元素的下标位置实际上是通过哈希值 & (数组容量 - 1) 获得的。

那么哈希表扩容后，hash值不会变，变的只有数组容量，{新数组容量 - 1}和{原数组容量 - 1}的区别只是他们的二进制值前者比后者多了一位高位1。例如{原数组容量 - 1}二进制是1111，那么{新数组容量 - 1}二进制就是11111。

这样新的下标索引存放在哪个位置实际上就是看这个hash值在高位上是0还是1，这样是不是一下子就豁然开朗了。

我们知道了旧元素在新表中存储的位置，那有童鞋可能会问，这样有什么好处吗？

发生扩容时，原哈希表每个数组下标存储的可不一定只有单个元素，还有可能是链表或者是红黑树。那链表和红黑树怎么存储到新的哈希表中呢？

其实也挺简单，HashMap中是这么做的。因为新的下标索引只有两种值，例如a和b，所以将原链表或者红黑树拆分成两个新链表。值是a的元素插入到一个链表，值是b的元素插入到另一个链表。然后将两个链表分别插入到新哈希表数组下标的a和b位置。

上面截图的代码在HashMap的resize()方法中，可以看出旧链表确实是转化成了两个新链表。

其实，我们插入的也不一定是两个链表，还有可能是红黑树。这里还涉及到红黑树退化成链表和链表转化为红黑树的操作，我就不单独拿出来介绍了，感兴趣的童鞋可以自己看这部分源码。HashMap类的split()方法，是红黑树分割成两个链表的操作。其中untreeify()是红黑树转链表，treeify()是链表转红黑树。

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

HashMap红黑树什么时候会退化为链表

1. 当HashMap扩容时，新的数组下标节点数量小于等于6时，红黑树会退化为链表。
   
2. 当HashMap删除元素时，若删除的是红黑树节点，且删除节点后红黑树节点数量过少时，也会触发红黑树退化为链表。
   

HashMap为什么是线程不安全的

主要原因是可能会造成数据覆盖。

当你调用put()方法时，putVal()方法里面有好几处代码会产生数据覆盖。

如上图所示，当有两个线程a和b在tab[i]处存储node时，当a线程检查到tab[i]没有node，在存储元素前被挂起了；b线程也检查到tab[i]没有node，就在该位置存储node了。a线程被唤醒后，没有重新检查该位置有没有新node，结果就是a线程的node覆盖了b线程的node。

如上图所示，在putVal()方法里，有两个线程，假设HashMap的size为15。线程A从主内存获得15，准备进行++的操作的时候，被挂起，然后线程B拿到size并执行++操作，并写回主内存，这时size是16，然后线程A继续执行(这时A线程内存size还是15)++操作，然后写回主内存，即线程A和线程B都进行了put操作，然后size值只增加了1，所以数据被覆盖了。

同理，在向红黑树或者链表插入元素时，因为多线程的不安全性，同样会造成数据覆盖。

ConcurrentHashMap是怎么解决线程不安全的

1. 对有写操作的变量采用CAS操作。
   
   如上所示，在数组索引下标为空的位置存储node时，加入了CAS操作，避免了数据覆盖。
   
   如上所示，对于数组已使用容量baseCount增加时，也加入了CAS操作。
2. 在向链表或红黑树插入元素时，使用Synchronized保证线程安全。
   
   如上所示，向链表和红黑树插入元素的方法在Synchronized修饰的代码块中。

---

• 个人公众号
  
• 个人小游戏