資料結構面試之十三——Hash表(散清單)

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

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

                   {

                           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]));

    system("pause");

}