C#算法之散列表怎么定義

本篇內(nèi)容介紹了“C#算法之散列表怎么定義”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

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

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

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

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

1.散列函數(shù)

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

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

假設(shè)我們有一個應(yīng)用程序，其中的鍵是美國的社會保險號。諸如123-45-6789之類的社會保險號是分為三個字段的9位數(shù)字。第一個字段標(biāo)識地理區(qū)域發(fā)出號碼的位置（例如，第一個字段為035的號碼來自羅德島，而第一個字段為214的號碼來自馬里蘭州），其他兩個字段標(biāo)識個人。有十億個不同的社會保險號，但是假設(shè)我們的應(yīng)用程序只需要處理幾百個密鑰，那么我們就可以使用大小為M = 1000的哈希表。實現(xiàn)哈希函數(shù)的一種可能方法是使用三個密鑰中的數(shù)字。使用右側(cè)字段中的三位數(shù)字可能比使用左側(cè)字段中的三位數(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ù)，我們可能無法利用鍵中包含的所有信息，可能導(dǎo)致無法均勻地散列散列值。例如，如果鍵是十進(jìn)制數(shù)而 M 為 10^k ，那么我們只能利用鍵的后 k 位。 但如果使用素數(shù) 97 ，散列值的分布顯然會更好（一個離100更遠(yuǎn)的素數(shù)會更好）。

浮點數(shù)

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

字符串

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

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

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

組合鍵

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

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

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

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

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

自定義的 HashCode

自定義的 HashCode() 需要將鍵平均地散布為所有可能的 32 位整數(shù)。也就是說，對于任意對象 x ，調(diào)用 x.HashCode() 有均等的機(jī)會得到 2^32 個不同整數(shù)中的任意一個 32 位整數(shù)值。更簡單的方法：對實例變量使用hashCode（）方法將每個實例變量轉(zhuǎn)換為32位int值，然后進(jìn)行算術(shù)運(yùn)算。

    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)生相等的散列值；

• 高效性：計算簡便；

• 均勻性：均勻地散列所有的鍵。

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

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

你的散列函數(shù)能夠?qū)⒁唤M鍵均勻地散布在 0到 M-1之間嗎？

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

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

2.基于拉鏈法的散列表

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

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

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

因為我們要用 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);
        }
    }

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

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

散列表的大小

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

刪除操作

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

有序性相關(guān)的操作

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

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

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

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

• 命中：該位置的鍵和查找的鍵相同；

• 未命中：鍵為空（該位置沒有鍵）；

• 繼續(xù)查找：該位置的鍵和被查找的鍵不同。

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

開放地址類的散列表的核心思想是與其將內(nèi)存用作鏈表，不如將它們作為在散列表的空元素，這些空元素可以作為查找結(jié)束的標(biāo)志。我們在實現(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 中我們不允許α 達(dá)到1（散列表被占滿），因為此時未命中的查找會導(dǎo)致無限循環(huán)。為了保證性能，會動態(tài)調(diào)整數(shù)組的大小來保證使用率 在 1/8 到 1/2 之間。

刪除操作

如何從基于線性探測的散列表中刪除一個鍵？如果直接將該鍵所在的位置設(shè)為 null 會使得在此位置之后的元素?zé)o法被查找。因此我們需要將簇中被刪除的右側(cè)的所有鍵重新插入列表。

        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è)，數(shù)組的每個位置都有相同的可能性被插入一個新鍵，長鍵簇更長的可能性比短鍵簇更大，因為新鍵的散列值無論落在簇中的任何位置都會使簇的長度加一。

線性探測法的性能分析

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

在一張大小為 M 并含有 N =α M 個鍵的基于線性探測的散列表中，，基于均勻性假設(shè)，命中和未命中的查找所需的探測次數(shù)分別為： ~ 1/2 (1 + (1 / (1 - α )) ) 和~ 1/2 (1 + (1 / (1 -α) ^ 2) ) 。特別是當(dāng)α 約為 1/2 時，查找命中所需的探測次數(shù)約為 3/2 ，未命中所需的約為 5/2 。當(dāng)α 趨近于 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 之間）：當(dāng) N >= 8*M 時，Resize(2*M)；當(dāng) N > 0 && N <= 2*M 時 ，Resize( M/2 )。

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

均攤分析

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

假設(shè)一張散列表能夠自己調(diào)整數(shù)組大小，初始為空。基于均勻性假設(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），比二叉查找樹的每個結(jié)點還多需要一個引用。在使用動態(tài)調(diào)整數(shù)組大小來保證表的使用率在 1/8 到 1/2 之間的情況下，線性探測使用 4N 到 16N 個引用。對于原始數(shù)據(jù)類型，這些計算又有所不同?？梢钥闯觯鶕?jù)內(nèi)存使用來選擇散列表的實現(xiàn)并不容易。

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

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

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

• 每種類型的鍵都需要一個優(yōu)秀的散列函數(shù)；

• 性能保證來自于散列函數(shù)的質(zhì)量；

• 散列函數(shù)的計算可能復(fù)雜而且昂貴；

• 難以支持有序性相關(guān)的符號表操作。

“C#算法之散列表怎么定義”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！