由浅入深的分析HashMap原理

旧城等待， 2023-06-22 03:21 12阅读 0赞

**目录**

•写在前面

•HashMap简介

•Hash函数

•初始容量和负载因子

•通过put和get看底层结构

•高并发下的HashMap

--------------------

# •写在前面 #

对于大多数人HashMap是一个熟悉又陌生的的类，我们经常在需要使用键值对的地方使用HashMap，但是要你说上HashMap相关实现细节，估计就支支吾吾了，这里我对HashMap进行由浅入深的分析，文章涉及到的HashMap底层源码版本是JDK1.8，可以直接通过查看源码同步文章的学习。

# •HashMap简介 #

我们都知道，HashMap是储存键值对数据结构（很多人喜欢把HashMap说成集合，其实严格的来讲，HashMap不属于Java集合类，HashMap实现了Map接口，而Map不属于Java集合类Collections中），每个储存的键值对也叫作Entry。而HashMap是使用数组和链表实现的一种数据结构，这也就铺垫了HashMap可以通过hash算法将key计算在数组中的索引地址，然后存入到数组中。HashMap是基于哈希表的Map接口实现，它提供了所有可选的映射操作，并允许使用null值和null键，它不保证映射的顺序，特别是它不保证顺序恒久不变，并且它是非线性安全的，也就是说在多线程的环境下，可能会存在问题（经常和它一同比较的HashTable则是线程安全的，他们两个除了HashMap是不同步和允许使用null之外，大致相同）。HashMap的初始值是Null，像下面这样子。

![20191213180853534.png][]

# •Hash函数 #

介绍的时候提到了，我们是根据Key使用Hash算法得到索引下标，在源码中是一个Hash函数。想一想我们怎么实现一个均匀分布的Hash函数？我们通过Key的HashCode值来做某种运算，从而映射到储存位置，这种运算是何种运算？我们很容易想到的是取模运算，即将Key的HashCode和容量进行取模运算，从而映射到储存位置。但是事实并不是这样的，因为取模运算虽然简单，但效率非常低，所以为了实现高效的Hash算法，设计者使用的是位运算。我贴上源码里面的实现

![20191213172032821.png][]

我们可以更加简化的类比成形如下面这样的形式

index = HashCode(Key) & (Length - 1)

举个例子来演示运算的过程，比如我们使用“book”作为Key，第一步先计算“book”的hash值（你自己写一行代码，直接输出“book”.hashCode()就可以了），结果是十进制的3029737，转换成二进制是1011100011101011101001，因为默认初始容量是16（上式中的Length），则Length-1为15，二进制是1111。这个时候计算1011100011101011101001 & 1111 = 1001，也就是十进制的9，所以得到index为9。从而我们可以看出，Hash算法最后得到index的结果，完全取决于Key的HashCode值的后几位。

# •初始容量和负载因子 #

HashMap的实例又两个参数影响它的性能，分别是初始容量和复杂因子，在讲解前先说明，HashMap的默认初始容量是16，负载因子默认值是0.75（用于Hash计算），注意哦，初始容量设置太高或者负载因子设置太低，都会导致HashMap迭代性能下降。HashMap核心的东西是哈希表，初始容量和负载因子也是用于哈希表的，容量其实就是哈希表中桶的数量，初始容量只是哈希表在创建时的容量，负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的储存的数量超过了负载因子与当前容量的乘积时，就要对哈希表进行rehash操作（即重新构建内部的数据结构，相当于扩容，扩容的大小也有规定，无论是自动还是手动扩容，每次扩容之后的大小必须是2的幂）。这里我贴一下源码里的这两个东西。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70][]

仔细想想，为什么初始容量要选择16？其实这是为了服务于从Key映射到index（下标索引）的Hash算法。Hash算法大致过程上面讲了，现在，我们重复一下上面的计算过程，不过把容量从原来的16改为10，则1011100011101011101001 & 1001 = 1001，看起来和原来没有区别，对吧，那再换一个HashCode值，比如1011100011101011101011 & 1001 = 1001，还是1001。我不信邪，咱们再换一个1011100011101011101111 & 1001  = 1001，还是1001。现在能不能想到点什么了，没错，如果我们把长度换成了10，有一些index的值出现的几率更大，而有一些将永远不会出现（比如这个例子中0111不会出现），这样一来完全不符合hash算法均匀分布的原则，相反，我们把长度设置成2的幂，则Length-1的值是所有二进制全为1，这种情况下，index的结果等同于HashCode后几位的值，只要输入的HashCode本身均匀分布，咱们Hash算法计算出来的结果就是均匀的。

# •通过put和get看底层结构 #

我们在代码中使用HashMap进行插入的使用方式是hashMap.put("hhh",1)，代表我们插入一个Key为hhh的元素，这时，我们通过哈希函数确定Entry的插入位置，假设我们计算出来的index是2，那么结果如下：

![20191213180726940.png][]

但是我们想一下，HashMap的长度毕竟是有限的，当插入的Entry越来越多的时候，再完美的hash函数也难免出现index冲突的情况，类似下面这样子。

![20191213181123857.png][]

这个时候怎么办？直接扩容？那如果运气很不好，HashMap只有一个Entry的时候，就发生了冲突怎么办，还直接扩容么？当然不会直接扩容这种方法，而是利用链表来解决。HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头结点。每一个Entry对象通过Next指针指向它的下一个Entry节点，当新来的Entry映射到冲突的数组位置时，我们只需要插入到对应的链表即可，像下面这样

![20191213181248929.png][]

注意了，新的Entry节点插入链表的时候，使用的是“头插法”，至于为什么，下面将get的时候会解释。put的大致流程我们了解了，现在我们讨论一下get。

使用get的时候，首先我们需要输入Key做一次hash映射，得到对应的index，大致存取流程和put差不多，我就不多讲，我这里重点说一下冲突，由于刚才所说的Hash冲突，同一个位置可能匹配到多个Entry，这个时候就需要顺着对应的链表的头节点，一个一个向下来查找，假设我们要查找的Key是“hhh”

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 1][]

我们查看的是头节点Entry6，Entry6的Key是banana，不匹配，下一个next节点是Entry1，Entry1的Key是hhh，完成查找。这里解释一下为什么新来的放在头部，是因为设计者认为后插入的Entry被查找的可能性更大。

# •高并发下的HashMap #

我们想要深入这一块，我们必须先要知道Rehash，Rehash前面有提到过，是HashMap的扩容。HashMap容量有限，当HashMap达到一定饱和度时，Key映射位置冲突的几率会逐渐提高。前面说了，HashMap扩容的两个重要因素是容量和负载因子，分别是2的幂和0.75f，当HashMap.Size >= Capacity \* LoadFactor，出发扩容。扩容的步骤大致如下，首先创建一个新的Entry空数组，长度是原数组的2倍，遍历原Entry数组，把所有的Entry重新计算Hash，映射到新的数组中。下面我粘一下源码中resize。

/**
         * 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
            }
            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
                            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;
        }

仔细看到你就会发现，上述说的那个遍历过程。但HashMap并不算是完美的设计，因为前面讲到的流程都是在单线程下执行的，但是HashMap是非线程安全的。

现在我们来看看在并发的时候，HashMap会发生什么。假设一个HashMap已经到了Resize的临界点。此时有两个线程A和B，在同一时刻对HashMap进行Put操作，如下。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 2][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 3][]

这时候，两个线程都走到了ReHash的步骤。让我们回顾一下ReHash的代码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 4][]

假如此时线程B遍历到Entry3对象，刚执行完红框里的这行代码，线程就被挂起。对于线程B来说：

e = Entry3
    next = Entry2

这时候线程A畅通无阻地进行着Rehash，当ReHash完成后，结果如下（图中的e和next，代表线程B的两个引用）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 5][]

直到这一步，看起来没什么毛病。接下来线程B恢复，继续执行属于它自己的ReHash。线程B刚才的状态是：

e = Entry3
    next = Entry2

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 6][]

在此基础上往复执行，最后会到如下这种状态。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 7][]

此时，问题还没有直接产生。当调用Get查找一个不存在的Key，而这个Key的Hash结果恰好等于3的时候，由于位置3带有环形链表，所以程序将会进入**死循环**！

这种情况下，在高并发场景下，我们通常采用另一个类ConcurrentHashMap。这个类兼顾了线程安全和性能。

[20191213180853534.png]: https://img-blog.csdnimg.cn/20191213180853534.png
[20191213172032821.png]: https://img-blog.csdnimg.cn/20191213172032821.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191213175854325.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE=,size_16,color_FFFFFF,t_70
[20191213180726940.png]: https://img-blog.csdnimg.cn/20191213180726940.png
[20191213181123857.png]: https://img-blog.csdnimg.cn/20191213181123857.png
[20191213181248929.png]: https://img-blog.csdnimg.cn/20191213181248929.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191213182030863.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191213193510180.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191213193539125.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191213193721889.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191213193818508.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191213194016393.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20191213194210898.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE=,size_16,color_FFFFFF,t_70