jdk1.7与jdk1.8中HashMap区别(面试最详细版)

jdk1.7与jdk1.8中HashMap区别(面试最详细版)一、区别1.最重要的一点是底层结构不一样,1.7是数组+链表,1.8则是数组+链表+红黑树结构;2.jdk1.7中当哈希表为空时,会先调用inflateTable()初始化一个数组;而1.8则是直接调用resize()扩容;3.插入键值对的put方法的区别,1.8中会将节点插入到链表尾部,而1.7中是采用头插;4.jdk1.7中的hash函数对哈希值的计算直接使用key的h…

一、区别

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 }

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/36748.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注