算法技术手册 – 查找 – 散列查找(Hash查找)

对于含有n个元素的集合C,我们先构造一个Hash函数,让n映射到b个桶内,当选择合理时,速度会很快,时间复杂度O(1)。

完美哈希函数:不会产生冲突,是存在的。

对于>=1个值映射到同一个桶的情况下,就会发生碰撞。处理方法:

  • 链表:每个桶拉一个链表,第一遍散列后,在链表中查找是否存在元素。
  • 开放定址:构造双变量散列函数h(u, j)。h(u, 0) = h(u),此时退化为原始散列函数。

开放定址,分两类:

  • 线性探测h(u, j)=(h(u)+j) mod n
  • 二次探测h(u, j)=(h(u) + f(j)) mod m,其中f(j)是二次方函数

主要算法:

1、load:读取元素,构造散列表(使用链表)

2、search:查找,hash(val)算出slot,然后在slot的链表上查找是否存在。

源代码:

Java提供了Hashtable类,比我们实现的散列查找具有更好的性能。它引入了负载因子的概念。a=n/b,即每个链上的平均元素数量。当a过高(默认超过0.75),则会重散列,以提高性能,降低平均链上长度。

Leave a Reply

Your email address will not be published.