关于后端:面经手册-第4篇HashMap数据插入查找删除遍历源码分析

作者：小傅哥
博客：https://bugstack.cn

积淀、分享、成长，让本人和别人都能有所播种！????

一、前言

在上一章节咱们解说并用数据验证了，HashMap 中的，散列表的实现 、 扰动函数 、 负载因子 以及 扩容拆分 等外围知识点以及相应的作用。

除了以上这些知识点外，HashMap 还有根本的数据性能；存储 、 删除 、 获取 、 遍历 ，在这些性能中常常会听到链表、红黑树、之间转换等性能。而红黑树是在 jdk1.8 引入到 HashMap 中解决链表过长问题的，简略说当链表长度>=8 时，将链表转换位红黑树 ( 当然这里还有一个扩容的知识点，不肯定都会树化[MIN_TREEIFY_CAPACITY])。

那么本章节会进行解说以下知识点；

1. 数据插入流程和源码剖析
2. 链表树化以及树转链表
3. 遍历过程中的无序 Set 的外围常识

???? 留神： 倡议浏览上一篇后，再浏览本篇文章《HashMap 外围常识，扰动函数、负载因子、扩容链表拆分，深度学习》

二、HashMap 源码剖析

1. 插入

1.1 疑难点 & 考题

通过上一章节的学习：《HashMap 外围常识，扰动函数、负载因子、扩容链表拆分，深度学习》

大家对于一个散列表数据结构的 HashMap 往里面插入数据时，根本曾经有了一个印象。简略来说就是通过你的 Key 值获得哈希再计算下标，之后把相应的数据寄存到外面。

但再这个过程中会遇到一些问题，比方；

1. 如果呈现哈希值计算的下标碰撞了怎么办？
2. 如果碰撞了是扩容数组还是把值存成链表构造，让一个节点有多个值寄存呢？
3. 如果寄存的数据的链表过长，就失去了散列表的性能了，怎么办呢？
4. 如果想解决链表过长，什么时候应用树结构呢，应用哪种树呢？

这些疑难点都会在前面的内容中逐渐解说，也能够本人思考一下，如果是你来设计，你会怎么做。

1.2 插入流程和源码剖析

HashMap 插入数据流程图

visio 原版流程图，能够通过关注公众号：bugstack 虫洞栈，进行下载

以上就是 HashMap 中一个数据插入的整体流程，包含了；计算下标、何时扩容、何时链表转红黑树等，具体如下；

1. 首先进行哈希值的扰动，获取一个新的哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

2. 判断 tab 是否位空或者长度为 0，如果是则进行扩容操作。

   if ((tab = table) == null || (n = tab.length) == 0)
       n = (tab = resize()).length;

3. 依据哈希值计算下标，如果对应小标正好没有存放数据，则直接插入即可否则须要笼罩。tab[i = (n - 1) & hash])
4. 判断 tab[i]是否为树节点，否则向链表中插入数据，是则向树中插入节点。
5. 如果链表中插入节点的时候，链表长度大于等于 8，则须要把链表转换为红黑树。treeifyBin(tab, hash);
6. 最初所有元素解决实现后，判断是否超过阈值；threshold，超过则扩容。
7. treeifyBin, 是一个链表转树的办法，但不是所有的链表长度为 8 后都会转成树，还须要判断寄存 key 值的数组桶长度是否小于 64 MIN_TREEIFY_CAPACITY。如果小于则须要扩容，扩容后链表上的数据会被拆扩散列的相应的桶节点上，也就把链表长度缩短了。

JDK1.8 HashMap 的 put 办法源码如下:

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) {Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 初始化桶数组 table，table 被提早到插入新数据时再进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果桶中不蕴含键值对节点援用，则将新键值对节点的援用存入桶中即可
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            
        // 如果桶中的援用类型为 TreeNode，则调用红黑树的插入方法
        else if (p instanceof TreeNode)  
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 对链表进行遍历，并统计链表长度
            for (int binCount = 0; ; ++binCount) {
                // 链表中不蕴含要插入的键值对节点时，则将该节点接在链表的最初
                if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
                    // 如果链表长度大于或等于树化阈值，则进行树化操作
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                // 条件为 true，示意以后链表蕴含要插入的键值对，终止遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 判断要插入的键值对是否存在 HashMap 中
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 示意是否仅在 oldValue 为 null 的状况下更新键值对的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 键值对数量超过阈值时，则进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

1.3 扩容机制

HashMap 是基于数组 + 链表和红黑树实现的，但用于寄存 key 值得的数组桶的长度是固定的，由初始化决定。

那么，随着数据的插入数量减少以及负载因子的作用下，就须要扩容来寄存更多的数据。而扩容中有一个十分重要的点，就是 jdk1.8 中的优化操作，能够不须要再从新计算每一个元素的哈希值，这在上一章节中曾经讲到，能够浏览系列专题文章，机制如下图；

里咱们次要看下扩容的代码(正文局部)；

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // Cap 是 capacity 的缩写，容量。如果容量不为空，则阐明曾经初始化。if (oldCap > 0) {
        // 如果容量达到最大 1 << 30 则不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        
        // 按旧容量和阀值的 2 倍计算新容量和阀值
        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
    
        // initial capacity was placed in threshold 翻译过去的意思，如下；// 初始化时，将 threshold 的值赋值给 newCap，// HashMap 应用 threshold 变量临时保留 initialCapacity 参数的值
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 这一部分也是，源代码中也有相应的英文正文
        // 调用无参构造方法时，数组桶数组容量为默认容量 1 << 4; aka 16
        // 阀值；是默认容量与负载因子的乘积，0.75
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // newThr 为 0，则应用阀值公式计算容量
    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"})
        // 初始化数组桶，用于寄存 key
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 如果旧数组桶，oldCap 有值，则遍历将键值映射到新数组桶中
        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)
                    // 这里 split，是红黑树拆分操作。在从新映射时操作的。((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;
                    // 这里是链表，如果以后是依照链表寄存的，则将链表节点按原程序进行分组{这里有专门的文章介绍，如何不须要从新计算哈希值进行拆分《HashMap 外围常识，扰动函数、负载因子、扩容链表拆分，深度学习》}
                    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. 扩容时计算出新的 newCap、newThr，这是两个单词的缩写，一个是 Capacity，另一个是阀 Threshold
2. newCap 用于翻新的数组桶 new Node[newCap];
3. 随着扩容后，原来那些因为哈希碰撞，寄存成链表和红黑树的元素，都须要进行拆分寄存到新的地位中。

1.4 链表树化

HashMap 这种散列表的数据结构，最大的性能在于能够 O(1)工夫复杂度定位到元素，但因为哈希碰撞不得已在一个下标里寄存多组数据，那么 jdk1.8 之前的设计只是采纳链表的形式进行寄存，如果须要从链表中定位到数据工夫复杂度就是 O(n)，链表越长性能越差。因为在 jdk1.8 中把过长的链表也就是 8 个，优化为自均衡的红黑树结构，以此让定位元素的工夫复杂度优化近似于 O(logn)，这样来晋升元素查找的效率。但也不是齐全摈弃链表，因为在元素绝对不多的状况下，链表的插入速度更快，所以综合思考下设定阈值为 8 才进行红黑树转换操作。

链表转红黑树，如下图；

以上就是一组链表转换为红黑树的状况，元素包含；40、51、62、73、84、95、150、161 这些是通过理论验证可调配到 Idx：12 的节点

通过这张图，根本能够有一个 链表 换行到 红黑树 的印象，接下来浏览下对应的源码。

链表树化源码

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 这块就是咱们下面提到的，不肯定树化还可能只是扩容。次要桶数组容量是否小于 64 MIN_TREEIFY_CAPACITY 
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {// 又是单词缩写；hd = head (头部)，tl = tile (结尾)
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 将一般节点转换为树节点，但此时还不是红黑树，也就是说还不肯定均衡
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            // 转红黑树操作，这里须要循环比拟，染色、旋转。对于红黑树，在下一章节具体解说
            hd.treeify(tab);
    }
}

这一部分链表树化的操作并不简单，简单点在于下一层的红黑树转换上，这部分知识点会在后续章节中专门介绍；

以上源码次要包含的知识点如下；

1. 链表树化的条件有两点；链表长度大于等于 8、桶容量大于 64，否则只是扩容，不会树化。
2. 链表树化的过程中是先由链表转换为树节点，此时的树可能不是一颗均衡树。同时在树转换过程中会记录链表的程序，tl.next = p，这次要不便后续树转链表和拆分更不便。
3. 链表转换成树实现后，在进行红黑树的转换。先简略介绍下，红黑树的转换须要染色和旋转，以及比对大小。在比拟元素的大小中，有一个比拟有意思的办法，tieBreakOrder加时赛，这次要是因为 HashMap 没有像 TreeMap 那样自身就有 Comparator 的实现。

1.5 红黑树转链

在链表转红黑树中咱们重点介绍了一句，在转换树的过程中，记录了原有链表的程序。

那么，这就简略了，红黑树转链表时候，间接把 TreeNode 转换为 Node 即可，源码如下；

final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    // 遍历 TreeNode
    for (Node<K,V> q = this; q != null; q = q.next) {
        // TreeNode 替换 Node
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

// 替换办法
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {return new Node<>(p.hash, p.key, p.value, next);
}

因为记录了链表关系，所以替换过程很容易。所以好的数据结构能够让操作变得更加容易。

2. 查找

上图就是 HashMap 查找的一个流程图，还是比较简单的，同时也是高效的。

接下来咱们在联合代码，来剖析这段流程，如下；

public V get(Object key) {
    Node<K,V> e;
    // 同样须要通过扰动函数计算哈希值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 判断桶数组的是否为空和长度值
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // 计算下标，哈希值与数组长度 -1
        (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 节点间接调用红黑树的查找办法，工夫复杂度 O(logn)
            if (first instanceof TreeNode)
                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);
        }
    }
    return null;
}

以上查找的代码还是比较简单的，次要包含以下知识点；

1. 扰动函数的应用，获取新的哈希值，这在上一章节曾经讲过
2. 下标的计算，同样也介绍过 tab[(n - 1) & hash])
3. 确定了桶数组下标地位，接下来就是对红黑树和链表进行查找和遍历操作了

3. 删除

 public V remove(Object key) {
     Node<K,V> e;
     return (e = removeNode(hash(key), key, null, false, true)) == null ?
         null : e.value;
 }
 
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 定位桶数组中的下标地位，index = (n - 1) & hash
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 如果键的值与链表第一个节点相等，则将 node 指向该节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            // 树节点，调用红黑树的查找办法，定位节点。if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 遍历链表，找到待删除节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        
        // 删除节点，以及红黑树须要修复，因为删除后会毁坏平衡性。链表的删除更加简略。if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
} 

• 删除的操作也比较简单，这外面都没有太多的简单的逻辑。
• 另外红黑树的操作因为被包装了，只看应用上也是很容易。

4. 遍历

4.1 问题点

HashMap 中的遍历也是十分罕用的 API 办法，包含；

KeySet

 for (String key : map.keySet()) {System.out.print(key + " ");
 }

EntrySet

 for (HashMap.Entry entry : map.entrySet()) {System.out.print(entry + " ");
 }

从办法上以及日常应用都晓得，KeySet 是遍历是无序的，但每次应用不同形式遍历包含keys.iterator()，它们遍历的后果是固定的。

那么从实现的角度来看，这些种遍历都是从散列表中的链表和红黑树获取汇合值，那么他们有一个什么固定的法则吗？

4.2 用代码测试

测试的场景和前提；

1. 这里咱们要设定一个既有红黑树又有链表构造的数据场景
2. 为了能够有这样的数据结构，咱们最好把 HashMap 的初始长度设定为 64，防止在链表超过 8 位后扩容，而是间接让其转换为红黑树。

3. 找到 18 个元素，别离放在不同节点(这些数据通过程序计算得来)；

   1. 桶数组 02 节点：24、46、68
   2. 桶数组 07 节点：29
   3. 桶数组 12 节点：150、172、194、271、293、370、392、491、590

代码测试

@Test
public void test_Iterator() {Map<String, String> map = new HashMap<String, String>(64);
    map.put("24", "Idx：2");
    map.put("46", "Idx：2");
    map.put("68", "Idx：2");
    map.put("29", "Idx：7");
    map.put("150", "Idx：12");
    map.put("172", "Idx：12");
    map.put("194", "Idx：12");
    map.put("271", "Idx：12");
    System.out.println("排序 01：");
    for (String key : map.keySet()) {System.out.print(key + " ");
    }
    
    map.put("293", "Idx：12");
    map.put("370", "Idx：12");
    map.put("392", "Idx：12");
    map.put("491", "Idx：12");
    map.put("590", "Idx：12");
    System.out.println("\n\n 排序 02：");
    for (String key : map.keySet()) {System.out.print(key + " ");
    }    
    
    map.remove("293");
    map.remove("370");
    map.remove("392");
    map.remove("491");
    map.remove("590");
    System.out.println("\n\n 排序 03：");
    for (String key : map.keySet()) {System.out.print(key + " ");
    }
    
}

这段代码别离测试了三种场景，如下；

1. 增加元素，在 HashMap 还是只链表构造时，输入测试后果 01
2. 增加元素，在 HashMap 转换为红黑树时候，输入测试后果 02
3. 删除元素，在 HashMap 转换为链表构造时，输入测试后果 03

4.3 测试后果剖析

排序 01：24 46 68 29 150 172 194 271 

排序 02：24 46 68 29 271 150 172 194 293 370 392 491 590 

排序 03：24 46 68 29 172 271 150 194 
Process finished with exit code 0

从 map.keySet()测试后果能够看到，如下信息；

1. 01 状况下，排序定位哈希值下标和链表信息

1. 02 状况下，因为链表转换为红黑树，树根会挪动到数组头部。moveRootToFront()办法

1. 03 状况下，因为删除了局部元素，红黑树进化成链表。

三、总结

• 这一篇 API 源码以及逻辑与上一篇数据结构中扰动函数、负载因子、散列表实现等，内容的联合，算是把 HashMap 根本罕用技术点，梳理实现了。但常识绝不止于此，这里还有红黑树的相干技术内容，后续会进行具体。
• 除了 HashMap 以外还有 TreeMap、ConcurrentHashMap 等，每一个外围类都有一些相干的外围知识点，每一个都十分值得深入研究。这个烧脑的过程，是学习取得常识的最佳形式。
• 可能对于 HashMap 还有一些疏漏的点，也心愿浏览的小伙伴能够提出更多的问题，互相学习，共同进步，本文就到这里，感谢您的浏览！

四、举荐浏览

• HashMap 外围常识，扰动函数、负载因子、扩容链表拆分，深度学习
• HashCode 为什么应用 31 作为乘数？
• 面经手册 · 开篇《面试官都问我啥》
• 工作两年简历写成这样，谁要你呀！
• 讲道理，只有你是一个爱折腾的程序员，毕业找工作真的不须要再花钱培训！
• 大学四年到毕业工作 5 年的学习路线资源汇总