hashmap存储方式 hash碰撞及其解决方式

1.Map的存储特点

在Map这个结构中，数据是以键值对（key-value）的形式进行存储的，每一个存储进map的数据都是一一对应的。

创建一个Map结构可以使用new HashMap()以及new TreeMap()两种方式，两者之间的区别是：TreeMap是支持 排序的。

2.HashMap的底层存储方式

 

总结:

1. 用hashMap存储数据(key,value)的时候使用put方法

2. put方法会调用putVal方法,把hash(hey)和当前的key，value作为参数传进来

3. 判断数组是否为空，即判断是否是第一次添加数据,如果是的话，会先调用resize方法扩容

4. 之后,根据当前key的hash值找到它在数组中的下标 (怎么算的? index = (n - 1) & hash)，判断当前下标位置是 否已经存在元素

5. 如果不存在，直接把key、value包装成Node节点作为链表头存入数组

6. 如果存在，分为三种情况

1. ）比较一下已有数据和存入数据 如果hash值等于传过来的hash，并且他们的key值也相等 最后会把 value的值覆盖处理

2. ）上一步不相等，就判断一下当前是不是红黑树结构，是则调用putTreeVal()把它加入到红黑树

3. ）既不相等，也不是红黑树结构，说明是普通链表结构，遍历这个链表，将数据存到链表尾部

1. 在遍历过程中，如果是最后一个节点，则插入新节点 newNode(hash, key, value, null)

2. 如果链表长度超过了8，则转化为红黑树 treeifyBin(tab, hash)3. 如果遍历的时候遇到了相同的key 把value的值覆盖处理

7. 如果当前数组中的元素个数超过阈值，则扩容 resize();

8. putVal（）方法 没修改value就返回NULL 修改了就返回旧值（之前的value）

3.什么是hash碰撞

Hash Collision 就是我们说的 Hash 碰撞或者 Hash 冲突。

这个其实也非常好理解，就是 2 个输入不同的数据，经过 Hash 算法后，得到的 Hash 值是一样的。

在HashMap的查询和添加过程中，绕不过去的是计算元素在数组的位置index，key的HashCode作为这个计算的 基础。计算后的Hash值存在相同的情况，hash与长度取余的结果也有相同的情况，这个时候运算结果相同的两个 对象就需要存储到同一个链表中，这就是HashMap中的Hash碰撞。

4.如何解决hash碰撞

1.开放地址方法

1）线性探测

按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。 就是在

此空间不足时，直接放入此空间的后一个空的空间

2）再平方探测

按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个

单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。 要注意平方不能超过容量的值 Size=16的时候，找备

选的单元只能取i=1,2,3，也就是距离冲突单元1,4,9个单位的位置了。

3）伪随机探测

按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发

生哈希冲突。

2.链式地址法（HashMap的哈希冲突解决方法）

对于相同的值，使用链表进行连接。使用数组存储每一个链表。 就是hashmap的底层原理 ：数组+链表 就是没有

红黑树

补充：在JDK1.8中HashMap通过链式寻址法以其红黑树来解决哈希冲突的，其中红黑树是为了优化哈希表的链表

过长 导致遍历时间复杂度增加的问题。当链表长度大于8并且哈希表的容量大于64,再向链表中添加元素,会转化为

红黑树。优点：

1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较

2）

由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况； （

3）开放定址法为

减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉 链法中增加的指针域可忽略不计，因此节省空间； （

4）在用拉链法构造的散列表中，删除结点的操作易于实现。

只要简单地删去链表上相应的结点即可。 缺点：

1） 指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。

3.建立公共溢出区

建立公共溢出区存储所有哈希冲突的数据

4.再哈希法

对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。

5.如何解决并发

HashMap的线程不安全主要体现在下面两个方面：

1.在JDK1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。 2.在JDK1.8中，在并发执行put操作时会

发生数据覆盖的情况。 1、if((p = tab[i =(n -1)& hash])==null)// 1、此处线程不安全——用来判定索引位置是否

hash碰撞，比如两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完第六

行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线

程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致 了线程B插入的数据被线程A覆盖了，从而线程不安全。

2、if (++size > threshold)中的++size：同样还是线程A、B，这两个线程同时进行put操作时，假设当前HashMap

的zise大小为10，当线程A执行到此行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片

耗尽只好让出CPU，线程B快乐的拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将

size=11写回主内存，然后线程A再次拿到CPU并继续执行(此时size的值仍为10)，当执行完put操作后，还是将

size=11写回内存，此时线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导

致了线程不安全。

解决方法： 1.Hashtable

HashTable为了实现多线程安全，在几乎所有的方法上都加上了synchronized锁（锁的是类的实例,也就是整个

map结构），当一个线程访 问 Hashtable 的同步方法时，其他线程如果也要访问同步方法，会被阻塞住。

2.Collections.synchronizedMap(一般不用) 缺点:从锁的角度来看，基本上是锁住了尽可能大的代码块.性能会比较

差 3.ConcurrentHashMap（常用） JDK 1.7 中，采用分段锁的机制，实现并发的更新操作，底层采用数组+链表的 存储结构，包括两个核心静态内部类 Segment 和 HashEntry。 ①、Segment 继承 ReentrantLock（重入锁） 用

来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶； ②、HashEntry 用来封装映射表的键-值 对； ③、每个桶是由若干个 HashEntry 对象链接起来的链表 分段锁：Segment数组中，一个Segment对象就是一 把锁,对应一个HashEntry数组,该数组中的数据同步依赖于同一把锁,不同HashEntry数组的读写互不干扰

JDK 1.8中抛弃了原有的 Segment 分段锁，来保证采用Node + CAS + Synchronized来保证并发安全性。取消类 Segment，直接用table 数组存储键值对；当 Node对象组成的链表长度超过TREEIFY_THRESHOLD 时，链表转换

为红黑树，提升性能。底层变更为数组 + 链表 + 红黑树。 CAS性能很高，但synchronized之前一直都是重量级的 锁，jdk1.8 引入了synchronized，采用锁升级的方式。