Fork me on GitHub

散列

背景

散列其实我们在开发的过程中经常遇到,比如iOS中NSDictionary其内部就是通过散列中分离链表来实现的。当我们自定义一个类的时候,实现-(BOOL)isEqual:方法的时候,同时也要实现- (unsigned int)hash方法,这些都是基于散列所要求的。

散列

散列表的实现叫作散列

散列函数

每个关键字被映射到从0到TableSize-1这个范围中的某个数,并且被放到适当的单元中。这个映射叫作散列函数

常用的散列函数:Key mod Tablesize(最好是素数)

散列过程中会出现冲突,常见的解决方法是:分离链表法和开放定址法

分离链表法

分离链表法是将散列到同一个值的所有元素保留到一个表中。

最近插入的元素最优可能不久被访问,所以会将新元素插入到链表的前端

除链表外,像二叉查找树或甚至另外一个散列表都将可以。但是,我们期望如果散列表是大的并且散列函数是好的,那么所有的链表都是短的,从而任何复杂的尝试都不值得考虑了

分离链表散列法一般法则是使得链表的大小与预料的元素个数大致相等

开放定址法

分离链表散列算法的缺点是使用一些链表。一般来说,不使用分离链表的散列表来说,其装填因子应该低于λ=0.5。我们把这样的表叫作探测散列表

名称 定义 缺点 备注
线性探测 函数f是i的线性函数,典型情形是f(i)=i 一次聚集 一次聚集即表即使相对较空,占据的单元也会形成一些区块,其结果称为一次聚集,也就是说,散列到区块中的任何关键字都需要多次试选单元才能够解决冲突,然后该关键字被添加到相应的区块中
平方探测法 冲突函数f(i)=i2 二次聚集,理论是小缺憾 虽然二次平方排出了一次聚集,但是散列到同一位置上的那些元素将探测相同的备选单元,这叫作二次聚集。平方探测是在线性探测的基础上,出现冲突时的一个解决方法
双散列 f(i)=i*hash2(x) hash2选择得不好将会是灾难性的。 将第二个散列函数应用到x并在距离hash2(x),2hash2(x)…等处探测。

再散列

使用平方探测的开放定址散列法,如果散列表填得太满,那么操作的运行时间将开始消耗过长,切插入操作可能失败。

再散列就是如果散列表过满的时候,建立另外一个大约两倍大的表(而且使用一个相关的新散列函数),扫描整个原始散列表,计算每个(未删除)元素的新散列值并将其插入到新表中。

再散列策略:

  • 只要表满到一半就再散列
  • 只有当插入失败时才散列
  • 途中策略:当散列表到达某一个装填因子时再进行散列。此策略可能是最好的。

完美散列

按照最原始的思路,每个二级散列表将用一个不同的散列函数进行构造,直到没有冲突为止。如果产生的冲突次数高于要求的值,主散列也可以被构建多次

名称 解释
布谷鸟散列 在布谷鸟散列中,假设有N个项,我们维护两个分别超过半空的表,且有两个独立的散列函数,可以把每个项分配到每个表中的一个位置。布谷鸟散列保持不变的是一个项总是被会被存储在这两个位置之一
跳房子散列 它尝试改进经典的线性探测算法
0%