如果所有的鍵都是小整數(shù)，我們可以使用一個數(shù)組來實現(xiàn)無序的符號表，將鍵作為數(shù)組的索引而數(shù)組中鍵 i 處存儲的就是它對應的值。散列表就是用來處理這種情況，它是簡易方法的擴展并能夠處理更加復雜的類型的鍵。我們需要用算術操作將鍵轉換為數(shù)組的索引來訪問數(shù)組中的鍵值對。

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

散列表是算法在時間和空間上作出權衡的經(jīng)典例子。如果沒有內(nèi)存限制，我們可以直接將鍵直接作為（可能超大）數(shù)組的索引，那么所有查找操作只需訪問一次即可。另一方面，如果沒有時間限制，我們可以使用無序數(shù)組并進行順序查找，這樣就只需很少的內(nèi)存。而散列表使用了適度的空間和時間并在兩個極端之間找到了一種平衡。我們只需要調(diào)整散列算法的參數(shù)就可以在空間和時間之間作出取舍。

使用散列表可以實現(xiàn)在一般應用中（均攤后）常數(shù)級別的查找和插入操作的符號表。這使得它在很多情況下成為實現(xiàn)簡單符號表的最佳選擇。

1.散列函數(shù)

散列算法的第一個問題就是散列函數(shù)的計算，這個過程會將鍵轉化為數(shù)組的索引。如果我們有一個能夠保存 M 個鍵值對的數(shù)組，那么我們就需要一個能夠將任意鍵轉化為數(shù)組范圍內(nèi)的索引（[0, M-1] 范圍內(nèi)的整數(shù)）的散列函數(shù)。我們要找的散列函數(shù)應該易于計算并且能夠均勻分布所有的鍵，即對于任意鍵，0 到 M-1 之間的每個整數(shù)都有相等的可能性與之對應（與鍵無關）。要理解散列，就首先要思考如何去實現(xiàn)一個散列函數(shù)。

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

假設我們有一個應用程序，其中的鍵是美國的社會保險號。諸如123-45-6789之類的社會保險號是分為三個字段的9位數(shù)字。第一個字段標識地理區(qū)域發(fā)出號碼的位置（例如，第一個字段為035的號碼來自羅德島，而第一個字段為214的號碼來自馬里蘭州），其他兩個字段標識個人。有十億個不同的社會保險號，但是假設我們的應用程序只需要處理幾百個密鑰，那么我們就可以使用大小為M = 1000的哈希表。實現(xiàn)哈希函數(shù)的一種可能方法是使用三個密鑰中的數(shù)字。使用右側字段中的三位數(shù)字可能比使用左側字段中的三位數(shù)字更可?。ㄒ驗榭蛻粼诘乩韰^(qū)域上可能分布不均），但是更好的方法是使用所有九位數(shù)字一個int值，然后考慮整數(shù)的哈希函數(shù)。

正整數(shù)

將整數(shù)散列最常用方法是除留余數(shù)法。我們選擇大小為素數(shù) M 的數(shù)組，對于任意正整數(shù) k ，計算 k 除以 M 的余數(shù)。這個函數(shù)的計算簡單并且能有效地將鍵散布在 0 到 M-1 的范圍內(nèi)。如果 M 不是素數(shù)，我們可能無法利用鍵中包含的所有信息，可能導致無法均勻地散列散列值。例如，如果鍵是十進制數(shù)而 M 為 10^k ，那么我們只能利用鍵的后 k 位。 但如果使用素數(shù) 97 ，散列值的分布顯然會更好（一個離100更遠的素數(shù)會更好）。

浮點數(shù)

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

字符串

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

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

如果 R 比任何字符的值都大，這種計算相當于將字符串當作一個 N 位的 R 進制值，將它除以 M 并取余。一種叫做 Horner 方法的經(jīng)典算法用 N 次乘法，加法和取余來計算一個字符串的散列值。只要 R 足夠?。ㄈ?31），不造成溢出，那么結果就能落在 0 至 M-1 之內(nèi)。

組合鍵

如果鍵類型具有多個整數(shù)字段，則通?？梢园凑談偛裴槍?tt>String值所述的方式將它們混合在一起。

將 HashCode() 的返回值轉化為一個數(shù)組索引

由于我們的目標是數(shù)組索引，而不是32位整數(shù)，因此我們在實現(xiàn)中將 HashCode() 和除留余數(shù)法結合，以產(chǎn)生0到M-1之間的整數(shù)：

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

這段代碼會將符號位屏蔽（將一個 32 位整數(shù)變?yōu)橐粋€ 31 位非負整數(shù)），然后用除留余數(shù)法。在使用這樣的代碼時我們一般會將數(shù)組的大小 M 取為素數(shù)以充分利用原散列值的所有位。

自定義的 HashCode

自定義的 HashCode() 需要將鍵平均地散布為所有可能的 32 位整數(shù)。也就是說，對于任意對象 x ，調(diào)用 x.HashCode() 有均等的機會得到 2^32 個不同整數(shù)中的任意一個 32 位整數(shù)值。更簡單的方法：對實例變量使用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;
        }
    }

系數(shù)的具體值（這里是 31）并不是很重要。

軟緩存

如果散列值的計算很耗時，那么我們可以將每個鍵的散列值緩存起來。第一次調(diào)用 HashCode() 時，我們需要計算對象的散列值，但之后可以直接返回緩存。

總的來說，要為一個數(shù)據(jù)類型實現(xiàn)一個優(yōu)秀的散列方法需要滿足三個條件：

• 一致性：等價的鍵必然產(chǎn)生相等的散列值；
• 高效性：計算簡便；
• 均勻性：均勻地散列所有的鍵。

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

計算散列函數(shù)和比較兩個鍵，哪個耗時更多？

你的散列函數(shù)能夠將一組鍵均勻地散布在 0到 M-1之間嗎？

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

這些討論的背后是我們在使用散列時作出一個重要的假設（均勻散列假設），我們使用的散列函數(shù)能夠均勻并獨立地將所有鍵散布于 0 到 M-1 之間。這個假設是一個我們實際上無法達到的理想模型，但它是我們實現(xiàn)散列函數(shù)時的指導思想。原因有兩點：一是設計散列函數(shù)時盡量避免隨意指定參數(shù)以防止大量的碰撞，這是我們的重要目標；二是它提示我們使用數(shù)學分析來預測散列算法的性能并在實驗中進行驗證。

2.基于拉鏈法的散列表

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

這個方法的基本思想就是選擇足夠大的 M ，使得所有鏈表都盡可能短以保證高效的查找。查找分兩步：首先根據(jù)散列值找到對應的鏈表，然后沿著鏈表順序查找對應的鍵。

拉鏈法的一種簡單實現(xiàn)方法是，為 M 個元素分別構建符號表來保存散列到這里的鍵，可以使用之前查找樹的代碼。

因為我們要用 M 條鏈表保存 N 個鍵，無論鍵在各個鏈表中額分布如何，鏈表的平均長度肯定是 N/M。

    public class SeparateChainingHashST<Key,Value>
    {
        private int N;//鍵值總對數(shù)
        private int M;//散列表的大小
        private SequentialSearchST<Key, Value>[] ST;//存放鏈表對象的數(shù)組

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

當你能預知所需要的符號表的大小時，這段短小的方案能夠得到不錯的性能。一種更可靠的方案是動態(tài)調(diào)整數(shù)組的大小。

在一張含有 M 條鏈表和 N 個鍵的散列表中，未命中查找和插入操作所需的比較次數(shù)為 ～N/M。

散列表的大小

在實現(xiàn)基于拉鏈法的散列表時，我們的目標是選擇適當?shù)臄?shù)組大小 M，既不會因為空鏈表而浪費大量內(nèi)存，也不會因為鏈表太長而在查找上浪費太多時間。而拉鏈法的一個好處就是這并不是關鍵性的選擇。如果存入的鍵多于預期，查找所需的時間只會比選擇更大的數(shù)組稍長；如果少于預期，雖然空間浪費但查找會非?？?。當內(nèi)存不是很緊張時，可以選擇一個足夠大的 M，使得查找需要的時間變?yōu)槌?shù)；當內(nèi)存緊張時，選擇盡量大的 M 仍然能夠將性能提高 M倍。另一種方法是動態(tài)調(diào)整數(shù)組的大小以保持短小的鏈表。

刪除操作

要刪除一個鍵值對，先用散列值找到含有該鍵的SequentialSearchST 對象，然后調(diào)用該對象的 Delete 方法。

有序性相關的操作

散列最主要的目的在于均勻地將鍵散布開來，因此在計算散列后鍵的順序信息就丟失了?；诶湻ǖ纳⒘斜韺崿F(xiàn)簡單，在鍵的順序不重要的應用中，他可能是最快的，也是使用最廣泛的符號表實現(xiàn)。

3.基于線性探測法的散列表

實現(xiàn)散列表的另一種方式就是用大小為 M 的數(shù)組保存 N 個鍵值對，其中 M > N 。我們需要依靠數(shù)組中的空位解決碰撞沖突?；谶@種策略的所有方法被統(tǒng)稱為開放地址散列表。

開放地址散列表中最簡單的方法叫做線性探測法：當發(fā)生碰撞時（當一個鍵的散列值已經(jīng)被另一個不同的鍵占用），我們直接檢查散列表的下一個位置（將索引值加一）。這樣的線性探測可能會產(chǎn)生三種結果：

• 命中：該位置的鍵和查找的鍵相同；
• 未命中：鍵為空（該位置沒有鍵）；
• 繼續(xù)查找：該位置的鍵和被查找的鍵不同。

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

開放地址類的散列表的核心思想是與其將內(nèi)存用作鏈表，不如將它們作為在散列表的空元素，這些空元素可以作為查找結束的標志。我們在實現(xiàn)中使用了并行數(shù)組，一條保存鍵，一條保存值。

    public class LinerProbingHashST<Key,Value>
    {
        private int N;//符號表中鍵值對的總數(shù)
        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>
        /// 調(diào)整數(shù)組大小
        /// </summary>
        /// <param name="v"></param>
        private void Resize(int v)
        {
            throw new NotImplementedException();
        }
    }

和拉鏈法一樣，開放地址類的散列表的性能也依賴于α = N/M 的比值，但意義有所不同。我們將α 稱為散列表的使用率。對于基于拉鏈法的散列表，α 是每條鏈表的長度，因此一般大于 1 ；對于基于線性探測的散列表，α 是表中已被占有的空間的比例，它是不可能大于 1 的。事實上，在LinerProbingHashST 中我們不允許α 達到1（散列表被占滿），因為此時未命中的查找會導致無限循環(huán)。為了保證性能，會動態(tài)調(diào)整數(shù)組的大小來保證使用率 在 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);
        }

鍵簇

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

線性探測法的性能分析

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

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

調(diào)整數(shù)組大小

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

動態(tài)數(shù)組可以為我們保證α 不大于 1/2 。

拉鏈法

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

對于拉鏈法，如果能準確地估計用例所需的散列表的大小，調(diào)整數(shù)組的工作并不是必需的，只需根據(jù)查找耗時和 （1 + N/M）成正比來選取一個適當?shù)?M 即可。而對于線性探測法，調(diào)整數(shù)組的大小是必需的，因為當用例插入的鍵值對數(shù)量超過預期時它的查找時間不僅會變長，還會在散列表被填滿時進入無限循環(huán)。

均攤分析

理論上，當我們動態(tài)調(diào)整數(shù)組大小時，需要找出均攤成本的上限，因為使散列表長度加倍的插入操作需要大量的探測。

假設一張散列表能夠自己調(diào)整數(shù)組大小，初始為空。基于均勻性假設，執(zhí)行任意順序的 t 次查找，插入和刪除操作所需的時間和 t 成正比，所使用的內(nèi)存量總是在表中鍵的總數(shù)的常數(shù)因子范圍內(nèi)。

4.內(nèi)存的使用

我們希望將散列表的性能調(diào)整到最優(yōu)，理解它的內(nèi)存使用情況是非常重要的。我們可以通過估計引用使用數(shù)量來粗略計算所需的內(nèi)存量：除了存儲鍵和值所需的空間之外，我們實現(xiàn)的SeparateChainingHashST 保存了 M 個SequentialSearchST 對象和它們的引用。每個SequentialSearchST 對象需要 16 字節(jié)，它的每個引用需要 8 字節(jié)。另外還有 N 個 node 對象，每個需要 24 字節(jié)以及三個引用（key , value 和 next），比二叉查找樹的每個結點還多需要一個引用。在使用動態(tài)調(diào)整數(shù)組大小來保證表的使用率在 1/8 到 1/2 之間的情況下，線性探測使用 4N 到 16N 個引用。對于原始數(shù)據(jù)類型，這些計算又有所不同。可以看出，根據(jù)內(nèi)存使用來選擇散列表的實現(xiàn)并不容易。

還有很多關于實現(xiàn)散列表的算法，大多數(shù)改進都能降低 時間 - 空間的曲線：在查找耗時相同的情況下使用更少的空間，或使在使用相同空間的情況下進行更快的查找。其他方法包括提供更好的性能保證，如最壞情況下的查找成本；改進散列函數(shù)的設計等。

拉鏈法和線性探測的詳細比較取決于實現(xiàn)的細節(jié)和用例對空間和時間的要求。即使基于性能考慮，選擇拉鏈法而非線性探測法也不一定是合理的。在實踐中，兩種方法的性能差別主要是因為拉鏈法為每個鍵值對都分配了一小塊內(nèi)存而線性探測則為整張表使用了兩個很大的數(shù)組。對于非常大的散列表，這些做法對內(nèi)存管理系統(tǒng)的要求也很不同。

基于均勻性假設，期望散列表能支持和數(shù)組大小無關的常數(shù)級別的查找和插入操作是可能的。對于任意的符號表實現(xiàn)，這個期望都是理論上的最優(yōu)性能。但散列表并非包治百病，因為：

• 每種類型的鍵都需要一個優(yōu)秀的散列函數(shù)；
• 性能保證來自于散列函數(shù)的質(zhì)量；
• 散列函數(shù)的計算可能復雜而且昂貴；
• 難以支持有序性相關的符號表操作。

到此這篇關于C#算法之散列表的文章就介紹到這了。希望對大家的學習有所幫助，也希望大家多多支持腳本之家。