您所在位置：主题：哈希表的设计(共享)
Chipset
[专家分：16190] 发布于 2011-08-12 08:45:00
1 哈希表
哈希表的设计可以追溯到1953年。在1953年元月，H. P. Luhn用开链哈希写了一个备忘录供IBM内部使用，几乎同一时间G. N. Amdahl, E. M. Boehme, N. Rochester还有Arthur Samuel几个人用程序实现了哈希表。开地址线性探测再散列哈希则应归功于Amdahl和Ershov，后者是俄国人。
相比于其它数据结构，哈希表的优点在于速度快，尤其数据量较大时，这种优点更为突出。如果事先能预测出数据量，哈希表可以更加高效，因为这样可以省去重新设定存储区大小所带来的时间开销。如果待存储数据宽度固定且事先预知可能设计出一个基本没有冲突的哈希表，甚至键值也不用存储在表里。
哈希表的缺点也是比较明显的，首先，实现困难，一个像样的哈希表比平衡树的实现要困难的多。第二，设计一个高效的哈希函数几乎可以看成是艺术问题而非技术问题。在开地址哈希表的设计中，很容易设计出低效的哈希函数。第三，对于一些特殊的应用中，例如拼写检查，哈希表可能比不上trie、有向无环图、Judy数组高效。第四，尽管哈希表的平均操作速度很快，但是某个操作可能花费时间很长(相对而言)，在某些实时性要求高的场合，这是不允许的。
1.1 哈希表的理论基础
哈希表一般用于快速检索，根据不同的领域，有的哈希表用来加密，有的哈希表用于拼写检查，有的哈希表用于网络路由计算……
设计一个通用且高效的哈希表非常困难，需要低内存消耗的数据结构，高效的哈希函数，快速访问的算法，当然了，技巧也十分关键。
1.1.1 基本概念
键值：就是关键字，例如根据身份证号码检索个人信息时，那么身份证号码就是关键字。
哈希表：在计算机科学里一个哈希表是一种这样的数据结构，它使用一个哈希函数把给定的键值映射到所关联的值上。或者这样比喻可能更容易理解一点，一个哈希表相当于一个关联数组，哈希函数的作用就是计算出该数组的下标，然后根据下标找到具体的值。
冲突：在理想的情况下，哈希函数应该把每个不同的键值映射到不同的值上，或者说，对于不同的键值，用同一个哈希函数计算出的地址应该是互不相同的。然而现实是比较残酷的，很多时候不同的键值经哈希函数计算出的地址会出现相同的时候，这就是所谓的”冲突”。使用数组存储元素时，这里的所谓的“地址”就是下标。
哈希函数：根据键值计算出关联值位置的函数。通俗的讲，就是计算出哈希表数组下标的函数。
开地址哈希：所有的元素都存储在一个数组里，为了解决哈希冲突问题，使用探测的办法，也就是说搜索可能的位置，直到找到一个待查的值或者空位置为止。
拉链哈希：为了解决哈希冲突问题，该方法使用链表把映射到同一位置的所有元素链接起来。所有链表的头指针用一个数组来存储，发生冲突时从表头开始顺链表搜索。当然了，也可以不用链表，使用动态数组或平衡树之类的数据结构，它们都是拉链哈希的变种。
装填因子：用来衡量冲突程度的一个值，范围为(0, 1.0]，该值越小说明冲突次数越多，该值越大说明冲突次数越少。装填因子也用于反应内存利用程度，该值越小说明内存利用率越低，该值越大说明内存利用率越高。在开地址哈希表中，抛开哈希函数不考虑，该值可能会严重影响速度，因为随着空间利用率上升，冲突的可能性大大增加，当然了，不好的哈希函数即使在装填因子比较低的情况下也可能产生很多聚集。
聚集：很明显，一个比较理想的哈希函数根据不同的键值计算出的位置会在某个区间产生一个均匀分布，此时也称谓聚集轻微，一个糟糕的哈希函数根据不同的键值计算出的位置会产生很多相同的情况(位置冲突)，此时也称谓聚集严重。
1.1.2 哈希函数的设计
对某个值进行哈希，至少需要分两步来进行，首先，不论什么数据类型，都需要要转换成非负整数(否则怎么跟数组下标对应起来？)，然后才能再映射到某个有限区间中。
1.1.2.1 怎么转换成非负整数？
正整数一般不必转换，给一个负整数哈希可以强制转换成正整数。指针也可以强制转换成正整数，字符也容易转换成正整数……
a) 字符窜怎么转换成正整数？
boost有一个通用的做法，对一个序列进行转换。
template <class T>
inline std::size_t hash_range(T* first, T* last) // size_t is an unsigned long typedef
{
std::size_t seed = 0;
for(; first != last; ++first)
{
boost::hash<T> hasher;
seed ^= hasher(*first) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
return seed;
}
比较简单的做法如下，但是可能会产生很多冲突。
inline unsigned long hash_string(const char* s)
{
UInt32 h = 0;
for(; *s; ++s)
h = (h << 5) - h + *s;
return static_cast<UInt32>(h);
}
更好一点的字符窜哈希函数介绍见http://burtleburtle.net/bob/hash/perfect.html
b) 浮点数怎么转换成正整数？
浮点数能表示的范围比正整数能表示的范围要大得多，当范围事先无法确定时，无论使用什么样的通用哈希函数都避免不了可能产生大量冲突。
最简单的办法就是直接取整，如果这样方法导致严重聚集就再配合一些位运算。如果还不行的话，就只能针对具体的数据分布自定义哈希函数了。
c) 自定义类型
只能自己定义特定的哈希函数(别人怎么可能知道你要定义什么？)。
1.1.2.2 如何映射到一个有限区间？
a) 取模
这是最为常见的方法，为了尽可能的降低冲突，模通常使用素数。多数哈希表映射键值到具体地址时使用了这种设计方法。
b) 位与运算
取模需要做除法，以现在的CPU架构，做除法比较慢(做一次除法至少比做一次加法慢太多)，因此可以考虑使用位运算。为了便于计算地址，数组容量通常开辟成2的指数大小，这样做可能会浪费一些内存(最坏情况浪费50%)。问题是位与运算可能产生大量冲突(例如参与掩码运算的整数二进制低位或高位全0或全1)，从软件工程的角度去考虑，此问题最好放到数据类型转换阶段去解决(上面1.1.2.1)。
1.1.3 冲突的解决方法
无论什么样的哈希函数，当元素性质无法预料时，都避免不了冲突。既然冲突无法避免，那就需要根据具体哈希方案使用有效的办法来解决。
1.1.3.1 开地址哈希
解决冲突的办法是使用探测，常用的探测方法有三种：分别是线性探测、二次方探测和二次哈希。线性探测就是间隔位置固定的查找，一般是间隔值是1，也就是顺序搜索。二次方探测就是查找间隔成线性增加(通常用一个二次函数计算出下一个检索位置)。二次哈希就是发生冲突时，再用另外一个哈希函数重新计算位置。
1.1.3.2 拉链哈希
解决冲突的办法是用单链表，每个元素有一个指针的空间开销，冲突时需要顺序搜索，理论上，最坏情况搜索的时间复杂度为O(n)，为了提升搜索速度，可以使用平衡树，理论上最坏情况时间复杂度为O(logn)，但是耗费更多的内存。也可以使用动态数组，免去单链表每个节点那一个指针的空间开销，但是最坏情况下的搜索速度不会下降，由于不能保证动态数组全部填满，因此，是否真的节约内存不太容易估计。
1.1.3.3 组合哈希
把开地址哈希和拉链哈希组合在一起，就成了一种新的哈希方案。
1.1.4 静态哈希和动态哈希
如果能事先能估计或计算出需要哈希的元素个数，那么就可以一次性开辟一块足够大的内存来存储所有元素，从而减少动态调整存储空间的麻烦，这就是所谓的静态哈希。
如果事先无法估计或计算出需要哈希的元素个数，那只能随着更多的元素需要哈希，动态增加哈希表的容量。调整容量的方法之一是复制元素到新空间，销毁原来空间，调整容量的方法之二是动态创建对象，必要时修改指针。两种容量调整方法各有所长。
1.2 哈希表的设计
本文将会简要介绍三个哈希表的设计，分别是开地址哈希和拉链哈希的组合，使用复制元素的方法调整容量；拉链哈希，使用复制元素的方法调整容量；拉链哈希，动态创建对象动态销毁，调整容量时修改指针。三个哈希表均使用相同的哈希函数，且都使用位于运算计算元素存储地址。
1.2.1 开地址组合拉链哈希表的设计
如果所有的元素都存储在一个预先开辟的数组里，插入元素时，就无需不停的调用new (或malloc)动态分配内存，速度上可以快一些，再者，使用new(或malloc)在堆上每开辟一块内存都会有metadata(应用程序看不到它，但是操作系统内核清楚，详见第8次课内存管理)，使用一个数组可以避免这种无谓的内存开销，节约内存。这就是我第一个哈希表设计的初衷。
既能节约内存又能提升速度，何乐而不为呢？下面看一看它的设计原理。
a) 地址计算
很多应用场合使用静态哈希表。在对象创建时即指定容量，为了计算地址方便，元素空间均是2的指数。很明显，如果待哈希的元素数目不是2的指数，那么这个哈希表的空间利用率不会很高，最坏情况下空间利用率仅50%。为了提升空间利用率，需要解决任意元素数目哈希地址计算这个问题。
计算地址使用取模能解决这个问题，但每哈希一次都要做一次取模运算，显然速度太慢了。因此还只能采用位于运算计算地址，只不过我们计算成2的指数时可以取下界。类似如下这样：
// 1 => 1
// 2, 3 => 2
// 4, 5, 6, 7 => 4
// 8, 9, ..., 14, 15 => 8
// 16, 17, ..., 30, 31 => 16
……
但这会引发新的问题，设想有63个元素，那么用于计算地址的掩码将会是31(二进制11111)，也就是位于运算计算出的下标落在0～31之间，其余元素怎么办，计算下标相同出现地址冲突怎么办？
b) 解决冲突
每个元素都附加一个指针，冲突时链接起来(由于只有一个数组，这需要一点编程技巧)。发生冲突时使用线性探测的办法从数组尾部向前顺序搜索空闲位置，这样能恰好弥补掩码太小映射不到的高端地址问题。为了提升搜索速度，设置一个指针，记录当前位置，下次搜索时从该位置继续向前搜。
c) 容量扩张
如果事先无法估计出元素个数，随着插入元素数目的增加，容量应该能自动动态增加。解决这个问题的办法可以参照vector的做法，容量不足时扩大至原来的2倍，但比较麻烦的是，每个元素都需要重新计算新的哈希地址，并插入到合适的位置。
4) 删除元素
由于只有一个数组，删除元素时容量要动态减小(否则空闲空间岂不是浪费了？)。比较麻烦的是所有对象都在一个数组里创建，且相关的用指针链接在一起，相当于一个数组里存储了多个链表。因此，删除元素时要格外小心，因为一旦一个链表“断了线”后续节点都成为无用的垃圾。
此外，当哈希表中的元素数目远小于容量时，应该能自动压缩空间。采取的办法是复制元素到较小空间，然后销毁原来空间。具体操作起来比较麻烦，因为每个元素均需要重新计算地址。正常情况下的减肥发生在当前元素数目不足容量一半的时刻，当然了，也允许重新指定新容量手工减肥，以便适合特殊情况。
1.2.2 拉链哈希的设计
很明显，上面的那个哈希表还能在速度上做一点改进，插入元素时它需要线性搜索空位，我们稍微改一下数据结构就可以避免这种不必要的搜索。
把链表头节点指针独立出来用一个数组存储(需要一点额外内存)，所有元素存储在另外一个数组里，给第二个数组设置一个指针记录位置，每插入一个元素就在第二个数组里创建一个对象链接到第一个数组所对应的表头节点，第二个数组记录位置的指针前移一个位置指向下一个空位。
为了能用于一般性场合，我们需要在LWitte基础上做一点改进。首先，要把它改造成动态表，元素数目无法确定时，插入元素容量自动动态调整。为了尽可能节约内存和操作方便，用作静态表时，容量可以指定任意值(不能仅是2的指数)。再扩充一点功能，提供删除操作，且能自动减肥。
a) 地址计算
在上一版本中，取2的指数下界，为了减少冲突次数，这次我们取上界。由于该值仅用于计算头指针地址，实际存储元素的数组则保持原来大小不变(有多少元素就开辟多大空间)，只要不用于哈希很小的对象，这样做就不至于浪费太多内存。类似如下这样：
// 1 => 1
// 2, 3 => 4
// 5, 6, 7, 8 => 8
// 9, ..., 14, 15, 16 => 16
// 17, ..., 30, 31, 32 => 32
……
b) 解决冲突
解决冲突的办法同上，还是使用单链表，只不过头指针独立出来用一个数组存储。
c) 容量扩张
容量成2的倍数增加，跟vector的设计类似，发生扩张时需要复制当前所有元素到新空间，然后销毁当前空间，比较麻烦的是，每个元素都需要重新计算新的哈希地址，并插入到合适的位置。
d) 删除元素
既然是动态表就应该提供删除操作，由于每个链表的头节点指针都独立出来了，因此比开地址组合拉链哈希表(1.2.1)的删除操作实现起来要容易的多。删除一个元素首先用哈希函数计算出地址，找到对应链表头节点指针，接下来则相当于从单链表中删除某个节点。
当哈希表中元素数目远小于容量时，将复制现有元素到较小空间，然后销毁当前空间。具体处理起来比较麻烦，因为每个元素都需要重新计算地址。正常情况下的减肥发生在当前元素数目不足容量一半的时刻，也允许重新指定新容量手工减肥，以便适合特殊情况。
1.2.3 又一个拉链哈希的设计
这个哈希表的结构跟一般编译器和库内建的哈希表类似。不同之处在于使用自定义的一个微型内存管理器为哈希的每个元素管理内存。
a) 地址计算
地址计算跟上一个哈希表(1.2.2)方法相同。
b) 解决冲突
使用单链表，所有单链表的头指针存储在一个数组里，数组容量调整时用new/delete来管理内存。
c) 容量扩张
由于所有单链表的头指针用一个数组存储，当这个数组容量不足时，会成2的倍数递增。创建的每个对象单独使用一块堆内存，因此即使容量变化时也不必复制元素，仅需要修改每个节点的指针。
理论上，在哈希较大的对象时，该方法十分有效，因为它可以免去复制对象产生的开销。
d) 删除元素
删除元素需要先计算出地址，找到对应链表的头指针，顺表头搜索，然后删除对应的节点。
e) 专用微型内存管理器
由于一个哈希表中所有对象大小相同(各个对象占用等大的内存块)，因此理论上不必像new/malloc那样为每块内存设置metadata(关于内存管理介绍见第8次课)，这样可以节约一点内存。但问题并不这么简单，我们需要考虑各种情况。因为需要哈希的元素可能会很多且删除和插入操作也可能会批量进行。此时，如果内存管理器中的每块内存彻底省去了metadata，则意味着这些内存只能等到整个哈希表废弃时再一次性交给系统，期间可能影响到其它程序动态申请内存的需要。也就是说，第8次课中介绍的自由列表算法在这里是不能用于设计这个专用微型内存管理器的。
为了解决这个问题，我们可以采用折中的办法，想一想第8次课中介绍的位图算法。用于设计哈希表的微型内存管理器时，每块内存大小信息可以不要(因为每个对象大小相同)，但是索引位不能去掉。32块小内存隶属于一块大内存，每个大块有一个位图，当整个大块中所有对象都死亡时(它包含的32个小块内存都闲置)，该大块内存可以交给系统。
理论上，用这种思想设计的哈希表专用内存管理器不但能节约一点内存，还具有较快的响应速度。
1.2.4 是否需要multixxx？
前面已经说过，不论什么数据类型，哈希时均需要转换成非负整数才能计算地址。如果在这个转换中出现同一数据类型的不同元素转换成相同的非负整数怎么办？难道此时不允许两个不同元素存入到同一个哈希表中吗？从这个意义上而言，我们是需要multixxx的。
为了节约篇幅，我们不再赘述这种哈希表设计的基本理论，因为它跟一般的哈希表设计上没有什么两样，仅仅是实现上略有不同罢了。
1.3 哈希表的性能测试
哈希表是新的C++标准(C++0x)加入的，测试编译器内建的哈希表时需要使用最新版的编译器。最容易获得的编译器是gcc，也是跟标准符合的最好的编译器，对于那些喜欢微软编译器产品的朋友而言，如果您想看一下VC++里哈希表的表现，您需要用VS2010。我们在此用gcc4.6.1以及boost1.47(写本文时它是最新版本)的哈希表作为对比。
仅仅测试unordered_map，数据量1M(1048576)，类型为64位随机整数，其他数据量和数据类型未必是这种趋势。用作动态表(不预先指定容量)时，测试结果见下表。
开地址哈希 拉链哈希 拉链哈希2 gcc4.6.1 boost1.47
时间
(ms) 插入 248.016 187.775 377.861 698.311 804.473
查找 100.422 89.5238 99.9342 84.5003 127.562
删除 246.384 220.711 496.983 545.507 546.939
理论内存 24MB 28MB 30MB 36MB 36MB
实际内存 25.5MB 29.5MB 32MB 37.5MB 39.5MB
用作静态表，(初始容量1048576)，测试结果见下表。
开地址哈希 拉链哈希 拉链哈希2 gcc4.6.1 boost1.47
时间
(ms) 插入 128.308 105.818 278.525 555.969 615.248
查找 101.690 96.0691 97.9075 84.3108 127.669
删除 254.986 240.722 495.749 546.412 548.968
理论内存 24MB 28MB 30MB 36MB 36MB
实际内存 25.4MB 29.4MB 32MB 37.5MB 39.5MB
对比以上测试结果可以看出，处理小对象(64位随机正整数)时，无论是用作动态表还是静态表，我们的三个哈希表均比gcc编译器和boost1.47库中的哈希表速度快一些。如果数据量能预先估计出来，用静态表往往效果会更好一些。
与gcc和boost1.47库中的哈希表比较，无论理论上还是实际表现，表面看上去我们的三个哈希表还是比较节约内存的。实则可不一定，前两个哈希表用动态数组存储元素，空间利用率最差时50%，此时它们内存消耗将超越gcc和boost1.47库中的unordered_xxx系列。
如果数据量事先无法预料，且处理较大对象，理论上拉链哈希表的第2个版本存取速度可能会更快一些，因为容量自动调整时，它仅仅修改指针，并不复制对象，但此处不再给出测试结果。
如果待哈希的非负整数二进制低位或高位全0或全1的话，理论上我们的三个哈希表都会慢的无法忍受，在此不再给出测试结果。解决办法是自定义哈希函数对象(参考源代码中注释掉的哈希函数实现)。
1.4 小结
本文简要介绍了哈希表的基本概念和三个哈希表的设计原理。虽然使用了简单的算法和数据结构，但编码设计上使用了一些技巧，这使得我们的三个哈希表都获得了不俗的表现。
哈希表主要用于快速检索的场合，如果数据量能预先估计出来，且变化范围不大，静态表可能是最佳选择。
哈希表的设计可以追溯到1953年。在1953年元月，H. P. Luhn用开链哈希写了一个备忘录供IBM内部使用，几乎同一时间G. N. Amdahl, E. M. Boehme, N. Rochester还有Arthur Samuel几个人用程序实现了哈希表。开地址线性探测再散列哈希则应归功于Amdahl和Ershov，后者是俄国人。
相比于其它数据结构，哈希表的优点在于速度快，尤其数据量较大时，这种优点更为突出。如果事先能预测出数据量，哈希表可以更加高效，因为这样可以省去重新设定存储区大小所带来的时间开销。如果待存储数据宽度固定且事先预知可能设计出一个基本没有冲突的哈希表，甚至键值也不用存储在表里。
哈希表的缺点也是比较明显的，首先，实现困难，一个像样的哈希表比平衡树的实现要困难的多。第二，设计一个高效的哈希函数几乎可以看成是艺术问题而非技术问题。在开地址哈希表的设计中，很容易设计出低效的哈希函数。第三，对于一些特殊的应用中，例如拼写检查，哈希表可能比不上trie、有向无环图、Judy数组高效。第四，尽管哈希表的平均操作速度很快，但是某个操作可能花费时间很长(相对而言)，在某些实时性要求高的场合，这是不允许的。
1.1 哈希表的理论基础
哈希表一般用于快速检索，根据不同的领域，有的哈希表用来加密，有的哈希表用于拼写检查，有的哈希表用于网络路由计算……
设计一个通用且高效的哈希表非常困难，需要低内存消耗的数据结构，高效的哈希函数，快速访问的算法，当然了，技巧也十分关键。
1.1.1 基本概念
键值：就是关键字，例如根据身份证号码检索个人信息时，那么身份证号码就是关键字。
哈希表：在计算机科学里一个哈希表是一种这样的数据结构，它使用一个哈希函数把给定的键值映射到所关联的值上。或者这样比喻可能更容易理解一点，一个哈希表相当于一个关联数组，哈希函数的作用就是计算出该数组的下标，然后根据下标找到具体的值。
冲突：在理想的情况下，哈希函数应该把每个不同的键值映射到不同的值上，或者说，对于不同的键值，用同一个哈希函数计算出的地址应该是互不相同的。然而现实是比较残酷的，很多时候不同的键值经哈希函数计算出的地址会出现相同的时候，这就是所谓的”冲突”。使用数组存储元素时，这里的所谓的“地址”就是下标。
哈希函数：根据键值计算出关联值位置的函数。通俗的讲，就是计算出哈希表数组下标的函数。
开地址哈希：所有的元素都存储在一个数组里，为了解决哈希冲突问题，使用探测的办法，也就是说搜索可能的位置，直到找到一个待查的值或者空位置为止。
拉链哈希：为了解决哈希冲突问题，该方法使用链表把映射到同一位置的所有元素链接起来。所有链表的头指针用一个数组来存储，发生冲突时从表头开始顺链表搜索。当然了，也可以不用链表，使用动态数组或平衡树之类的数据结构，它们都是拉链哈希的变种。
装填因子：用来衡量冲突程度的一个值，范围为(0, 1.0]，该值越小说明冲突次数越多，该值越大说明冲突次数越少。装填因子也用于反应内存利用程度，该值越小说明内存利用率越低，该值越大说明内存利用率越高。在开地址哈希表中，抛开哈希函数不考虑，该值可能会严重影响速度，因为随着空间利用率上升，冲突的可能性大大增加，当然了，不好的哈希函数即使在装填因子比较低的情况下也可能产生很多聚集。
聚集：很明显，一个比较理想的哈希函数根据不同的键值计算出的位置会在某个区间产生一个均匀分布，此时也称谓聚集轻微，一个糟糕的哈希函数根据不同的键值计算出的位置会产生很多相同的情况(位置冲突)，此时也称谓聚集严重。
1.1.2 哈希函数的设计
对某个值进行哈希，至少需要分两步来进行，首先，不论什么数据类型，都需要要转换成非负整数(否则怎么跟数组下标对应起来？)，然后才能再映射到某个有限区间中。
1.1.2.1 怎么转换成非负整数？
正整数一般不必转换，给一个负整数哈希可以强制转换成正整数。指针也可以强制转换成正整数，字符也容易转换成正整数……
a) 字符窜怎么转换成正整数？
boost有一个通用的做法，对一个序列进行转换。
template <class T>
inline std::size_t hash_range(T* first, T* last) // size_t is an unsigned long typedef
{
std::size_t seed = 0;
for(; first != last; ++first)
{
boost::hash<T> hasher;
seed ^= hasher(*first) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
return seed;
}
比较简单的做法如下，但是可能会产生很多冲突。
inline unsigned long hash_string(const char* s)
{
UInt32 h = 0;
for(; *s; ++s)
h = (h << 5) - h + *s;
return static_cast<UInt32>(h);
}
更好一点的字符窜哈希函数介绍见http://burtleburtle.net/bob/hash/perfect.html
b) 浮点数怎么转换成正整数？
浮点数能表示的范围比正整数能表示的范围要大得多，当范围事先无法确定时，无论使用什么样的通用哈希函数都避免不了可能产生大量冲突。
最简单的办法就是直接取整，如果这样方法导致严重聚集就再配合一些位运算。如果还不行的话，就只能针对具体的数据分布自定义哈希函数了。
c) 自定义类型
只能自己定义特定的哈希函数(别人怎么可能知道你要定义什么？)。
1.1.2.2 如何映射到一个有限区间？
a) 取模
这是最为常见的方法，为了尽可能的降低冲突，模通常使用素数。多数哈希表映射键值到具体地址时使用了这种设计方法。
b) 位与运算
取模需要做除法，以现在的CPU架构，做除法比较慢(做一次除法至少比做一次加法慢太多)，因此可以考虑使用位运算。为了便于计算地址，数组容量通常开辟成2的指数大小，这样做可能会浪费一些内存(最坏情况浪费50%)。问题是位与运算可能产生大量冲突(例如参与掩码运算的整数二进制低位或高位全0或全1)，从软件工程的角度去考虑，此问题最好放到数据类型转换阶段去解决(上面1.1.2.1)。
1.1.3 冲突的解决方法
无论什么样的哈希函数，当元素性质无法预料时，都避免不了冲突。既然冲突无法避免，那就需要根据具体哈希方案使用有效的办法来解决。
1.1.3.1 开地址哈希
解决冲突的办法是使用探测，常用的探测方法有三种：分别是线性探测、二次方探测和二次哈希。线性探测就是间隔位置固定的查找，一般是间隔值是1，也就是顺序搜索。二次方探测就是查找间隔成线性增加(通常用一个二次函数计算出下一个检索位置)。二次哈希就是发生冲突时，再用另外一个哈希函数重新计算位置。
1.1.3.2 拉链哈希
解决冲突的办法是用单链表，每个元素有一个指针的空间开销，冲突时需要顺序搜索，理论上，最坏情况搜索的时间复杂度为O(n)，为了提升搜索速度，可以使用平衡树，理论上最坏情况时间复杂度为O(logn)，但是耗费更多的内存。也可以使用动态数组，免去单链表每个节点那一个指针的空间开销，但是最坏情况下的搜索速度不会下降，由于不能保证动态数组全部填满，因此，是否真的节约内存不太容易估计。
1.1.3.3 组合哈希
把开地址哈希和拉链哈希组合在一起，就成了一种新的哈希方案。
1.1.4 静态哈希和动态哈希
如果能事先能估计或计算出需要哈希的元素个数，那么就可以一次性开辟一块足够大的内存来存储所有元素，从而减少动态调整存储空间的麻烦，这就是所谓的静态哈希。
如果事先无法估计或计算出需要哈希的元素个数，那只能随着更多的元素需要哈希，动态增加哈希表的容量。调整容量的方法之一是复制元素到新空间，销毁原来空间，调整容量的方法之二是动态创建对象，必要时修改指针。两种容量调整方法各有所长。
1.2 哈希表的设计
本文将会简要介绍三个哈希表的设计，分别是开地址哈希和拉链哈希的组合，使用复制元素的方法调整容量；拉链哈希，使用复制元素的方法调整容量；拉链哈希，动态创建对象动态销毁，调整容量时修改指针。三个哈希表均使用相同的哈希函数，且都使用位于运算计算元素存储地址。
1.2.1 开地址组合拉链哈希表的设计
如果所有的元素都存储在一个预先开辟的数组里，插入元素时，就无需不停的调用new (或malloc)动态分配内存，速度上可以快一些，再者，使用new(或malloc)在堆上每开辟一块内存都会有metadata(应用程序看不到它，但是操作系统内核清楚，详见第8次课内存管理)，使用一个数组可以避免这种无谓的内存开销，节约内存。这就是我第一个哈希表设计的初衷。
既能节约内存又能提升速度，何乐而不为呢？下面看一看它的设计原理。
a) 地址计算
很多应用场合使用静态哈希表。在对象创建时即指定容量，为了计算地址方便，元素空间均是2的指数。很明显，如果待哈希的元素数目不是2的指数，那么这个哈希表的空间利用率不会很高，最坏情况下空间利用率仅50%。为了提升空间利用率，需要解决任意元素数目哈希地址计算这个问题。
计算地址使用取模能解决这个问题，但每哈希一次都要做一次取模运算，显然速度太慢了。因此还只能采用位于运算计算地址，只不过我们计算成2的指数时可以取下界。类似如下这样：
// 1 => 1
// 2, 3 => 2
// 4, 5, 6, 7 => 4
// 8, 9, ..., 14, 15 => 8
// 16, 17, ..., 30, 31 => 16
……
但这会引发新的问题，设想有63个元素，那么用于计算地址的掩码将会是31(二进制11111)，也就是位于运算计算出的下标落在0～31之间，其余元素怎么办，计算下标相同出现地址冲突怎么办？
b) 解决冲突
每个元素都附加一个指针，冲突时链接起来(由于只有一个数组，这需要一点编程技巧)。发生冲突时使用线性探测的办法从数组尾部向前顺序搜索空闲位置，这样能恰好弥补掩码太小映射不到的高端地址问题。为了提升搜索速度，设置一个指针，记录当前位置，下次搜索时从该位置继续向前搜。
c) 容量扩张
如果事先无法估计出元素个数，随着插入元素数目的增加，容量应该能自动动态增加。解决这个问题的办法可以参照vector的做法，容量不足时扩大至原来的2倍，但比较麻烦的是，每个元素都需要重新计算新的哈希地址，并插入到合适的位置。
4) 删除元素
由于只有一个数组，删除元素时容量要动态减小(否则空闲空间岂不是浪费了？)。比较麻烦的是所有对象都在一个数组里创建，且相关的用指针链接在一起，相当于一个数组里存储了多个链表。因此，删除元素时要格外小心，因为一旦一个链表“断了线”后续节点都成为无用的垃圾。
此外，当哈希表中的元素数目远小于容量时，应该能自动压缩空间。采取的办法是复制元素到较小空间，然后销毁原来空间。具体操作起来比较麻烦，因为每个元素均需要重新计算地址。正常情况下的减肥发生在当前元素数目不足容量一半的时刻，当然了，也允许重新指定新容量手工减肥，以便适合特殊情况。
1.2.2 拉链哈希的设计
很明显，上面的那个哈希表还能在速度上做一点改进，插入元素时它需要线性搜索空位，我们稍微改一下数据结构就可以避免这种不必要的搜索。
把链表头节点指针独立出来用一个数组存储(需要一点额外内存)，所有元素存储在另外一个数组里，给第二个数组设置一个指针记录位置，每插入一个元素就在第二个数组里创建一个对象链接到第一个数组所对应的表头节点，第二个数组记录位置的指针前移一个位置指向下一个空位。
为了能用于一般性场合，我们需要在LWitte基础上做一点改进。首先，要把它改造成动态表，元素数目无法确定时，插入元素容量自动动态调整。为了尽可能节约内存和操作方便，用作静态表时，容量可以指定任意值(不能仅是2的指数)。再扩充一点功能，提供删除操作，且能自动减肥。
a) 地址计算
在上一版本中，取2的指数下界，为了减少冲突次数，这次我们取上界。由于该值仅用于计算头指针地址，实际存储元素的数组则保持原来大小不变(有多少元素就开辟多大空间)，只要不用于哈希很小的对象，这样做就不至于浪费太多内存。类似如下这样：
// 1 => 1
// 2, 3 => 4
// 5, 6, 7, 8 => 8
// 9, ..., 14, 15, 16 => 16
// 17, ..., 30, 31, 32 => 32
……
b) 解决冲突
解决冲突的办法同上，还是使用单链表，只不过头指针独立出来用一个数组存储。
c) 容量扩张
容量成2的倍数增加，跟vector的设计类似，发生扩张时需要复制当前所有元素到新空间，然后销毁当前空间，比较麻烦的是，每个元素都需要重新计算新的哈希地址，并插入到合适的位置。
d) 删除元素
既然是动态表就应该提供删除操作，由于每个链表的头节点指针都独立出来了，因此比开地址组合拉链哈希表(1.2.1)的删除操作实现起来要容易的多。删除一个元素首先用哈希函数计算出地址，找到对应链表头节点指针，接下来则相当于从单链表中删除某个节点。
当哈希表中元素数目远小于容量时，将复制现有元素到较小空间，然后销毁当前空间。具体处理起来比较麻烦，因为每个元素都需要重新计算地址。正常情况下的减肥发生在当前元素数目不足容量一半的时刻，也允许重新指定新容量手工减肥，以便适合特殊情况。
1.2.3 又一个拉链哈希的设计
这个哈希表的结构跟一般编译器和库内建的哈希表类似。不同之处在于使用自定义的一个微型内存管理器为哈希的每个元素管理内存。
a) 地址计算
地址计算跟上一个哈希表(1.2.2)方法相同。
b) 解决冲突
使用单链表，所有单链表的头指针存储在一个数组里，数组容量调整时用new/delete来管理内存。
c) 容量扩张
由于所有单链表的头指针用一个数组存储，当这个数组容量不足时，会成2的倍数递增。创建的每个对象单独使用一块堆内存，因此即使容量变化时也不必复制元素，仅需要修改每个节点的指针。
理论上，在哈希较大的对象时，该方法十分有效，因为它可以免去复制对象产生的开销。
d) 删除元素
删除元素需要先计算出地址，找到对应链表的头指针，顺表头搜索，然后删除对应的节点。
e) 专用微型内存管理器
由于一个哈希表中所有对象大小相同(各个对象占用等大的内存块)，因此理论上不必像new/malloc那样为每块内存设置metadata(关于内存管理介绍见第8次课)，这样可以节约一点内存。但问题并不这么简单，我们需要考虑各种情况。因为需要哈希的元素可能会很多且删除和插入操作也可能会批量进行。此时，如果内存管理器中的每块内存彻底省去了metadata，则意味着这些内存只能等到整个哈希表废弃时再一次性交给系统，期间可能影响到其它程序动态申请内存的需要。也就是说，第8次课中介绍的自由列表算法在这里是不能用于设计这个专用微型内存管理器的。
为了解决这个问题，我们可以采用折中的办法，想一想第8次课中介绍的位图算法。用于设计哈希表的微型内存管理器时，每块内存大小信息可以不要(因为每个对象大小相同)，但是索引位不能去掉。32块小内存隶属于一块大内存，每个大块有一个位图，当整个大块中所有对象都死亡时(它包含的32个小块内存都闲置)，该大块内存可以交给系统。
理论上，用这种思想设计的哈希表专用内存管理器不但能节约一点内存，还具有较快的响应速度。
1.2.4 是否需要multixxx？
前面已经说过，不论什么数据类型，哈希时均需要转换成非负整数才能计算地址。如果在这个转换中出现同一数据类型的不同元素转换成相同的非负整数怎么办？难道此时不允许两个不同元素存入到同一个哈希表中吗？从这个意义上而言，我们是需要multixxx的。
为了节约篇幅，我们不再赘述这种哈希表设计的基本理论，因为它跟一般的哈希表设计上没有什么两样，仅仅是实现上略有不同罢了。
1.3 哈希表的性能测试
哈希表是新的C++标准(C++0x)加入的，测试编译器内建的哈希表时需要使用最新版的编译器。最容易获得的编译器是gcc，也是跟标准符合的最好的编译器，对于那些喜欢微软编译器产品的朋友而言，如果您想看一下VC++里哈希表的表现，您需要用VS2010。我们在此用gcc4.6.1以及boost1.47(写本文时它是最新版本)的哈希表作为对比。
仅仅测试unordered_map，数据量1M(1048576)，类型为64位随机整数，其他数据量和数据类型未必是这种趋势。用作动态表(不预先指定容量)时，测试结果见下表。
开地址哈希 拉链哈希 拉链哈希2 gcc4.6.1 boost1.47
时间
(ms) 插入 248.016 187.775 377.861 698.311 804.473
查找 100.422 89.5238 99.9342 84.5003 127.562
删除 246.384 220.711 496.983 545.507 546.939
理论内存 24MB 28MB 30MB 36MB 36MB
实际内存 25.5MB 29.5MB 32MB 37.5MB 39.5MB
用作静态表，(初始容量1048576)，测试结果见下表。
开地址哈希 拉链哈希 拉链哈希2 gcc4.6.1 boost1.47
时间
(ms) 插入 128.308 105.818 278.525 555.969 615.248
查找 101.690 96.0691 97.9075 84.3108 127.669
删除 254.986 240.722 495.749 546.412 548.968
理论内存 24MB 28MB 30MB 36MB 36MB
实际内存 25.4MB 29.4MB 32MB 37.5MB 39.5MB
对比以上测试结果可以看出，处理小对象(64位随机正整数)时，无论是用作动态表还是静态表，我们的三个哈希表均比gcc编译器和boost1.47库中的哈希表速度快一些。如果数据量能预先估计出来，用静态表往往效果会更好一些。
与gcc和boost1.47库中的哈希表比较，无论理论上还是实际表现，表面看上去我们的三个哈希表还是比较节约内存的。实则可不一定，前两个哈希表用动态数组存储元素，空间利用率最差时50%，此时它们内存消耗将超越gcc和boost1.47库中的unordered_xxx系列。
如果数据量事先无法预料，且处理较大对象，理论上拉链哈希表的第2个版本存取速度可能会更快一些，因为容量自动调整时，它仅仅修改指针，并不复制对象，但此处不再给出测试结果。
如果待哈希的非负整数二进制低位或高位全0或全1的话，理论上我们的三个哈希表都会慢的无法忍受，在此不再给出测试结果。解决办法是自定义哈希函数对象(参考源代码中注释掉的哈希函数实现)。
1.4 小结
本文简要介绍了哈希表的基本概念和三个哈希表的设计原理。虽然使用了简单的算法和数据结构，但编码设计上使用了一些技巧，这使得我们的三个哈希表都获得了不俗的表现。
哈希表主要用于快速检索的场合，如果数据量能预先估计出来，且变化范围不大，静态表可能是最佳选择。
