HashMap如何解决哈希冲突?

简介: HashMap如何解决哈希冲突?

1. Hash算法和Hash表


了解Hash冲突首先了解Hash算法和Hash表


image.png

  1. Hash算法就是把任意长度的输入通过散列算法变成固定长度的输出,这个输出结果就是一个散列值


  1. Hash表又叫做“散列表”,它是通过key直接访问到内存存储位置的数据结构,在具体的实现上,我们通过Hash函数,把key映射到表中的某个位置,来获取这个位置的数据,从而加快数据的查找



2. Hash冲突


Hash冲突是由于哈希算法,被计算的数据是无限的,而计算后的结果的范围是有限的,总会存在不同的数据,经过计算之后得到值是一样,那么这个情况下就会出现所谓的哈希冲突



3. 解决Hash冲突的方法有四种


  1. 开放定址法也称线性探测法,就是从发生冲突的那个位置开始,按照一定次序从Hash表找到一个空闲位置然后把发生冲突的元素存入到这个位置,而在java中,ThreadLocal就用到了线性探测法来解决Hash冲突


image.png

如图,在Hash表索引1的位置存了key=name,再向它添加key=hobby的时候,假设计算得到的索引也是1,那么这个时候发生哈希冲突,而开放开放定址法就是按照顺序向前找到一个空闲的位置,来存储这个冲突的key


2.链式寻址法,这是一种常见的方法,简单理解就是把存在Hash冲突的key,以单向链表来进行存储,比如HashMap

image.png
如图存在冲突的key直接以单向链表的方式去进行存储


  1. 再Hash法,就是通过某个Hash函数计算的key,存在冲突的时候,再用另外一个Hash函数对这个可以进行Hash,一直运算,直到不再产生冲突为止,这种方式会增加计算的一个时间,性能上呢会有一些影响


  1. 建立公共移除区,就是把Hash表分为基本表和益处表两个部分,凡是存在冲突的元素,一律放到益处表中



4.HashMap在JDK1.8版本的优化


HashMap在JDK1.8版本中是通过链式寻址法以及红黑树来解决Hash冲突的问题,其中红黑树是为了优化Hash表的链表过长导致时间复杂度增加的问题,当链表长度大于等于8并且Hash表的容量大于64的时候,再向链表添加元素,就会触发链表向红黑树的一个转化



相关文章
|
1月前
|
存储 算法 Serverless
解决哈希冲突的方式
解决哈希冲突的方式
38 0
|
9月前
|
存储 算法 安全
HashMap底层实现原理
HashMap底层实现原理
109 0
|
1月前
|
存储 C++
为什么HashMap的键值可以为null,而ConcurrentHashMap不行?
为什么HashMap的键值可以为null,而ConcurrentHashMap不行?
26 1
|
8月前
|
设计模式 算法 Java
面试官:JDK1.8 HashMap扩容rehash算法是如何优化的?
本文跟大家聊一聊一个常见的面试题,那就是JDK1.8 HashMap扩容rehash算法是如何优化的?
|
1月前
|
存储 算法 Java
深入剖析HashMap:理解Hash、底层实现与扩容机制
深入剖析HashMap:理解Hash、底层实现与扩容机制
356 1
|
1月前
|
安全
搞懂HashTable, HashMap, ConcurrentHashMap 的区别,看着一篇就足够了!!!
搞懂HashTable, HashMap, ConcurrentHashMap 的区别,看着一篇就足够了!!!
44 0
|
10月前
|
存储 Java
解决 Java 中的哈希冲突:深入了解哈希冲突及其解决方案
在 Java 编程中,哈希表(Hash Table)是一种常用的数据结构,用于存储键值对,并提供快速的数据访问。然而,当不同的键被映射到相同的哈希桶时,就会产生哈希冲突。本文将深入探讨哈希冲突的原因、解决方案以及在 Java 中如何应对哈希冲突的问题。
|
Java
【JAVA数据结构】哈希表-HashSet and HashMap(二)
JAVA数据结构 & 哈希表 -HashSet and HashMap
61 0
|
Java
【JAVA数据结构】哈希表-HashSet and HashMap
JAVA数据结构 & 哈希表 -HashSet and HashMap
48 0