您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

算法导论第十一章 散列表

时间:07-22来源:作者:点击数:

一、散列表的概念

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

当数据量很大的时候,要保证效率,这时采用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、全域散列法:hasha,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 ) + c1i + c2i2 ) % m

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

3、双重探查:h ( key, i ) = ( hash1( key ) + i hash2( key ) ) % m

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

这里需要注意的是:hash2(key)必须与m互素,有一种比较好的方法是:首先取m为素数,然后,hash1( key ) = key % m,hash2( 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;
 }
方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
上一篇:很抱歉没有了 下一篇:算法---冒泡排序
推荐内容
相关内容
栏目更新
栏目热门