详细理解了Hash碰撞及处理方法

为什么会出现hash碰撞

在hash算法下,假设两个输入串的值不同,但是得到的hash值相同, 即会产生hash碰撞

一个很简单的例子:

假设你自己设计了一个计算hash的算法toHashValue(String). 是取的输入值的Unicode编码值(当然实际的情况会比这复杂很多很多)

那么 toHashValue('A'+'D')  得到的unicode 与 toHashValue('B'+'C')  相等.  所以产生了hash碰撞.

因为AD跟BC我存的实际的值并不一样, 不能做覆盖, 所以就需要解决hash碰撞.

 

解决hash碰撞

JAVA里一般用的是链表法

以hashMap为例:

hashMap的底层结构是一个数组加链表式的结构, 可以理解为key的hash值放在数组里, value放在链表里,

当出现hash碰撞时,即key的hash值相同,那么新添加的这个值会在该元素下的链表的value后面添加一个元素.

用get() 方法取到该hash值后,需要遍历所有的链表, 取出与key值对应的value

但是问题来了, 最坏最坏的情况下, 假设你不停插入的key的hash值都是同一个,那么这个数组+链表的结构就会退化成单头数组+长链表的这种结构,而每次查询都是要遍历所有链表值的,效率就会大大降低. 于是这时候提出了红黑树的概念

当链表的长度大于8时,会转化成红黑树,效率会大大提升.ps.红黑树是一个平衡二叉树, 如果有想了解这块的同学,可以单独搜下,此处不再赘述.

参考了两位大佬的文章

----------------侵删------------------

https://www.jianshu.com/p/379680144004

https://blog.csdn.net/qq_35583089/article/details/80048285