jdk1.8源码解析:HashMap底层数据结构之链表转红…
2019-08-16 11:38:10来源:博客园 阅读 ()
jdk1.8源码解析:HashMap底层数据结构之链表转红黑树的具体时机
前言
本文从三个部分去探究HashMap的链表转红黑树的具体时机:
一、从HashMap中有关“链表转红黑树”阈值的声明;
二、【重点】解析HashMap.put(K key, V value)的源码;
三、测试;
一、从HashMap中有关“链表转红黑树”阈值的声明,简单了解HashMap的链表转红黑树的时机
在 jdk1.8 HashMap底层数据结构:散列表+链表+红黑树(图解+源码)的 “四、问题探究”中,我有稍微提到过散列表后面跟什么数据结构是怎么确定的:
HashMap中有关“链表转红黑树”阈值的声明:
/** * 使用红黑树(而不是链表)来存放元素。当向至少具有这么多节点的链表再添加元素时,链表就将转换为红黑树。 * 该值必须大于2,并且应该至少为8,以便于删除红黑树时转回链表。 */ static final int TREEIFY_THRESHOLD = 8; /** * 当桶数组容量小于该值时,优先进行扩容,而不是树化: */ static final int MIN_TREEIFY_CAPACITY = 64;
二、【重点】解析HashMap.put(K key, V value)的源码,去弄清楚链表转红黑树的具体时机
通过查看HashMap的源码可以发现,它的put(K key, V value)方法调用了putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)来实现元素的新增。所以我们实际要看的是putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)的源码。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K, V>[] tab; Node<K, V> p; int n, i; 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); //直接放在散列表上的节点,并没有特意标识其为头节点,其实它就是"链表/红黑树.index(0)" else { Node<K, V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; 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节点,找到该桶上的最后一个节点: p.next = newNode(hash, key, value, null); //直接生成新节点,链在最后一个节点的后面;
//“binCount >= 7”:p从链表.index(0)开始,当binCount == 7时,p.index == 7,newNode.index == 8; //也就是说,当链表已经有8个节点了,此时再新链上第9个节点,在成功添加了这个新节点之后,立马做链表转红黑树。 if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash); //链表转红黑树 break;
}
……
p = e;
}
}
……
}
……
}
通过源码解析,我们已经很清楚HashMap是在“当链表已经有8个节点了,此时再新链上第9个节点,在成功添加了这个新节点之后,立马做链表转红黑树”。
三、通过debug,进一步理解链表转红黑树的具体时机
1. 自定义一个类:该类中去重写hashCode(),让一组数据能得到同样的哈希值,从而实现哈希碰撞。同时也重写equals()方法。
public class A03Bean { protected int number; public A03Bean(int number) { this.number = number; } /** * 重写hashCode()方法,只要是4的倍数,最后算出的哈希值都会是0. */ @Override public int hashCode() { return number % 4; } /** * 也必须重写equals()方法。当发生哈希冲突的时候,需要调用equals()方法比较两个对象的实际内容是否相同。 */ @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; A03Bean other = (A03Bean) obj; if (number != other.number) return false; return true; } }
2. 将自定义类A03Bean的实例放到HashMap中:
public class A03Method_TreeifyBin2 { public static void main(String[] args) { HashMap<A03Bean, Integer> hashMap = new HashMap<>(); hashMap.put(new A03Bean(4), 0); hashMap.put(new A03Bean(8), 1); hashMap.put(new A03Bean(12), 2); hashMap.put(new A03Bean(16), 3); hashMap.put(new A03Bean(20), 4); hashMap.put(new A03Bean(24), 5); hashMap.put(new A03Bean(28), 6); hashMap.put(new A03Bean(32), 7); hashMap.put(new A03Bean(36), 8); hashMap.put(new A03Bean(40), 9); hashMap.put(new A03Bean(44), 10); System.out.println("hashMap.size = " + hashMap.size()); //查看是否所有对象都放到HashMap中了: for(A03Bean key : hashMap.keySet()) { System.out.println(key.number); } } }
3.debug,断点查看当同一个桶上的链表的长度达到多长时会做“链表转红黑树”的操作。
断点打在HashMap.putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法的“treeifyBin(tab, hash);”这里。
4.测试结果:
当put进第9个元素(hashMap.put(new A03Bean(36), 8);)时,HashMap做了链表转红黑树的操作。
也就是说:当链表已经有8个元素了,此时put进第9个元素,先完成第9个元素的put,然后立刻做链表转红黑树。这个结论和第2点中得到的结论一致。
最后的输出结果也证明了所有的元素都成功put进了集合中,hashMap.size等于11。
到这里,有关“HashMap的链表转红黑树的具体时机”算是解释清楚了,有时间再探究“HashMap的红黑树转回链表的具体时机”。
原文链接:https://www.cnblogs.com/laipimei/p/11282055.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- JVM常见面试题解析 2020-06-11
- 你说研究过Spring里面的源码,循环依赖你会么? 2020-06-09
- 深入解析ThreadLocal和ThreadLocalMap 2020-06-08
- 通俗理解spring源码(六)—— 默认标签(import、alias、be 2020-06-07
- 学习源码的第八个月,我成了Spring的开源贡献者 2020-06-02
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash