此文是翻译文章
网页版
http://gamehevenhome.blogspot.tw/2015/08/c.html
C++不叫Hash Table，而是取了一个华丽名字叫无序容器(unordered associative
container)。从2011开始c++提供了四种无序容器。
unordered_set , unordered_map (不可接受重复的元素)
unordered_multiset , unordered_multimap (可接受重复的元素)
一个常用的方法是采用单向连结。
在这种状况下，每个桶子内部都是一个指标，指向一个单向序列。如果Hash算法设计的
好，每个链结都很短，插入跟删除效率会接近O(1)。如图所示， b1,b3只有一个元素，b2
有两个元素。简单方便，但是在C++不合用，因为规范要求容器必须可以遍历，必须提供
一个iterator，可以让 iterator从头到尾扫过一遍。那要如何从b1跳到b2？最明显的方
法是继续扫描阵列，直到下一个有装东西的桶子。但这不可用，因为阵列愈大，扫描愈
慢。偏偏规范明定++i;效率要保持O(1)。为了符合规范，只好把所有元素都串在一起。
我们来看一些Hash Table常用的结构。加上一个模仿Boost.MutiIndex的设计。先假设所
有元素都不一样。
(unordered_multiset , unordered_multimap以后再讨论)
假设有N笔资料，阵列有B个桶子。
Dinkumware函式库
这是微软Visual C++的实现方法。请看图。
(请注意，桶子的顺序不一定要跟元素顺序一样。图片只是为了绘图方便)
就跟你想的一样，所有元素都串在一起。使用双向连结。现在可以用iterator双向访问，
代价是要多一个指标。好处是删除元素非常容易。阵列里面每个桶 子都有两个指标，指
向链结的头跟尾。
插入元素的方法：
1.使用Hash先找到桶子。(常数时间)
2.元素如果重复要放弃插入，所以要扫描桶子里面所有元素。(桶子大小线性时间)
3.新元素插入在链结的头。(常数时间)
4.调整桶子里面的两个指标。(常数时间)
删除元素的方法：
1.使用Hash先找到桶子。(常数时间)
2.删除链结一个元素，调整前后指标。(常数时间)
3.调整桶子里面的两个指标。(常数时间)
4.操作效率是O(1)，内存消耗，每个元素要两个指标，每个桶子也要两个指标。
2N+2B
看起来很好，但其实Dinkumware的方法对于删除元素，有一个严重的瑕疵。
使用Hash先找到桶子。(常数时间)
如果Hash函式会丢出例外，今天删除动作就失败了。偏偏规范又讲明删除保证要成功，而
且不可以丢出任何例外。所以Dinkumware方法其实不符合规 范。
Boost.Unordered, libc++ , libstdec++ -V3函式库
Boost.Unordered, libc++函式库使用类似的资料结构。但设计成单向链结。
所有元素用单向链结串在一起。
因为删除动作不可以抛出异常。删除的时候不可以呼叫Hash函式，所以只好把Hash后的数
字也存起来。
因为是单向链结，为了删除方便。桶子里面的指标不是指向第一笔元素，而是第一笔的前
一个。所以图片中的b2指标指向前一个的b1。
删除元素的方法：
1.因为节点里面已经有Hash值，可直接定位到桶子。(常数时间，不会丢出异常)
2.链结扫过一遍。(桶子大小线性时间)
3.删除链结一个元素，调整前后指标。(常数时间)
4.调整桶子里面的指标。(常数时间)
插入删除都是O(1)。满足规范。记忆消耗如下
2N+1B
(我们假设Hash的数字，占用大小跟一个指标一样)
libstdec++ -V3提供了一个最佳化设计。如果Hash函式确定不会丢出异常。(有使用
nonexcpt)。函式库会标记成fast模式。节点里面不会储存Hash数 字。我觉得这设计有点
危险。代码里面使用__is_fast_hash type来标记，基本型态通通设定为true。使用者自
订Hash函式默认是false，除非函式有用nonexcept，才会变成true。
不考虑最佳化的特殊机制，2N+1B似乎已经是好的设计了。但事实上还有更好的方法，不
需要再增加任何内存。
簿记式的资料结构
Boost 1.56 Boost.MutiIndex里面使用了一种全新的方式。双向链结改用环状的方式。
定一个节点叫做X，下一个节点叫做Xn，前一个节点叫做Xp。环形链结代表
X = Xnp = Xpn
这个条件永远成立。
连结往前再往后一定会回到自己。
连结往后再往前一定会回到自己。
我们现在看一下完整的示意图
把阵列桶子也加进来，做一个小改动。
如果元素是桶子的第一个元素，Xp改成指向桶子自己。
可以导出一些规则。
如果Xpn != X，代表X是这个桶子的第一个元素
如果Xnp != X，代表X是这个桶子的最后一个元素
下一个元素一定可以用Xn取得。
前一个元素比较麻烦，如果是桶子的第一个元素，前一个元素就是Xpn，其他元素直接用
Xp存取即可。
所有动作都是常数时间，我们可以把它还是当作环形链结。只是往前移动需要特殊处理。
删除元素的方法：
1.从双向连结删除元素，调整前后指标。(常数时间)
2.调整桶子里面的指标。(常数时间)
删除元素不需要把一个桶子都翻遍，就算遇到差劲的Hash算法也没差。内存不用增加
。还是2N+1B。