目录
1 hashtable
1.1 概述
要提供常数时间的操作，可以通过配置一个array，array的每一个元素值代表元素的出现次数，元素所在array中的位置为索引。这种解法的额外负担是array的空间和初始化时间。
存在两个问题：
- 元素是32-bits的，那么array太大
- 若元素形态是字符串非整数，则无法作为array的索引，即使通过编码也可能最终回归问题一，导致更大的索引值
解决方法：使用某种映射函数，将大数映射为小数。
散列函数(hash function)：负责将某一元素映射为一个“大小可接受之索引”
碰撞问题：不同的元素被映射到相同位置
解决碰撞问题的方法：线性探测、二次探测、开链
1.1.1 线性探测
负载系数：元素个数除以表格大小，负载系数永远在0~1之间
-
元素插入：使用hash function计算出插入位置后，发现位置不可用，则循序往下一一寻找
-
元素搜寻：同上
-
元素删除：惰性删除，只标记删除记号，实际删除待表格重新整理——hash table中的每一个元素不仅表述它们自己，也关系到每个元素的排列
1.1.2 二次探测
1.线性探测法每次探测的都必然是一个不同的位置，二次探测法是否能够保证如此？二次探测法是否能够保证如果表格之中没有X，那么我们插入X一定能够成功？
假设表格大小为质数，而且永远保持负载系数在0.5以下（超过0.5重新配置并重新整理表格），那么可确定每次插入一个新元素所需的探测次数不多于2
2.线性探测法的运算过程极其简单，二次探测法则显然复杂得多。这是否会在执行效率上带来太多的负面影响？
3.不论线性探测或二次探测，当负载系数过高时，表格是否能够动态成长？
欲扩充表格，首先必须找出下一个新的而且够大（大约两倍）的质数，然后必须考虑表格重建（rehashing）的成本——不只是原封不动地拷贝而已，还必须检验旧表格中的每一个元素，计算其在新表格中的位置，然后再插入到新表格中。
小结：
二次探测可以消除主集团（primary clustering），却可能造成次集团（secondary clustering）：两个元素经hash function 计算出来的位置若相同，则插入时所探测的位置也相同，形成某种浪费。
消除次集团的办法：复式散列
1.1.3 开链
在每一个表格元素中维护一个list：hash function会分配一个list，可在list上执行元素的插入、搜寻和删除等操作。虽然针对list而进行的搜寻只能是一种线性操作，但如果list够短，速度还是够快。
1.2 hashtable的buckets和nodes
hashtable的节点定义：
template <class Value>
struct __hashtable_node {
__hashtable_node* next;
Value val;
};
1.3 hashtable的迭代器
迭代器类型：typedef forward_iterator_tag iterator_category
因此，hashtable的迭代器无后退操作（operator–()）
1.4 hashtable的数据结构
SGI STL会以质数来设计表格大小（开链法并不要求表格大小必须为质数），并将28个质数计算好，以备随时方法，同时提供一个函数__stl_next_prime(unsigned long n)用来查询在这28个质数之中，最接近并大于n的质数
1.5 hashtable的构造与内存管理
专属节点配置器：typedef simple_alloc<node, Alloc> node_allocator
构造一个拥有50个节点的hashtable（传入50，返回53）
hashtable(size_type n, const HashFcn& hf, const EqualKey& eql) : hash(hf), equals(eql), get_key(ExtractKey()), num_elements(0) {
initialize_buckets(n);
}
void initialize_buckets(size_type n) {
const size_type n_buckets = next_size(n); //返回最接近并大于n的质数
buckets.reserve(n_buckets);
buckets.insert(buckets.end(), n_buckets, (node*)0);
num_elements = 0;
}
1.5.1 插入与表格重整
//插入元素，不允许重复
pair<iterator, bool> insert_unique(const value_type& obj) {
resize(num_elements + 1); //判断是否需要重建表格，如需要就扩充
return insert_unique_noresize(obj);
}
表格重建与否的判断函数：将新增元素计入后的元素个数和buckets vector的大小来比。如果前者大于后者，就重建表格。由此可判断，每个bucket（list）的最大容量和buckets vector的大小相同
template<class V, class K, class HF, class Ex, class Eq, class A> void hashtable<V, K, HF, Ex, Eq, A>::resize(size_type nume_elements_hint)
不允许键值重复的新节点插入函数：
template<class V, class K, class HF, class Ex, class Eq, class A>
pair<typename hashtable<V, K, HF, Ex, Eq, A>::iterator, bool>
hashtable<V, K, HF, Ex, Eq, A>::hashinsert_unique_noresize(const value_tyoe& obj)
允许键值重复，则使用insert_equal()，不再是inert_unique()。即原先发现与链表中的某键值相同时，不插入立即返回；insert_equal马上插入然后返回。
1.5.2 判知元素的落脚处（bkt_num）
通过bkt_num()函数调用hash function，取得一个可以执行moduls（取模）运算的数值。
因为有些元素型别无法直接拿来对hashtable的大小进行模运算，例如字符字符串，需要做一些转换。
1.5.3 复制和整体删除
由于整个hashtable由vector和linked-list组合而成，因此，复制和整体删除都需要特别注意内存的释放问题。
template<class V, class K, class HF, class Ex, class Eq, class A> void hashtable<V, K, HF, Ex, Eq, A>::clear() {
//针对每一个bucket
for(size_type i = 0; i < buckets.size(); ++i) {
node* cur = buckets[i];
//将bucket list中的每一个节点删除掉
while(cur != 0) {
node* next = cur->next;
delete_node(cur);
cur = next;
}
bucket[i] = 0; //令bucket内容为null指针
}
num_elements = 0; //令总节点个数为0
//buckets vector并未释放掉空间，仍抱有原来大小
}
template<class V, class K, class HF, class Ex, class Eq, class A> void hashtable<V, K, HF, Ex, Eq, A>::copy_from(const hashtable& ht) {
buckets.clear();
buckets.reserve(ht.buckets.size());
buckets.insert(buckets.end(), ht.buckets.size(), (node*)0); //从己方的buckets vector尾端开始插入n个null指针
__STL_TRY {
for(size_type i = 0; i < ht.buckets.size(); ++i) {
//复制vector的每一个元素
if(const node* cur = ht.buckets[i]) {
node* copy = new_node(cur->val);
buckets[i] = copy;
//针对同一个bucket list，复制每一个节点
for(node* next = cur->next; next; cur = next, next = cur->next) {
copy->next = new_node(next->val);
copy = copy->next;
}
}
}
num_elements = ht.num_elements;
}
__STL_UNWIND(clear());
}
1.5.4 应用实例
hashtable提供的find和count函数：
iterator find(const key_type& key) {
size_type n = bkt_num_key(key); //首先判知元素落脚处，即在哪一个bucket内
node* first;
//从bucket list开始，一一比对每个元素的键值
for(first = buckets[n]; first && !equals(get_key(first->val), key), first = first->next) {}
return iterator(first, this);
}
size_type count(const key_type& key) const {
const size_type n = bkt_num_key(key);
size_type result = 0;
//从bucket list开始，一一比对每个元素的键值,比对成功则加1
for(const node* cur = buckets[n]; cur; cur = cur->next)
if(equals(get_key(cur->val), key)) ++result;
return result;
}
1.6 hash functions
针对char，int，long等整数型别， hash functions只是返回原值：
__STL_TEMPLATE_NULL struct hash<char> {
size_t operator()(char x) const { return x; }
}
对于char*,const char*则需要经过一个转换函数__stl_hash_string():
inline size_t __stl_hash_string(const char* s) {
unsigned long h = 0;
for(; *s; ++s)
h = 5*h + *s;
return size_t(h);
}
2 hash_set
-
hash_set以hashtable为底层机制
-
使用set的目的：快速搜寻元素。而由于RB-tree有自动排序而hashtable没有，因此set的元素能够自动排序而hsh_set没有。
元素插入的次序可能受底层hashtable大小和元素大小的影响！
-
hash_set的键值就是实值，实值就是键值。
-
插入操作使用
insert_unique()，不允许键值重复
3 hash_map
-
hash_map也以hashtable为底层机制，因此没有自动排序
-
hash_map的每一个元素同时拥有一个实值和键值（使用方式与map相同）
-
插入操作使用
insert_unique()，不允许键值重复
4 hash_multiset&hash_multimap
-
hash_multiset/hash_multimap也以hashtable为底层机制，因此hash_multiset/hash_multimap的元素不会被自动排序
-
与hash_set/hash_map的唯一区别：元素插入采用
insert_equal()