序.

数组是最常用的以常数时间插入、存取的一种数据结构。但是数组的索引值只能为正整数，当然对于字符串的处理，我们可以写一个映射函数，将字符串映射为一个index。但是，这样做会不切实际的导致数组的空间急剧增长，内存还是挺吃紧的，就自然不愿意这样干了。

站在巨人的肩膀上，推出了散列表。用武之地相当的广！核心思想是：将大数映射为小数，这样不仅继承了数组的访问、存取效率，还缩减了空间。当然，事物并非完美，散列表也存在瑕疵，但是我们已经在极力的权衡效率。

写在推敲之前

1.散列表元素的插入

散列表的插入很简单，通过映射函数（散列函数）将待存之物（这里没有写整数，因为我们也可以对字符串这样的类型操作）映射为hash key。这就不可避免的导致可能映射为同一个key（出现了碰撞）。

2.散列表元素的删除

至于散列表元素的删除，采用了惰性删除，何为惰性删除？——先将待删除的元素所占的位置给腾出来（不要占着坑嘛^-^），我们对它做一个删除记号，不要到时找不着。如果下次有相同key元素被插入，我们就可以直接把这个位置给它，与nginx里的如出一辙啊。如果我们进行了大量元素插入，进行了表格的重新整理（reshaping），此时在对它进行真正删除，因为在散列表中每一个元素不是独立的，对其他元素的位置是有影响的。概括一下删除：置空，贴标签，后续处理！

3.碰撞处理（也是散列表的性能关键之处）

在元素插入时我们提到了会产生碰撞，下面简述一些经典的解决碰撞的技术。

名词：负载系数loading factor = 元素个数/表格大小

a.线性探测

假设散列函数为key=f(i)，常见的f(i)=i%N;此时对j进行散列时有f(i)=f(j),那么进行线性探测：key=f(j)+f(k),k=1,2,3…。

 

b.二次探测

二次探测就是将一次探测的k换成k^2。为什么这么做？因为在一次探测中，会不可避免的出现有一大块碰撞的表格，待下次进行插入时，我们需要先爬过这些沼泽地，最后才可能击中目标，如此重复，沼泽地面积越来越大，以后的过程更为艰难。这片沼泽地的术语为：主集团（primary clustering）。而二次探测是为缓解这个问题诞生的，但不是完美的解决方案。

c.开链法

开链法维护为每一个碰撞的槽位维护了一个链表。相同的的key被填入该槽位的链表中，（以头插方式维护）。

d.其他处理方法

推敲STL散列表hashtable

• hashtable数据结构

STL是以开链法解决散列的碰撞的。先让我们hashtable的内部基本构成：

1.桶子（buckets）

这样的叫法我不经常见。至少对我来说比较新鲜。桶可以纳物，数组的特性相似。对于出现碰撞的桶子会维护一个桶子链表bucket list（开链了^-^）。

2.节点（nodes）

此处的节点是链表中的节点：(单链表结构)

template<class Value>

struct __hashtable_node{

__hashtable_node* next; //指向下一节点

Value val;

};

3.buckets底层是以vector实现的，因为其具有动态扩充能力。

4.以素数来设计表格大小

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  };

STL建了一个素数数组，假设插入元素个数为n，函数__stl_next_prime(n)会返回最接近并大于等于n的那个素数。即为bucket size

• hashtable内存管理

内存管理重点谈谈函数resize的设计，因为它伴随着散列的每一次插入操作。

// 调整hashtable的容量 

template 
    
       void  hashtable
     
      ::resize(size_type num_elements_hint)  {    const size_type old_n = buckets.size();    // 如果新调整的大小当前大小才进行调整    if (num_elements_hint > old_n) {      const size_type n = next_size(num_elements_hint);      // 如果已经到达hashtable的容量的极限, 那么也不进行更改      if (n > old_n) {        // 建立新的线性表来扩充容量        vector
      
         tmp(n, (node*) 0);        __STL_TRY {          // 重新进行元素的散列操作！        for (size_type bucket = 0; bucket < old_n; ++bucket) {            node* first = buckets[bucket];  //每一个bucket聚合物          while (first) {              size_type new_bucket = bkt_num(first->val, n);  //新的散列key            buckets[bucket] = first->next;              first->next = tmp[new_bucket]; //进行头插操作             tmp[new_bucket] = first;              first = buckets[bucket]; //已经指向下一个node           }          }          buckets.swap(tmp);        }      }    }  }
      
     
    

 

• 衍生容器set（hash_set）

区别于基于红黑树实现的set，hash_set没有自动排序机制。操作与set类似。此处不作赘述。

• 衍生容器map(hash_map)

区别于基于红黑树实现的map，hash_map没有自动排序机制。操作与map类似。此处不作赘述。