Hash冲突解决方法

什么是hash冲突?

hash冲突就是在操作哈希表(散列表)的时候,不同的key值经过hash函数(散列算法)之后得到相同的hash值,那么一个位置没法放置两份value,这种情况就是hash冲突。

Hash冲突常用解决方法

开放地址法(open addressing)

简单来说就是通过计算出来冲突的hash值进行再次的运算,直到得到可用的地址,主要有以下3种:

  1. 线性探测再散列:发生冲突时,顺序查看哈希表下一单元是否可用,直到找到可用的单元
  2. 二次探测再散列:发生冲突时,以冲突的位置为中心向左右探测是否有可用单元
  3. 伪随机探测再散列:通过一组伪随机数列计算得到对应的单位位置

单独链表法

就是在哈希表中,针对相同的hash值使用链表的方式来存放

再Hash

提供多个hash函数,冲突时使用其他的hash函数再次运算

建立公共溢出区

建立一个溢出表,hash冲突的时候放入溢出表

Java中HashMap如何解决冲突

其实,Java中的HashMap采用的hash冲突解决方案就是单独链表法,也就是在hash表节点使用链表存储hash值相同的值

不过需要知道的是JDK8之后,如果链表长度超过8将会将链表转化为红黑树以便提高在hash冲突严重情况下的查询效率,也能够避免一定的hash碰撞攻击。