Hash函数及冲突

Hash函数及冲突


Hash表

  • 非Hash表:关键字在表中和它之间存在的位置不确定,查找的过程为定值一次和各个关键字进行比较,查找的效率取决于和给定值比较的次数。
  • Hash表:关键字和表中的位置存在确定的关系。
  • 哈希函数:关键字在Hash表中的具体分布,取决于哈希函数。

装填因子

装填因子 α = 填入哈希表中的元素个数/哈希表的长度
α越小,填入表中的元素较少,产生冲突的可能性就越少


Hash函数

Hash函数设计原则

关键字经过Hash函数映射之后,应该尽可能覆盖整个Hash函数的空间,并且关键字映射至桶中的概率尽可能一致,总而言之,随机性强,规律性越弱的Hash函数越好。

除余法

hash(key) = key mod M
M取素数能降低冲突

MAD法

hash(key) = (a*key + b) mod M

伪随机数法

hash(key) = rand(key) mod M


Hash冲突解决办法

开放定制法

这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:
Hi=(H()key)+di)% m i=1,2,…,n
其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下三种:

线性探测再散列

di i=1,2,3,…,m-1
这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

二次探测再散列

di = 1^2, -1^2, 2^2, -2^2, … , k^2, -k^2 (k<=m/2)
这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

伪随机探测再散列

di=伪随机数序列。


再哈希法

这种方法是同时构造多个不同的哈希函数:
Hi = RH1(key), i = 1, 2, …, k
当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。


链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。


建立公共溢出区

这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。且溢出表也可采用同样的哈希函数,易于实现,可理解为一种递归形势的散列表。


开放定址和封闭定址

  • 开放地址:哈希表的每一个桶单元都有可能存放关键字,故称之为开放定址,其散列地址仅限于散列表所覆盖的范围之内,称之为封闭散列。

    • 优点:
      • 记录更容易进行序列化(serialize)操作;
      • 如果记录总数可以预知,可以创建完美哈希函数,此时处理数据的效率是非常高的。
    • 缺点:
      • 存储记录的数目不能超过桶数组的长度,如果超过就需要扩容,而扩容会导致某次操作的时间成本飙升,这在实时或者交互式应用中可能会是一个严重的缺陷;
      • 使用探测序列,有可能其计算的时间成本过高,导致哈希表的处理性能降低;
      • 由于记录是存放在桶数组中的,而桶数组必然存在空槽,所以当记录本身尺寸(size)很大并且记录总数规模很大时,空槽占用的空间会导致明显的内存浪费;
      • 删除记录时,比较麻烦。比如需要删除记录a,记录b是在a之后插入桶数组的,但是和记录a有冲突,是通过探测序列再次跳转找到的地址,所以如果直接删除a,a的位置变为空槽,而空槽是查询记录失败的终止条件,这样会导致记录b在a的位置重新插入数据前不可见,所以不能直接删除a,而是设置删除标记。这就需要额外的空间和操作。
  • 封闭地址:哈希表的关键字发生冲突之后,采用另外的数据结构存放冲突的关键字,这样的散列称之为开放散列。

    • 优点:
      • 对于记录总数频繁可变的情况,处理的比较好(也就是避免了动态调整的开销);
      • 由于记录存储在结点中,而结点是动态分配,不会造成内存的浪费,所以尤其适合那种记录本身尺寸(size)很大的情况,因为此时指针的开销可以忽略不计了;
      • 删除记录时,比较方便,直接通过指针操作即可;
    • 缺点:
      • 存储的记录是随机分布在内存中的,这样在查询记录时,相比结构紧凑的数据类型(比如数组),哈希表的跳转访问会带来额外的时间开销;
      • 如果所有的 key-value 对是可以提前预知,并之后不会发生变化时(即不允许插入和删除),可以人为创建一个不会产生冲突的完美哈希函数(perfect hash function),此时封闭散列的性能将远高于开放散列;
      • 由于使用指针,记录不容易进行序列化(serialize)操作。

参考资料
解决hash冲突的三个方法
hash冲突的四种办法