当许多密钥具有相同的哈希码时,Java 8的HashMap如何退化为平衡树？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了当许多密钥具有相同的哈希码时,Java 8的HashMap如何退化为平衡树？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2021字，纯文字阅读大概需要3分钟。

内容图文

当许多密钥具有相同的哈希码时,Java 8的HashMap如何退化为平衡树？我读到键应该实现Comparable来定义一个排序. HashMap如何结合散列和自然排序来实现树？那些没有实现Comparable的类,或者多个不可相互比较的Comparable实现是同一个映射中的键的情况呢？

解决方法:

HashMap中的implementation notes comment是对HashMap操作的更好描述,而不是我自己写的.理解树节点及其排序的相关部分是：

This map usually acts as a binned (bucketed) hash table, but when bins get too large, they are transformed into bins of TreeNodes, each structured similarly to those in java.util.TreeMap. […] Bins of TreeNodes may be traversed and used like any others, but additionally support faster lookup when overpopulated. […]

Tree bins (i.e., bins whose elements are all TreeNodes) are ordered primarily by hashCode, but in the case of ties, if two elements are of the same “class C implements Comparable” type then their compareTo method is used for ordering. (We conservatively check generic types via reflection to validate this — see method 07001). The added complexity of tree bins is worthwhile in providing worst-case O(log n) operations when keys either have distinct hashes or are orderable, Thus, performance degrades gracefully under accidental or malicious usages in which hashCode() methods return values that are poorly distributed, as well as those in which many keys share a hashCode, so long as they are also Comparable. (If neither of these apply, we may waste about a factor of two in time and space compared to taking no precautions. But the only known cases stem from poor user programming practices that are already so slow that this makes little difference.)

当两个对象具有相同的哈希码但不能相互比较时,首先通过getClass().getName()(！)上的字符串比较,然后通过比较System.identityHashCode,调用方法tieBreakOrder来打破平局.

实际的树构建开始于treeifyBin,从bin到达TREEIFY_THRESHOLD(当前为8)开始,假设哈希表具有至少MIN_TREEIFY_CAPACITY容量(当前为64).这是一个大多数正常的红黑树实现(crediting CLR),有一些复杂性来支持遍历,就像哈希箱一样(例如,removeTreeNode).

内容总结

以上是互联网集市为您收集整理的当许多密钥具有相同的哈希码时,Java 8的HashMap如何退化为平衡树？全部内容，希望文章能够帮你解决当许多密钥具有相同的哈希码时,Java 8的HashMap如何退化为平衡树？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端