Hash是一种校验方法, 其中应用最广为人知的就是 HashMap。 当然Hash算法并不完美,有可能两个不同的原始值在经过哈希运算后得到同样的结果, 这样就是哈希碰撞。
哈希碰撞有几种解决办法 · 开放定址法 · 链地址
链地址法其实就是HashMap中用的策略。 原理是在HashMap中同样哈希值的位置以一串链表存储起来数据, 把多个原始值不同而哈希结果相同的数据以链表存储起来。
当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。 用方程来表达的话是这样子,
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ( k ≤ m – 1))
m 是哈希表的长度。 举一个实际的例子, 一个哈希函数是 H ( key ) = key mod 7 , 哈希表长度为 7, 关键字序列( 32 , 13 , 49 , 55 , 22 , 38 , 21 ) 如果以线性探测再散列来生成哈希表的话, 过程是这样的
32 % 7 = 4 ; 13 % 7 = 6 ; 49 % 7 = 0 ; 55 % 7 = 6 发生冲突,下一个存储地址( 6 + 1 )% 7 = 0 ,仍然发生冲突,再下一个存储地址:( 6 + 2 )% 7 = 1 未发生冲突,可以存入。 22 % 7 = 1 发生冲突,下一个存储地址是:( 1 + 1 )% 7 = 2 未发生冲突; 38 % 7 = 3 ; 21 % 7 = 0 发生冲突,按照上面方法继续探测直至空间 5 ,不发生冲突
所得到的哈希表对应存储位置:
下标: 0 1 2 3 4 5 6 49 55 22 38 32 21 13