數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)溫故-6.查找（下）：哈希表

哈希（散列）技術(shù)既是一種存儲(chǔ)方法，也是一種查找方法。然而它與線性表、樹、圖等結(jié)構(gòu)不同的是，前面幾種結(jié)構(gòu)，數(shù)據(jù)元素之間都存在某種邏輯關(guān)系，可以用連線圖示表示出來，而哈希技術(shù)的記錄之間不存在什么邏輯關(guān)系，它只與關(guān)鍵字有關(guān)聯(lián)。因此，哈希主要是面向查找的存儲(chǔ)結(jié)構(gòu)。哈希技術(shù)最適合的求解問題是查找與給定值相等的記錄。

一、基本概念及原理

1.1 哈希定義的引入

　　這里首先看一個(gè)場(chǎng)景：在大多數(shù)情況下，數(shù)組中的索引并不具有實(shí)際的意義，它僅僅表示一個(gè)元素在數(shù)組中的位置而已，當(dāng)需要查找某個(gè)元素時(shí)，往往會(huì)使用有實(shí)際意義的字段。例如下面一段代碼，它使用學(xué)生的學(xué)號(hào)來查找學(xué)生的地址。

　　（1）學(xué)生實(shí)體類定義

    public class StudentInfo
    {
        public string Number { get; set; }

        public string Address { get; set; }

        public StudentInfo(string number, string address)
        {
            Number = number;
            Address = address;
        }
    }

　　（2）通過索引遍歷查找

        static StudentInfo[] InitialStudents()
        {
            StudentInfo[] arrStudent = {
                new StudentInfo("200807001","四川達(dá)州"),
                new StudentInfo("200807002","四川成都"),
                new StudentInfo("200807003","山東青島"),
                new StudentInfo("200807004","河南鄭州"),
                new StudentInfo("200807005","江蘇徐州")
            };

            return arrStudent;
        }

        static void NormalSearch(StudentInfo[] arrStudent, string searchNumber)
        {
            bool isFind = false;
            foreach (var student in arrStudent)
            {
                if (student.Number == searchNumber)
                {
                    isFind = true;
                    Console.WriteLine("Search successfully!{0} address:{1}", searchNumber, student.Address);
                }
            }

            if (!isFind)
            {
                Console.WriteLine("Search {0} failed!", searchNumber);
            }
        }

        static void Main(string[] args)
        {
            StudentInfo[] arrStudent = InitialStudents();
            // 01.普通數(shù)組遍歷查找
            NormalSearch(arrStudent, "200807005");

            Console.ReadKey();
        }

　　運(yùn)行結(jié)果如下圖所示，可以看到圓滿完成了查找任務(wù)。

　　但是，如果查找的記錄位于數(shù)組的最后或者根本就不存在，仍然需要遍歷整個(gè)數(shù)組。當(dāng)數(shù)組非常巨大時(shí)，還以這樣的方式查找將會(huì)消耗較多的時(shí)間。是否有一種方法可以通過學(xué)號(hào)關(guān)鍵字就能直接地定位到相應(yīng)的記錄？

　　（3）改寫查找方式為哈希查找

　　通過觀察學(xué)號(hào)記錄與索引的對(duì)應(yīng)關(guān)系，學(xué)號(hào)的后三位數(shù)組恰好是一組有序數(shù)列，如果把每個(gè)學(xué)生的學(xué)號(hào)后三位數(shù)組抽取出來并減去1，結(jié)果剛好可以與數(shù)組的索引號(hào)一一對(duì)應(yīng)。于是，我們可以將上例改寫為如下方式：

        static int GetHashCode(string number)
        {
            string index = number.Substring(6);
            return Convert.ToInt32(index) - 1;
        }

        static void HashSearch(StudentInfo[] arrStudent, string searchNumber)
        {
            Console.WriteLine("{0} address:{1}", searchNumber, arrStudent[GetHashCode(searchNumber)].Address);
        }

        static void Main(string[] args)
        {
            StudentInfo[] arrStudent = InitialStudents();

            HashSearch(arrStudent, "200807005");
            HashSearch(arrStudent, "200807001");

            Console.ReadKey();
        }

　　可以看出，通過封裝GetHashCode()方法，實(shí)現(xiàn)了學(xué)號(hào)與數(shù)組索引的一一對(duì)應(yīng)關(guān)系，在查找中直接定位到了索引號(hào)，避免了遍歷操作，從而提高了查詢效率，從原來的O(n)提高到了O(1)，運(yùn)行結(jié)果如下圖所示：

上例中的學(xué)號(hào)是不重復(fù)的，它可以唯一標(biāo)識(shí)學(xué)生集合中的每一條記錄，這樣的字段就被稱為key（關(guān)鍵字）。而在記錄存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系h，使得每個(gè)關(guān)鍵字和一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。在查找時(shí)，只需要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系h，就可以找到所需關(guān)鍵字及其對(duì)應(yīng)的記錄，這種查找方式就被稱為哈希查找，關(guān)鍵字和存儲(chǔ)位置的對(duì)應(yīng)關(guān)系可以用函數(shù)表示為：

h(key)=存儲(chǔ)地址

1.2 構(gòu)造哈希函數(shù)的方法

　　構(gòu)造哈希函數(shù)的目標(biāo)在于使哈希地址盡可能均勻地分布在連續(xù)的內(nèi)存單元地址上，以減少發(fā)生沖突的可能性，同時(shí)使計(jì)算盡可能簡(jiǎn)單以達(dá)到盡可能高的時(shí)間效率，這里主要看看兩個(gè)構(gòu)造哈希函數(shù)的方法。

　　（1）直接地址法

　　直接地址法取關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址，即h(key)=key 或 h(key)=a*key+b

　　其中，a、b均為常數(shù)，這樣的散列函數(shù)優(yōu)點(diǎn)就是簡(jiǎn)單、均勻，也不會(huì)產(chǎn)生沖突，但問題是這需要事先知道關(guān)鍵字的分布情況，適合查找表較小且連續(xù)的情況。由于這樣的限制，在現(xiàn)實(shí)應(yīng)用中，此方法雖然簡(jiǎn)單，但卻并不常用。

　　（2）除留余數(shù)法

　　除留余數(shù)法采用取模運(yùn)算（%）把關(guān)鍵字除以某個(gè)不大于哈希表表長(zhǎng)的整數(shù)得到的余數(shù)作為哈希地址，它也是最常用的構(gòu)造哈希函數(shù)的方法，其形式為：h(key)=key%p

　　本方法的關(guān)鍵就在于選擇合適的p，p如果選得不好，就可能會(huì)容易產(chǎn)生同義詞。

PS：根據(jù)前輩們的經(jīng)驗(yàn)，若哈希表表長(zhǎng)為m，通常p為小于或等于表長(zhǎng)（最好接近m）的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)。

1.3 解決哈希沖突的方法

　　（1）閉散列法

　　閉散列法時(shí)把所有的元素都存儲(chǔ)在哈希表數(shù)組中，當(dāng)發(fā)生沖突時(shí)，在沖突位置的附近尋找可存放記錄的空單元。尋找“下一個(gè)”空位的過程則稱為探測(cè)。上述方法可用如下公式表示為：

　　其中，h(key)為哈希函數(shù)，m為哈希表長(zhǎng)度，di為遞增的序列。根據(jù)di的不同，又可以分為幾種探測(cè)方法：線性探測(cè)法、二次探測(cè)法以及雙重散列法。

　　（2）開散列法

　　開散列法的常見形式是將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中。我們稱這種表為同義詞子表，在散列表中只存儲(chǔ)所有同義詞子表的頭指針。對(duì)于關(guān)鍵字集合{12,67,56,16,25,37,22,29,15,47,48,34}，我們用前面同樣的12為除數(shù)，進(jìn)行除留余數(shù)法，可得到如下圖所示的結(jié)構(gòu)，此時(shí)，已經(jīng)不存在什么沖突換址的問題，無論有多少個(gè)沖突，都只是在當(dāng)前位置給單鏈表增加結(jié)點(diǎn)的問題。

　　該方法對(duì)于可能會(huì)造成很多沖突的散列函數(shù)來說，提供了絕不會(huì)出現(xiàn)找不到地址的保障。當(dāng)然，這也就帶來了查找時(shí)需要遍歷單鏈表的性能損耗。在.NET中，鏈表的各個(gè)元素分散于托管堆各處，也會(huì)給GC垃圾回收帶來壓力，影響程序的性能。

二、.NET中的Hashtable

2.1 Hashtable的用法

　　在.NET中，實(shí)現(xiàn)了哈希表數(shù)據(jù)結(jié)構(gòu)的集合類有兩個(gè)，其中一個(gè)就是Hashtable，另一個(gè)是泛型版本的Dictionary<TKey,TValue>。這里我們首先看看Hashtable的用法，由于Hashtable中key/value鍵值對(duì)均為object類型，所以Hashtable可以支持任何類型的key/value鍵值對(duì)。

        static void HashtableTest()
        {
            // 創(chuàng)建一個(gè)Hashtable實(shí)例
            Hashtable ht = new Hashtable();
            // 添加key/value鍵值對(duì)
            ht.Add("北京", "帝都");
            ht.Add("上海", "魔都");
            ht.Add("廣州", "省會(huì)");
            ht.Add("深圳", "特區(qū)");
            
            // 根據(jù)key獲取value
            string capital = (string)ht["北京"];
            Console.WriteLine("北京：{0}", capital);
            Console.WriteLine("--------------------");
            // 判斷哈希表是否包含特定鍵,其返回值為true或false
            Console.WriteLine("包含上海嗎？{0}",ht.Contains("上海"));
            Console.WriteLine("--------------------");
            // 移除一個(gè)key/value鍵值對(duì)
            ht.Remove("深圳");
            // 遍歷哈希表
            foreach (DictionaryEntry de in ht)
            {
                Console.WriteLine("{0}:{1}", de.Key, de.Value);
            }
            Console.WriteLine("--------------------");
            // 移除所有元素
            ht.Clear();
            // 遍歷哈希表
            foreach (DictionaryEntry de in ht)
            {
                Console.WriteLine("{0}:{1}", de.Key, de.Value);
            }
        }

　　運(yùn)行結(jié)果如下圖所示：

2.2 剖析Hashtable

　　（1）閉散列法

　　Hashtable內(nèi)部使用了閉散列法來解決沖突，它通過一個(gè)結(jié)構(gòu)體bucket來表示哈希表中的單個(gè)元素，這個(gè)結(jié)構(gòu)體有三個(gè)成員：

private struct bucket
{
    public object key;
    public object val;
    public int hash_coll;
}

　　兩個(gè)object類型（那么必然會(huì)涉及到裝箱和拆箱操作）的變量，其中key表示鍵，val表示值，而hash_coll則是一個(gè)int類型，它用于表示鍵所對(duì)應(yīng)的哈希碼。眾所周知，一個(gè)int類型占4個(gè)字節(jié)（這里主要探討32位系統(tǒng)中），一個(gè)字節(jié)又是8位，那么4*8=32位。它的最高位是符號(hào)位，當(dāng)最高位為“0”時(shí)，表示是一個(gè)正整數(shù)，而為“1”時(shí)則表示是一個(gè)負(fù)整數(shù)。hash_coll使用最高位表示當(dāng)前位置是否發(fā)生沖突，為“0”時(shí)也就是正數(shù)時(shí)，表示未發(fā)生沖突；為“1”時(shí)，則表示當(dāng)前位置存在沖突。之所以專門使用一個(gè)標(biāo)志位用于標(biāo)注是否發(fā)生沖突，主要是為了提高哈希表的運(yùn)行效率。

　　（2）雙重散列法

　　Hashtable解決沖突使用了雙重散列法，但又與普通的雙重散列法不同。它探測(cè)地址的方法如下：

　　其中，哈希函數(shù)h1和h2的公式有如下所示：

　　由于使用了二度哈希，最終的h(key,i)的值有可能會(huì)大于hashsize，所以需要對(duì)h(key,i)進(jìn)行取模運(yùn)算，最終計(jì)算的哈希地址為：

　　這里需要注意的是：在bucket結(jié)構(gòu)體中，hash_coll變量存儲(chǔ)的是h(key,i)的值而不是最終的哈希地址。

　　Hashtable通過關(guān)鍵字查找元素時(shí)，首先會(huì)計(jì)算出鍵的哈希地址，然后通過這個(gè)哈希地址直接訪問數(shù)組的相應(yīng)位置并對(duì)比兩個(gè)鍵值，如果相同，則查找成功并返回；如果不同，則根據(jù)hash_coll的值來決定下一步操作。

　　①當(dāng)hash_coll為0或整數(shù)時(shí)，表明沒有沖突，此時(shí)表明查找失敗；

　　②當(dāng)hash_coll為負(fù)數(shù)時(shí)，表明存在沖突，此時(shí)需要通過二度哈希繼續(xù)計(jì)算哈希地址進(jìn)行查找，如此反復(fù)直到找到相應(yīng)的鍵值表明查找成功，如果在查找過程中遇到hash_coll為正數(shù)或計(jì)算二度哈希的次數(shù)等于哈希表長(zhǎng)度則查找失敗。

　　由此可知，將hash_coll的高位設(shè)為沖突檢測(cè)位主要是為了提高查找速度，避免無意義地多次計(jì)算二度哈希的情況。

　　（3）使用素?cái)?shù)實(shí)現(xiàn)hashsize

　　通過查看Hashtable的構(gòu)造函數(shù)，我們可以發(fā)現(xiàn)調(diào)用了HashHelpers的GetPrime方法生成了一個(gè)素?cái)?shù)來為hashsize賦值：

public Hashtable(int capacity, float loadFactor)
{
    .......
    int num2 = (num > 3.0) ? HashHelpers.GetPrime((int) num) : 3;
    this.buckets = new bucket[num2];
    this.loadsize = (int) (this.loadFactor * num2);
    .......
}

　　Hashtable是可以自動(dòng)擴(kuò)容的，當(dāng)以指定長(zhǎng)度初始化哈希表或給哈希表擴(kuò)容時(shí)都需要保證哈希表的長(zhǎng)度為素?cái)?shù)，GetPrime(int min)方法正是用于獲取這個(gè)素?cái)?shù)，參數(shù)min表示初步確定的哈希表長(zhǎng)度，它返回一個(gè)比min大的最合適的素?cái)?shù)。

三、.NET中的Dictionary

3.1 Dictionary的用法

　　Dictionary是泛型版本的哈希表，但和Hashtable之間并非只是簡(jiǎn)單的泛型和非泛型的區(qū)別，兩者使用了完全不同的哈希沖突解決辦法，我們先來看看Dictionary如何使用。

        static void DictionaryTest()
        {
            Dictionary<string, StudentInfo> dict = new Dictionary<string, StudentInfo>();
            for (int i = 0; i < 10; i++)
            {
                StudentInfo stu = new StudentInfo()
                {
                    Number = "200807" + i.ToString().PadLeft(3, '0'),
                    Name = "Student" + i.ToString()
                };
                dict.Add(i.ToString(), stu);
            }

            // 判斷是否包含某個(gè)key
            if (dict.ContainsKey("1"))
            {
                Console.WriteLine("已經(jīng)存在key為{0}的鍵值對(duì)了，它是{1}", 1, dict["1"].Name);
            }
            Console.WriteLine("--------------------------------");
            // 遍歷鍵值對(duì)
            foreach (var de in dict)
            {
                Console.WriteLine("Key:{0},Value:[Number:{1},Name:{2}]", de.Key, de.Value.Number, de.Value.Name);
            }
            // 移除一個(gè)鍵值對(duì)
            if(dict.ContainsKey("5"))
            {
                dict.Remove("5");
            }
            Console.WriteLine("--------------------------------");
            // 遍歷鍵值對(duì)
            foreach (var de in dict)
            {
                Console.WriteLine("Key:{0},Value:[Number:{1},Name:{2}]", de.Key, de.Value.Number, de.Value.Name);
            }
            // 清空鍵值對(duì)
            dict.Clear();
            Console.WriteLine("--------------------------------");
            // 遍歷鍵值對(duì)
            foreach (var de in dict)
            {
                Console.WriteLine("Key:{0},Value:[Number:{1},Name:{2}]", de.Key, de.Value.Number, de.Value.Name);
            }
        }

　　運(yùn)行結(jié)果如下圖所示：

3.2 剖析Dictionary

　　（1）較Hashtable簡(jiǎn)單的哈希地址公式

　　Dictionary的哈希地址求解方式較Hashtable簡(jiǎn)單了許多，其計(jì)算公式如下所示：

　　通過查看其源碼，在Add方法中驗(yàn)證是否是上面的地址計(jì)算方式：

int num = this.comparer.GetHashCode(key) & 0x7fffffff;
int index = num % this.buckets.Length;

　　（2）內(nèi)部?jī)蓚€(gè)數(shù)組結(jié)合的存儲(chǔ)結(jié)構(gòu)

　　Dictionary內(nèi)部有兩個(gè)數(shù)組，一個(gè)數(shù)組名為buckets，用于存放由多個(gè)同義詞組成的靜態(tài)鏈表頭指針（鏈表的第一個(gè)元素在數(shù)組中的索引號(hào)，當(dāng)它的值為-1時(shí)表示此哈希地址不存在元素）；另一個(gè)數(shù)組為entries，它用于存放哈希表中的實(shí)際數(shù)據(jù)，同時(shí)這些數(shù)據(jù)通過next指針構(gòu)成多個(gè)單鏈表。entries中所存放的是Entry結(jié)構(gòu)體，Entry結(jié)構(gòu)體由4個(gè)部分組成，如下所示：

private struct Entry
{
    public int hashCode;
    public int next;
    public TKey key;
    public TValue value;
}

　　Dictionary將多個(gè)鏈表繼承于一個(gè)順序表之中進(jìn)行統(tǒng)一管理：

Hashtable 與 Dictionary 的區(qū)別：

①Hashtable使用閉散列法來解決沖突，而Dictionary使用開散列法解決沖突；

②Dictionary相對(duì)Hashtable來說需要更多的存儲(chǔ)空間，但它不會(huì)發(fā)生二次聚集的情況，并且使用了泛型，相對(duì)非泛型可能需要的裝箱和拆箱操作，Dictionary的速度更快；

③Hashtable使用了填充因子的概念，而Dictionary則不存在填充因子的概念；

④Hashtable在擴(kuò)容時(shí)由于重新計(jì)算哈希地址，會(huì)消耗大量時(shí)間計(jì)算，而Dictionary的擴(kuò)容相對(duì)Hashtable來說更快；

⑤單線程程序中推薦使用Dictionary，而多線程程序中則推薦使用Hashtable。默認(rèn)的Hashtable允許單線程寫入，多線程讀取，對(duì)Hashtable進(jìn)一步調(diào)用Synchronized()方法可以獲得完全線程安全的類型。相反，Dictionary不是線程安全的，必須人為使用lock語句進(jìn)行保護(hù)，效率有所降低。

四、.NET中幾種查找表的對(duì)比

4.1 測(cè)試對(duì)比介紹

　　在.NET中有三種主要的查找表的數(shù)據(jù)結(jié)構(gòu)，分別是SortedDictionary（前面已經(jīng)介紹過了，其內(nèi)部是紅黑樹數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)）、Hashtable與Dictionary。本次測(cè)試會(huì)首先創(chuàng)建一個(gè)100萬個(gè)隨機(jī)排列整數(shù)的數(shù)組，然后將數(shù)組中的數(shù)字依次插入三種數(shù)據(jù)結(jié)構(gòu)中，最后從三種數(shù)據(jù)結(jié)構(gòu)中刪除所有數(shù)據(jù)，每個(gè)操作分別計(jì)算耗費(fèi)時(shí)間（這里計(jì)算操作使用了老趙的CodeTimer類實(shí)現(xiàn)性能計(jì)數(shù)）。

　　（1）準(zhǔn)備工作：初始化一個(gè)100萬個(gè)隨機(jī)數(shù)的數(shù)組

            int length = 1000000;
            int[] arrNumber = new int[length];
            // 首先生成有序數(shù)組進(jìn)行初始化
            for (int i = 0; i < length; i++)
            {
                arrNumber[i] = i;
            }
            Random rand = new Random();
            // 隨機(jī)將數(shù)組中的數(shù)字打亂順序
            for (int i = 0; i < length; i++)
            {
                int randIndex = rand.Next(i,length);
                // 交換兩個(gè)數(shù)字
                int temp = arrNumber[i];
                arrNumber[i] = arrNumber[randIndex];
                arrNumber[randIndex] = temp;
            }

　　（2）測(cè)試SortedDictionary

    // Test1:SortedDictionary類型測(cè)試
    SortedDictionary<int, int> sd = new SortedDictionary<int, int>();
    Console.WriteLine("SortedDictionary插入測(cè)試開始：");
    CodeTimer.Time("SortedDictionary_Insert_Test", 1, () =>
    {
        for (int i = 0; i < length; i++)
        {
            sd.Add(arrNumber[i], arrNumber[i]);
        }
    });
    Console.WriteLine("SortedDictionary插入測(cè)試結(jié)束；");
    Console.WriteLine("-----------------------------");
    Console.WriteLine("SortedDictionary刪除測(cè)試開始：");
    CodeTimer.Time("SortedDictionary_Delete_Test", 1, () =>
    {
        for (int i = 0; i < length; i++)
        {
            sd.Remove(arrNumber[i]);
        }
    });
    Console.WriteLine("SortedDictionary刪除測(cè)試結(jié)束；");
    Console.WriteLine("-----------------------------");

　　（3）測(cè)試Hashtable

    // Test2:Hashtable類型測(cè)試
    Hashtable ht = new Hashtable();
    Console.WriteLine("Hashtable插入測(cè)試開始：");
    CodeTimer.Time("Hashtable_Insert_Test", 1, () =>
    {
        for (int i = 0; i < length; i++)
        {
            ht.Add(arrNumber[i], arrNumber[i]);
        }
    });
    Console.WriteLine("Hashtable插入測(cè)試結(jié)束；");
    Console.WriteLine("-----------------------------");
    Console.WriteLine("Hashtable刪除測(cè)試開始：");
    CodeTimer.Time("Hashtable_Delete_Test", 1, () =>
    {
        for (int i = 0; i < length; i++)
        {
            ht.Remove(arrNumber[i]);
        }
    });
    Console.WriteLine("Hashtable刪除測(cè)試結(jié)束；");
    Console.WriteLine("-----------------------------");

　　（4）測(cè)試Dictionary

    // Test3:Dictionary類型測(cè)試
    Dictionary<int, int> dict = new Dictionary<int, int>();
    Console.WriteLine("Dictionary插入測(cè)試開始：");
    CodeTimer.Time("Dictionary_Insert_Test", 1, () =>
    {
        for (int i = 0; i < length; i++)
        {
            dict.Add(arrNumber[i], arrNumber[i]);
        }
    });
    Console.WriteLine("Dictionary插入測(cè)試結(jié)束；");
    Console.WriteLine("-----------------------------");
    Console.WriteLine("Dictionary刪除測(cè)試開始：");
    CodeTimer.Time("Dictionary_Delete_Test", 1, () =>
    {
        for (int i = 0; i < length; i++)
        {
            dict.Remove(arrNumber[i]);
        }
    });
    Console.WriteLine("Dictionary刪除測(cè)試結(jié)束；");
    Console.WriteLine("-----------------------------");