哈希表（散列函数）的构造方法和哈希冲突

哈希表（散列表）的构造方法和哈希冲突

• 一、散列函数的构造方法

• • 1、直接定址法
  • 2、数字分析法
  • 3、平方取中法
  • 4、折叠法
  • 5、除留余数法
  • 6、随机数法

• 二、解决哈希冲突的方法

• • 1、开放定址法
  • 2、再散列函数法
  • 3、链地址法
  • 4、公共溢出区法

一、散列函数的构造方法

1、直接定址法

取关键字的某个线性函数的值作为地址：

    F(key) = A * key + B   (A、B为常数)

比如我要存储某个社区年龄0-20岁的人，那么我们可以直接使用年龄的数值作为地址：

    F(key) = key    (A=1、B=0)

采用这种方法构造的散列表结构简单，不会产生冲突。缺点就是需要事先知道关键字key的分布情况。
适合表小且连续的情况，一般使用较少

2、数字分析法

我们的手机号、身份证号、学号等等，数字位数较多，但是他们分布较为均匀。比如手机号，一般是后四位为用户的用户号，我们可以选取后四位作为散列地址。如何仍有哈希冲突，我们可以进行字符串反转等等方法去解决这类方法的哈希冲突。
通常适用于处理关键字key位数较大且已知关键字的分布

3、平方取中法

将关键字key平方，然后取平方数的中间三位作为散列地址。
假设key为100，则平方后为10000，取中间三位000作为地址
适用于不知道key的分布且位数不大

4、折叠法

折叠法是将关键字从左到右分割成位数相等的几部分(注意最后一部分位数不够时可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如我们的关键字是9876543210散列表表长为三位，我们将它分为四组，987|654|32110,然后将它们叠加求和987+654+321+0=1962，再求后3位得到散列地址为962。
有时可能这还不能够保证分布均匀，不妨从一端向另一端来回折叠后对齐相加。比如我们将987和321反转，再与654和0相加，变成789+654+123+0=1566，此时散列地址为566。

适用于不知道key的分布且位数较大

5、除留余数法

此方法是最常用的构造方法
对关键字key进行取模，模数就是散列地址：

    F(key) = key mod p (p<=散列表长)

当然这个p需要选取得恰当，不然会造成哈希冲突。根据经验，通常p选取为小于等于散列表长，最好接近于表长的最小质数。
另外，我们可以对key折叠或者平方取中再取模等。

6、随机数法

取关键字key的随机函数为散列地址：

    F(key) = random(key)

适用于关键字的长度不等时

二、解决哈希冲突的方法

1、开放定址法

一旦发生冲突，就去找下一个空的散列地址，前提是散列表的长度一定要比要存储的元素数多：

    f(key) = (f(key)+d) mod m  (d = 1,2,3,4...,m-1)

当没有冲突时，直接存入：f(key) = key mod m ；
若有冲突，则f(key) + d,每次加的d都从1开始，知道找到空的散列地址为止，我们也称这种开放定址法为线性探测法。
如果我们对d的取值进行改进：
对线性探测法的改进就是，当有冲突时，不仅是向后查找空散列地址，也可以向前查找（1、-1）。另外增加平方的意思是不让其堆积在一起，影响效率。这种改进后的方法我们称之为二次探测法。

2、再散列函数法

当使用某中构造方法造成散列冲突时，此时针对当前冲突的key可以使用其他的函数构造方法来完成，比如平方取中法、随机数法、折叠法等等。这不会造成聚集，但是此种方法增加了计算时间。

3、链地址法

有冲突则创建一个单链表，存储相同地址不同内容的元素，散列表中只存放链表的头指针。
这种方法不能使链表太长，否则会造成查找时间长。Java中的HashMap底层就是使用这种方法来实现的，在链表长度达到一定时，链表会转为红黑树。

4、公共溢出区法

当发生冲突时，将发生冲突时的key放到另外一个表中。最终会有两个表，一个我们叫基本表，一个我们可以叫做溢出表，溢出表中存放的为冲突的key。

参考资料：
1、《大话数据结构》