Python中的字典可以这样用:

mydict = {123:"a",2345:"b",50000:"c"}

print(mydict[123])
print(mydict[2345])
print(mydict[50000])

思考一下,如何使用数组实现同样的功能?

mylist = [None for i in range(50001)]
mylist[123] = "a"
mylist[2345] = "b"
mylist[50000] = "b"

print(mylist[123])
print(mylist[2345])
print(mylist[50000])

为了不改变键,我们必须要创建一个长度为50001的数组,如此大的数组我们仅存3个数据,真是大大的浪费资源.散列表就是为了这种情况而设计的。另外Python的字典就是通过散列表实现的——Python dictionary implementation.

直接寻址表

数组可以理解为直接寻址表,能在 $O(1)$ 时间内完成任意位置的查找.

直接寻址表特点很明显,关键字对应着数据存储的位置,这样知道关键字就知道数据的位置.

散列表

直接寻址表有明显的缺点,就是如果一个位置没有存储数据,也是要占用内存的,如果当 $T$ 表比较长的时候,在一台计算机上存储都不太可能,而且没有存储数据的部分会浪费大量的空间.

散列表不是以关键字作为存储位置,而是由关键字k通过函数h计算出存储位置.这样就可以用长度为 $m<U$ 的列表T存储数据,节省空间.

但这么做肯定会有冲突的情况,也就是说不通的关键字映射到同一个地址了.最简单的方法是把散列到同一个位置的数据放到一个链表中:

散列函数

除法散列函数

除法散列函数通过取k除以m的余数,将k映射到m个位置.

$h ( k ) = k \bmod m$

这很好理解, $h ( k )$ 会在0-m之间,这样就将U压缩到m长度.

乘法散列函数

乘法散列函数将k乘以常数A(0<A<1),然后取小数部分.

$h ( k ) = \lfloor m ( k A \bmod 1 ) \rfloor$

开放寻址法

链连接的方式需要用额外的空间来存储链表的指针,某种程度上也是一种浪费,开放寻址法方式不使用链表的形式,节省了存储指针的空间.

开放寻址法处理冲突的办法是,如果冲突就换一个位置,为此需要对哈希函数加一个尝试次数的参数.

比如说,我们现在要存键为k值为v的数据.使用哈希函数计算出存储位置:

h(k,1)

我们发现这个位置已经有数据了,也就是冲突了,这时将尝试次数加1,重新计算存储位置:

h(k,2)

如果还冲突,接着计算:

h(k,3)

直到找到空闲位置为止.

读取数据的时候,也是用同样的方式计算存储位置,当该位置的k与要读取的k不一致时,增加尝试次数,重新计算存储位置.

开放寻址法在删除数据的时候有些麻烦,因为将一个数据置为None,那么后面的数据就不能被检索到了,虽然有各种各样的删除办法,但是都比较麻烦.为此,在必须删除关键字的应用中,通常使用链连接的方式.

开放寻址法的散列函数有多种实现方式,其中最简单的就是线性探查:

$h ( k , i ) = \left( h ^ { \prime } ( k ) + i \right) \bmod m$

当第 $h ^ { \prime } ( k )$ 个槽发生冲突的时候,取检查下一个槽,即 $h ^ { \prime } ( k ) +1$ 个槽,但是这种方式存在一定的问题,即当连续占用的槽越来越多的时候,会出现集群效益,平均查找时间会增加.
二次探查对线性探查增加了一个二次函数,可以减小集群效益带来的影响: