JDK1.8 HashMap原理实现

客官°小女子只卖身不卖艺 2023-07-18 09:27 10阅读 0赞

## 前言 ##

HashMap应该算是Java后端工程师面试的必问题，因为其中的知识点太多，很适合用来考察面试者的Java基础。  
JDK1.8版本

## HashMap的内部数据结构 ##

**1、HashMap采用数组和链表（红黑树）的结构**

![HashMap内部结构][HashMap]

**2、HashMap的数据插入原理**  
![put原理][put]

1.  计算 k 的 hash 值
2.  判断数组是否为空，为空进行初始化;
3.  不为空，通过(n - 1) & hash计算应当存放在数组中的下标 index;
4.  查看 table\[index\] 是否存在数据，没有数据就构造一个Node节点存放在 table\[index\] 中；
5.  存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；
6.  如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；
7.  如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于 8，并且数组大小大于等于于64，满足条件链表转换为红黑树；
8.  插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。

**3、HashMap初始化**  
一般如果new HashMap() 不传值，默认大小是16，负载因子是0.75， 如果自己传入初始大小k，初始化大小为 大于k的 2的整数次方，例如如果传10，大小为16。（补充说明:实现代码如下）

/**
         * Returns a power of two size for the given target capacity.
         */
        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，4，8，16位，分别与自己位或，把高位第一个为1的数通过不断右移，把高位为1的后面全变为1，111111 + 1 = 1000000 =26（符合大于50并且是2的整数次幂 ）。int的长度是31位，右移31次，能概括所有值  
![计算2的整数次幂][2]  
**4、哈希函数hash实现**  
hash函数是先拿到通过key 的hashcode，是32位的int值，然后让hashcode的高16位和低16位进行异或操作

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

设计优点

1.  算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；
2.  一定要尽可能降低hash碰撞，越分散越好；  
    通过实现分析，才hashmap长度512的情况下，使用了扰动函数后hash碰撞大大减少。  
      另外Java1.8相比1.7做了调整，1.7做了四次移位和四次异或，但明显Java 8觉得扰动做一次就够了，做4次的话，多了可能边际效用也不大，所谓为了效率考虑就改成一次了。

**5、1.8主要的优化**

1.  数组+链表改成了数组+链表或红黑树；  
     优点：将时间复杂度由O(n)降为O(logn)
2.  链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7将新元素放到数组中，原始节点作为新节点的后继节点，1.8遍历链表，将元素放置到链表的最后；  
     优点：因为1.7头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环；A线程在插入节点B，B线程也在插入，遇到容量不够开始扩容，重新hash，放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环
3.  扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；  
     优点：因为扩容长度是原长度的2倍，用于计算数组位置的掩码仅仅只是高位多了一个1，只需要判断高位是1还是0，高位
4.  在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容；  
    源码解析

public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            //p：链表节点  n:数组长度   i：链表所在数组中的索引坐标
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //判断tab[]数组是否为空或长度等于0，进行初始化扩容
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //判断tab指定索引位置是否有元素，没有则，直接newNode赋值给tab[i]
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            //如果该数组位置存在Node
            else {
                //首先先去查找与待插入键值对key相同的Node，存储在e中，k是那个节点的key
                Node<K,V> e; K k;
                //判断key是否已经存在(hash和key都相等)
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //如果Node是红黑二叉树，则执行树的插入操作
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                //否则执行链表的插入操作（说明Hash值碰撞了，把Node加入到链表中）
                else {
                    for (int binCount = 0; ; ++binCount) {
                        //如果该节点是尾节点，则进行添加操作
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            //判断如果链表长度，如果链表长度大于8则调用treeifyBin方法，判断是扩容还是把链表转换成红黑二叉树
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        //如果键值存在，则退出循环
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        //把p执行p的子节点，开始下一次循环（p = e = p.next）
                        p = e;
                    }
                }
                //在循环中判断e是否为null，如果为null则表示加了一个新节点，不是null则表示找到了hash、key都一致的Node。
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    //判断是否更新value值。（map提供putIfAbsent方法，如果key存在，不更新value，但是如果value==null任何情况下都更改此值）
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    //此方法是空方法，什么都没实现，用户可以根据需要进行覆盖
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            //只有插入了新节点才进行++modCount；
            ++modCount;
            //如果size>threshold则开始扩容（每次扩容原来的1倍）
            if (++size > threshold)
                resize();
            //此方法是空方法，什么都没实现，用户可以根据需要进行覆盖
            afterNodeInsertion(evict);
            return null;
        }
          /**
         * 扩容
         */
    	final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;         //创建一个oldTab数组用于保存之前的数组
            int oldCap = (oldTab == null) ? 0 : oldTab.length;  //获取原来数组的长度
            int oldThr = threshold;             //原来数组扩容的临界值
            int newCap, newThr = 0;
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {   //如果原来的数组长度大于最大值(2^30)
                    threshold = Integer.MAX_VALUE;  //扩容临界值提高到正无穷
                    return oldTab;                  //返回原来的数组，也就是系统已经管不了了，随便你怎么玩吧
                }
                //else if((新数组newCap)长度乘2) < 最大值(2^30) && (原来的数组长度)>= 初始长度(2^4))
                //这个else if 中实际上就是咋判断新数组(此时刚创建还为空)和老数组的长度合法性，同时交代了，
                //我们扩容是以2^1为单位扩容的。下面的newThr(新数组的扩容临界值)一样，在原有临界值的基础上扩2^1
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0)
                newCap = oldThr;    //新数组的初始容量设置为老数组扩容的临界值
            else {               // 否则 oldThr == 0,零初始阈值表示使用默认值
                newCap = DEFAULT_INITIAL_CAPACITY;  //新数组初始容量设置为默认值
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);     //计算默认容量下的阈值
            }
            if (newThr == 0) {  //如果newThr == 0，说明为上面 else if (oldThr > 0)
            //的情况(其他两种情况都对newThr的值做了改变),此时newCap = oldThr;
                float ft = (float)newCap * loadFactor;  //ft为临时变量，用于判断阈值的合法性
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);     //计算新的阈值
            }
            threshold = newThr; //改变threshold值为新的阈值
            @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab; //改变table全局变量为，扩容后的newTable
            if (oldTab != null) {
                for (int j = 0; j < oldCap; ++j) {  //遍历数组，将老数组(或者原来的桶)迁移到新的数组(新的桶)中
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {  //新建一个Node<K,V>类对象，用它来遍历整个数组
                        oldTab[j] = null;
                        if (e.next == null)
                                    //将e也就是oldTab[j]放入newTab中e.hash & (newCap - 1)的位置，
                            newTab[e.hash & (newCap - 1)] = e;  //这个我们之前讲过，是一个取模操作
                        else if (e instanceof TreeNode)     //如果e已经是一个红黑树的元素，这个我们不展开讲
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // 链表重排，这一段是最难理解的，也是ldk1.8做的一系列优化，我们在下面详细讲解
                            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 1]

[HashMap]: /images/20230528/da8ede8618654930a59dbf6571ef6f95.png
[put]: /images/20230528/4272dce0791c4b09bd41572313b38194.png
[2]: /images/20230528/cac0ced725bb41bc89e09686df5f6399.png
[HashMap 1]: https://blog.csdn.net/zhengwangzw/article/details/104889549?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522158510350219725222460423%2522%252C%2522scm%2522%253A%252220140713.130056874..%2522%257D&request_id=158510350219725222460423&biz_id=0&utm_source=distribute.pc_search_result.none-task