C#演演算法之雜湊表

2022-04-19 13:00:24

如果所有的鍵都是小整數，我們可以使用一個陣列來實現無序的符號表，將鍵作為陣列的索引而陣列中鍵 i 處儲存的就是它對應的值。雜湊表就是用來處理這種情況，它是簡易方法的擴充套件並能夠處理更加複雜的型別的鍵。我們需要用算術操作將鍵轉換為陣列的索引來存取陣列中的鍵值對。

使用雜湊表的查詢演演算法分為兩步。第一步是用雜湊函數將被查詢的鍵轉換為陣列的一個索引理想情況下，不同的鍵都能轉化為不同的索引值。當然，這只是理想情況，所以我們需要面對兩個或多個鍵都會雜湊到相同的索引值的情況。因此雜湊查詢的第二步是一個處理碰撞衝突的過程。解決碰撞的方法：拉鍊法和線性探測法。

雜湊表是演演算法在時間和空間上作出權衡的經典例子。如果沒有記憶體限制，我們可以直接將鍵直接作為（可能超大）陣列的索引，那麼所有查詢操作只需存取一次即可。另一方面，如果沒有時間限制，我們可以使用無序陣列並進行順序查詢，這樣就只需很少的記憶體。而雜湊表使用了適度的空間和時間並在兩個極端之間找到了一種平衡。我們只需要調整雜湊演演算法的引數就可以在空間和時間之間作出取捨。

使用雜湊表可以實現在一般應用中（均攤後）常數級別的查詢和插入操作的符號表。這使得它在很多情況下成為實現簡單符號表的最佳選擇。

1.雜湊函數

雜湊演演算法的第一個問題就是雜湊函數的計算，這個過程會將鍵轉化為陣列的索引。如果我們有一個能夠儲存 M 個鍵值對的陣列，那麼我們就需要一個能夠將任意鍵轉化為陣列範圍內的索引（[0, M-1] 範圍內的整數）的雜湊函數。我們要找的雜湊函數應該易於計算並且能夠均勻分佈所有的鍵，即對於任意鍵，0 到 M-1 之間的每個整數都有相等的可能性與之對應（與鍵無關）。要理解雜湊，就首先要思考如何去實現一個雜湊函數。

雜湊函數和鍵的型別有關係。嚴格地說，對於每種型別的鍵都需要一個與之對應的雜湊函數。如果鍵是一個數，比如社會保險號，我們就可以直接使用這個數；如果鍵是一個字串，比如一個人的名字，我們就需要將這個字串轉化為一個數；如果鍵含有多個部分，比如郵件地址，我們需要用某種方法將這些部分結合起來。

假設我們有一個應用程式，其中的鍵是美國的社會保險號。諸如123-45-6789之類的社會保險號是分為三個欄位的9位數位。第一個欄位標識地理區域發出號碼的位置（例如，第一個欄位為035的號碼來自羅德島，而第一個欄位為214的號碼來自馬里蘭州），其他兩個欄位標識個人。有十億個不同的社會保險號，但是假設我們的應用程式只需要處理幾百個金鑰，那麼我們就可以使用大小為M = 1000的雜湊表。實現雜湊函數的一種可能方法是使用三個金鑰中的數位。使用右側欄位中的三位數位可能比使用左側欄位中的三位數位更可取（因為客戶在地理區域上可能分佈不均），但是更好的方法是使用所有九位數位一個int值，然後考慮整數的雜湊函數。

正整數

將整數雜湊最常用方法是除留餘數法。我們選擇大小為素數 M 的陣列，對於任意正整數 k ，計算 k 除以 M 的餘數。這個函數的計算簡單並且能有效地將鍵散佈在 0 到 M-1 的範圍內。如果 M 不是素數，我們可能無法利用鍵中包含的所有資訊，可能導致無法均勻地雜湊雜湊值。例如，如果鍵是十進位制數而 M 為 10^k ，那麼我們只能利用鍵的後 k 位。但如果使用素數 97 ，雜湊值的分佈顯然會更好（一個離100更遠的素數會更好）。

浮點數

如果鍵是介於0和1之間的實數，我們可以乘以M並四捨五入為最接近的整數以獲得介於0和M-1之間的索引。儘管很直觀，但是這種方法是有缺陷的，因為它給按鍵的最高有效位賦予了更大的權重。最低有效位不起作用。解決這種情況的一種方法是將鍵表示位二進位制數然後再使用除留餘數法。

字串

除留餘數法也可以處理較長的鍵，如字串，我們只需將它們當作大整數即可：

int hash = 0;
for(int i = 0;i < s.Length;i++)
{
     hash = (R * hash + s.CharAt(i)) % M;  
}

如果 R 比任何字元的值都大，這種計算相當於將字串當作一個 N 位的 R 進位制值，將它除以 M 並取餘。一種叫做 Horner 方法的經典演演算法用 N 次乘法，加法和取餘來計算一個字串的雜湊值。只要 R 足夠小（如 31），不造成溢位，那麼結果就能落在 0 至 M-1 之內。

組合鍵

如果鍵型別具有多個整數位段，則通常可以按照剛才針對String值所述的方式將它們混合在一起。

將 HashCode() 的返回值轉化為一個陣列索引

由於我們的目標是陣列索引，而不是32位元整數，因此我們在實現中將 HashCode() 和除留餘數法結合，以產生0到M-1之間的整數：

private int Hash(Key x)
{
     return (x.HashCode() & 0x7fffffff) % M;  
}

這段程式碼會將符號位遮蔽（將一個 32 位整數變為一個 31 位非負整數），然後用除留餘數法。在使用這樣的程式碼時我們一般會將陣列的大小 M 取為素數以充分利用原雜湊值的所有位。

自定義的 HashCode

自定義的 HashCode() 需要將鍵平均地散佈為所有可能的 32 位整數。也就是說，對於任意物件 x ，呼叫 x.HashCode() 有均等的機會得到 2^32 個不同整數中的任意一個 32 位整數值。更簡單的方法：對範例變數使用hashCode（）方法將每個範例變數轉換為32位元int值，然後進行算術運算。

    public class Transaction
    {
        private string who;
        private string when;
        private double amount;

        public int HashCode()
        {
            int hash = 17;
            hash = 31 * hash + who.GetHashCode();
            hash = 31 * hash + when.GetHashCode();
            hash = 31 * hash + amount.GetHashCode();
            return hash;
        }
    }

係數的具體值（這裡是 31）並不是很重要。

軟快取

如果雜湊值的計算很耗時，那麼我們可以將每個鍵的雜湊值快取起來。第一次呼叫 HashCode() 時，我們需要計算物件的雜湊值，但之後可以直接返回快取。

總的來說，要為一個資料型別實現一個優秀的雜湊方法需要滿足三個條件：

一致性：等價的鍵必然產生相等的雜湊值；
高效性：計算簡便；
均勻性：均勻地雜湊所有的鍵。

在有效能要求時應該謹慎使用雜湊，因為糟糕的雜湊函數經常是效能問題的罪魁禍首。保證均勻性的最好辦法也許就是保證鍵的每一位都在雜湊值的計算中起到了相同的作用。實現雜湊函數最常見的錯誤也許就是忽略了鍵的高位。無論雜湊函數的實現是什麼，當效能很重要時應該測試所使用的雜湊函數：

計算雜湊函數和比較兩個鍵，哪個耗時更多？

你的雜湊函數能夠將一組鍵均勻地散佈在 0到 M-1之間嗎？

用簡單的實現測試這些問題能夠預防未來的悲劇。

這些討論的背後是我們在使用雜湊時作出一個重要的假設（均勻雜湊假設），我們使用的雜湊函數能夠均勻並獨立地將所有鍵散佈於 0 到 M-1 之間。這個假設是一個我們實際上無法達到的理想模型，但它是我們實現雜湊函數時的指導思想。原因有兩點：一是設計雜湊函數時儘量避免隨意指定引數以防止大量的碰撞，這是我們的重要目標；二是它提示我們使用數學分析來預測雜湊演演算法的效能並在實驗中進行驗證。

2.基於拉鍊法的雜湊表

一個雜湊函數能夠將鍵轉化為陣列索引。雜湊演演算法的第二步是碰撞處理，也就是處理兩個或多個鍵的雜湊值相同的情況。一種直接的方法是將大小為 M 的陣列中的每個元素指向一條連結串列，連結串列中的每個結點都儲存了雜湊值為該元素的索引的鍵值對，這種方法稱為拉鍊法。

這個方法的基本思想就是選擇足夠大的 M ，使得所有連結串列都儘可能短以保證高效的查詢。查詢分兩步：首先根據雜湊值找到對應的連結串列，然後沿著連結串列順序查詢對應的鍵。

拉鍊法的一種簡單實現方法是，為 M 個元素分別構建符號表來儲存雜湊到這裡的鍵，可以使用之前查詢樹的程式碼。

因為我們要用 M 條連結串列儲存 N 個鍵，無論鍵在各個連結串列中額分佈如何，連結串列的平均長度肯定是 N/M。

    public class SeparateChainingHashST<Key,Value>
    {
        private int N;//鍵值總對數
        private int M;//雜湊表的大小
        private SequentialSearchST<Key, Value>[] ST;//存放連結串列物件的陣列

        public SeparateChainingHashST(int M)
        {
            this.M = M;
            ST = new SequentialSearchST<Key, Value>()[M];
            for (var i = 0; i < M; i++)
            {
                ST[i] = new SequentialSearchST<Key, Value>();
            }
        }

        private int Hash(Key key)
        {
            return (key.GetHashCode() & 0x7fffffff) % M;
        }

        public Value Get(Key key)
        {
            return ST[Hash(key)].Get(key);
        }

        public void Put(Key key, Value value)
        {
            ST[Hash(key)].Put(key,value);
        }
    }

當你能預知所需要的符號表的大小時，這段短小的方案能夠得到不錯的效能。一種更可靠的方案是動態調整陣列的大小。

在一張含有 M 條連結串列和 N 個鍵的雜湊表中，未命中查詢和插入操作所需的比較次數為～N/M。

雜湊表的大小

在實現基於拉鍊法的雜湊表時，我們的目標是選擇適當的陣列大小 M，既不會因為空連結串列而浪費大量記憶體，也不會因為連結串列太長而在查詢上浪費太多時間。而拉鍊法的一個好處就是這並不是關鍵性的選擇。如果存入的鍵多於預期，查詢所需的時間只會比選擇更大的陣列稍長；如果少於預期，雖然空間浪費但查詢會非常快。當記憶體不是很緊張時，可以選擇一個足夠大的 M，使得查詢需要的時間變為常數；當記憶體緊張時，選擇儘量大的 M 仍然能夠將效能提高 M倍。另一種方法是動態調整陣列的大小以保持短小的連結串列。

刪除操作

要刪除一個鍵值對，先用雜湊值找到含有該鍵的SequentialSearchST 物件，然後呼叫該物件的 Delete 方法。

有序性相關的操作

雜湊最主要的目的在於均勻地將鍵散佈開來，因此在計算雜湊後鍵的順序資訊就丟失了。基於拉鍊法的雜湊表實現簡單，在鍵的順序不重要的應用中，他可能是最快的，也是使用最廣泛的符號表實現。

3.基於線性探測法的雜湊表

實現雜湊表的另一種方式就是用大小為 M 的陣列儲存 N 個鍵值對，其中 M > N 。我們需要依靠陣列中的空位解決碰撞衝突。基於這種策略的所有方法被統稱為開放地址雜湊表。

開放地址雜湊表中最簡單的方法叫做線性探測法：當發生碰撞時（當一個鍵的雜湊值已經被另一個不同的鍵佔用），我們直接檢查雜湊表的下一個位置（將索引值加一）。這樣的線性探測可能會產生三種結果：

命中：該位置的鍵和查詢的鍵相同；
未命中：鍵為空（該位置沒有鍵）；
繼續查詢：該位置的鍵和被查詢的鍵不同。

我們用雜湊函數找到鍵在陣列中的索引，檢查其中的鍵和被查詢的鍵是否相同。如果不用則繼續查詢（將索引增大，到達陣列結尾時折回陣列的開頭），直到找到該鍵或者遇到一個空元素。我們將檢查一個陣列位置是否含有被查詢的鍵的操作稱為探測。

開放地址類的雜湊表的核心思想是與其將記憶體用作連結串列，不如將它們作為在雜湊表的空元素，這些空元素可以作為查詢結束的標誌。我們在實現中使用了並行陣列，一條儲存鍵，一條儲存值。

    public class LinerProbingHashST<Key,Value>
    {
        private int N;//符號表中鍵值對的總數
        private int M = 16;//線性探測表的大小
        private Key[] keys;//鍵
        private Value[] values;//值

        public LinerProbingHashST()
        {
            keys = new Key[M];
            values = new Value[M];
        }

        private int Hash(Key key)
        {
            return (key.GetHashCode() & 0x7ffffff) % M;
        }

        public void Put(Key key, Value value)
        {
            if (N >= M / 2)
                Resize(2*M);
            int i;
            for (i = Hash(key); keys[i] != null; i = (i + 1) % M)
            {
                if (keys[i].Equals(key))
                {
                    values[i] = value;
                    return;
                }
            }

            keys[i] = key;
            values[i] = value;
            N++;

        }

        public Value Get(Key key)
        {
            for(int i = Hash(key);keys[i] != null;i = (i+1)%M)
            {
                if (keys[i].Equals(key))
                    return values[i];
            }

            return default(Value);
        }

        /// <summary>
        /// 調整陣列大小
        /// </summary>
        /// <param name="v"></param>
        private void Resize(int v)
        {
            throw new NotImplementedException();
        }
    }

和拉鍊法一樣，開放地址類的雜湊表的效能也依賴於α = N/M 的比值，但意義有所不同。我們將α 稱為雜湊表的使用率。對於基於拉鍊法的雜湊表，α 是每條連結串列的長度，因此一般大於 1 ；對於基於線性探測的雜湊表，α 是表中已被佔有的空間的比例，它是不可能大於 1 的。事實上，在LinerProbingHashST 中我們不允許α 達到1（雜湊表被佔滿），因為此時未命中的查詢會導致無限迴圈。為了保證效能，會動態調整陣列的大小來保證使用率在 1/8 到 1/2 之間。

刪除操作

如何從基於線性探測的雜湊表中刪除一個鍵？如果直接將該鍵所在的位置設為 null 會使得在此位置之後的元素無法被查詢。因此我們需要將簇中被刪除的右側的所有鍵重新插入列表。

        public void Delete(Key key)
        {
            if (!keys.Contains(key))
                return;

            int i = Hash(key);
            while (!key.Equals(keys[i]))
                i = (i + 1) % M;
            keys[i] = default(Key);
            values[i] = default(Value);

            i = (i + 1) % M;
            while (keys[i] != null)
            {
                Key keyToRedo = keys[i];
                Value valueToRedo = values[i];
                keys[i] = default(Key);
                values[i] = default(Value);
                N--;//重新插入
                Put(keyToRedo,valueToRedo);
                i = (i + 1) % M;
            }

            N--;
            if (N > 0 && N >= M / 8)
                Resize(M/2);
        }

鍵簇

線性探測的平均成本取決於元素再插入陣列後聚整合的一組連續的條目，也叫鍵簇。顯然，短小的鍵簇才能保證較高的效率。隨著插入的鍵越來越多，這個要求很難滿足，較長的鍵簇會越來越多。另外，基於均勻性假設，陣列的每個位置都有相同的可能性被插入一個新鍵，長鍵簇更長的可能性比短鍵簇更大，因為新鍵的雜湊值無論落在簇中的任何位置都會使簇的長度加一。

線性探測法的效能分析

儘管最後的結果的形式相對簡單，準確分析線性探測法的效能是非常有難度的。

在一張大小為 M 並含有 N =α M 個鍵的基於線性探測的雜湊表中，，基於均勻性假設，命中和未命中的查詢所需的探測次數分別為： ~ 1/2 (1 + (1 / (1 - α )) ) 和~ 1/2 (1 + (1 / (1 -α) ^ 2) ) 。特別是當α 約為 1/2 時，查詢命中所需的探測次數約為 3/2 ，未命中所需的約為 5/2 。當α 趨近於 1 時，這些估計值的精確度會下降，我們會保證雜湊表的使用率小於 1/2 。下面我們看看動態調整陣列大小。

調整陣列大小

private void Resize(int cap)
{
    LinearProbingHashST<Key,Value> t = new LinearProbingHashST<Key,Value>(cap);
    for(int i = 0;i<M;i++)
    {
         if(keys[i] != null)
         {
             t.Put(keys[i],values[i]);
         }  
    }  

     keys = t.keys;
     values = t.values;
     M = t.M;
}

動態陣列可以為我們保證α 不大於 1/2 。

拉鍊法

我們可以使用相同的方法在拉連結串列中保持較短的連結串列（平均長度在 2 到 8 之間）：當 N >= 8*M 時，Resize(2*M)；當 N > 0 && N <= 2*M 時，Resize( M/2 )。

對於拉鍊法，如果能準確地估計用例所需的雜湊表的大小，調整陣列的工作並不是必需的，只需根據查詢耗時和（1 + N/M）成正比來選取一個適當的 M 即可。而對於線性探測法，調整陣列的大小是必需的，因為當用例插入的鍵值對數量超過預期時它的查詢時間不僅會變長，還會在雜湊表被填滿時進入無限迴圈。

均攤分析

理論上，當我們動態調整陣列大小時，需要找出均攤成本的上限，因為使雜湊表長度加倍的插入操作需要大量的探測。

假設一張雜湊表能夠自己調整陣列大小，初始為空。基於均勻性假設，執行任意順序的 t 次查詢，插入和刪除操作所需的時間和 t 成正比，所使用的記憶體量總是在表中鍵的總數的常數因子範圍內。

4.記憶體的使用

我們希望將雜湊表的效能調整到最優，理解它的記憶體使用情況是非常重要的。我們可以通過估計參照使用數量來粗略計算所需的記憶體量：除了儲存鍵和值所需的空間之外，我們實現的SeparateChainingHashST 儲存了 M 個SequentialSearchST 物件和它們的參照。每個SequentialSearchST 物件需要 16 位元組，它的每個參照需要 8 位元組。另外還有 N 個 node 物件，每個需要 24 位元組以及三個參照（key , value 和 next），比二叉查詢樹的每個結點還多需要一個參照。在使用動態調整陣列大小來保證表的使用率在 1/8 到 1/2 之間的情況下，線性探測使用 4N 到 16N 個參照。對於原始資料型別，這些計算又有所不同。可以看出，根據記憶體使用來選擇雜湊表的實現並不容易。

方法	N 個元素所需的記憶體（參照型別）
基於拉鍊法的雜湊表	～ 48N + 32M
基於線性探測的雜湊表	在～32N 和～128N 之間
各種二叉查詢樹	～ 56N

還有很多關於實現雜湊表的演演算法，大多數改進都能降低時間 - 空間的曲線：在查詢耗時相同的情況下使用更少的空間，或使在使用相同空間的情況下進行更快的查詢。其他方法包括提供更好的效能保證，如最壞情況下的查詢成本；改進雜湊函數的設計等。

拉鍊法和線性探測的詳細比較取決於實現的細節和用例對空間和時間的要求。即使基於效能考慮，選擇拉鍊法而非線性探測法也不一定是合理的。在實踐中，兩種方法的效能差別主要是因為拉鍊法為每個鍵值對都分配了一小塊記憶體而線性探測則為整張表使用了兩個很大的陣列。對於非常大的雜湊表，這些做法對記憶體管理系統的要求也很不同。

基於均勻性假設，期望雜湊表能支援和陣列大小無關的常數級別的查詢和插入操作是可能的。對於任意的符號表實現，這個期望都是理論上的最優效能。但雜湊表並非包治百病，因為：