【HashMap原理+红黑树】_hashmap底层实现原理红黑树

                HashMap原理+红黑树

一、HashMap原理

        HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体。
在JDK1.8中，链表长度大于8的时候，链表会转成红黑树！

二、HashMap在JDK1.8之前和之后的区别

        在JDK1.8之前 结构是数组+链表，缺点就是哈希函数很难使元素百分百的均匀分布，这会产生一种极端的可能，就是大量的元素存在一个桶里

在jdk1.8之后，HashMap采用数组加链表或是红黑树的形式

1、在HashMap添加元素时，按照数组+链表形式添加，当桶中的数量大于8时，链表会转换成红黑树的形式。

2、删除元素、扩容时，同上，数量大于8时，也是采用红黑树形式存贮，但是在数量较少时，即数量小于6时，会将红黑树转换回链表。

3、遍历、查找时，使用红黑树，他的时间复杂度O（log n），便于性能的提高。

三、红黑树的作用

        Java 中的 HashMap 采用链表法来解决哈希冲突HashMap 原理，即具有相同桶下标的键值对使用一个链表储存。当链表变长时，查找和添加（需要确定 key 是否已经存在）都需要遍历这个链表，速度会变慢。JDK 1.8 后加入了链表转换为红黑树的机制，但是红黑树的转换并不是一个廉价的操作，只有当链表长度大于等于 TREEIFY_THRESHOLD 才会 treeify。

        实际上并不是只要链表长度大于 8 就会 treeify。当 table.length（桶的个数）小于 MIN_TREEIFY_CAPACITY 时会优先扩容而不是转换为红黑树。

四、扩容机制

        HashMap是基于数组+链表和红黑树实现的，但用于存放key值得的数组桶的长度是固定的，由初始化决定。

        那么，随着数据的插入数量增加以及负载因子的作用下，就需要扩容来存放更多的数据。而扩容中有一个非常重要的点，就是jdk1.8中的优化操作，可以不需要再重新计算每一个元素的哈希值。