hash碰撞解决办法

在hash碰撞的情况下，主要的处理方法有：

1.开放地址法

开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)

基本思想：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。

2.rehash（再hash法）

使用第二个或第三个...计算地址，知道无冲突。比如：按首字母进行hash冲突了，则按照首字母第二位，进行hash寻址。

3.链地址法（拉链法）

创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

java hashmap使用的就是拉链法解决hash碰撞。

哈希表是由链表+数组组成。

通过hash(key)%len存储到相对应的数组中，如140%16=12.意味着数组下标相同，并不表示hashCode相同。

1、哈希就是做一个映射,为的是查找快.冲突是zd因为映射毕竟是有一个范围的,这个范围可能会小于你原来的那个范围,所以可能好多个值映射了之后成为一个值了.

举例来说,可能希望查版找字符串比较快,你会用一种计算方法将一个字符串权映射为一个整数,而且要求这个数字在100以内.那么如果处理了10000个字符串,他们映射的值肯定会冲突.

2、hash：hashing定义了一种百将字符组成的字符串转换为固定长度度(一般是更短长度)的数值或索引值的方法，称为问散列法，也叫哈希法。

冲突：两个不同的关答键字，由于散列函数值相同，因而被内映射到同一表位置上。该容现象称为冲突(collision)或碰撞。

3、哈希计算就是努力的把比较大的数据存放到相百对较小的空间中。

最常见的哈希算法是取模法。

下面简单讲讲取模法的计算过程。

比如：数组的长度是5。这时有度一个数据是6。那么如何把这个

6存放到长度只有5的数组中呢。按照取模法，计算

6％5，结果是1，那么就把6放到数组下标是1的位问置。那么，7

就应该放到2这个位置。到此位置，哈希冲突还没有出现。

这时，有个数据是11，按照取模法，11％5＝1，也等于1。那么

原来数组下标是1的地方已经有数了答，是6。这时又计算出1这个

位置，那么数组1这个位置，就回必须储存两个数了。这时，就叫

哈希答冲突。冲突之后就要按照顺序来存放了。

如果数据的分布比较广泛，而且储存数据的数组长度比较大。

那么哈希冲突就比较少。否则冲突是很高的。

具体的算法你要参照更加专业的书籍。

希望对你有帮助。

出自：百度知道

---