数据结构与算法（18）词典

[TOC]

1.概述

1.1.词典

借助数据结构来表示和组织的数字信息，可将所有数据视作一个整体统筹处理，进而提高信息访问的规范性和其处理的效率。例如，借助关键码直接查找和访问数据元素的形式，已为越来越多的数据结构所采用，这也成为现代数据结构的一个重要特征。词典（dictionary）即是其中最典型的例子。

逻辑上的词典是由一组数据构成的集合，其中各元素都是由关键码和数据项合成的词条（entry）。映射（map）结构与词典结构一样，也是词条的集合。二者的差别仅仅在于，映射要求不同词条的关键码互异，而词典则允许多个词条拥有相同的关键码。除了静态查找，映射和词典都支持动态更新，二者统称作符号表（symbol table）。本章将不再过分强调二者的差异，而是笼统地称作词典。

尽管此处词典和映射中的数据元素，仍表示和实现为词条形式，但这一做法并非必须。与搜索树相比，符号表并不要求词条之间能够根据关键码比较大小，甚至也不需要按照大小次序来组织数据项——即便各数据项之间的确定义有某种次序。

实际上，以散列表为代表的符号表结构，将转而依据数据项的数值，直接做逻辑查找和物理定位。对于此类结构，在作为基本数据单位的词条内部，关键码（key）与数值（value）的地位等同，二者不必加以区分。此类结构所支持的这种新的数据访问方式，即所谓的循值访问（call-by-value）。

为支持循值访问的方式，在符号表的内部，仍然必须强制地在数据对象的数值与其物理地址之间建立某种关联。而散列，正是在兼顾空间与时间效率的前提下，讨论和研究赖以设计并实现这种关联的一般性原则、技巧与方法。

1.2.词典ADT

1.2.1.操作接口

除通用的接口之外，词典结构主要的操作接口可归纳为下表：get(key)

操作接口	功能描述
get(key)	若词典中存在以key为关键码的词条，则返回该词条的数据对象；否则，返回NULL
put(key,value)	插入词条(key, value)，并报告是否成功
remove(key)	若词典中存在以key为关键码的词条，则删除之并返回true；否则，返回false

1.2.2.接口定义

首先以如下代码所示模板类的形式定义词典的操作接口。

template <typename K, typename V> struct Dictionary { //词典Dictionary模板类
   virtual int size() const = 0; //当前词条总数
   virtual bool put ( K, V ) = 0; //插入词条（禁止雷同词条时可能失败）
   virtual V* get ( K k ) = 0; //读取词条
   virtual bool remove ( K k ) = 0; //删除词条
};

其中，所有的操作接口均以虚函数形式给出，留待在派生类中予以具体实现。另外，尽管词条关键码类型可能支持大小比较，但这并非词典结构的必要条件，Dictionary模板类中的Entry类只需支持判断等操作。

2.散列

散列以最基本的向量作为底层支撑结构，通过适当的散列函数在词条的关键码与向量单元的秩之间建立起映射关系。只要散列表、散列函数以及冲突排解策略设计得当，散列技术可在期望的常数时间内实现词典的所有接口操作。即就平均时间复杂度的意义而言，可以使这些操作所需的运行时间与词典的规模基本无关。尤为重要的是，散列技术完全摒弃了“关键码有序”的先决条件，故就实现词典结构而言，散列所特有的通用型和灵活性是其他方式无法比拟的。

2.1.散列表

散列表（hashtable）是散列方法的底层基础，逻辑上由一系列可存放词条（或其引用）的单元组成，故这些单元也称作桶（bucket）或桶单元，各桶单元也应按其逻辑次序在物理上连续排列。因此这种线性的底层结构用向量来实现再自然不过；为简化实现并进一步提高效率，往往直接使用数组，此时的散列表亦称作桶数组（bucket array）。若桶数组的容量为R，则其中合法秩的区间[0, R)也称作地址空间（address space）。

一组词条在散列表内部的具体分布，取决于所谓的散列（hashing）方案——事先在词条与桶地址之间约定的某种映射关系，可描述为从关键码空间到桶数组地址空间的函数：

$$hash():key \to hash(key)$$

这里的hash( )称作散列函数（hash function），反过来，hash(key)也称作key的散列地址（hashing address），亦即与关键码key相对应的桶在散列表中的秩。

完美散列（perfect hashing）：在时间和空间性能方面均达到最优的散列，可在$O(1)$时间内确定散列地址，并完成一次查找、插入或删除；空间性能方面，每个桶恰好存放一个词条，即无空余亦无重复。而完美散列实际上并不常见，在更多的应用环境中，为兼顾空间和时间的效率，无论散列表或散列函数都需要经过更为精心的设计。

在实际应用中往往会遇到一类问题，其共同的特点可归纳为：尽管词典中实际需要保存的词条数N（比如25000）远远小于可能出现的词条数R（如10^8），但R个词条中的任何一个都有可能出现在词典中。仿照对向量空间利用率的度量方法，可以将散列表中非空桶的数目与桶单元总数的比值称作装填因子（load factor）：$\lambda=N/M=$ 存放的词条 / |桶数组|

2.2.散列函数

不妨先假定关键码均为[0, R)范围内的整数，将词典中的词条数记作N，散列表长度记作M，于是通常有：$R>>M>N$，如下图所示，散列函数hash( )的作用可理解为：将关键码空间[0, R)压缩为散列地址空间[0, M)。

好的散列函数hash( )应具备以下的条件：

• 确定性，无论所含的数据项如何，词条E在散列表中的映射地址hash(E.key)必须完全取决于其关键码E.key；
• 映射过程自身不能过于复杂，唯此方能保证散列地址的计算可快速完成，从而保证查询或修改操作整体的$O(1)$期望执行时间；
• 所有关键码经映射后应尽量覆盖整个地址空间[0, M)，唯此方可充分利用有限的散列表空间，即函数hash()最好是满射。

因定义域规模R远大于取值域规模M，hash()不可能是单射。这就意味着关键码不同的词条被映射到同一散列地址的情况——散列冲突（collision），难以彻底避免。

最为重要的一条原则就是，关键码映射到各桶的概率应尽量接近于1/M——若关键码均匀且独立地随机分布，这也是任意一对关键码相互冲突的概率。就整体而言，这等效于将关键码空间“均匀地”映射到散列地址空间，从而避免导致极端低效的情况。

总之，随机越强、规律性越弱的散列函数越好，当然完全符合上述条件的散列函数并不存在，我们只能通过先验地消除可能导致关键码分布不均匀的因素，最大限度地模拟理想的随机函数，尽最大可能降低发生冲突的概率。

2.2.1.除余法

符合上述要求的一种最简单的映射方法，就是将散列表长度M取作素数，并将关键码key映射到key关于M整除的余数：

$$hash(key)=key \,\,\,mod\,\,\,M$$

以校园电话簿为例，若取M = 90001，如下图所示。

需要注意的是，采用除余法时，M必须选为素数，否则关键码被映射至[0, M)范围内的均匀度将大幅降低，发生冲突的概率将随M所含素因子的增多而迅速加大。

在实际应用中，对统一词典内词条的访问往往具有某种周期性，若其周期与M具有公共的素因子，则冲突的概率将急剧增加。考虑一个例子：某散列表从全空的初始状态开始，插入的前10个词条对应的关键码是等价数列$\{1000,1015,1030,\dots,1135\}$。

如图(a)，若散列表长度取作M = 20，则其中每一关键码，都与另外一个或两个关键码相冲突；而反过来，散列表中80%的桶，此时却处于空闲状态。词条集中到散列表内少数若干桶中（或附近）的现象，称作词条的聚集（clustering）。显然好的散列函数应尽可能避免此类现象，而采用素数表长则是降低聚集发生概率的捷径。

一般地，散列表的长度M与词条关键码间隔T之间的最大公约数越大，发生冲突的可能性也讲越大。因此，若M取素数，则简便对于严格或大致等间隔的关键码序列，也不致出现冲突激增的情况，同时提高空间效率。如图(b)改用表长M = 19，则没有任何冲突，且空间利用率提高至50%以上；再如图(c)，取表长M = 11，则同样不致发生任何冲突，且仅有一个桶空闲。

若T本身足够大而且恰好可被M整除，则所有被访问词条都将相互冲突。如图(d)将表长取为素数M = 5，且只考虑插入序列中的前5个关键码，则所有关键码都将聚集于一个桶内，但实际中发生这种情况的概率极低。

除余法的缺陷：

以素数为表长的除余法尽管可在一定程度上保证词条的均匀分布，但从关键码空间到散列地址空间映射的角度看，依然残留有某种连续性。比如，相邻关键码所对应的散列地址，总是彼此相邻，称为零阶均匀；极小的关键码，通常都被集中映射到散列表的起始区段——其中，特别地，0值居然是一个“不动点”，其散列表地址总是0，而与散列表长度无关。

2.2.2.MAD法

为了弥补除余法的不足，可采用MAD法（multiply-add-divide method），它将关键码key映射为：

$$(a \times key +b)\,\,\,mod\,\,\,M$$

其中，M仍为素数，$a>0,b>0$，且$a\,\,\,mod\,\,\,M \ne 0$

尽管运算量略有增加，但只要常数a和b选取得当，MAD法可以很好地克服除余法原有的连续性缺陷。

如上图，若采用除余法，将关键码$\{2011,2012,2013,2014,2015,2016\}$插入长度为M = 17的空散列表后，这组词条将存放至地址连续的6个桶中，尽管没有任何关键码的冲突，却可以改善为“更高阶”的均匀性。若采用MAD法，当选取a = 31和b = 2时，各关键码的均匀性相对于图(a)有了很大改善。

2.2.3.更多的散列函数

除了上面介绍的两种散列函数，还有很多种形式的散列函数。

2.3.Hashtable模板类

按照词典的标准接口，可以模板类的形式，定义Hashtable类，实现如下。

#include "Dictionary/Dictionary.h" //引入词典ADT
#include "Bitmap/Bitmap.h" //引入位图

template <typename K, typename V> //key、value
class Hashtable : public Dictionary<K, V> { //符合Dictionary接口的Hashtable模板类
   /*DSA*/friend class UniPrint;
private:
   Entry<K, V>** ht; //桶数组，存放词条指针
   int M; //桶数组容量
   int N; //词条数量
   Bitmap* lazyRemoval; //懒惰删除标记
#define lazilyRemoved(x)  (lazyRemoval->test(x))
#define markAsRemoved(x)  (lazyRemoval->set(x))
protected:
   int probe4Hit ( const K& k ); //沿关键码k对应的查找链，找到词条匹配的桶
   int probe4Free ( const K& k ); //沿关键码k对应的查找链，找到首个可用空桶
   void rehash(); //重散列算法：扩充桶数组，保证装填因子在警戒线以下
public:
   Hashtable ( int c = 5 ); //创建一个容量不小于c的散列表（为测试暂时选用较小的默认值）
   ~Hashtable(); //释放桶数组及其中各（非空）元素所指向的词条
   int size() const { return N; } // 当前的词条数目
   bool put ( K, V ); //插入（禁止雷同词条，故可能失败）
   V* get ( K k ); //读取
   bool remove ( K k ); //删除
};

散列表构造

template <typename K, typename V> Hashtable<K, V>::Hashtable ( int c ) { //创建散列表，容量为
   M = primeNLT ( c, 1048576, "../../_input/prime-1048576-bitmap.txt" ); //不小于c的素数M
   N = 0; ht = new Entry<K, V>*[M]; //开辟桶数组（还需核对申请成功），初始装填因子为N/M = 0%
   memset ( ht, 0, sizeof ( Entry<K, V>* ) *M ); //初始化各桶
   lazyRemoval = new Bitmap ( M ); //懒惰删除标记比特图
   //*DSA*/printf("A bucket array has been created with capacity = %d\n\n", M);
}

int primeNLT(int c, int n, char* file){ //根据file文件中的记录，在[c, n)内取最小的素数
    Bitmap B( file n);  //file 已经按位图格式，记录了n以内的所有素数，因此只要
    while( c < n)       //从c开始，逐位地
        if( B.test( c ) ) c++;   //测试，即可
        else return c;  //返回首个发现的素数
    return c;           //若没有这样的素数，返回n(实用中不能如此简化处理)
}

为了加速素数的选取，事先计算出不超过1049576的所有素数，并存放于文件中备查。于是在创建散列表（或重散列）时，对于在此范围内任意给定的长度下限c，都可通过调用primeNLT()，迅速地从该查询表中找到不小于c的最小素数M作为散列表长度，并依次为新的散列表申请相应数量的空调；同时创建一个同样长度的位图结构，作为懒惰删除标志表。

primeNLT()从长度下限c开始，逐个测试对应的标志位，直到第一个足够大的素数。

散列表析构

template <typename K, typename V> Hashtable<K, V>::~Hashtable() { //析构前释放桶数组及非空词条
   for ( int i = 0; i < M; i++ ) //逐一检查各桶
      if ( ht[i] ) release ( ht[i] ); //释放非空的桶
   release ( ht ); //释放桶数组
   release ( lazyRemoval ); //释放懒惰删除标记
} //release()负责释放复杂结构，与算法无直接关系，具体实现详见代码包

在销毁散列表之前，需在逐一释放各桶中的词条（如果存在）之后，释放整个散列表ht[]以及对应的懒惰删除表lazyRemoval[]。

3.排解冲突

散列表的基本构思，可以概括为：

• 开辟物理地址连续的桶数组ht[]，借助散列函数hash()，将词条关键码key映射；
• 为桶地址hash(key)，从而快速地确定待操作词条的物理位置

然而遗憾的是，无论散列函数设计得如何巧妙，也不可能保证不同的关键码之间互不冲突。比如课堂中的学生，发生生日（birthday）相同的概率，将全年各天视作365个桶，将学生视作词条，只要学生人数$n\ge23$，则至少发生一次冲突的概率$P_{365}(n)\ge 50\%$，而此时的装填因子仅为$\lambda=23/365=6.3\%$。对于更长的散列表，只需更低的装填因子，即友50%概率会发生一次冲突。因此冲突具有普遍性。

3.1.开放散列

3.1.1.多槽位法（multiple slots）

最直接了当的一种对策是，将彼此冲突的每一组词条组织为一个小规模的子词典，分别存放于它们共同对应的桶单元中。比如一种简便的方法是，统一将各桶细分为更小的称作槽位（slot）的若干单元，每一组槽位可组织为向量或列表。

如对于下图的冲突散列，可将各桶细分为四个槽位，只要相互冲突的各组关键码不超过4个，即可分别保存与对应桶单元内的不同槽位。

按照这一思路，针对关键码key的任一操作都将转化为对一组槽位的操作。比如put(key,value)操作，将首先通过hash(key)定位对应的桶单元，并在其内部的一组槽位内，进一步查找key。若失败，则创建新词条(key, value)，并将其插至该桶单元内的空闲槽位中。get(key)和remove(key)操作的过程与此类似。

多槽位的缺陷也显而易见：

• 绝大多数的槽位通常都处于空闲状态，若每个桶被细分为k个槽位，则当散列表总共存有N个词条时，装填因子：$\lambda’=N/(kM)=\lambda/k$ 将降低至原先的$1/k$。
• 很难在事先确定槽位应细分到何种程度，方可保证在任何情况下都够用。比如在极端情况下，有可能所有（或接近所有）的词条都冲突与单个桶单元，此时尽管几乎其余所有的桶都处于空闲状态，该桶却会因冲突过多而溢出。

3.1.2.独立链法（separate chaining）

独立链法与多槽位法类似，也令相互冲突的每组词条构成小规模的子词典，只不过采用列表来实现各子词典，令各桶内相互冲突的词条串接成一个列表。

既然好的散列函数已能保证通常不致发生极端的冲突，故个子词典的规模往往都不是很大，大多数往往只含单个词条或者甚至是空的，因此采用此前学过的基本列表结构足矣。

优点：

• 相对于多槽位法，独立链法可更为灵活地动态调整各子词典的容量和规模，从而有效地降低空间消耗。

缺陷：

• 指针需要额外空间，节点需要动态申请。
• 在查找过程中一旦发生冲突，则需要遍历整个序列，导致查找成本的增加。

3.1.3.公共溢出区法（overflow area）

公共溢出区法是在原散列表之外另设一个词典结构$D_{overflow}$，一旦在插入词条时发生冲突就将该词条转存至$D_{overflow}$。就效果而言，$D_{overflow}$相当于一个存放冲突词条的公共缓冲池，就整体而言，此时的散列表也可理解为是一种递归形式的散列表。

尽管就逻辑结构而言，独立链等策略便捷而紧凑，但也有缺点。比如因需要引如次级关联结构，实现相关算法的代码自身的复杂程度和出错概率都将大大增加。反过来，因不能保证物理上的关联性，对于稍大规模的词条集，查找过程中将需做更多的I/O操作。

3.2.封闭散列

实际上，仅仅靠基本的散列结构，且就地排解冲突，反而是更好的选择。即若新词条与已有词条冲突，则只允许在散列表内部为其寻找另一空桶。如此，各桶并非注定只能存放特定的一组词条，从理论上讲每个桶单元都有可能存放任一词条。因为散列地址空间对所有词条开放，故这一新的策略亦称作开放定址（open addressing）；同时因可用的散列地址仅限于散列表所覆盖的范围之内，故亦称闭散列（closed hashing）。因不得使用附件空间，故装填因子需要适当降低，通常都取$\lambda \le 0.5$。

3.2.1.线性试探法（linear probing）

开放定址策略最基本的一种形式是：在插入关键码key时，若发现桶单元ht[hash(key)]已被占用，则转而试探桶单元ht[hash(key)+1]；若ht[hash(key)+1]也被占用，则继续试探ht[hash(key)+2]，如此不断直到发现一个可用空桶。为确保桶地址的合法，最后还需统一对M取模，第i次试验的桶单元应为：

$$ht[(hash(key)+i)\,\,\,mod\,\,\,M],\,\,\,i=1,2,3,\dots$$

如此被试探的桶单元在物理空间上一次连贯，其地址构成等差数列

查找链

采用开放地址策略时，散列表中每一组相互冲突的词条都将被视作一个有序序列，对其中任何一员的查找都需要借助这一序列，该序列被称作查找链（probing chain）。对应的查找过程，可能终止于三种情况：

• 在当前桶单元命中目标关键码，则成功返回；
• 当前桶单元非空，则其中关键码与目标关键码不等，则须转入下一桶单元继续试探；
• 当前桶单元为空，则查找以失败返回。

如下图，长度为M = 17的散列表，设采用除余法定址，采用线性试探排解冲突。如图(a)，从开表开始依次插入5个相互冲突的关键码$\{2011,2028.2045.2062.2079\}$。此后针对其中任一关键码的查找都将从ht[hash(key)] = ht[5]出发，试探各相邻的桶单元，与这组关键码对应的桶单元ht[5,10)构成一个有序序列，对其中任一关键码的查找都将沿该序列顺序进行。

对应长度为n的查找链，失败查找长度就是n+1，在等概率假设下，平均成功查找长度为$\lceil n/2 \rceil$。需要注意的是，尽管相互冲突的关键码必属于同一查找链，但反过来，同一查找链中的关键码却未必相互冲突。如将上图中的(a)和(b)合并，并按从大到小的次序逐一插入空散列表如图(c)，对于2079或2082关键码而言，查找链中的关键码未必与它们冲突。原因在于，多组各自冲突的关键码所对应的查找链，有可能相互交织和重叠，此时各组关键码的查找长度将会进一步增加。

由上可见，线性试探法中组成各查找链的词条，在物理上保持一定的连贯性，具有良好的数据局部性，故系统缓存的作用可以充分发挥，查找过程中几乎无需I/O操作。尽管闭散列策略同时也会在一定程度上增加冲突发生的可能，但只要散列表的规模不是很小，装填因子不是很大，则相对于于I/O负担的降低而言，这些问题都将微不足道。因此，相对于独立链等开散列策略，闭散列策略的实际应用更为广泛。

3.2.2.懒惰删除

查找链中任何一环的缺失，都会导致后续词条因无法抵达而丢失，表现为有时无法找到实际已存在的词条。因此若采用开放定址策略，则在执行删除操作时，需同时做特别的调整。

如下图，若为删除词条ht[9]=2031，按常规方法将其清空，则该桶的缺失将导致对应的查找链“断裂”，从而致使五个后续词条“丢失”——尽管它们在词典中的确存在，但查找却会失败。

一种简明而有效的方法是：为每个桶另设一个标志位，指示该桶尽管目前为空，但此前确曾存放过词条。在Hashtable模板类中，名为lazyRemoval的Bitmap对象正是起到了这一作用。删除词条时，只需将对应的桶ht[r]标志位lazilyRemoved(r)，如此该桶虽不存放任何实质的词条，却依然是查找链上的一环。

带有删除标记的桶所扮演的角色，因具体的操作类型而异：

• 查找词条时，被视作“ 必不匹配的非空桶 “，查找链在此得以延续；
• 插入词条时，被视作“ 必然匹配的空闲桶 ”，可以用来存放新词条。

因此采用“ 懒惰删除 ”策略之后，get()，put()和remove() 等操作中的查找算法，都需要做相应的调整。

词条查找接口get()的实现：

template <typename K, typename V> V* Hashtable<K, V>::get ( K k ) //散列表词条查找算法
{  int r = probe4Hit ( k ); return ht[r] ? & ( ht[r]->value ) : NULL;  } //禁止词条的key值雷同

/****************************************************************************
 * 沿关键码k对应的查找链，找到与之匹配的桶（供查找和删除词条时调用）
 * 试探策略多种多样，可灵活选取；这里仅以线性试探策略为例
 ***************************************************************************/
template <typename K, typename V> int Hashtable<K, V>::probe4Hit ( const K& k ) {
   int r = hashCode ( k ) % M; //从起始桶（按除余法确定）出发
   //*DSA*/printf(" ->%d", r);
   while ( ( ht[r] && ( k != ht[r]->key ) ) || ( !ht[r] && lazilyRemoved ( r ) ) )
      r = ( r + 1 ) % M; //沿查找链线性试探：跳过所有冲突的桶，以及带懒惰删除标记的桶
   //*DSA*/printf(" ->%d", r);
   //*DSA*/printf("\n");
   return r; //调用者根据ht[r]是否为空，即可判断查找是否成功
}

/****************************************************************************
 * 沿关键码k对应的查找链，找到首个可用空桶（仅供插入词条时调用）
 * 试探策略多种多样，可灵活选取；这里仅以线性试探策略为例
 ***************************************************************************/
template <typename K, typename V> int Hashtable<K, V>::probe4Free ( const K& k ) {
   int r = hashCode ( k ) % M; //从起始桶（按除余法确定）出发
   //*DSA*/printf(" ->%d", r); //首个试探的桶单元地址
   while ( ht[r] ) r = ( r + 1 ) % M; //沿查找链逐桶试探，直到首个空桶（无论是否带有懒惰删除标记）
//*DSA*/   while (ht[r]) { r = (r+1) % M; printf(" ->%d", r); } printf("\n");
   return r; //为保证空桶总能找到，装填因子及散列表长需要合理设置
}

首先采用除余法确定首个试探的桶单元，然后按线性试探法沿查找链逐桶试探。这里共有两只试探终止的可能：在一个非空的桶内找到目标关键码（成功），或者遇到一个不带懒惰删除标记的空桶（失败）。否则，无论是当前桶中词条的关键码与目标码不等，还是当前桶为空但带有懒惰删除标记，都意味着有必要沿着查找链前进一步继续查找，该算法同一返回最后被试探桶的秩，上层调用者只需核对该桶是否为空，即可判断查找是否失败。

词条删除接口remove()的实现如下：

template <typename K, typename V> bool Hashtable<K, V>::remove ( K k ) { //散列表词条删除算法
   int r = probe4Hit ( k ); if ( !ht[r] ) return false; //对应词条不存在时，无法删除
   release ( ht[r] ); ht[r] = NULL; markAsRemoved ( r ); N--; return true;
   //否则释放桶中词条，设置懒惰删除标记，并更新词条总数
}

这里首先调用probe4Hit(k)算法，沿关键码k对应的查找链顺序查找。若在某桶单元命中，则释放其中的词条，为该桶单元设置懒惰删除标记，并更新词典的规模。

词条插入接口put()的实现如下：

template <typename K, typename V> bool Hashtable<K, V>::put ( K k, V v ) { //散列表词条插入
   if ( ht[probe4Hit ( k ) ] ) return false; //雷同元素不必重复插入
   int r = probe4Free ( k ); //为新词条找个空桶（只要装填因子控制得当，必然成功）
   ht[r] = new Entry<K, V> ( k, v ); ++N; //插入（注意：懒惰删除标记无需复位）
   if ( N * 2 > M ) rehash(); //装填因子高于50%后重散列
   return true;
}

调用一下probe4Free(k)算法，若沿关键码k所属查找链能找到一个空桶，则在其中创建对应的词条，并更新词典的规模。

3.2.3.重散列（rehashing）

就对散列表性能及效率的影响而言，装填因子$\lambda=N/M$是最为重要的一个因素，随着$\lambda$的上升，词条在散列表中聚集的程度亦将迅速加剧。若同时还采用基本的懒惰删除法，则不带懒惰删除标记的桶单元必将持续减少，这也势必加剧查找成本的进一步增多。理论分析和实验统计均表明，只要能将装填因子$\lambda$控制在适当范围内，闭散列策略的平均效率，通常都可保持在较为理想的水平，比如一般的建议是保持$\lambda<0.5$。

重散列是常用的一种将装填因子控制在一定范围以内的方法，其实现如下：

/****************************************************************************
 * 重散列算法：装填因子过大时，采取“逐一取出再插入”的朴素策略，对桶数组扩容
 * 因散列函数的定址与表长M直接相关，既然M已改变，就不可简单地批量复制原桶数组
 ***************************************************************************/
template <typename K, typename V> void Hashtable<K, V>::rehash() {
   int old_capacity = M; Entry<K, V>** old_ht = ht;
   M = primeNLT ( 2 * M, 1048576, "../../_input/prime-1048576-bitmap.txt" ); //容量至少加倍
   N = 0; ht = new Entry<K, V>*[M]; memset ( ht, 0, sizeof ( Entry<K, V>* ) * M ); //新桶数组
   release ( lazyRemoval ); lazyRemoval = new Bitmap ( M ); //新开懒惰删除标记比特图
   //*DSA*/printf("A bucket array has been created with capacity = %d\n\n", M);
   for ( int i = 0; i < old_capacity; i++ ) //扫描原桶数组
      if ( old_ht[i] ) //将非空桶中的词条逐一
         put ( old_ht[i]->key, old_ht[i]->value ); //插入至新的桶数组
   release ( old_ht ); //释放原桶数组——由于其中原先存放的词条均已转移，故只需释放桶数组本身
}

重散列的效果，只不过是将原词条集，整体“搬迁”至容量至少加倍的新散列表中。与可扩充向量同理，这一策略也可使重散列所耗费的时间，在分摊至各次操作后可以忽略不计。

3.2.4.平方试探法（quadratic probing）

线性试探法虽然简明紧凑，但各查找链均由物理地址连续的桶单元组成，因而会加剧关键码的聚集趋势。如下图，采用除余法将7个关键码$\{2011,2012,2013,2014,2015,2016,2017\}$依次插入长度M = 17的散列表，则会形成聚集区段ht[5, 12)。接下来若想插入关键码3456和4000，由hash(3456) = hash(4000) = hash(2011) = 5，二者的试探都将起始于桶单元ht[5]，分别经过8次和9次试探，它们将被插入聚集区段右侧的位置，形成更长的聚集区段。如果再考虑到聚集区段的生长还会加剧不同聚集区段之间的相互交叠，查找操作平均的下降程度将会更加严重。

采用2.2.2节的MAD法，可在一定程度上减缓上述聚集现象。而平方试探法则是一种更为有效的方法。具体地，在试探过程中若连续发生冲突，则按如下规则确定第i次试探的桶地址：

$$(hash(key)+j^2)\,\,\,mod\,\,\,M,\,\,\,j=0,1,2,\dots$$

各次试探的位置起始位置的距离，以平方速率增长。如上图(c)，为插入3456，将依次试探秩为5、6、9、14的桶单元，插入ht[14]；为插入4000，将依次试探秩为5、6、9、14、21 $\equiv$ 4的桶单元，并最终将其插入ht[4]。

可见，聚集区段并未扩大，同时针对这两个关键码的后续查找，也分别只需3次和4次试探，速度得以提高至两倍以上。平试探之所以能够有效地缓解聚集现象，是因为充分利用了平方函数的特点——顺着查找链，试探位置的间距将以线性（而不再是常数1的）速度增长。于是一旦发生冲突，即可“ 尽快逃离 ”关键码聚集的区段。

要注意的是：装填因子须足够小。只要散列表长度M为素数且装填因子$\lambda\le50\%$，则平方试探迟早必将终止于某个空桶。

双向平方试探法

正向和逆向的子查找链，各包含$\lceil M/2 \rceil$个互异的桶。表长取作素数 $M=4\times k+3$，必然可以保证查找链的前M项均互异。

再散列法（double hashing）

再散列也是延缓词条聚集趋势的一种有效方法，需选取一个适宜的二级散列函数：

若取$hash_2(key)=1$即是线性试探。

3.3.散列码转换

为扩大散列技术的适用范围，散列函数hash()必须能够将任意类型的关键码key映射为地址空间[0, M)内的一个整数hash(key)，以便确定key所对应的散列地址。由关键码到散列地址的映射，可分解为两步：

• 利用某一种散列码转换函数hashCode()，将关键码key统一转换为一个整数——称作散列码（hash code）
• 再利用散列函数将散列码映射为散列地址。

散列码转换函数hashCode()应具备以下的条件：

• 取值范围应覆盖系统所支持的最大整数范围；
• 各关键码经hashCode()映射后得到的散列码，相互之间的冲突也应可能减少；
• hashCode()也应与判等器保持一致，即被判等器判定为相等的词条，对应的散列吗应该相等。

强制转换为整数

对于byte、short、int和char等本身即可表示为不超过32位整数的数据类型，可通过类型强制将它们转化为32位的整数。

对成员对象求和

long long和double之类长度超过32位的基本类型，不宜强制转换为整数。可以将高32位和低32位分别看作两个32位整数，将二者之和作为散列码。这一方法可推广至由任意多个整数构成的组合对象，如可将其成员对象各自对应的整数累加起来，再截取低32位作为散列码。

多项式散列码

与一般的组合对象不同，字符串内各字符之间的次序具有特定含义，故在做散列码转换时，务必考虑它们之间的次序。为计入各字符的出现次序，可取常数$a\ge2$，并将字符串$x_0x_1\dots x_{n-1}$的散列码取作：

$$x_0a^{n-1}+x_1a^{n-2}+\dots x_{n-2}a^{1}+x_{n-1}$$

这一转换等效于，依次将字符串中的各个字符，视作一个多项式的各项系数，故亦称作多项式散列码（polynomial hash code）。其中的常数a非常关键，为尽可能多地保留原字符串的信息以减少冲突，其低比特位不得全为0。另外，针对不同类型的字符串，应通过实验确定a的最佳取值，如对于英语单词之类的字符串，a = 33、37、39或41都是不错的选择。

利用重载机制，实现散列码的统一转换方法hashCode()。

static size_t hashCode ( char c ) { return ( size_t ) c; } //字符
static size_t hashCode ( int k ) { return ( size_t ) k; } //整数以及长长整数
static size_t hashCode ( long long i ) { return ( size_t ) ( ( i >> 32 ) + ( int ) i ); }
static size_t hashCode ( char s[] ) { //生成字符串的循环移位散列码（cyclic shift hash code）
   unsigned int h = 0; //散列码
   for ( size_t n = strlen ( s ), i = 0; i < n; i++ ) //自左向右，逐个处理每一字符
      { h = ( h << 5 ) | ( h >> 27 ); h += ( int ) s[i]; } //散列码循环左移5位，再累加当前字符
   return ( size_t ) h; //如此所得的散列码，实际上可理解为近似的“多项式散列码”
} //对于英语单词，"循环左移5位"是实验统计得出的最佳值

4.散列应用

4.1.桶/计数排序

给定[0, M)内的n个互异整数（$n\le M$），如何高效地对其排序？自然，此前学过的向量排序器或列表排序器中的任一排算法，均可完成这一任务，但CBA式排序算法注定在最坏情况下需要$\Omega(n \log n)$时间。实际上，针对数值类型和取值范围特定的这一具体问题，完全可在更短时间内完成排序。

简单情况

为此，引入长度为M的散列表，如下图为M = 10和n = 5的一个实例。可使用最简单的散列函数hash(key) = key，将这些整数视作关键码并逐一插入散列表中。然后顺序遍历一趟该散列表，依次输出非空桶中存放的关键码，即可得到原整数集合的排序结果。该算法借助一组桶单元实现对一组关键码的分拣，故称作桶排序（bucketsort）。

该算法所用散列表共占$O(M)$空间，散列表的创建和初始化耗时$O(M)$，将所有关键码插入散列表耗时$O(n)$，依次读出非空桶中的关键码耗时$O(M)$，故总体运行时间为$O(n+M)$。

一般情况

若将上述问题进一步推广：若允许输入整数重复，又改如何高效地实现排序？

依然可以沿用以上构思，只不过这次需要处理散列冲突。如上图用过独立链法排解冲突，在将所有整数作为关键码插入散列表之后，只需一趟顺序遍历将各非空桶中的独立链依次串接起来即可得到完整的排序结果。而且只要在串联时留意链表方向，甚至可以确保排序结果的稳定，故如此实现的桶排序算法属于稳定算法。

推广之后的桶排序算法，总体运行时间依然为$O(n+M)$。其实这一问题十分常见，它涵盖了众多实际应用中的具体需求，这类问题还具有一个特点：$n\gg M$。

在$n\gg M$的场合，桶排序算法的运行时间将是：$O(n+M)=O(\max(n,M))=O(n)$，线性正比与于待排序元素的数目，突破了$\Omega(n \log n)$的下界。这是因为，以上基于散列表的桶排序算法，采用的是循秩访问的方式，摒弃了以往基于关键码大小比较式的设计思路，故不在受到CBA式算法固有的下界约束。正因为此，桶排序在算法设计方面也占有其独特的地位。

桶排序例子：最大间隙

问题：任意n个互异点均将实轴分为n-1段有界区间，其中哪一段最长？

平凡算法：

• 对所有点排序，最坏情况下$\Omega(n \log n)$；
• 依次计算各相邻点对的间距，保留最大者，$\Theta(n)$。

利用散列：

• 通过一趟顺序扫描找到最靠左和最靠右的点，将其坐标分别记作lo和hi；

• 建立一个长度为n的散列表，并使用散列函数 $hash(x)=\lfloor (n-1)*(x-lo)/(hi-lo)\rfloor$，讲各点分别插入对应的桶单元，其中x为各点的坐标值，hash(x)为对应的桶编号；

• 对散列表做一趟遍历，在每个非空桶（黑色）内部确定最靠左和最靠右的点，并删除所有的空桶（白色）；
• 再顺序扫描一趟散列表，即可确定相邻非空桶之间的间隙，记录并报告其中的最大者，即为全局的最大间隙。

正确性：

MaxGap至少与相邻的两个桶相交，等价地，定义MaxGap的点不可能属于同一个桶，既有maxGap $\ge$ w = ( hi - lo ) /( n - 1)。这就意味着MaxGap的两个端点绝不可能落在同一个桶单元内，进一步地，它们必然来自两个不同的非空桶，且左端点在前一非空桶的应该最靠右，右端点在后一非空桶中应该最靠左——故在散列过程中只需记录各桶中的最左、最右点。

复杂度：

空间上，除了输入本身这里只需维护一个散列表，共占用$O(n)$的辅助空间。

无论是生成散列表、找出各桶最左和最右点，还是计算相邻非空桶之间的间距，并找出其中的最大者，该算法的每一步均耗时$O(n)$。故即便在最坏情况下，累计运行时间也不超过$O(n)$。

4.2.基数排序

实际应用环境中词条的关键码，未必都是整数。比如，一种常见的情形是，关键码由多个域（字段）组合而成，并采用所谓的字典序（lexicographical order）确定大小次序：任意两个关键码之间的大小关系，取决于它们第一个互异的域。

如日期型关键码，可分解为year、month和day三个整数字段，并按常规惯例，以“ 年 - 月 - 日 ”的优先级定义字典序。有时同一关键码内各字段的类型也未必一致，如扑克牌所对应的关键码，可以分解为枚举型的suite（花色）和整型的number（点数），若按桥牌的约定，以“ 花色 - 点数 ”为字典序，则每副牌都可按大小排列为：

不妨假定个字段类型所对应的比较器均已就绪。设关键码由t个字段$\{k_t,k_{t-1},\dots,k_1\}$，优先级由高到低。于是以其中任一字段$k_i$为关键码，均可调用以上桶排序算法做一趟排序。只需按优先级递增的次序（从$k_1$到$k_t$）针对每一字段各做一趟桶排序，即可实现按整个关键码字典序的排序。

这一算法称作基数排序（radixsort），它采用了低位字段优先（least significant digit first）的策略，其中所作桶排序的趟数，取决于组成关键码的字段数。

正确性：

复杂度：

由以上基数排序的流程，总体运行时间应等于其中各趟桶排序所需时间的总和。设各字段取值范围为$[0,M_i)，1\le i \le t$，若记$M=\max\{M_1,M_2,\dots,M_t\}$。

则总体运行时间不超过：

$$O(n+M_1)+O(n+M_2)+\dots O(n+M_t)=O(t*(n+M))$$