二叉搜索树具有对数平均时间的表现，但这样的表现还建立在一个假设上：输入数据足够随机。

　　hashtable（散列表）的数据结构在插入、删除、搜索等操作上具有“常数平均时间”的表现，而且这种表现以统计为基础，不需要依赖输入元素的随机性。

　　简单的说，hashtable就像是用一个array来作为容器，把要存储的数据value编码成数字i，然后把value保存到array[i]的位置，以后要搜索该value，就直接取它的编码对应的索引值就行了。

　　这样带来的问题是，array可能需要很大的容量。假如所有元素都是16位无符号整型，需要65536个元素的array；假如所有元素都是32位的，array的大小就要4GB，这太荒谬了。

　　如何解决这个问题呢？办法之一就是使用某种映射函数，将大数映射成小数。负责这个映射过程的函数称为hash function（散列函数），例如TableSize是array的大小，则X%TableSize得到一个范围在0~TableSize-1之间的整数，恰可作为表格的索引。

　　但是使用hash function也显然会遇到一个问题：可能有不同的元素被映射到相同的位置，即所谓的“碰撞”。解决“碰撞”问题的方法有很多种，如线性探测、二次探测、开链等。

SGI STL使用的是开链法。

　　简单的说，开链法就是，array（STL中使用的是vector容器）中的元素不是value，而是一个value的链表list，SGI中把这个list称为桶子(bucket)。

　　hash table的节点定义如下：

template<class Value>
struct __hashtable_node
{
	__hashtable_node* next;
	Value val;
}

　　注意bucket维护的linked list并不是STL的list或slist。

　　hashtable的迭代器中的关键定义如下：

template<class Value, ...>
struct __hashtable_iterator
{
typedef hashtable<Value, ...> hashtable;
typedef __hashtable_node<Value> node;

node* cur; // 迭代器目前所指的节点
hashtable* ht; // 保持对容器的连续关系，因为可能需要从bucket跳到bucket
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& it) const { return cur == it.cur; }
}

　　__hashtable__iterator中定义了递增操作。它的前进操作首先是尝试从目前所指的节点出发，去往该节点的next位置，如果该节点位于list的尾端，即next为空，就跳至下一个bucket，即下一个List的头部节点。

　　迭代器没有定义后退操作，也没有定义reverse iterator。

　　通常，hashtable的窗口大小都是质数。这在线性探测法和二次探测法中意义重大，开链法虽并不需要如此，但SGI仍以质数来要求表格大小，并先将28个质数计算好，并提供外部接口next_size(n)取得比n大的最小质数。

　　hashtable的模板参数相当多：template<class Value, class Key, class HashFunc, class ExtractKey, class EqualKey, class Alloc>，意义分别是：

　　Value：节点实值型别

　　Key：节点键值型别

　　HashFunc：hash function的型别

　　ExtractKey：从节点中取出键值的方法（函数或仿函数）

　　EqualKey：判断键值是否相同的方法

　　Alloc：空间配置器，默认使用std::alloc

　　hashtable的使用方法：

// 客户端程序不能直接include <stl_hashtable.h>，而应该include用到hashtable的容器头文件，如<hash_set.h>或<hash_map.h>
typedef hashtable<int, int, hash<int>, identity<int>, equal_to<int>, alloc> MyHashTable;
MyHashTable iht(50, hash<int>(), equal_to<int>());	// 指定保留50个buckets
cout<<iht.size()<<endl;	// 0
cout<<iht.bucket_count()<<endl;	// 53 这是STL提供的最小质数
cout<<iht.max_bucket_count()<<endl;	// 4294967291 这是STL提供的最大质数

iht.insert_unique(59);
iht.insert_unique(63);
iht.insert_unique(108);
iht.insert_unique(2);
iht.insert_unique(53);
iht.insert_unique(55);
cout<<iht.size()<<endl;	// 6 即hashtable<T>::num_elements()

// 以迭代器遍历hashtable
MyHashTable::iterator it = iht.begin();
for( int i = 0; i< iht.size; i++, it++)
	cout<<*it<<'   ';	// 53, 55, 2, 108, 59, 63
// 遍历所有buckets
for( int i = 0; i< iht.bucket_count(); i++)
{
	int n = iht.elements_in_bucket(i);
}

// 查找元素
it = iht.find(2);
// 获取元素的出现次数
iht.insert_equal(2);
cout<<iht.count(2)<<endl;	// 2