HashMap JDK8的原理讲解

超、凢脫俗 2022-02-28 11:14 227阅读 0赞

## 前言 ##

本文讲解 HashMap JDK 8 的原理，结合源码，只分析 put ，get ，resize 方法的流程。

参考文献：

[https://blog.csdn.net/goosson/article/details/81029729\#commentBox][https_blog.csdn.net_goosson_article_details_81029729_commentBox]

[https://blog.csdn.net/yyyljw/article/details/80903391][https_blog.csdn.net_yyyljw_article_details_80903391]

## 正文 ##

相关基础问题请查看我之前 HashMap 的文章：[https://blog.csdn.net/weixin\_38003389/article/details/83274983][https_blog.csdn.net_weixin_38003389_article_details_83274983]

### HashMap 结构图 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70][]

**结构图分析：**

左侧部分我习惯叫做 “桶” ，HashMap默认的桶是16，也是最小的桶大小。

每一个桶后面跟着的 是链表，我们说 当 hash 冲突的时候以链表的形式追加在桶后面，但是并不是链表里 的 hash 都是冲突才会追加的，因为还有一个重要的概念是，当前这个 K，V 应该放在哪 是根据 当前key 的hash值 和当前桶大小的 余数 ，打个比方，假如桶现在大小 16， hash（key）=53，那么根据计算： 53/16 的余数是5（hash（key）小于桶大小放对应桶内），所以这个元素应该落在第五个桶里，如果第五个桶有元素，那么就放在桶后的链表。关于这个比喻后文会有图片详细说明。

链表不能无限追加，因为链表查找是从头到尾遍历，所以HashMap规定链表长度大于8的部分转为红黑树。

## ##

### put ###

流程图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 1][]

这个图实在太完美了，出自参考文献中，大家在前言处点击链接查看。

我推荐大家边看源码边看流程图，下面我把 put 方法的源码贴出来，并翻译每句代码。

//对外开发使用
    public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    //真正put的方法
        /**
         * Implements Map.put and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @param value the value to put
         * @param onlyIfAbsent if true, don't change existing value
         * @param evict if false, the table is in creation mode.
         * @return previous value, or null if none
         */
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
    //定义一个数组，一个链表，n永远存放数组长度，i用于存放key的hash计算后的值，即key在数组中的索引
            Node<K,V>[] tab; Node<K,V> p; int n, i;
    //判断table是否为空或数组长度为0，如果为空则通过resize()实例化一个数组并让tab作为其引用，并且让n等于实例化tab后的长度，HashMap声明的时候 table是null，所以第一次put的时候需要扩容。
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
    //根据key经过hash()方法得到的hash值与数组最大索引做与运算得到当前key所在的索引值，并且将当前索引上的Node赋予给p并判断是否该Node是否存在。
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
    //该位置存在数据的情况，需要放到链表上。
            else {
                Node<K,V> e; K k;//重新定义一个Node，和一个k
    // 该位置上数据Key计算后的hash等于要存放的Key计算后的hash，并且该位置上的Key等于要存放的Key
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;//将该位置的Node赋予给e
                else if (p instanceof TreeNode)//判断当前node类型是否是TreeNode
                //进行红黑树插值法,写入数据
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    //否则遍历当前位置链表
                    for (int binCount = 0; ; ++binCount) {
    //查找当前位置链表上的表尾，链表尾的next节点必然为null,找到链表尾将数据赋给下一个节点
                        if ((e = p.next) == null) {
    //如果下一个节点事null直接将数据写到下个节点
                            p.next = newNode(hash, key, value, null);
    //如果此时已经到第八个了，还没找个链表尾，那么从第八个开始就要进行红黑树操作。
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);//红黑树具体操作方法。
                            break;
                        }
    //如果当前位置的key与要存放的key的相同，直接跳出，不做任何操作
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
     //如果e不为空，即找到了一个去存储Key-value的Node 
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
    //当最后一次调整之后Size大于了临界值，需要调整数组的容量
            if (++size > threshold)
                resize();
    //在HashMap中当前方法是空实现，在LinkedHashMap，用来回调移除最早放入Map的对象
            afterNodeInsertion(evict);
            return null;
        }

### get ###

//对外公开方法
    public V get(Object key) {
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
    
        /**
         * Implements Map.get and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @return the node, or null if none
         */
    //实际逻辑控制方法
        final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //保证Map中的桶不为空，并且存储的有值，并且查找的key对应的索引位置上有值
            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) {
    //是不是TreeNode
                    if (first instanceof TreeNode)
    //通过TreeNode的get方法获取值
                        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);
                }
            }
    //什么也没找到 ，返回null
            return null;
        }

### resize ###

final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;//现在的桶
            int oldCap = (oldTab == null) ? 0 : oldTab.length;//未扩容时数组的容量
            int oldThr = threshold;//扩容的阀值
            int newCap, newThr = 0;//定义新的容量和扩容阀值
    //当前Map容量大于零，非第一次put值
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {//超过最大容量:2^30，大概是10个亿
                    threshold = Integer.MAX_VALUE;//超过就把阀值设置0x7fffffff，大概20个亿
                    return oldTab;
                }
    //当前容量在默认值和最大值的一半之间
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; //新阀值为当前扩容阀值的两倍，<<1就是扩大一倍。
            }
    //当前容量为0，但是当前阀值不为0，
            else if (oldThr > 0) 
    //让新的容量等于当前扩容阀值
                newCap = oldThr;
            else {//当前容量和扩容阀值都为0,让新的容量为默认值。
                newCap = DEFAULT_INITIAL_CAPACITY;
    //阀值=初始容量*默认加载因子
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
    //如果新的阀值为0
            if (newThr == 0) {
    //计算阀值
                float ft = (float)newCap * loadFactor;
    //新容量小于最大容量，并且新阀值小于最大容量，那就去刚刚计算的阀值为新阀值，否则新阀值就是20亿。
                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
            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;//此时newCap = oldCap*2，扩大二倍
                        else if (e instanceof TreeNode)//节点为红黑树，进行切割操作
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { 
                        //链表的下一个节点还有值，但节点位置又没有超过8
                        //loTail就是扩容后仍然在原地的元素链表
    				//hiTail就是扩容后下标为  原位置+原容量  的元素链表，从而不需要重新计算hash。
                            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对比

![70][]

## 番外篇 ##

之前面试碰到一个问题 hash 是不是有序的问题，我回答无序，面试官说有序，只是一个看不出来，但是有一定规律的顺序。首先，我不信啊，我下面我就介绍一下hash，然后证明上面的问题。

介绍hash

hash 也分 hash树和hash表的，这里我只讲hash表。

首先，hash是找到一种数据内容和数据存放地址之间的映射关系。但这种关系并不是说hash就是顺序的。

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

所以说 我们用hash 一般用来查找单个元素很快，

介绍 hash 怎么存储和查询

哈希表hashtable(key，value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。如果多个 hash 取余在一个桶就在这个桶后追加链表，

而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

所以上面的问题就有了答案，我们查找数据快不是因为 散列表的存储有规律，而是把 key 经过hash 算法取余找到数组下标，进一步找到值，而且数组查找是通过下标而不是遍历，但是桶后追加的元素是 链表，所以 查找hash冲突的元素影响效率，故 HashMap把 链表中第9个元素以及后面的转为红黑树。

所以一个好的 hash 函数或者一个好的hash 数据结构是会把所有数据均匀分布在桶内，避免过多的冲突引发的效率问题。

常用的构造散列函数的方法有

（1）、直接定址法

取关键字或关键字的某个线性函数值为散列地址，即：

h(key) = key   或 h(key) = a \* key + b

其中a和b为常数。

（2）、数字分析法

（3）、平方取值法

取关键字平方后的中间几位为散列地址。

（4）、折叠法

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址。

（5）、除留余数法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址，即：

h(key) = key MOD p    p ≤ m

（6）、随机数法

选择一个随机函数，取关键字的随机函数值为它的散列地址，即：

h(key) = random(key)

其中random为随机函数。

**不难看出，HashMap 的hash 采用的是 除留余数法** 。

我认为无论是哪种方法构造出来的hash散列表都是无序，只是说每种方式都有固定的算法而已，但是分布在散列表中形成的样子是乱序的。

如果有兴趣请加微信或微信公众号

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 2][]![20190326125952754.jpeg][]

[https_blog.csdn.net_goosson_article_details_81029729_commentBox]: https://blog.csdn.net/goosson/article/details/81029729#commentBox
[https_blog.csdn.net_yyyljw_article_details_80903391]: https://blog.csdn.net/yyyljw/article/details/80903391
[https_blog.csdn.net_weixin_38003389_article_details_83274983]: https://blog.csdn.net/weixin_38003389/article/details/83274983
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70]: /images/20220228/993d4ed337bd42f1992db005872fa7b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 1]: /images/20220228/de9133342f074fae95dca1fec206c7d3.png
[70]: /images/20220228/84332d23244240b88c5c0c336abe5ceb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190326125901655.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAwMzM4OQ==,size_16,color_FFFFFF,t_70
[20190326125952754.jpeg]: /images/20220228/db592da52e3c4faa9dd2676ffcaa75df.png