HashMap解决Hash冲突为什么要使用红黑树

1.HashMap的数据结构

                HashMap是由数组与链表来实现的，同时，也具备了数组和链表的所以特点

2.什么是hash冲突

                hash冲突：就是根据key即经过一个哈希变换得到的结果的作为地址去存放当前的key与 value键值对 (这个是hashmap的存值方式)，却发现，当前要存放的地址被另一组key 与 value占据了。就是要和别人在同一个地址值，这就是hash冲突（碰撞）。

3.什么是红黑树 

                 红黑树是一个接近平衡的二叉树，红黑树优点：插入快。缺点：查找慢

红黑树比较传统的定义是需要满足以下五个特征：
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

4.为什么在解决hash冲突需要红黑树

                不同的对象算出来的数组下标是相同的这样就会产生 hash 冲突，当单线链表达 到一定长度 后效率会非常低。在链表长度大于 8 的时候 ，将链表就会变成红黑树 ， 提高查询的效率。

                当然解决hash冲突还有别的方法：

• 再hash法，就是如果某个hash函数产生了冲突，再用另外一个hash进行计算，比如布隆过滤器就采用了这种方法。
• 开放寻址法，就是直接从冲突的数组位置往下寻找一个空的数组下标进行数据存储，这个在ThreadLocal里面有使用到。
• 建立公共溢出区，也就是把存在冲突的key统一放在一个公共溢出区里面。