8.2 静态散列

  • 在静态散列方法中,把标识符存储在一个固定大小的表中,该表称为 「散列表 hash table」
  • 使用一个函数 ff 确定标识符 xx 在散列表中的地址(或位置)。因此,f(x)f(x) 给出了 xx 在散列表中的散列地址(或标识地址)。散列表 htht 存放在一片连续的内存空间中,该空间被分割为 bb 个散列桶:ht[0],,ht[b1]ht[0], \cdots, ht[b-1]。每个散列桶包含有 ss 个槽,通常 s=1s = 1。标识符 xx 所有可能的取值共有 TT 个。
  • 「标识符密度 identifier density」 =n/T= n/T
  • 「装载密度 loading density」「装载因子 loading factor」 定义为 α=n/(sb)\alpha = n/(sb)
  • 由于散列表中的散列桶的数量 bb 通常比所有可能出现的标识符的数量 TT 小几个量级,所以散列函数 ff 就必定会将不同的标识符映射到相同的散列桶中。如果 f(i1)=f(i2)f(i_1) = f(i_2),则称标识符 i1i_1i2i_2 是关于 ff 的同义词。但是,当把一个新的标识符 ii 映射到一个已经满的散列桶(即没有空闲槽)中时,就会发生 「溢出 overflow」。把两个不同的标识符散列到同一个散列桶中的现象称为 「冲突 collision」。当散列桶的大小为 1 时,冲突和溢出同时发生。
  • 例如一散列表 htht,具有 b=26b = 26 个散列桶、每个散列桶有 s=2s = 2 个槽。现在有 n=10n = 10 个不同的标识符:acos, define, float, exp, char, atan, ceil, floor, clock, ctime。该散列表的装载因子是 α=10/52=0.19\alpha = 10/52 = 0.19。可以构造一个非常简单的散列函数:把字符 a ~ z 分别与这 26 个散列桶相对应,然后把散列函数 f(x)f(x) 定义为 xx 的首字符。那么这些标识符分别散列到散列桶 0, 3, 5, 4, 2, 0, 2, 5, 2, 2。如下表。当标识符 clock 散列到散列桶 ht[2]ht[2] 上时,由于这个散列桶已满,所以就会产生溢出。在散列表上插入、删除或查找一个标识符所需的时间复杂度为 O(1)O(1)
bb 槽 0 槽 1
0 acos atan
1
2 char ceil
3 define
4 exp
5 float floor
6
...
25
  • 在散列表中,任意的标识符 xx 可以等概率地散列到 bb 个散列桶上。称满足这种性质的散列函数为 「均匀分布散列函数 uniform hash function」。下面给出 4 种均匀分布散列函数,首先假定标识符已按适当的方式转换为等价的数字形式。
  • 「平均取中法 middle of square」 散列函数 fmf_m 的计算过程为:首先对标识符进行平方运算,然后从平方数的中间适当地选取若干二进制位数字作为标识符的散列桶地址。由于平方数的中间几位二进制数字通常与标识符中的所有字符有关,所以不同的标识符产生不同的散列地址的概率非常大,即使两个标识符部分字符相同,其散列地址也不同。用于表示散列桶地址的数字位数依赖散列表的大小。如果使用 rr 位二进制数字,那么得到的地址范围是 2r2^r。因此,当采用这种散列机制时,散列表的大小应该是 2 的幂。
  • 「质数余除法」 用标识符 xx 除以某个数 MM,其余数即为 xx 的散列地址。散列函数表示为 fD(x)=x%Mf_D(x) = x \% M。该散列函数给出的散列桶地址范围是 00M1M - 1,其中 MM 是散列表的大小。MM 的选取方法很关键。如果 MM 能被 2 整除,那么奇数关键字都将被映射到奇数地址的散列桶中,而偶数关键字都被映射到偶数地址的散列桶中。因此,如果 MM 是偶数,那么当大多数标识符为偶数(或奇数)时,就会使散列表出现不均衡的使用。 令 X=x1x2X = x_1x_2Y=x2x1Y = x_2x_1 是两个标识符,每个标识符都由字符 x1x_1x2x_2 组成。如果字符 x1x_1 的二进制表示为 C(x1)C(x_1),而字符 x2x_2 的二进制表示为 C(x2)C(x_2),且假定每个字符都用 6 位二进制表示,那么,XX 的值等于 26C(x1)+C(x2)2^6C(x_1) + C(x_2)。如果某素数 pp 可以整除 MM,则有: (fD(X)fD(Y))%p=(26C(x1)%p+C(x2)%p26C(x2)%pC(x1)%p)%p (f_D(X) - f_D(Y)) \% p = (2^6C(x_1)\%p + C(x_2)\%p - 2^6C(x_2)\%p - C(x_1)\%p)\%p 如果 p=3p = 3,则有: (fD(X)fD(Y))%p=0%3 (f_D(X) - f_D(Y)) \% p = 0 \% 3 也就是说,由相同字符集上的字符的不同排列,其散列地址的间隔为 3。于是,当很多标识符都是由相同字符组成(只是排列不同)时,就会出现散列表的不均衡使用。造成上述现象的原因是因为 26%3=64%3=12^6 \% 3 = 64 \% 3 = 1。相同的的情况也会出现在 7 可以整除 MM 时,因为此时也有 64%7=164 \% 7 = 1。因此,选择 MM 的较好方法是:MM 首先是一个素数,且对于小整数 kkaaMM 不能整除 rk±ar^k \pm a (rr 是字符集的基数,上例中 r=64r = 64)。经验表明:在实际应用中,可以选择满足上述条件且没有小于 20 的素因子的 MM
  • 「折叠法」 将标识符 xx 分割为若干个部分。各个部分(除了最后一个部分以外)都具有相同的长度。然后,把各个部分相加在一起就得到 xx 的散列地址。有两种相加方式:
    1. 「移位折叠 shift folding」 把除最后一个部分外的其余部分进行移位,使其最低有效位与最后一个部分的最低有效位对齐,然后把所有部分相加就得到 f(x)f(x)。例如:标识符 xx 分割成如下几个部分:x1=123,x2=203,x3=241,x4=112,x5=20x_1 = 123, x_2 = 203, x_3 = 241, x_4 = 112, x_5 = 20。将 x1,x2,x3,x4x_1, x_2, x_3, x_4x5x_5 对齐,相加就得到散列地址 699。
    2. 「分界折叠 folding at the boundaries」 在各部分相加之前,把其中的某些部分首尾翻转。例如将标识符 xx 的第二部分和第四部分首尾翻转,即 x2=302,x4=211x_2 = 302, x_4 = 211,再相加,得到散列地址 897。
  • 「数字分析法 digit analysis」 用于静态文件中。「静态文件 static file」 是指文件中的所有标识符都预先已知。数字分析法首先把所有标识符转换成某个基数 rr 下的数,然后检查所有标识符的数位,删除偏离分布最大的数位。重复上述删除过程,直至留下的数位个数不大于散列表地址范围。对于所有标识符,计算散列地址的数位必须都相同,而且不能出现异常的峰值或者谷值情况(即标准方差必须小)。

results matching ""

    No results matching ""