Java集合09 - JDK1.8中的HashMap

柔光的暖阳◎ 2022-12-29 14:28 146阅读 0赞

**目录**

1.底层实现原理

2.resize()函数详解

3.put()方法流程

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

个人建议：学习1.8的HashMap前，务必要把1.7的HashMap底层实现结构、hash函数、resize()扩容机制、transfer()数据迁移、put()函数流程了解清楚，再对比1.8看做了哪些改变，直接看1.8容易懵。

### 1.底层实现原理 ###

众所周知，1.8的HashMap底层实现结构是数组+链表+红黑树，其内部定义了这样两个成员变量：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70][]

这两个变量用于对链表树化时机进行判断，那么思考这样一个问题，**为什么大于8才树化，为什么小于6要链化，别的值不行么？****源码注释已经很好地帮我们解答了这个问题：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1][]

解释下为：**如果用户采用的hash函数分布良好的话，红黑树是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，注释中给我们展示了节点数从1~8的具体命中概率，当链表长度为8时，概率概率仅为0.00000006，可以看到发生此事件的概率已经很小了。总结下来说：套入泊松分布公式，计算出6和8这两个值是合适值。**

### 2.resize()函数详解 ###

1.8HashMap的扩容方法和1.7中有些许区别，1.7中扩容方法只负责扩容，但在1.8中扩容方法还负责对底层空数组的初始化操作，我们先看一下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
         * 
         * 初始化或者翻倍表大小。
         * 如果为空，则根据字段阈值中保留的初始容量目标进行分配。
         * 否则，因为我们使用的是二次展开的幂，每个bin中的元素必须保持在相同的索引中，
         * 或者在新表中以2的幂次偏移量移动。
         */
        final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            //新的容量值，新的扩容阀界值
            int newCap, newThr = 0;
            //oldTab!=null,则oldCap>0
            if (oldCap > 0) {
                //已经到了最大容量，则阈值设置为整数的最大值 Integer.MAX_VALUE，直接返回这个oldTab的内存地址。 
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                //如果(当前容量*2<最大容量&&当前容量>=默认初始化容量(16))
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    //如果能进来证明是扩容而不是初始化
                    //将原扩容阀界值*2)赋值给newThr
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) 
                //进入此if证明创建Map时使用的带参构造：public HashMap(int initialCapacity)或 public HashMap(int initialCapacity, float loadFactor)
                newCap = oldThr;
            else {              
                //进入此if证明创建Map时使用的无参构造：
                //然后将新容量、新扩容阀值进行初始化
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
                //进入此if有两种可能
                //一：进入此“if (oldCap > 0)”中且不满足该if中的两个if
                //二：进入这个“else if (oldThr > 0)”
                //分析：进入此if证明该Map在创建时使用的带参构造，如果是第一种情况就说明进行扩容且oldCap（旧容量）小于16，如果是第二种说明是第一次执行put()
                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;
            //如果“oldTab != null”说明是扩容，否则直接返回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的实例
                            ((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;//此对象接收会放在“j + oldCap”（当前位置索引+原容量的值）
                            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;
        }

具体初始化流程笔者写在了代码注释里，接下来我们重点关注下1.8下的数据迁移是怎么实现的：假设我们有A~F六个值，其对应hash值如图所示，碰巧所有元素都放在了一个位置上形成链表，（12%7=5）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2][]

第一次：

![20201227152147618.png][]

第二次：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3][]

第三次：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 4][]

第四次：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 5][]

第五次：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 6][]

第六次：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 7][]

最终结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 8][]

### 3.put()方法流程 ###

JDK1.8put方法流程图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 9][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70]: /images/20221120/b2b3c6c8b5e3450ba889aa6b2f72ca60.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1]: /images/20221120/a2a0dcb6dac34273be172c36409a1676.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2]: /images/20221120/2e2990664e46479e9e9f0a9db768862f.png
[20201227152147618.png]: /images/20221120/351364de77384e3dab6ddf19d0c7e857.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3]: /images/20221120/ec75010034fc430589bba147b8533328.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 4]: /images/20221120/fd478f7a52f143a1861f25550c3c9271.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 5]: /images/20221120/98afdded88b24c108b7e46cd348645c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 6]: /images/20221120/6a91b883caec41709d9c2fa1d3e09f93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 7]: /images/20221120/bf387df6782241b0a961d47c3189559d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 8]: /images/20221120/8e6b445c5bc34d0380f72452ce9f1972.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 9]: /images/20221120/c358e712459f4bf0bcb957181d7a2ea8.png