資料結構面試之十三——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");
 
 }