【校招VIP】jdk1.7与jdk1.8中HashMap区别（面试最详细版）- 校招VIP

转载声明：文章链接：https://blog.csdn.net/xing123456jl/article/details/108044431

一、区别
1. 最重要的一点是底层结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构;
2. jdk1.7中当哈希表为空时，会先调用inflateTable()初始化一个数组；而1.8则是直接调用resize()扩容;
3. 插入键值对的put方法的区别，1.8中会将节点插入到链表尾部，而1.7中是采用头插；
4. jdk1.7中的hash函数对哈希值的计算直接使用key的hashCode值，而1.8中则是采用key的hashCode异或上key的hashCode进行无符号右移16位的结果，避免了只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，使元素分布更均匀；
5. 扩容时1.8会保持原链表的顺序，而1.7会颠倒链表的顺序；而且1.8是在元素插入后检测是否需要扩容，1.7则是在元素插入前；
6. jdk1.8是扩容时通过hash&cap==0将链表分散，无需改变hash值，而1.7是通过更新hashSeed来修改hash值达到分散的目的；
7. 扩容策略：1.7中是只要不小于阈值就直接扩容2倍；而1.8的扩容策略会更优化，当数组容量未达到64时，以2倍进行扩容，超过64之后若桶中元素个数不小于7就将链表转换为红黑树，但如果红黑树中的元素个数小于6就会还原为链表，当红黑树中元素不小于32的时候才会再次扩容。
二、JDK1.8 HashMap源码解读
1.桶的树形化 treeifyBin()
(1)根据哈希表容量以及元素个数确定是扩容还是树形化；
(2)如果是树形化则遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系；
(3)让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容；

//将桶内所有的 链表节点 替换成 红黑树节点
1 final void treeifyBin(Node<K,V>[] tab, int hash) {
2   int n, index; Node<K,V> e;
3    //如果当前哈希表为空，或者哈希表中元素的个数小于 进行树形化的阈值(默认为 64)，就去新建/扩容
4   if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
5        resize();
6    else if ((e = tab[index = (n - 1) & hash]) != null) {
7        //如果哈希表中的元素个数超过了 树形化阈值，进行树形化
8        // e 是哈希表中指定位置桶里的链表节点，从第一个开始
9        TreeNode<K,V> hd = null, tl = null; //红黑树的头、尾节点
10        do {
11            //新建一个树形节点，内容和当前链表节点 e 一致
12            TreeNode<K,V> p = replacementTreeNode(e, null);
13            if (tl == null) //确定树头节点
14                hd = p;
15           else {
16               p.prev = tl;
17                tl.next = p;
18            }
19            tl = p;
20        } while ((e = e.next) != null); 
21        //让桶的第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了
22        if ((tab[index] = hd) != null)
23            hd.treeify(tab);
24    }
25 }
26    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
27    return new TreeNode<>(p.hash, p.key, p.value, next);
28 }

2.put()
①.判断键值对数组table[i]是否为空，否则执行resize()扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否不小于7，不小于7就把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量是否超过阈值，如果超过了就进行扩容；

1 public V put(K key, V value) {
2     // 对key的hashCode()做hash
3     return putVal(hash(key), key, value, false, true);
4 }
5
6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
7                boolean evict) {
8     Node<K,V>[] tab; Node<K,V> p; int n, i;
9     // 步骤①：tab为空则创建
10     if ((tab = table) == null || (n = tab.length) == 0)
11         n = (tab = resize()).length;
12     // 步骤②：计算index，并对null做处理
13     if ((p = tab[i = (n - 1) & hash]) == null)
14         tab[i] = newNode(hash, key, value, null);
15     else {
16         Node<K,V> e; K k;
17         // 步骤③：节点key存在，直接覆盖value
18         if (p.hash == hash &&
19             ((k = p.key) == key || (key != null && key.equals(k))))
20             e = p;
21         // 步骤④：判断该链为红黑树
22         else if (p instanceof TreeNode)
23             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
24         // 步骤⑤：该链为链表
25         else {
26             for (int binCount = 0; ; ++binCount) {
27                 if ((e = p.next) == null) {
28                     p.next = newNode(hash, key,value,null);
                        //链表长度大于8转换为红黑树进行处理
29                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
30                         treeifyBin(tab, hash);
31                     break;
32                 }
                    // key已经存在直接覆盖value
33                 if (e.hash == hash &&
34                     ((k = e.key) == key || (key != null && key.equals(k))))
35                            break;
36                 p = e;
37             }
38         }
39        
40         if (e != null) { // existing mapping for key
41             V oldValue = e.value;
42             if (!onlyIfAbsent || oldValue == null)
43                 e.value = value;
44             afterNodeAccess(e);
45             return oldValue;
46         }
47     }
48     ++modCount;
49     // 步骤⑥：超过最大容量就扩容
50     if (++size > threshold)
51         resize();
52     afterNodeInsertion(evict);
53     return null;
54 }

3.红黑树中查找元素 getTreeNode()
(1) HashMap的查找方法是get(),它通过计算指定key的哈希值后，调用内部方法 getNode()；
(2) getNode()方法中根据哈希表元素个数与哈希值计算出对应索引位置，找到key所在的桶的头结点，如果头节点恰好是红黑树节点，就调用红黑树节点的getTreeNode()方法，否则就遍历链表节点；
(3) getTreeNode()方法通过调用红黑树的find()方法进行查找即可；
(4) 由于之前添加时已经保证整个树是有序的，因此查找时基本就是折半查找，效率很高；

1 final Node<K,V> getNode(int hash, Object key) {
2    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
3    if ((tab = table) != null && (n = tab.length) > 0 &&
4        (first = tab[(n - 1) & hash]) != null) {
5       if (first.hash == hash && // always check first node
6            ((k = first.key) == key || (key != null && key.equals(k))))
7            return first;
8        if ((e = first.next) != null) {
9            if (first instanceof TreeNode)
10                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
11            do {
12               if (e.hash == hash &&
13                    ((k = e.key) == key || (key != null && key.equals(k))))
14                    return e;
15            } while ((e = e.next) != null);
16        }
17    }
18    return null;
19 }
20
21 final TreeNode<K,V> getTreeNode(int h, Object k) {
22   return ((parent != null) ? root() : this).find(h, k, null);
23 }