HashMap的实现原理

HashMap的数据结构： HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

HashMap 基于 Hash 算法实现的

1. 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数 组中的下标
2. 存储时，如果出现hash值相同的key，此时有两种情况。

1. 如果key相同，则覆盖原始值；
2. 如果key不同（出现冲突），则将当前的key-value放入链表中

3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

HashMap JDK1.8之前

JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

HashMap JDK1.8之后

相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8） 时，将链表转化为红黑树，以减少搜索时间。扩容 resize( ) 时，红黑树拆分成的 树的结点数小于等于临界值6个，则退化成链表。