词典

发表于 分类于

借助数据结构来表示和组织的数据结构，将所有数据视作一个整体统筹处理，进而提高信息访问的规范性及其处理的效率。例如，借助关键码查找和访问数据元素，其中最典型的例子即为词典。逻辑上的词典，为由一组数据构成的集合，其中各元素都是由关键码和数据项合成的词条。

映射和词典一样，也是词条的集合，二者的差异仅在于，映射要求不同词条的关键码互异，而词典则允许多个词条拥有相同的关键码。除了静态查找，映射和词典都支持动态更新，二者均统称为符号表。符号表并不要求词条之间可根据关键码比较大小，也不需要按照大小次序来组织数据项。以散列表为代表的符号表结构，转而根据数据项之间的数值，直接做逻辑查找和物理定位。在此类结构中，关键码和数值的地位等同，这种数据访问方式即为循值访问。为了循值访问，在符号表内部仍需强制地在数据对象的数值与其物理地址之间建立某种关联。

应用情景

散列以最基本的向量作为底层支撑结构，通过适当的散列函数在词条的关键码与向量单元的秩之间建立映射关系。只要散列表、散列函数、冲突排解策略安排得当，可在期望的常数时间内实现词典的所有接口操作。

电话查询系统

假设某大学拟建立一个电话簿查询系统，由电话号码查询机主信息，

蛮力：使用数组，按电话号码索引，静态的查找和动态的删除仅需要常数时间。

在使用8位编号系统时，可能的电话门数可能达到$10^8$次，而该校所有人员涉及的电话门数仅为25000门。上述方案使用的数组长度大致与$10^8$相当,此时的空间有效利用率仅为$25000/10^8=0.025$%，绝大部分空间处于闲置状态。

此类问题在实际应用中非常常见，共同特点可归纳为：尽管词典实际需要保存的词条数N远远少于可能出现的词条数R，但是R个词条中任何一个均有可能出现在此词典中。

散列表是散列方法的底层基础，逻辑上由一系列可存放词条的单元组成，故这些单元也被称为桶或桶单元，与之对应地，各桶单元也应按照其逻辑次序在物理上连续排列，往往用向量(数组)实现。此时地散列表亦称作桶数组。

设桶数组的大小为M，则$N<M<<R$，空间$=O(N+M)=O(N)$。

散列函数

一组词条在散列表内部的分布取决于散列方案，即事先在词条与桶地址之间定义某种映射关系，可描述为从关键码空间到桶地址空间的函数。

hash():key->hash(key)

这里的hash()称作散列函数，hash(key)称作key的散列地址，即与关键码key相对应的桶在散列表中的秩。

例如，某学校学生学号为10160000到10163999,则可直接使用一个长度为4000的散列表A[0~3999]，并取

hash(key)=key-10160000

从而将学号为x的学生学籍词条存放于桶单元A[hash(x)]。

如此之后，根据任一合法学号，都可在常数时间内确定其散列地址，并完成一次查找、插入或删除。

同义词，key1不等于key2，hash(key1)=hash(key2)。

是否存在某种定址方法，保证不出现冲突(消除同义词)，即散列函数等效于一个单射。

在关键码满足某些条件时，的确可以实现单射式散列。对于已知且固定的关键码集，可实现完美散列，采用两级散列，仅需$O(n)$空间，关键码之间互不冲突。一般情况下，完美散列无法保证存在。

设计原则

作为一个比较好的散列函数，应该具备以下特性：

  • 确定性，无论所含的数据项如何，词条E在散列表中的映射地址完全取决于关键码
  • 映射过程不可过于复杂，从而使查询和修改操作可在常数时间内完成
  • 所有关键码经过映射后应尽量覆盖整个地址空间[0,M),充分利用有效的散列表空间，即hash()最好是满射

定义域规模R远远大于取值域规模M,hash()不可能是单射。这意味着散列冲突在所难免。最为重要的一条原则就是关键码映射到各桶的概率应尽量接近于1/M，若关键码独立均匀分布，这也是任意一对关键码相互冲突的概率。整体而言，等效于将关键码空间均匀地映射到散列地址空间，从而避免极短低效的情况。总之，随机越强、规律性越弱的散列函数越好。

除余法

hash(key)=key % M

一般地，散列表长度$M$与词条关键码间隔$T$之间的公约数越大，发生冲突的可能性也越大。在实际应用中，对同一词典的访问往往具有某种周期性，若其周期与$M$有公共的因子，则冲突的概率将急剧攀升。若$M$为素数时，对于严格或大致等间隔的关键码序列，也不会出现冲突激增的情况。同时，数据对散列表的覆盖最充分，分布最均匀。

若取$M=2^k$，则对任何词条都有：

key%M=key &(M-1)=key & 00...001111..11

此时采用模余法的效果，等同于从key的展开式中截取末尾的$k$个比特。词条key中更高的其余比特位对散列的位置没有任何影响，从而在很大程度上降低了散列的随机性和均匀性。

假定散列表长度为$M$，采用除余法，若从空开始将间隔为$T$的$M$个关键码插入其中，若$g=gcd(M,T)$为$M$和$T$的最大公约数，则每个关键码大约与$g$个关键码冲突

这一组关键码序列依次构成一个等差数列，其公差为$T$。不失一般性，设他们分别是：

${0,T,2T,3T,…,(M-1)T}$

按照模余法，任何一对关键码相互冲突，当且仅当它们关于散列表长$M$，属于同一同余类。$g$为$M$和$T$的最大公约数，故相对于$M$而言，这些关键码来自于$M/g$个同余类。每一类各有彼此冲突的$g$个关键码。例如，其中0所属的同余类为：

${0,TM/g,2TM/g,3TM/g,…,(g-1)TM/g}$

散列表的$M$个桶与$M$的$M$个同余类一一对应。既然此时的关键码只能来自其中M/g个同余类，故必有M-M/g个桶闲置，空间利用率不超过：$\displaystyle \frac{M/g}{M}=1/g$

除余法的缺陷

  1. 不动点：无论表长M取值如何，总有hash(0)=0
  2. 零阶均匀：$[0,R)$的关键码，平均分配至$M$个桶，但相邻关键码的散列地址也必相邻

MAD法

一阶均匀：邻近的关键码，散列地址不再邻近

取M为素数,$a>0$,$b>0$,$a%M!=0$，

$hash(key)=(a*key+b)%M$

当然，某些条件下未必需要更高阶的均匀性。

数字分析法

从关键码key特定进制的展开中取特定的若干位，构成一个整形地址。比如，取十进制表示的奇数位，$hash(123456789)=13579$

平方取中法

从关键码key的平方的十进制或二进制展开中取居中的若干位，构成一个整形地址。

折叠法

将关键码的十进制或二进制展开分割为等宽的若干段，经异或运算后得到散列地址。

位异或法

将特定的二进制展开分割为等宽的若干段，经异或运算得到地址

总之，越是随机，越是没有规律越好。

伪随机数法

散列函数和目标与随机数的目标一致，所以通过随机数法映射地址：

$hash(key)=rand(key)%M$

散列码转换

作为词典的散列表结构，既不能假定词条关键码所属的类型天然地支持大小比较，更不应将关键码仅限定为整数类型。为扩大散列奇数地适用范围，散列函数hash()需要将任一类型的关键码映射为地址空间$[0,M)$内的一个整数hash(key)，通常可分解为两步

  • 利用某一种散列码转换函数hashcode()将关键码key统一转换为一个整数，称为散列码
  • 再利用散列函数将散列码映射为散列地址

那么，这里的散列转换函数hashCode()支持什么条件呢？

为支持后续尺度不同的散列空间，取值范围应覆盖系统所支持的最大整数范围，其次，各关键码经hashCode()映射后所得的散列码，相互之间的冲突也应尽可能减少，否则，这一阶段出现的冲突后一阶段将无法消除。

强制转换

对于byte,short,int和char等本身即可表示为不超过32位整数的数据类型，可直接将它们的这种表示作为散列码。比如，可通过类型强制转换为32位整数。

多项式法

与一般的组合对象不同，字符串各字符之间的次序具有特定含义，在散列码转换时务必考虑它们之间的次序。以英文为例，同一组字母往往可组成意义完全不同的多个单词，比如stop和tops等。

1
2
3
4
5
6
static size_t hashCode ( char s[] ) { //生成字符串的循环移位散列码（cyclic shift hash code）
   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位"是实验统计得出的最佳值

若简单地将各字母分别对应到整数，并将其总和作为散列码，则很多单词将相互冲突。为计入各字符之间出现的相对次序，可取常数$a \geq 2$,并将$x_0x_1…x_{n-1}$的散列码取作：

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

依次将字符串中的每个字符视为一个多项式的各项系数，故亦称为多项式散列码。其中的常数a非常关键，为了尽可能多地保留原字符串的信息以减少冲突，其低比特位不得全为0。针对不同类型的字符串，应通过实验确定a的最佳取值。

开散列

散列表中很大概率会有冲突，所以必须制定一套有效的对策，以处理和排解时常发生的冲突。

多槽位法

将彼此冲突的每一组词条组织为一个小规模的词典，分别存放于它们共同对应的桶单元中。比较简便的一种方法是，统一将各桶细分为更小的称作槽位的单元，每一组槽位可组织为向量或列表。只要槽位数目不多，仍可保证常数复杂度。

但是绝大多数槽位都处于空闲状态，若每个桶都被细分为$k$个槽位，则当散列表总共存有$n$个词条时，装填因子

$\lambda’ = N/(kM)=\lambda /k$ 将降低至原来的$1/k$。

其次，很难在事先确定槽位应细分到何种程度，方可保证在任何情况下都够用，在极端情况下，可能所有(或接近所有)词条都冲突于单个桶单元。尽管几乎其余所有的桶都会处于空闲状态，该桶却会因为冲突过多而溢出。

独立链法

每个桶存放一个指针，冲突的词条组织成列表。

各子词典的规模往往不大，大多数往往只含单个词条或者甚至是空的。无需为每个桶预留多个槽位，任意多次的冲突都可解决。可更为灵活地动态调整各子词典地容量和规模，删除操作实现简单、统一。

但是指针需要额外空间，节点也需要动态申请。一旦发生冲突，则需要遍历整个列表，导致查找成本的增加。对于列表结构来说，空间未必连续分布，系统缓存几乎失效。

公共溢出区法

单独开辟一块连续空间，发生冲突的词条，顺序存入此区域。

不冲突则已，一旦发生冲突，处理冲突词条的时间正比于溢出区的规模。

闭散列

就逻辑结构而言，独立链等策略便捷紧凑，但因需要引入次级关联结构，不能保证物理上的关联性，在查找过程中需要更多的I/O操作。实际上，仅仅依靠基本的散列表结构，就地排解冲突，反而是更好的选择。在冲突时允许在散列表内部寻找另一空桶存放，如此，各桶并非只能存放特定的一组词条。从理论上来说，每个桶单元可存放任一词条，所以这一策略也称作开放定址，同时，因为可用的散列地址仅限于散列表覆盖的范围内，所以亦称作闭散列。

线性试探法

在插入关键码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…

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

查找链

散列表每一组相互冲突的词条将视为一个有序序列，对其中任意一员的查找都需要借助这一序列。对应的查找过程，可能终止于三种情况：

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

对于长度为n的查找链，失败查找长度为n+1，在等概率假设下，平均成功查找长度为$\lceil n/2 \rceil$

相互冲突的关键码必定属于同一查找链，但是同一查找链的关键码却未必相互冲突。究其原因在于，多组各自冲突的关键码，有可能相互交织和重叠。此时，各组关键码的查找长度将进一步增加。

局部性

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

在散列表内部解决冲突，无需附加的指针(指针、链表或溢出区等)空间，结构本身保持简洁。只要还有空桶，迟早会找到。但是已发生过(并已排解)的冲突，将会导致本不必发生的冲突。

懒惰删除

查找链中任何一环的确是，都会导致后续词条因无法抵达而缺失，表现为有时无法找到实际已存在的词条。所以采用闭散列时，执行删除操作需要特别调整。

为了保证查找链的完整，可将后继词条悉数取出，再重新插入，但如此将导致删除操作的复杂度增加。简明有效的方法是，为每个桶另设一个标志位，指示该桶尽管目前为空，但此前的确曾存放过词条。该桶虽不存放任何实质的词条，但仍是查找链中的一环。如此标记后，对后继词条的查找仍可照常进行，而不致中断。

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

  • 在删除等操作之前对某一目标词条的查找，在查找过程中，只有在当前桶单元为空，且不带懒惰删除标记时方可报告查找失败，否则，无论该桶非空，或带有懒惰删除标记，都将沿着查找链继续试探。
  • 在插入等操作之前对某一目标词条的查找，无论当前桶为空，还是带有懒惰删除标记，均可报告查找成功，否则都将继续沿着查找链继续试探。

懒惰标记的操作借助位图实现，具体操作如下：

1
2
3
Bitmap* lazyRemoval; //懒惰删除标记
#define lazilyRemoved(x)  (lazyRemoval->test(x))
#define markAsRemoved(x)  (lazyRemoval->set(x))

考虑如下调整：

  • 每次查找成功后，将命中词条前移至查找链中第一个带有懒惰删除标记的空桶(若的确命中存在且位于空桶之前)
  • 每次查找失败后，若查找链的某一后缀完全由带懒惰删除标记的空桶组成，则清除它们的标记

但是以上调整并不可行，为了删除带有懒惰删除标记的桶，实质上等效于压缩查找链。但是查找链可能彼此有所重叠，任何一个带有懒惰删除标记的桶，都可能同时属于多个查找链。所以其中一条查找链的压缩，都将可能导致其他查找链的断裂。因此为了使这些策略可行，还必须做更多的处理，通常都未免弄巧成拙，得不偿失。

查找

1
2
3
4
5
6
7
template <typename K, typename V> V* Hashtable<K, V>::get ( K k ) //散列表词条查找算法
{  int r = probe4Hit ( k ); return ht[r] ? & ( ht[r]->value ) : NULL;  } //禁止词条的key值雷同
template <typename K, typename V> int Hashtable<K, V>::probe4Free ( const K& k ) {
   int r = hashCode ( k ) % M; //从起始桶（按除余法确定）出发
   while ( ht[r] ) r = ( r + 1 ) % M; //沿查找链逐桶试探，直到首个空桶（无论是否带有懒惰删除标记）
   return r; //为保证空桶总能找到，装填因子及散列表长需要合理设置
}

首先采用除余法确定首个试探的桶单元，然后按线性试探法沿查找链逐桶试探。统一返回最后查找被试探的桶的秩，上层调用者只需核对该桶是否为空，即可判断是否查找失败。

删除

1
2
3
4
5
6
7
8
9
10
11
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;
   //否则释放桶中词条，设置懒惰删除标记，并更新词条总数
}
template <typename K, typename V> int Hashtable<K, V>::probe4Hit ( const K& k ) {
   int r = hashCode ( k ) % M; //从起始桶（按除余法确定）出发
   while ( ( ht[r] && ( k != ht[r]->key ) ) || ( !ht[r] && lazilyRemoved ( r ) ) )
      r = ( r + 1 ) % M; //沿查找链线性试探：跳过所有冲突的桶，以及带懒惰删除标记的桶
   return r; //调用者根据ht[r]是否为空，即可判断查找是否成功
}

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

插入

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

1
2
3
4
5
6
7
8
9
10
11
12
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;
}
template <typename K, typename V> int Hashtable<K, V>::probe4Free ( const K& k ) {
   int r = hashCode ( k ) % M; //从起始桶（按除余法确定）出发
   while ( ht[r] ) r = ( r + 1 ) % M; //沿查找链逐桶试探，直到首个空桶（无论是否带有懒惰删除标记）
   return r; //为保证空桶总能找到，装填因子及散列表长需要合理设置
}

装填因子$\lambda =N/M$是最为重要的因素。随着$\lambda$上升，词条在散列表中聚集的程度必将持续减少，这也势必加剧查找成本的进一步攀升。若将装填因子控制在适当范围内，闭散列的平均效率通常可保持在较为理想的水平。一般建议是$\lambda <0.5$。

重散列

将装填因子控制在一定范围内，重散列即是常用的一种方法。

1
2
3
4
5
6
7
8
9
10
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 ); //新开懒惰删除标记比特图
   for ( int i = 0; i < old_capacity; i++ ) //扫描原桶数组
      if ( old_ht[i] ) //将非空桶中的词条逐一
         put ( old_ht[i]->key, old_ht[i]->value ); //插入至新的桶数组
   release ( old_ht ); //释放原桶数组——由于其中原先存放的词条均已转移，故只需释放桶数组本身
}

重散列算法：装填因子过大时，采取“逐一取出再插入”的朴素策略，对桶数组扩容

不可简单地（通过memcpy()）将原桶数组复制到新桶数组（比如前端），否则存在两个问题：

  • 会继承原有冲突
  • 可能导致查找链在后端断裂，即便为所有扩充桶设置懒惰删除标志也无济于事

平方试探法

单向平方试探

线性试探法各查找链均由物理地址连续的桶单元组成，因而会加剧关键码的聚集趋势，查找操作的效率将有所降低。平凡试探法可有效缓解聚集现象，在试探过程中，按如下规则确定第j次试探的桶地址：

$(hash(key)+j^2)%M,j=0,1,2,…$

各次试探的位置到起始位置的距离以平方速率增长。

局部性

平凡试探法之所以可以有效地缓解聚集现象，是因为充分利用了平方函数的特点，顺着查找链，试探位置的间距将以线性的速度增长。同时，常规的I/O操作页面规模已足够大，只有在查找链极长时，才有可能引发额外的I/O操作。

设散列表长度取作素数$M>2$,试证明：任一关键码所对应的的查找链中，前$\lceil M/2 \rceil=(M+1)/2$个桶必然互异

反证，假设存在$0 \leq a < \lceil M/2 \rceil$,使查找链上的第$a$个位置与第$b$个位置冲突，于是$a^2$和$b^2$必然同属于关于$M$的同一同余类，亦即：

$a^2 \equiv b^2(mod M)$

于是$a^2-b^2=(a+b)(a-b) \equiv 0(mod M)$

无论是$(a+b)$还是$(a-b)$绝对值都严格小于M,故均不可能被M整除，这与M为素数的条件矛盾。

查找链的前$\lceil M/2 \rceil$项关于$M$必然属于不同的同余类，因此互不冲突。在装填因子不足50%时，$\lceil M/2 \rceil$ 至少有一个是空余的，因此不可能发生无法抵达空桶的情况。

M若为合数，$n^2%M$可能的取值必然少于$\lceil M/2 \rceil$种，M若为素数，$n^2%M$可能的取值恰好等于$\lceil M/2 \rceil$种，恰由查找链的前$\lceil M/2 \rceil$项取遍。

在装填因子超过50%时，只要适当调整各桶的位置，下一插入操作必然因无法达到空桶而失败

任取：$\lceil M/2 \rceil \leq c<M-1$,考查查找链上的第$c$项

总是存在$0 \leq d <\lceil m/2 \rceil $,查找链上第$d$项与该第$c$项冲突

实际上，只要令$d=M-c \neq c$

则有：$c^2-d^2=(c+d)(c-d)=M(c-d) \equiv 0(mod M)$

于是$c^2$和$d^2$同属一个同余类，作为散列地址相互冲突。

散列表长度$M$为合数时，即便装填因子低于50%,平方试探仍有可能无法终止

考查$M=12$的散列表，{$0^2$,$1^2$,$2^2$,$3^2$,$4^2$,…}关于$M$模余只有${0,1,4,9}$四种可能。于是，即便只有这四个位置为空，也会因为查找链的重合循环导致新的关键码0无法插入。但是此时的装填因子仅为$\lambda=4/12<50%$

此时，对于秩$0 \leq a<b<\lceil M/2\rceil$,即便

$a+b \equiv 0 (mod M)$

$a-b \equiv 0(mod M)$

均不成立，也依然可能有:

$a^2-b^2=(a+b)(a-b) \equiv 0 (modM)$

以以上例子为例，$M=12$的散列表，取$a=24$和$b=4$,则

$2+4=6 \equiv 0(mod 12)$

$2-4=-2 \equiv 0(mod 12)$

均不成立，然而依然有$2^2-4^2=-12\equiv 0(mod 12)$

双向平方试探

自冲突位置起，将以{$+1^2$,$-1^2$,$+2^2$,$-2^2$,$+3^2$,$-3^2$,…}为间距依次试探。整个试探过程中，跳转的方向前后交替，所以称为双向平方试探。

只要散列表取作$4k+3$($k$为非负整数)，则任一关键码所对应的查找链中，前$M$个桶必然互异

根据跳转的方向，查找链的前$M$项可分为三类：

  • O:第1次试探，位于原地的起点
  • A:第$2、4、6、…,M-1$次试探，相对于起点向前跳转
  • B:第$3、5、7、….M$次试探，相对于起点向后跳转

根据此前的结论,$O \cup A$和$O \cup B$内部的试探不至相互冲突。因此，只需考虑A类试探和B类试探之间是否会存在冲突。

假设第$2a$次试探和第$2b+1$次试探相互冲突，于是便有：

$a^2 \equiv b^2(mod M)$

亦即$n=a^2+b^2\equiv 0(mod M) $

对于形如$M=4k+3$的素数表长，这是不可能的

一个自然数$n$若可表示为一对整数的平方和，则称之为可平方拆分的。

不妨设n的素因子分解式为：

$n=p_1^{\alpha1}p_2^{\alpha2}p_3^{\alpha3}…p_d^{\alpha d}$

以下恒等式：

$(u^2+v^2)(s^2+t^2)=(us+vt)^2$

$n$是可平方拆分的当且仅当对每个$1\leq d \leq d$，或$\alpha i$为偶数，或$p_i$是可平方拆分的。

除了$2=1^2+1^2$,其余素数可以根据关于4的模余值划分为两个同余类。根据费马平方和定理，形如$4k+1$的素因子必可以平方拆分，而形如$4k+3$的素因子必然不可平方拆分。因此，若$n$可平方拆分，则对于其中每一个形如$p_i=4k+3$的素因子，$\alpha i$必然是偶数。

由以上式子得，$M=4k+3$应是$4k+3$的一个素因子。根据分析可知，n必然可以被$M^2$整除，于是便有：

$n=a^2+b^2 \geq M^2$

然而，对于取值在$[1,\lfloor M/2 \rfloor]$ 范围内的$a$和$b$，这是不可能的。

散列应用

桶排序

简单情况

考查如下问题：给定$[0,M)$内的$n$个互异整数，如何高效地进行排序？

借助散列表$E[0,M)$

  • 创建散列表并将散列表初始化为0
  • 使用最简单的散列函数$hash(key)=key4,将整数视为关键码逐一插入到散列表中
  • 顺序遍历一趟散列表，依次输出非空桶中存放的关键码

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

一般情况

允许关键码重复，又该如何高效排序？

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

散列表的创建初始化耗时$O(M)$,将所有关键码插入散列表耗时$O( n )$ ，依次读出非空桶中的关键码$O(M)$，总体运行时间为$O(n+M)$。在n>>M的场合，桶排序的时间将是:

$O(n+M)=O(max(n,M))=O(n)$

线性正比于待排序元素的数目，突破了$\Omega(nlogn)$的下界。在关键码均匀分布时，亦是如此。

基于散列表的排序算法采取的是循秩访问的方式，摒弃了以往基于关键码大小比较式的设计思路，所以不受下界约束。

最大间隙

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

平凡算法

  • 将各点按照坐标排序(最坏情况下$\Omega(n logn)$)

  • 依次计算相邻点对之间的距离，保留最大者$\Theta (n)$

线性算法

  • 一趟线性扫描找到最左点、最右点
  • 将有效范围划分为$n-1$段($n$个桶)
  • 通过散列将各点归入对应的桶
  • 在各桶中，动态记录最左点和最右点
  • 算出相邻(非空桶之间的距离)
  • 最大距离则为最大间隙

正确性

$n-1$个间隙中的最宽者，绝不可能窄于这些间隙的平均宽度，即各个桶单元对应的区间宽度。最大间隙的两个端点绝不可能落在同一桶单元内。必然来自两个非空桶，中间可能有若干非空桶。左端点应在前一桶中应该最靠右，而又端点在后一桶中应该最靠左，因此只需动态记录各桶的最左点和最右点。

复杂度

时间复杂度为$O(n)$，空间复杂度为维护散列表所需空间，$O(n)$辅助空间。

对于最小间隙的问题，则不可使用以上方法，因为上述方法可用基于最大间隙至少与相邻的两个桶相交的事实，而最小间隙既有可能与两个相邻的非空桶相交，也有可能只与其中一个桶相交。

基数排序

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

假定关键码由$t$个字段{$k_t$,$k_{t-1}$,$k_{t-2}$,…,$k_1$}组成，其中$k_t$优先级最高。只需按照优先级递增的顺序对每一字段做一趟桶排序，即可实现按整个关键码字典序的排序。这一算法称作基数排序，采用了低位字段优先的策略，其中所做桶排序的趟数，取决于组成关键码的字段数。

正确性与稳定性

以以下命题作为归纳假设：在经过基数排序的前i趟桶排序后，所有词条均已按照关键码最低的i个字段有序排列。

假定前$i-1$趟均成立，考查第i趟桶排序的情况

  • 凡第$i$位不同的词条：即便此前为逆序，现在亦必已转为有序
  • 凡第$i$位相同的词条，得益于桶排序的稳定性，必保持原有次序

如此实现的基数排序同样稳定。

复杂度

根据以上基数排序的流程，总体运行时间等于其中各趟桶排序所需时间的总和。

设各字段取值范围为$[0,m_i),1 \leq i \leq t $

$M=max{m_1,m_2,…,m_t}$

总体运行时间不超过:

$O(n+m_1)+O(n+m_2)+…O(n+m_t)=O(t(n+M))$

当$M=O(n)$且$t$为常数时，$O(n)$。

在一些特定场合，基数排序非常高效。例如，任给来自$[0,n^d)$范围内的$n$个整数，其中常数d>1，可在$O(n)$时间内完成对它们的排序。

  • 在$O(dn)=O(n)$时间内，将这些整数转换为$n$进制的表示。
  • 将每一位视作一个域，则这些整数的排序依据等效于按照这些域的字典序，直接套用基数排序即可完成排序

以上基数排序过程包含$d$趟桶排序，累计耗时：

$dO(n)=O(dn)=O(n)$

原因：

  1. 整数的取值范围有限制
  2. 不再是基于比较的计算模式

计数排序

若将任一有序序列等效地视作有序向量，则每个元素的秩，应恰好等于序列中不大于该元素的元素总数。例如，其中最小元素的秩为$0$，最大元素的秩为$n-14$，分别有$0$和$n-1$个元素不大于它们。根据这一原理，只需统计出各元素的对应这一指标，也就确定了它们在有序向量中各自对应的秩。

无需借助冲突的独立链表，由此可得计数排序算法

1
2
3
4
5
6
7
8
9
10
11
12
int* countingsort(int A[0,n))
   引入一个可计数的散列表H[0,M),其长度等于输入元素取值范围的宽度M
   将H[]中所有桶的数值初始化为0
   遍历序列A[0,n) //遍历计数，O(n)
     对于每一项，令H[A[k]]++
   遍历散列表H[0,M)
     对于每一项H[i],令H[i+1]+=H[i]
   创建序列S[0,n)，记录排序结果
   逆向遍历输入序列A[0,n)
     对于每一项A[k]
     令S[--H[A[k]]]=A[k]
   返回s[0,n)

注意，最后一步扫描不可从前到后，否则稳定性不再满足。

其中各个步骤所需的时间，总体而言不超过$O(n+M)$ 。若$n>>m$，则排序时间为$O(n)$。这就是所谓的小集合大数据的情况，在当下已经成为数据和信息处理的主流类型。

跳转表

可否综合向量与列表的优势，高效地实现词典接口？具体地，如何使得各接口的效率为$O(logn)$。

跳转表的宏观逻辑如图所示，其内部由沿纵向分层，横向相互耦合的多个列表{$S_0$,$S_1$,$S_2$,…,$S_h$}组成，$h$称为跳转表的高度。每一水平列表称作一层，其中$S_0$和$S_h$分别称作底层和顶层。同层节点之间可定义前驱和后继关系。为便于查找，同层节点都按关键码排序。层次不同的节点可能沿着纵向组成塔，同一塔内的节点以高度为序定义前驱和后继。塔与词典中的词条一一对应。

高层列表总是底层列表的子集，其中特别地，$S_0$包含词典中所有词条，而$S_h$除头、尾哨兵外不含任何实质地词条。跳转表的层高$h$必然决定于最大的塔高。

跳转表各塔高度的随机分布规律对跳转表的整体性能至关重要。控制跳转表的生长过程，在时间和空间上都可实现足够高的效率。此类控制策略必然满足所谓生长概率减半的条件：

对于任意的$0 \leq k<h$,$S_k$中任一节点在$S_{k+1}$中仍然出现的概率，始终为1/2。

可见，各塔高度符合集合分布：$Pr(h=k)=p^{k-1}(1-p)$

于是，期望的塔高为$E(h)=1/(1-p)=2$

也可以如此解释，$S_0$中任一关键码在$S_k$中依然出现的概率均为$2^{-k}$,第$k$层节点数的期望值$E(|S_k|)=n2^{-k}=n/2^k$。

于是，所有节点期望的总数(即各层列表所需空间总和)为

$E(\sum_k|S_k|)=\sum_kE(|S_k|)=n\sum_k2^{-k}<2n=O(n)$

跳转表所需空间期望值为$ O( n )$

初始化与构造

1
2
3
4
5
6
7
8
9
template <typename T> void Quadlist<T>::init() { //Quadlist初始化，创建Quadlist对象时统一调用
   header = new QuadlistNode<T>; //创建头哨兵节点
   trailer = new QuadlistNode<T>; //创建尾哨兵节点
   header->succ = trailer; header->pred = NULL; //沿横向联接哨兵
   trailer->pred = header; trailer->succ = NULL; //沿横向联接哨兵
   header->above = trailer->above = NULL; //纵向的后继置空
   header->below = trailer->below = NULL; //纵向的前驱置空
   _size = 0; //记录规模
} //如此构造的四联表，不含任何实质的节点，且暂时与其它四联表相互独立

每个词条都在所属的塔内同时存在多个副本，浪费了大量的空间。只需将所有词条组织为一个独立的横向列表，则各词条所对应的纵向列表即可不必重复保留词条的副本。纵向列表中的每个节点，只需通过引用指向横向列表中对应的词条。如此，一旦查找终止于某纵向列表，即可直接通过引用找到对应的词条。

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename K, typename V> V* Skiplist<K, V>::get ( K k ) { //跳转表词条查找算法
   if ( empty() ) return NULL;
   ListNode<Quadlist<Entry<K, V>>*>* qlist = first(); //从顶层Quadlist的
   QuadlistNode<Entry<K, V>>* p = qlist->data->first(); //首节点开始
   return skipSearch ( qlist, p, k ) ? & ( p->entry.value ) : NULL; //查找并报告
} //有多个命中时靠后者优先
template <typename K, typename V> bool Skiplist<K, V>::skipSearch (
   ListNode<Quadlist<Entry<K, V>>*>* &qlist, //从指定层qlist的
   QuadlistNode<Entry<K, V>>* &p, //首节点p出发
   K& k ) { //向右、向下查找目标关键码k
   while ( true ) { //在每一层
      while ( p->succ && ( p->entry.key <= k ) ) //从前向后查找
         p = p->succ; //直到出现更大的key或溢出至trailer
      p = p->pred; //此时倒回一步，即可判断是否
      if ( p->pred && ( k == p->entry.key ) ) return true; //命中
      qlist = qlist->succ; //否则转入下一层
      if ( !qlist->succ ) return false; //若已到穿透底层，则意味着失败
      p = ( p->pred ) ? p->below : qlist->data->first(); //否则转至当前塔的下一节点
   }  //课后：通过实验统计，验证关于平均查找长度的结论
}

这里的参数p和qlist分别指示命中关键码所属塔的顶部节点及其所属的列表。qlist和p的初始值分别为顶层列表及其首节点，返回后将为上层的查找节点提供必要的信息。

时间复杂度

考查第$k$层列表$S_k$,

$S_k$非空，当且仅当$S_0$所含的$n$个节点中,至少有一个会出现在$S_k$中，相应的概率为

$Pr(|S_k|>0) \leq n2^{-k}=n/2^k$

反过来，$S_k$ 为空的概率为

$Pr(|S_k|>0) \geq 1-n2^{-k}$

这一概率随着高度$k$的增加将迅速上升并接近100%。

以$k=3logn$层为例，该层列表为空，当且仅当$h<k$,对应的概率为

$Pr(h<k)=Pr(|S_k|=0)\geq 1-n/2^k=1-n/n^3=1-1/n^2$

一般地，$k=alogn$层列表为空的概率为$1-1/n^{a-1}$,$a>3$后这一概率将迅速地接近100%。

$h$的期望值$S(h)=O(logn)$

查找的过程中，每次跳转只能向右或向下，故活跃节点的高度必单调非增，每个高度上纵向跳转至多一次。因此，整个查找过程中消耗于纵向跳转的时间不超过跳转表高度的期望值$O(logn)$。

沿同一列表的横向跳转所经过的节点必然依次紧邻，且均为各自所属塔的塔顶。若将同层连续横向跳转的次数记作$Y$,跳转经过$k$个塔顶，一个非塔顶则有几何分布：

$Pr(Y=k)=(1-p)^kp$

$E(Y)=(1-p)/p=(1-0.5)/0.5=1$

同层列表中紧邻的塔顶节点，平均不过$1+1=2$个。沿着每条查找路径，在每一高度上平均只做常数次横向跳转。因此，整个查找过程中所做的横向跳转的期望次数，线性正比于跳转表的期望高度，亦是$O( log n)$。

插入

此处通过逻辑表达式rand%2 来模拟投掷硬币，并保证生长概率减半的条件。通过伪随机数的奇偶，近似地模拟一次理想的掷硬币实验。只要伪随机数为奇数，新塔就继续生长，否则停止生长。新塔的期望高度，将取决于此前连续的正面硬币的期望次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename K, typename V> bool Skiplist<K, V>::put ( K k, V v ) { //跳转表词条插入算法
   Entry<K, V> e = Entry<K, V> ( k, v ); //待插入的词条（将被随机地插入多个副本）
   if ( empty() ) insertAsFirst ( new Quadlist<Entry<K, V>> ); //插入首个Entry
   ListNode<Quadlist<Entry<K, V>>*>* qlist = first(); //从顶层四联表的
   QuadlistNode<Entry<K, V>>* p = qlist->data->first(); //首节点出发
   if ( skipSearch ( qlist, p, k ) ) //查找适当的插入位置（不大于关键码k的最后一个节点p）
      while ( p->below ) p = p->below; //若已有雷同词条，则需强制转到塔底
   qlist = last(); //以下，紧邻于p的右侧，一座新塔将自底而上逐层生长
   QuadlistNode<Entry<K, V>>* b = qlist->data->insertAfterAbove ( e, p ); //新节点b即新塔基座
   while ( rand() & 1 ) { //经投掷硬币，若确定新塔需要再长高一层，则
      while ( qlist->data->valid ( p ) && !p->above ) p = p->pred; //找出不低于此高度的最近前驱
      if ( !qlist->data->valid ( p ) ) { //若该前驱是header
         if ( qlist == first() ) //且当前已是最顶层，则意味着必须
            insertAsFirst ( new Quadlist<Entry<K, V>> ); //首先创建新的一层，然后
         p = qlist->pred->data->first()->pred; //将p转至上一层Skiplist的header
      } else //否则，可径自
         p = p->above; //将p提升至该高度
      qlist = qlist->pred; //上升一层，并在该层
      b = qlist->data->insertAfterAbove ( e, p, b ); //将新节点插入p之后、b之上
   }//课后：调整随机参数，观察总体层高的相应变化
   return true; //Dictionary允许重复元素，故插入必成功——这与Hashtable等Map略有差异
}

删除

从跳转表中删除关键码为$k$的词条的具体操作过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename K, typename V> bool Skiplist<K, V>::remove ( K k ) { //跳转表词条删除算法
   if ( empty() ) return false; //空表情况
   ListNode<Quadlist<Entry<K, V>>*>* qlist = first(); //从顶层Quadlist的
   QuadlistNode<Entry<K, V>>* p = qlist->data->first(); //首节点开始
   if ( !skipSearch ( qlist, p, k ) ) return false; //目标词条不存在，直接返回
   do { //若目标词条存在，则逐层拆除与之对应的塔
      QuadlistNode<Entry<K, V>>* lower = p->below; //记住下一层节点，并
      qlist->data->remove ( p ); //删除当前层节点，再
      p = lower; qlist = qlist->succ; //转入下一层
   } while ( qlist->succ ); //如上不断重复，直到塔基
   while ( !empty() && first()->data->empty() ) //逐一地
      List::remove ( first() ); //清除已可能不含词条的顶层Quadlist
   return true; //删除操作成功完成
}

QuadlistNode节点总是以塔为单位，自顶而下得成批被删除，其中每一节点的删除，都按照如下模式：节点p为当前的塔顶，将它从横向列表中删除，其下邻随后将称为新塔顶，并将在紧随其后的下一次删除操作中被删除。

1
2
3
4
5
6
7
8
9
10
11
12
template <typename T> //删除Quadlist内位置p处的节点，返回其中存放的词条
T Quadlist<T>::remove ( QlistNodePosi(T) p ) { //assert: p为Quadlist中的合法位置
   p->pred->succ = p->succ; p->succ->pred = p->pred; _size--;//摘除节点
   T e = p->entry; delete p; //备份词条，释放节点
   return e; //返回词条
}

template <typename T> int Quadlist<T>::clear() { //清空Quadlist
   int oldSize = _size;
   while ( 0 < _size ) remove ( header->succ ); //逐个删除所有节点
   return oldSize;
}

词条的删除算法，不外乎消耗于两个方面：

  • 查找目标关键码
  • 拆除与目标关键码相关的塔

词条删除操作所需时间不超过$O(h)=O(logn)$

位图

集合可视为一种抽象数据类型，考查其中的特例，整数集合，按照散列的思想，所有离散集或者显式地本身就是整数集，或者隐式地可转换为整数集。

对集合的操作有：

1
2
3
void set(int k);//将整数加入当前集合
void clear(int k);//从当前集合中排除整数k
bool test(int k)P;//判断整数是否属于当前集合

位图是一种特殊的序列结构，可用于动态地表示由一组无符号整数构成的集合，其长度无限，且每个元素取值为布尔型。

一种简洁的实现方式如下，使用物理地址连续的一段空间，各元素依次对应于一个比特位:若集合包含整数$k$,则该段空间中的第$k$个比特位为1，否则该比特位为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Bitmap { //位图Bitmap类
    private:
      char* M; int N; //比特图所存放的空间M[]，容量为N*sizeof(char)*8比特
      protected:
    void init ( int n ) { M = new char[N = ( n + 7 ) / 8]; memset ( M, 0, N ); }
    public:
    Bitmap ( int n = 8 ) { init ( n ); } //按指定或默认规模创建比特图（为测试暂时选用较小的默认值）
    Bitmap ( char* file, int n = 8 ) //按指定或默认规模，从指定文件中读取比特图
    {    
      init ( n ); 
      FILE* fp = fopen ( file, "r" ); fread ( M, sizeof ( char ), N, fp );                     fclose ( fp );  
    }
    ~Bitmap() { delete [] M; M = NULL; } //析构时释放比特图空间
    void set   ( int k ) { expand ( k );  M[k >> 3] |=   ( 0x80 >> ( k & 0x07 ) ); }
    void clear ( int k ) { expand ( k );  M[k >> 3] &= ~ ( 0x80 >> ( k & 0x07 ) ); }
    bool test  ( int k ) { expand ( k ); return M[k >> 3] &( 0x80 >> ( k & 0x07 ) );}
    
    void dump ( char* file ) //将位图整体导出至指定的文件，以便对此后的新位图批量初始化
    {  FILE* fp = fopen ( file, "w" ); 
       fwrite ( M, sizeof ( char ), N, fp ); 
       fclose ( fp );  
    }
    char* bits2string ( int n ) { //将前n位转换为字符串——
       expand ( n - 1 ); //此时可能被访问的最高位为bitmap[n - 1]
       char* s = new char[n + 1]; s[n] = '\0'; //字符串所占空间，由上层调用者负责释放
       for ( int i = 0; i < n; i++ ) s[i] = test ( i ) ? '1' : '0';
       return s; //返回字符串位置
    }
    void expand ( int k ) { //若被访问的Bitmap[k]已出界，则需扩容
         if ( k < 8 * N ) return; //仍在界内，无需扩容
         int oldN = N; char* oldM = M;
         init ( 2 * k ); //与向量类似，加倍策略
         memcpy_s ( M, N, oldM, oldN ); delete [] oldM; //原数据转移至新空间
   }

每个字节通常包含8个比特，故通过移位运算：$k>>3$ 即可确定该元素所属字节的秩，通过逻辑与运算$k&0x07$即可确定该比特位在该字节中的位置；通过移位操作(高位顺序在前)：

$0x80>>(k&0x07)$即可得到该比特位在此字节中的数值掩码。

dump()接口将位图导出至指定文件，以便于对此后的新位图进行初始化。

set(),clear(),test()仅涉及常数次基本运算，故其时间复杂度为$O(1)$。

位图向量所占的空间线性正比于集合的取值范围。

典型应用

int A[n]的元素均取自[0,m)，如何剔除其中的重复者

仿照无序向量的去重方法，先有序化，再扫描一次$O(nlogn+n)$

但是数据量虽大，但是重复率极高，比如$2^{24}<<n=10^{10}$

即$10000000000$个无符号整数，若采用内部排序算法需要$4*n=40GB$内存，否则，频繁的I/O操作将导致效率低下。

1
2
3
Bitmap B(m);
for(int i=0;i<n;i++) B.set(A[i]);//O(n)
for(int k=0;i<m;k++) if(B.test(k)) /*...*/;//O(m)

可通过位图来利用$m<<n$的条件

总体运行时间$O(n+m)$

空间复杂度$O(m)$,搜索引擎的应用类似，词表规模不大，但是重复的概率很高。

如何计算[0,n)内的素数

不计内循环，外循环自身每次仅一次加法、两次判断，累计O(n)

内循环每趟迭代$O(n/i)$步，由素数定理至多$n/lnn$趟，累计耗时不过

$n/2 + n/3 + n/5 + n/7 + n/11 + …< n/2 + n/3 + n/4 + n/6 + n/7 + … + n/(n/ln(n))$

$= O(n(ln(n/lnn) - 1))$

$= O(nln(n) - nln(ln(n)) - 1)$

$= O(nlogn)$

1
2
3
4
5
6
7
8
void Eratosthenes ( int n, char* file ) {
   Bitmap B ( n ); B.set ( 0 ); B.set ( 1 ); //0和1都不是素数
   for ( int i = 2; i < n; i++ ) //反复地，从下一
      if ( !B.test ( i ) ) //可认定的素数i起
         for ( int j = __min ( i, 46340 ) * __min ( i, 46340 ); j < n; j += i ) //以i为间隔
            B.set ( j ); //将下一个数标记为合数
   B.dump ( file ); //将所有整数的筛选标记统一存入指定文件，以便日后直接导入
}

内循环从$i * i$而非$i + i$开始，迭代步数由$O(n / i)$降至$O(max(1, n / i - i))$

快速初始化

将$B[m]$拆分为一堆等长的rank型向量，总体空间复杂度仍然为$O(m)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Bitmap { //位图Bitmap类：以空间作为补偿，节省初始化时间（仅允许插入，不支持删除）
private:
   Rank* F; Rank N; //规模为N的向量F，记录[k]被标记的次序（即其在栈T[]中的秩）
   Rank* T; Rank top; //容量为N的栈T，记录被标记各位秩的栈，以及栈顶指针

protected:
   inline bool valid ( Rank r ) { return ( 0 <= r ) && ( r < top ); }

public:
   Bitmap ( Rank n = 8 ) //按指定（或默认）规模创建比特图（为测试暂时选用较小的默认值）
   { N = n; F = new Rank[N]; T = new Rank[N]; top = 0; } //在O(1)时间内隐式地初始化
   ~Bitmap() { delete [] F; delete [] T; } //析构时释放空间

// 接口
   inline void set ( Rank k ) { //插入
      if ( test ( k ) ) return; //忽略已带标记的位
      F[k] = top++; T[ F[k] ] = k; //建立校验环
   }
   inline bool test ( Rank k ) //测试
   {  return valid ( F[k] ) && ( k == T[ F[k] ] );  }
};

每当需要调用set(k)标记新的$B[k]$位时，即可将$k$压入栈$T[]$中，并将当前元素(当前的顶元素)在栈中的秩存入$F[k]$。在$k$与$T[F[k]]$之间建立了一个校验环路，当$F[k]$指向栈$T[]$中某个有效元素(valid(F[k]))恰好等于$k$时，在逻辑上必然等效于B[k]=True,反之亦然。test(k)只需判断以上两个条件是否成立。

以上方法仅限于标记操作set()，尚且不支持clear()操作。如需兼顾这两个操作，就必须有效地区分两种操作，从未标记过的，以及曾经一度被标记后来又被清除的。否则，每次为无标记的位增加标记时简单套用目前的set()接口为其增加一个校验环，则无法限制在$N$以内，整个结构的空间复杂度也将随着操作的次数严格地单调增加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Bitmap { //位图Bitmap类：以空间作为补偿，节省初始化时间（既允许插入，亦支持删除）
private:
   Rank* F; Rank N; //规模为N的向量F，记录[k]被标记的次序（即其在栈T[]中的秩）
   Rank* T; Rank top; //容量为N的栈T，记录被标记各位秩的栈，以及栈顶指针

protected:
   inline bool valid ( Rank r ) { return ( 0 <= r ) && ( r < top ); }
   inline bool erased ( Rank k ) //判断[k]是否曾被标记过，且后来又被清除
   { return valid ( F[k] ) && ! ( T[ F[k] ] + 1 + k ); } //这里约定：T[ F[k] ] = - 1 - k

public:
   Bitmap ( Rank n = 8 ) //按指定（或默认）规模创建比特图（为测试暂时选用较小的默认值）
   { N = n; F = new Rank[N]; T = new Rank[N]; top = 0; } //在O(1)时间内隐式地初始化
   ~Bitmap() { delete [] F; delete [] T; } //析构时释放空间

// 接口
   inline void set ( Rank k ) { //插入
      if ( test ( k ) ) return; //忽略已带标记的位
      if ( !erased ( k ) ) F[k] = top++; //若系初次标记，则创建新校验环
      T[ F[k] ] = k; //若系曾经标记后被清除，则恢复原校验环
   }
   inline void clear ( Rank k ) //删除
   {  if ( test ( k ) ) T[ F[k] ] = - 1 - k;  } //忽略不带标记的位
   inline bool test ( Rank k ) //测试
   {  return valid ( F[k] ) && ( k == T[ F[k] ] );  }

这里的clear()接口将$T[F[k]]$取负之后再减一，也就是再与正常校验环不冲突的情况下就地保留原校验环的信息。

set(k)只需调用erased(k)即可判断$k$属于哪种类型，若从未标记过，则按之前的方法新建一个校验环，否则直接恢复原先的校验环。

再考查以上实现的空间复杂度，表面上看$F[]$和$T[]$的规模均不超过$N$,但是两个向量元素类型不再是比特位而是秩。二者的本质区别在于前一类元素自身所占的空间与整体规模无关，而后者有关。这里$rank$类型的取值必须足以覆盖Bitmap的规模，反之，可用Bitmap最大也不能超越$rank$类型的取值范围。比如，$rank$为四个字节类型的整数，则Bitmap的规模无法超过$2^{31}-1=O(10^9)$，否则$rank$的自身字宽必须相应加大。所幸目前多数应用均不超过这个规模，因此可近似认为以上算法具有线性复杂度。

还用于散列表和桶单元的初始化和图的初始化。