HashMap之Hash碰撞
详细理解了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.红黑树是一个平衡二叉树, 如果有想了解这块的同学,可以单独搜下,此处不再赘述.
参考了两位大佬的文章
----------------侵删------------------