jdk1.8 HshMap.put()方法详解

╰半橙微兮° 2022-05-29 10:21 189阅读 0赞

简单介绍一下JDK1.8 HashMap的数据如下  
![这里写图片描述][70]

HashMap存放的是一个Node

# 1、 jdk1.8 HshMap.put()方法详解 #

由上图可见，hashMap数据结构是：数组链表，  
数组里面存放的是链表的第一个节点Node，这个节点是个单向链表结果，有一个next()指向下一个节点

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

# 2、hash(key)源码如下： #

设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把***高16bit和低16bit***异或了一下，返回一个掩码。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞

// 计算hash值，hashcode值是32位，讲高16位和第16位做异或操作，返回一个掩码
    // 一个简单的操作，不会影响效率
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    // 计算桶的下标（桶的长度-1与hash值）
    // 因为桶的长度n不会很长（默认长度DEFAULT_INITIAL_CAPACITY为16）
    // 因此：key的高位和地位都参与了桶的下标计算，减少了碰撞
    (n - 1) & hash

# 3、putVal（） #

put方法主要做了以下操作

> 1、判断数组（哈希桶）是否为空，如果为空，重新计算一下大小(初始化一个桶)  
> 2、获取要插入元素在 哈希桶中的位置（tab\[(n - 1) & hash\]）  
> 3、如果桶的这个位置没有数据，new一个节点，存放桶里面  
> 4、如果有数据，判断这个位置的第一个节点是否相等（相等直接替换赋值，返回old值）  
> 5、如果和第一个节点不相等，再判断第一个节点的下一个节点是否是红黑树，如果是，通过红黑树方式put  
> 6、如果和第一个节点不相等，也不是红黑树，那么就按照链表结构处理。判断是否和链表的下一个相等，如果相等，直接复制替换。  
> 7、如果链表里面没有，如果大于了阙值(大于等于TREEIFY\_THRESHOLD，默认为8)， 需要扩容的大小，链表转换成红黑树；

具体源码如下：

// onlyIfAbsent在true的情况下不改变已有value值,evict(驱逐)在false的情况下table为创作模式.
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    
        Node<K, V>[] tab;
        Node<K, V> p;
        int n, i;
    
        // 1.判断数组（桶）是否为空，如果为空，重新计算一下大小(初始化一个桶)
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
    
        /** * 2. 获取要插入元素在 哈希桶中的位置,同时将值赋值给p(定位了桶的位置) * i = (n - 1) & hash:就是Node在哈希桶中tab的下标（位置） */
        // 如果这个位置没有Node,
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 直接创建一个新的Node
            tab[i] = newNode(hash, key, value, null);
    
            // 如果有这个位置的node不为null,原来这个桶的位置上有Node
        else {
            Node<K, V> e;
            K k;
    
            // 如果第一个位置和put的hash一致，直接替换
            // 桶里面存放的Node，node是一个单向链表结构
            if (p.hash == hash
                    && ((k = p.key) == key
                    || (key != null && ey.equals(k))))
                e = p;// 讲值赋值给e（其实后面是做替换）
    
                // 如果p链表的类型是属于红黑树，用红黑树的方式进行put
            else if (p instanceof TreeNode)
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
    
                // 如果不是红黑树，就是链表，按链表方式处理
                // 定位到这个hash桶了 但是这里面是链表（没有进行过树化）
            else {
    
                // 遍历链表
                for (int binCount = 0; ; ++binCount) {
    
                    // p节点的next为空 直接在后面插入，新建一个节点
                    // e是p节点的下一个节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
    
                        // 链表转变为红黑树。如果本来是链表 而且长度超过了8 那么就进行树化 
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
    
                    // 如果和下一个节点相等，且不为null，表明找到当前节点，结束循环
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
    
                    // 讲e(p.next())赋值给p，继续下一次循环
                    p = e;
                }
            }
    
            // 如果找到了节点，说明关键字相同，进行覆盖操作，直接返回旧的关键字的值
            // 注意e是p的下一个节点
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e); //空实现，里面没有实现方法
                return oldValue;
            }
        }
    
        // 没有找到相应的key执行下面操作
        // 修改次数+1 和fastRemove()有关也和并发修改有关
        ++modCount;
        // 容量hashmap存放node的个数+1，如果大于了阙值 需要扩容的大小
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict); //空实现,里面没有实现方法
        return null;
    }

# 4、put方法里面用到的函数 #

> 1、resize() 重新计算容量，或者是扩容方法  
> 2、p.putTreeVal(this, tab, hash, key, value) 存放数据倒红黑树里面  
> 3、treeifyBin(tab, hash) 将链表转换为红黑树

\[4.1\] ***resize()重新计算容量***

源码：

final HashMap.Node<K, V>[] resize() {
        // oldTable:当前的数组（旧的hash桶）
        HashMap.Node<K, V>[] oldTab = table;
        // 如果你是新创建的话 表的大小就是0 否则就是原来的大小
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 第一次是为0的 代表DEFAULT_INITIAL_CAPACITY = 1 << 4;
        int oldThr = threshold;
        // 新的容量，新的阙值：扩容后存放数据的大小（及hashmap的size）
        int newCap, newThr = 0;
        //如果旧的容量大于0
        if (oldCap > 0) {
            // 如果旧的容量大于等于最大容量，返回旧
            if (oldCap >= MAXIMUM_CAPACITY) {
                // 扩容大小 = 最大范围
                threshold = Integer.MAX_VALUE;
                // 直接返回就旧的数组
                return oldTab;
            } 
    
            // 将旧的数组（桶）扩容一倍赋值给newCap（数组）
            // 如果newCap小于最大容量，并且旧容量>=初始化16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY 
                    && oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 存放数据的size扩大一倍。左移1位，新size容量 = 旧size容量*2
                newThr = oldThr << 1; 
        }
    
        // 如果旧的存放数据的容量>0，那么新的桶大小=旧的容量
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        // 说明是 threshold为0的时候的情况
        else { // zero initial threshold signifies using defaults
            // 新的容量为默认容器的容量
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 新的阙值为 默认的容量 * 负载因子
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 如果新的如果新的扩容为0 ，上面走的else if (oldThr > 0)
        // 计算新的阙值
        if (newThr == 0) {
            // 计算得到新的阙值
            float ft = (float) newCap * loadFactor;
            // 如果新的桶容量小于最大容量 并且 阙值小于最大容量，新的阙值=ft，否则新的阙值= int型最大值
            newThr = (newCap < MAXIMUM_CAPACITY 
                    && ft < (float) MAXIMUM_CAPACITY ?
                    (int) ft : Integer.MAX_VALUE);
        }
        // 阙值 = 新的阙值
        threshold = newThr;
        @SuppressWarnings({
       "rawtypes", "unchecked"})
    
        // 建一个新的哈希数组桶 大小为新的容量
        HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
        table = newTab;
        // 如果旧的数组(桶)，遍历数组
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                HashMap.Node<K, V> e;
                // 如果旧的hash桶的元素不为null e为旧的hash桶的元素
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
    
                    // 如果hashmap就只有一个元素
                    if (e.next == null)
                        // 那么在新的hash桶给你安排一个位置
                        // 位置是你的hash值&新的桶的容量（size）-1,
                        // 这里是hashmap存放数据的一种算法，
                        newTab[e.hash & (newCap - 1)] = e;
    
                    // 如果不只一个元素并且是红黑树
                    else if (e instanceof HashMap.TreeNode)
                        // 分割 将树中的节点 分割到高位或者地位上去 
                        ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                    // 其他情况，就是一个普通的链表
                    else { // preserve order
                        // 如果扩容后，元素的index依然与原来一样，那么使用这个低位head和tail指针
                        HashMap.Node<K, V> loHead = null, loTail = null;
                        // 如果扩容后，元素的index=index+oldCap，那么使用这个高位head和tail指针
                        HashMap.Node<K, V> hiHead = null, hiTail = null;
                        // 下一个节点
                        HashMap.Node<K, V> next;
                        do {
                            next = e.next;
                            // 这个地方直接通过hash值与oldCap进行与操作得出元素在新数组的index
                            // 看是否需要进行位置变化 新增位的值 不需要变化就放在原来的位置
                            // 这里的判断需要引出一些东西：oldCap 假如是16，那么二进制为 10000，扩容变成 100000，也就是32.
                            // 当旧的hash值 与运算 10000，结果是0的话，那么hash值的右起第五位肯定也是0，那么该于元素的下标位置也就不变。
                            if ((e.hash & oldCap) == 0) {
                                // 第一次进来时给链头赋值
                                if (loTail == null)
                                    loHead = e;
                                // 给链尾赋值
                                else
                                    loTail.next = e;
                                // 重置该变量
                                loTail = e;
                            }
                            // 需要变化 就构建高位放置的链表
                            // 如果不是0，那么就是1，也就是说，如果原始容量是16，那么该元素新的下标就是：原下标 + 16（10000b）
                            else {
                                // 第一次进来时给链头赋值
                                if (hiTail == null)
                                    hiHead = e;
                                // 给链尾赋值
                                else
                                    hiTail.next = e;
                                // 重置该变量
                                hiTail = e;
                            }
                        } while ((e = next) != null);
    
                        // 理想情况下，可将原有的链表拆成2组，提高查询性能。
                        if (loTail != null) {
                            // 销毁实例，等待GC回收
                            loTail.next = null;
                            // 置入数组（桶bucket）中
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            // 在新链表的位置赋值
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

\[4.2\] ***p.putTreeVal(this, tab, hash, key, value) 存放数据倒红黑树里面***

下一节详细讲解红黑树  
\[4.3\] ***treeifyBin(tab, hash)讲红黑树转换为链表***

树化过程：  
1、根据哈希表中元素个数确定是扩容还是树形化  
2、树化  
遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系  
然后让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容  
但是我们发现，之前的操作并没有设置红黑树的颜色值，现在得到的只能算是个二叉树。在 最后调用树形节点 hd.treeify(tab) 方法进行塑造红黑树

/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */
    // 大体意思：在给定的散列中，替换桶中的所有链接节点，除非表太小，在这种情况下，可以进行调整。
    // 及树化
    final void treeifyBin(HashMap.Node<K, V>[] tab, int hash) {
        int n, index;
        HashMap.Node<K, V> e;
        // 如果当前哈希表为空，或者哈希表中元素的个数小于 进行树形化的阈值(默认为 64)，就去新建/扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        // hash表的元素个数大于MIN_TREEIFY_CAPACITY，树华操作
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            // 红黑树的头、尾节点
            HashMap.TreeNode<K, V> hd = null, tl = null;
            do {
                // 新建一个树节点，存放数据为当前链表节点e一直
                HashMap.TreeNode<K, V> p = replacementTreeNode(e, null);
    
                // 设置头节点
                if (tl == null)
                    hd = p;
                // 第二次循环后，设置上一个节点为tl，当链表节点e设置为tl的下一个节点
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                // 赋值，进行下一次循环
                tl = p;
            } while ((e = e.next) != null);
    
            // 将树的头节点放到hash表中，然后给树标记颜色，将二叉树转变为红黑树
            if ((tab[index] = hd) != null)
                // 二叉树转变为红黑树
                hd.treeify(tab);
        }
    }
    
    
    // 树化
    final void treeify(HashMap.Node<K, V>[] tab) {
        HashMap.TreeNode<K, V> root = null;
        for (HashMap.TreeNode<K, V> x = this, next; x != null; x = next) {
            next = (HashMap.TreeNode<K, V>) x.next;
            x.left = x.right = null;
    
            // 确定头结点，为黑色
            if (root == null) {
                x.parent = null;
                x.red = false;
                root = x;
            }
            // 确定根节点后，设置子节点
            else {
                K k = x.key;
                int h = x.hash;
                Class<?> kc = null;
                for (HashMap.TreeNode<K, V> p = root; ; ) {
    
                    // ph存放根节点的hash（父节点的hash），
                    // dir是存放 比较当前节点和父节点的大小的一个变量
                    int dir, ph;
                    K pk = p.key;
    
                    // 如果父节点hash大于当前节点的hash，dir=-1
                    if ((ph = p.hash) > h)
                        dir = -1;
    
                        // 如果父节点hash小于当前节点的hash，dir=1
                    else if (ph < h)
                        dir = 1;
    
                        // kc = comparableClassFor(k)) == null)：kc的类型==null
                        // dir = compareComparables(kc, k, pk)) == 0:比较kc的类型，当前key，父节点key是否相等
                    else if ((kc == null &&
                            (kc = comparableClassFor(k)) == null) ||
                            (dir = compareComparables(kc, k, pk)) == 0)
                        // 比较k和pk的内存地址（0,-1,1）
                        dir = tieBreakOrder(k, pk);
    
                    // 如果左右节点为空的时候，设置子节点，结束循环
                    HashMap.TreeNode<K, V> xp = p;
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
                        x.parent = xp;
                        if (dir <= 0)
                            xp.left = x;
                        else
                            xp.right = x;
                        root = balanceInsertion(root, x);
                        break;
                    }
                }
            }
        }
        moveRootToFront(tab, root);
    }

[70]: /images/20220529/b7cce3ae8a1242d8b8f4b7908fe4059b.png