应用场景：快速查找
通过计算元素的哈希码，得到元素的桶下标，计算元素位置。接下来只需要进行少量的比较即可找到元素。
当链表长度过长时，可以通过扩容减少链表长度。但如果元素的原始哈希码都一样时，即使扩容也无法改变链表长度，只能进行红黑树的树化。
底层数据结构，1.7与1.8有何不同？
1.7 数组+链表
1.8 数组+(链表|红黑树)
为什么要用红黑树？
红黑树：父节点左边都是比它小的元素；父节点右边都是比它大的元素。
数组链表过长会影响HashMap的性能。引入红黑树后链表过长也不会影响性能。
何时会树化？
1.链表长度大于8.
2.数组容量大于等于64.如果不够大会首先尝试扩容。
为何一上来不树化？
链表短时性能比红黑树好。树化会占用更多内存，没必要进行树化。
树化阈值为何是8？
正常情况下链表不会超过8.遭受到恶意攻击后链表长度才会过长。
1.红黑树用来避免Dos攻击，防止链表过长时性能下降，是偶然现象。hash表时间复杂度为O(1)，且Node占用空间小；而红黑树时间复杂度为O(log₂n)，且TreeNode占用空间较大。非必要时尽量使用链表。
2.hash值完全随机时，在hash表内按泊松分布。在负载因子为0.75的情况下，长度超过8的链表出现的概率为亿分之6.选择8使树化的几率足够小。
何时会退化为链表？
1.扩容时拆分树，树元素<=6时退化链表。
2.remove树节点，若root(根节点)、root.left(左孩子)、root.right(右孩子)、root.left.left(左孙子)有一个为null，也会退化链表。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/128077.html
