算法导论第十一章 散列表

一、散列表的概念

本章介绍了散列表（or hash table）的概念、散列函数的设计及哈希冲突的处理。散列表（为了形象描述，我们通常叫槽）从表意上看是一种数据结构，但把它归为算法思想更为贴切。对于大部分的查找问题，使用散列表能达到O(1)的效率。现在很多大公司在面试大数据的题目时，解决方案里绝对少不了散列表的思想，例如百度的一道面试题：Top K查找问题：

问题描述：
    搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
    假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

当数据量很大的时候，要保证效率，这时采用hash表来处理是最佳的解决方案。（详细可见July的博客：从头到尾解析hash表算法）。

散列表的实现是通过key-value的形式，将一个需要处理的元素通过某种方式计算key，然后通过key映射到散列表中相应的位置进行value的存储，访问的时候也是同样的思路，其中映射方式通过散列函数来实现。这样简单的一句话，其中蕴含着很多概念：

1）直接寻址表：key == value，直接存储，没有任何计算，前提是value的全域U很小时。

2）散列表：散列函数_HashFunction(value) = key，全域U很大，表有限，通过散列函数将value映射到一个较小的槽，以节省空间。

3）散列函数：散列函数设计的好坏，决定了不同的value映射到相同槽中，即冲突的概率的程度。此有三种设计的思路。

4）散列冲突：好的散列函数能够一定程度上避免冲突，由于随机性，冲突一定会发生。此有两种避免冲突的方法。

二、散列函数的设计：

好的散列函数的设计能达到事半功倍的效果，那怎么样设计一个好的散列函数呢？回答这个问题需要一定的数学底子，尤其是数论，据前人计算机科学家们多年的总结整理，有这样的三种设计方法，我们不纠结这些方法是如何设计出来，那样就违背了我们学习算法的原则，当然如果你想深究，那是甚好。

1、除法散列法：hash(key) = key % m

其中，m是散列表的大小，该函数的一个指导原则是将m选取为接近散列集合大小的质数。

2、乘法散列法：hash(key) = floor( m * ( key * A ) % 1)

其中，floor()表示下取整，m无任何特殊要求，A\in (0,1)，Don.Knuth认为A=(√5-1)/2（黄金分割点）最好。

3、全域散列法：hash_a,b(key)= ( (a * key + b) % p ) % m

全域散列法的基本思想是：一个固定的散列函数有诸多弊端，譬如说容易被恶意的人随意篡改，将所有关键字映射到一个槽中。这个时候引入随机性可以避免这种弊端：对于每一个关键字，随机选择散列函数，使之独立于要存储的关键字。这样就需要提供一组散列函数供选择，这一组散列函数，能将全域U内的所有关键字映射到槽{0,1,…,m-1}中，故称为全域散列。那如何设计一个全域散列函数类？也是前人已经从数学层面上帮我们想好了，就是上面这个式子。

其中，a \in {0,1,…,m-1}， b \in {0,1,…,m-1}，a, b的值都为运行时动态确定，同除法散列一样，m应为质数，p为一个较大的素数。由于a,b的值在运行时随机确定，所以可以形成一个m * (m-1)的散列函数簇。基于随机的思想，全域散列法不管在什么情况下，其平均性能是最好的。

三、Hash冲突的处理

即使设计了好的Hash函数，但还是不可避免Hash冲突。从宏观上看，有两种方法可以处理Hash冲突，一种是开放寻址法，另一种是链表法。其中，开放寻址法又细分为：线性探查法，二次探查法，双重散列法；链表法和桶排序的思想一样，位每一个槽建立一些个桶来存放散列值相同的value，由于这种方法比较简单，本文就不再做记录，后面的算法实现采用的是这种方法。

1、线性探查：h( key , i ) = ( hash ( key ) + i ) % m

其中，hash(key)为前面所说的任何一种散列函数，线性探查的思想是：当发生冲突的时候，以 +i 个槽的方式寻找空的槽，直到所有槽满了为止，故为线性探查，一般 i=1。这种方法的缺陷是容易陷入群集:即随着元素增加，连续被占用的槽也在增加，表面上看就形成元素的堆积，这样，后续元素的平均查找时间也在增加。

2、二次探查：h ( key, i ) = ( hash( key ) + c₁i + c₂i² ) % m

其中，c₁、c₂为正的辅助常数，i = 0,1,…,m-1，和线性探查不同的是，当发生冲突的时候，后续的探查位置加上一个依赖于 i 的二次方的偏移量，这种探查方式比线性探查要好很多。其中，c₁、c₂被证明当皆为1/2时性能最好。缺陷是同样群在二次群集的情况，但相对线性探查要好很多。

3、双重探查：h ( key, i ) = ( hash₁( key ) + i hash₂( key ) ) % m

其中，i = 0,1,…,m-1，hash₁( key ) 、hash₂( key )均为辅助散列函数，双重试探法的首个探查位置为hash₁( key ) 当产生碰撞之后，接下来的探查位置为( hash₁( key ) + hash₂( key ) ) % m，因此我们发现在双重试探法中，不仅初始探查位置依赖于关键字key，探查序列中的增量hash₂(key)同样依赖于关键字key，因而整个散列表提供了m²种不同的探查序列，较之于前两种开放寻址具备了更多的灵活性。

这里需要注意的是：hash₂(key)必须与m互素，有一种比较好的方法是：首先取m为素数，然后，hash₁( key ) = key % m，hash₂( key ) = 1+（k % m‘），其中m’略小于m，比如m’ = m-1。

下面使用链表法实现一个全域散列表，即使用全域散列函数：

 #include <iostream>
 #include <ctime>
 #include <vector>
 #include <iomanip>
 using namespace std;
 
 template<typename T>
 class UniversalHashTable {
 public:
     UniversalHashTable () {
         p = 101;    //一个足够大的质数
         m = 10;        //槽的个数
         _item.resize(m, NULL);
 
         for (int i = 0; i < m; i ++) {
             _item[i] = new _Node();
             _item[i]->m_pNext = NULL;
         }
 
         a = rand() % (p - 1) + 1;
         b = rand() % p;
     }
     
     ~UniversalHashTable() {
         for (int i = 0; i < m; i ++) {
             _Node *pT = _item[i]->m_pNext;
             while (pT) {
                 _Node *p = pT->m_pNext;
                 delete pT;
                 pT = p;
             }
         }
     }
 
     //向散列表中插入一个元素
     void Insert(T const &new_value) {
         //始终插入在键表的头，头结点之后的第一个位置
         _Node *new_item = new _Node();
         new_item->m_nItem = new_value;
         new_item->m_pNext = NULL;
 
         int hash_value = _HashFunction(new_value);
 
         new_item->m_pNext = _item[hash_value]->m_pNext;
         _item[hash_value]->m_pNext = new_item;
     }
 
     //从散列表中删除一个元素
     //@return 是否删除成功的这样的元素
     bool Delete(T const &delete_value) {
         int hash_value = _HashFunction(delete_value);
         _Node *root = _item[hash_value];
 
         while (root->m_pNext) {
             if (root->m_pNext->m_nItem == delete_value) {
                 _Node *temp = root->m_pNext;
                 root->m_pNext = root->m_pNext->m_pNext;
                 delete temp;
                 temp = NULL;
                 return true;
             }
             else
                 root = root->m_pNext;
         }
         return false;
     }
 
     //在散列表中搜索一个元素
     T * Search(T const &search_value) {
         int hash_value = _HashFunction(search_value);
         _Node *root = _item[hash_value]->m_pNext;
 
         while(root) {
             if (root->m_nItem == search_value) {
                 return &(root->m_nItem);
             }
             else
                 root = root->m_pNext;
         }
         return NULL;
     }
 
     //将散列表中所有元素显示在输出流中
     void Display(){
         for (int i = 0; i < m; i ++) {
             _Node *item = _item[i]->m_pNext; //跳过头结点
             cout << "槽[" << setw( 3 ) << i << setw( 3 ) << "]";
             while(item) {
                 cout << " -> " << item->m_nItem;
                 item = item->m_pNext;
             }
             cout << endl;
         }
     }
 
 private:
     struct _Node{
         T        m_nItem;
         _Node    *m_pNext;
     };
 
     //全域散列函数
     //h(a,b,k) = ((a*k+b) mod p) mod m
     int _HashFunction(T key) {
         return static_cast<int>(a * key + b) % p % m;
     }
     
     //除法散列
     int _HashFunctionMul(T key) {
         return static_cast<int> key % m;
     }
 
     //乘法散列
     //floor表示下取整
     int _HashFunctionDiv(T key) {
         return static_cast<int> floor(m * (a * key % 1))
     }
 
     int p, m, a, b;
     vector<_Node *> _item; //用单链表作为散列槽
 };
 
 int main() 
 {
     UniversalHashTable<int> table;
     cout << "往UniversalHashtable里添加内容[0,50):" << endl;
     for (int i = 0; i < 50; i ++) {
         table.Insert(i);
     }
     table.Display();
 
     cout << "开始删除内容[0,5):" << endl;
     for (int i = 0; i < 5; i ++) {
         table.Delete(i);
     }
     table.Display();
     for (int i = 0; i < 10; i ++) {
         int *finded = table.Search(i);
         cout << "开始检索节点[ " << i << " ]:";
         if (finded) 
             cout << *finded << endl;
         else
             cout << "未找到" << endl;
     } 
     return 0;
 }