数据结构面试之十三——Hash表(散列表)

题注

《面试宝典》有相关习题,但思路相对不清晰,排版有错误,作者对此参考相关书籍和自己观点进行了重写,供大家参考。

1.基本概念

若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function),按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象”作为记录在表中的存储位置,这种表便称为散列表,这一映象过程称为散列造表或散列,所得的存储位置称散列地址

若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

 

2.常用的构造散列函数的方法

散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位。

[1]直接定址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b,其中a和b为常数(这种散列函数叫做自身函数)

[2]数字分析法: 一般取一些大一点的素数,效果更好点。

[3]平方取中法:计算关键值再取中间r位形成一个2^r位的表。

[4]折叠法:把所有字符的ASCII码加起来 (对于字符串)。

[5]随机数法:选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key)=random(key),其中random为随机函数。通常关键字长度不等时采用此法构造哈希函数较恰当。 

[6]除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。这是一种最简单,也是最常用的构造哈希函数的方法。

[7]针对字符串的一些常用方法,比如ELFHash和BKDRHash(更易于编写,效率不错)

 

3.处理冲突的方法

[1]开放定址法;Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列,可有下列三种取法:

di=1,2,3,…, m-1,称线性探测再散列;

di=1^2, -1^2, 2^2,-2^2,3^2, …, ±k^2,(k<=m/2)称二次探测再散列;

di=伪随机数序列,称伪随机探测再散列。

[2]再散列法/再哈希法:Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。

[3]链地址法(拉链法)

[4]建立一个公共溢出区

 

4.查找的性能分析

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到,另一些关键码在散列函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对散列表查找效率的量度,依然用平均查找长度来衡量。

查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:

[1]散列函数是否均匀;

[2]处理冲突的方法;

[3]散列表的装填因子。

散列表的装填因子定义为:α=填入表中的元素个数 /散列表的长度。

α是散列表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,

u  α越大,填入表中的元素较多,产生冲突的可能性就越大;

u  α越小,填入表中的元素较少,产生冲突的可能性就越小。

实际上,散列表的平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。

 

5.简单的Hash表实现

 template <typename _Type>
 class HashTable
 {
 public:
     HashTable(int Length)
     {
                    Element = new _Type[Length];
                    for(int i=0;i<Length;i++)
                   {
                             Element[i] = -1;
                   }
                    this->Length = Length;
                    Count = 0;
     }
 
 
     ~HashTable()
     {
        delete[] Element;
     }
 
 
 
     // Hash函数
     virtual int Hash(_Type Data)
     {
         return Data % Length;
     }
 
 
 
     // 再散列法
     virtual int ReHash(int Index,int Count)
     {
         return ((Index + Count) % Length);
     }
 
     // 查找某个元素是否在表中
     virtual bool SerachHash(_Type Data,int& Index)
     {
        Index = Hash(Data);
        int Count = 0;
 
         while(Element[Index] != -1 && Element[Index] != Data)
           {
             Index = ReHash(Index,++Count);
           }
        return (Data == Element[Index] ? true :false);
     }
 
     virtual int SerachHash(_Type Data)
     {
         int Index = 0;
         if(SerachHash(Data,Index)) 
          {
                return Index;
          }
         else 
          {
               return -1;
          }
     }
 
     // 插入元素
   bool InsertHash(_Type Data)
     {
         int Index = 0;
         if(Count < Length && !SerachHash(Data,Index))
         {
            Element[Index] = Data;
             Count++;
             return true;
         }
         return false;
     }
 
 
 
     // 设置Hash表长度
     void SetLength(int Length)
     {
         delete[] Element;
         Element = new _Type[Length];
                    for(int i=0;i<Length;i++)
                    {
                            Element[i] = -1;
                    }
         this->Length = Length;
     }
 
     // 删除某个元素
     void Remove(_Type Data)
     {
         int Index = SerachHash(Data);
         if(Index != -1)
         {
             Element[Index] = -1;
             Count--;
         }
     }
 
 
     // 删除所有元素
     void RemoveAll()
     {
        for(int i=0;i<Length;i++)
 
         { Element[i] = -1;
         }
         Count = 0;
     }
 
     void Print()
     {
         for(int i=0;i<Length;i++)
 
         {
               printf("%d",Element[i]);
 
         }
         printf("\n");
     }
 protected:
     _Type* Element;           // Hash表
     int Length;               // Hash表大小
     int Count;                // Hash表当前大小
 };
 
 
 
 void main()
 {
     HashTable<int> H(10);
     printf("Hash Length(10)Test:\n");
     int Array[6] = {49,38,65,97,13,49};
     for(int i=0;i<6;i++)
        {
           printf("%d\n",H.InsertHash(Array[i]));
        }
 
     H.Print();
     printf("Find(97):%d\n",H.SerachHash(97));
     printf("Find(49):%d\n",H.SerachHash(49));
     H.RemoveAll();
     H.SetLength(30);
 
     printf("Hash Length(30)Test:\n");
     for(int j=0; j<6; j++)
          {
                    printf("%d\n",H.InsertHash(Array[j]));
          }
     H.Print();
     printf("Find(97):%d\n",H.SerachHash(97));
     printf("Find(49):%d\n",H.SerachHash(49));
     system("pause");
 
 }
上一篇:Google Maps API显示地图的小示例


下一篇:黄聪:VS2010开发如何在c#中使用Ctrl、Alt、Tab等全局组合快捷键