散列表是典型的以空间换取时间的数据结构；它在插入、删除、查找操作上也具有常数平均时间的表现，但是这种表现是以统计为基础的；
基本知识
（1）负载系数，指元素的个数除以表格大小，除非采用开链法（拉链法），否则负载系数应该在0~1之间；
（2）对应像字符串类型、float这样的类型，如何映射到表上，这时候使用散列函数hash function；hash function带来的问题是可能有不同的元素被映射到相同的位置，这是无法避免的，因为元素的个数有可能会大于表的大小，，这就是碰撞问题；如nginx中有这样一个散列函数：
#define ngx_hash(key, c) ((ngx_uint_t) key * 31 + c)//求槽的位置ngx_uint_tngx_hash_key(u_char *data, size_t len){ngx_uint_t i, key;key = 0;for (i = 0; i < len; i++) {key = ngx_hash(key, data[i]);//key的循环利用}return key;}
（3）解决碰撞的问题，线性探测（线性探测是逐个往下找，遇到惰性删除记号或空元素即可；因此要求表格足够大，但是该假设比较不符合实际，会带来一次群集问题）；二次探测（H为计算的槽位置，二次探测是使用H＋1^2,H-1^2,H＋2^2,H-2^2,……H+i^2,.H-i^2；但是也会带来二次群集的问题）；
（4）在nginx中散列表的建立会预先采用探测的方法来计算合适的表大小，因为nginx中的散列表不支持删除，只能够一次性创建，能够利用探测的方法计算出合适的空间大小；详情请见nginx专题中的hash的介绍；
（5）采用开链法，对每一个槽对于冲突的元素建立一个链表，只要链表足够短，速度还是够快的；在stl中，对于元素个数过多时，会动态调整表的大小，使得冲突的链表元素尽可能小；采用开链法，表格的负载系数将会大于1；
代码分析
（本节选取stl中hashtable的相关代码进行分析）
表格的质数表
static const int __stl_num_primes = 28;//先将28个质数计算好static const unsigned long __stl_prime_list[__stl_num_primes] ={ 53,97,193,389,769, 1543,3079,6151,12289,24593, 49157,98317,196613,393241, 786433, 1572869, 3145739,6291469,12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473ul, 4294967291ul};说明几点
（1）在stl中，表格的大小选取为一个最靠近某个数，并大于等于某个数的质数；通过上述表格来获取，总共有28个质数；
获得合适的表格大小
inline unsigned long __stl_next_prime(unsigned long n){ const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); //找到的是第一个小于等于n的某个质数，若n不存在，返回一个不小于n的元素 return pos == last ? *(last – 1) : *pos;//先判别pos是否与last相等，相等则返回最后一个质数，否则返回相应位置的质数}
桶节点//这个是hashtable的桶所维护的节点template <class Value>struct __hashtable_node{ __hashtable_node* next; //连接下一个桶 Value val;//元素值};
//创建节点 node* new_node(const value_type& obj)//节点空间配置 {node* n = node_allocator::allocate();//申请一块内存n->next = 0;__STL_TRY {construct(&n->val, obj);//构造return n;}__STL_UNWIND(node_allocator::deallocate(n)); }//删除节点 void delete_node(node* n)//节点空间释放 {destroy(&n->val);node_allocator::deallocate(n); }
hastable中的表结构
typedef __hashtable_node<Value> node; vector<node*,Alloc> buckets;//buckets是以vector来做桶的
构造散列表
//hashtable的构造函数 hashtable(size_type n,const HashFcn& hf,const EqualKey& eql): hash(hf), equals(eql), get_key(ExtractKey()), num_elements(0) {initialize_buckets(n); } size_type next_size(size_type n) const { return __stl_next_prime(n); } //获得表的大小 void initialize_buckets(size_type n) {const size_type n_buckets = next_size(n);//知道合适的表大小buckets.reserve(n_buckets);//创建表buckets.insert(buckets.end(), n_buckets, (node*) 0); //每一个表插入节点，为空指针num_elements = 0;//元素的个数为0 }说明几点
（1）buckets中插入的元素为NULL指针；
判断元素的插入位置
size_type bkt_num_key(const key_type& key) const {return bkt_num_key(key, buckets.size()); } //只接受实值 size_type bkt_num(const value_type& obj) const {return bkt_num_key(get_key(obj)); } size_type bkt_num_key(const key_type& key, size_t n) const {return hash(key) % n;//SGI所有内建的hash() } //接受实值和buckets个数 size_type bkt_num(const value_type& obj, size_t n) const {return bkt_num_key(get_key(obj), n); }
散列函数
//对于字符串类型char*的函数的转换函数inline size_t __stl_hash_string(const char* s){ unsigned long h = 0; for ( ; *s; ++s)h = 5*h + *s;return size_t(h);}__STL_TEMPLATE_NULL struct hash<char*>{ size_t operator()(const char* s) const { return __stl_hash_string(s); }};__STL_TEMPLATE_NULL struct hash<const char*>{ size_t operator()(const char* s) const { return __stl_hash_string(s); }};__STL_TEMPLATE_NULL struct hash<char> { size_t operator()(char x) const { return x; }};__STL_TEMPLATE_NULL struct hash<unsigned char> { size_t operator()(unsigned char x) const { return x; }};__STL_TEMPLATE_NULL struct hash<signed char> { size_t operator()(unsigned char x) const { return x; }};__STL_TEMPLATE_NULL struct hash<short> { size_t operator()(short x) const { return x; }};__STL_TEMPLATE_NULL struct hash<unsigned short> { size_t operator()(unsigned short x) const { return x; }};__STL_TEMPLATE_NULL struct hash<int> { size_t operator()(int x) const { return x; }};__STL_TEMPLATE_NULL struct hash<unsigned int> { size_t operator()(unsigned int x) const { return x; }};__STL_TEMPLATE_NULL struct hash<long> { size_t operator()(long x) const { return x; }};__STL_TEMPLATE_NULL struct hash<unsigned long> { size_t operator()(unsigned long x) const { return x; }};
散列表插入元素（元素值不允许重复）而现在我喜欢深邃的夜空，包容一切的黑暗和隐忍，留下眼泪也没人看见。
