在Java中，保存数据有两种比较简单的数据结构：数组和链表。
数组的特点是：寻址容易，插入和删除困难；
链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做拉链法的方式可以解决哈希冲突。
HashMap JDK1.8之前
JDK1.8之前采用的是拉链法。
拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
HashMap JDK1.8之后
相比于之前的版本，JDK1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
JDK1.7 VS JDK1.8 比较
JDK1.8主要解决或优化了以下问题：
1、resize 扩容优化
2、引入了红黑树，目的是避免单条链表过长而影响查询效率，红黑树算法请参考
3、解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。
| 不同 | JDK1.7 | JDK1.8 |
|---|---|---|
| 存储结构 | 数组+链表 | 数组+链表+红黑树 |
| 初始化方式 | 单独函数：inflateTable() | 直接集成到了扩容函数resize() |
| hash值计算方式 | 扰动处理=9次扰动=4次位运算+5次异或运算 | 扰动处理=2次扰动=1次位运算+1次异或运算 |
| 存放数据的规则 | 无冲突时，存放数组；冲突时，存放链表 | 无冲突时，存放数组；冲突&链表长度<8：存放单链表；冲突&链表长度>8：树化并存放红黑树 |
| 插入数据方式 | 头插法(先将原位置的数据移到后1位，再插入数据到该位置) | 尾插法(直接插入到链表尾部/红黑树) |
| 扩容后存储位置的计算方式 | 全部按照原来方法进行计算(即hashCode ->> 扰动函数 ->> (h&length-1)) | 按照扩容后的规律计算(即扩容后的位置 = 原位置 or 原位置 + 旧容量) |
Was this helpful?
0 / 0