面试题总结：HashMap实现原理

1.简单了解：

JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

HashCode是jdk根据对象的地址或字符串或者数字利用hash算法计算出的int类型的数值。

2.HashMap实现原理详解：

数组->链表->红黑树

首先有一个每个元素都是链表的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。
在jdk8中，HashMap处理“碰撞”增加了红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当较大时（>8个），采用红黑树（特点是查询时间是O（logn））存储（有一个阀值控制，大于阀值(8个)，将链表存储转换成红黑树存储）

3.红黑树是一种自平衡二叉查找树

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。 对于任何有效的红黑树都有以下要求：

• 1）节点是红色或黑色。
• 2）根节点是黑色。
• 3）每个叶节点是黑色的。
• 4）每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 5从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。