摘要：散列表用的是數組支持按照下標隨機訪問數據的特性，所以散列表其實就是數組的一種擴展，由數組演化而來。我們可以把它定義成，其中表示元素的鍵值，的值表示經過散列函數計算得到的散列值。

祝愿大家不要像菜菜這般苦逼，年中獎大大滴
在沒有年終獎的日子里，工作依然還要繼續.....一張冰與火的圖盡顯無奈

還記得菜菜不久之前設計的用戶空間嗎？沒看過的同學請進傳送門=》設計高性能訪客記錄系統

還記得遺留的什么問題嗎？菜菜來重復一下，在用戶訪問記錄的緩存中怎么來判斷是否有當前用戶的記錄呢？鏈表雖然是我們這個業務場景最主要的數據結構，但并不是當前這個問題最好的解決方案，所以我們需要一種能快速訪問元素的數據結構來解決這個問題？那就是今天我們要談一談的 散列表

散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
散列表其實可以約等于我們常說的Key-Value形式。
散列表用的是數組支持按照下標隨機訪問數據的特性，所以散列表其實就是數組的一種擴展，由數組演化而來。可以說，如果沒有數組，就沒有散列表。為什么要用數組呢？因為數組按照下標來訪問元素的時間復雜度為O（1），不明白的同學可以參考菜菜以前的關于數組的文章。既然要按照數組的下標來訪問元素，必然也必須考慮怎么樣才能把Key轉化為下標。這就是接下來要談一談的散列函數。

散列函數

散列函數通俗來講就是把一個Key轉化為數組下標的黑盒。散列函數在散列表中起著非常關鍵的作用。
散列函數，顧名思義，它是一個函數。我們可以把它定義成hash(key)，其中 key 表示元素的鍵值，hash(key) 的值表示經過散列函數計算得到的散列值。
那一個散列函數有哪些要求呢？

散列函數計算得到的值是一個非負整數值。

如果 key1 = key2，那hash(key1) == hash(key2)

如果 key1 ≠ key2，那hash(key1) ≠ hash(key2)

簡單說一下以上三點，第一點：因為散列值其實就是數組的下標，所以必須是非負整數（>=0），第二點：同一個key計算的散列值必須相同。
重點說一下第三點，其實第三點只是理論上的，我們想象著不同的Key得到的散列值應該不同，但是事實上，這一點很難做到。我們可以反證一下，如果這個公式成立，我計算無限個Key的散列值，那散列表底層的數組必須做到無限大才行。像業界比較著名的MD5、SHA等哈希算法，也無法完全避免這樣的沖突。當然如果底層的數組越小，這種沖突的幾率就越大。所以一個完美的散列函數其實是不存在的，即便存在，付出的時間成本，人力成本可能超乎想象。

散列沖突

既然再好的散列函數都無法避免散列沖突，那我們就必須尋找其他途徑來解決這個問題。

尋址

如果遇到沖突的時候怎么辦呢？方法之一是在沖突的位置開始找數組中空余的空間，找到空余的空間然后插入。就像你去商店買東西，發現東西賣光了，怎么辦呢？找下一家有東西賣的商家買唄。
不管采用哪種探測方法，當散列表中空閑位置不多的時候，散列沖突的概率就會大大提高。為了盡可能保證散列表的操作效率，一般情況下，我們會盡可能保證散列表中有一定比例的空閑槽位。我們用裝載因子（load factor）來表示空位的多少。

散列表的裝載因子 = 填入表中的元素個數 / 散列表的長度

裝載因子越大，說明空閑位置越少，沖突越多，散列表的性能會下降. 假設散列函數為 f=(key%1000),如下圖所示

鏈地址法（拉鏈法）

拉鏈法屬于一種最常用的解決散列值沖突的方式。基本思想是數組的每個元素指向一個鏈表，當散列值沖突的時候，在鏈表的末尾增加新元素。查找的時候同理，根據散列值定位到數組位置之后，然后沿著鏈表查找元素。如果散列函數設計的非常糟糕的話，相同的散列值非常多的話，散列表元素的查找會退化成鏈表查找，時間復雜度退化成O（n）

再散列法

這種方式本質上是計算多次散列值，那就必然需要多個散列函數，在產生沖突時再使用另一個散列函數計算散列值，直到沖突不再發生，這種方法不易產生“聚集”，但增加了計算時間。

建立一個公共溢出區

至于這種方案網絡上介紹的比較少，一般應用的也比較少。可以這樣理解：散列值沖突的元素放到另外的容器中，當然容器的選擇有可能是數組，有可能是鏈表甚至隊列都可以。但是無論是什么，想要保證散列表的優點還是需要慎重考慮這個容器的選擇。

這里需要在強調一次，散列表底層依賴的是數組按照下標訪問的特性（時間復雜度為O(1）），而且一般散列表為了避免大量沖突都有裝載因子的定義，這就涉及到了數組擴容的特性：需要為新數組開辟空間，并且需要把元素copy到新數組。如果我們知道數據的存儲量或者數據的大概存儲量，在初始化散列表的時候，可以盡量一次性分配足夠大的空間。避免之后的數組擴容弊端。事實證明，在內存比較緊張的時候，優先考慮這種一次性分配的方案也要比其他方案好的多。

散列表的尋址方案中，有一種特殊情況：如果我尋找到數組的末尾仍然無空閑位置，怎么辦呢？這讓我想到了循環鏈表，數組也一樣，可以組裝一個循環數組。末尾如果無空位，就可以繼續在數組首位繼續搜索。

關于散列表元素的刪除，我覺得有必要說一說。首先基于拉鏈方式的散列表由于元素在鏈表中，所有刪除一個元素的時間復雜度和鏈表是一樣的，后續的查找也沒有任何問題。但是尋址方式的散列表就不同了，我們假設一下把位置N元素刪除，那N之后相同散列值的元素就搜索不出來了，因為N位置已經是空位置了。散列表的搜索方式決定了空位置之后的元素就斷片了....這也是為什么基于拉鏈方式的散列表更常用的原因之一吧。

在工業級的散列函數中，元素的散列值做到盡量平均分布是其中的要求之一，這不僅僅是為了空間的充分利用，也是為了防止大量的hashCode落在同一個位置，設想在拉鏈方式的極端情況下，查找一個元素的時間復雜度退化成在鏈表中查找元素的時間復雜度O（n），這就導致了散列表最大特性的丟失。

拉鏈方式實現的鏈表中，其實我更傾向于使用雙向鏈表，這樣在刪除一個元素的時候，雙向鏈表的優勢可以同時發揮出來，這樣可以把散列表刪除元素的時間復雜度降低為O（1）。

在散列表中，由于元素的位置是散列函數來決定的，所有遍歷一個散列表的時候，元素的順序并非是添加元素先后的順序，這一點需要我們在具體業務應用中要注意。

有幾個地方菜菜需要在強調一下：

在當前項目中用的分布式框架為基于Actor模型的Orleans，所以我每個用戶的訪問記錄不必擔心多線程問題。

我沒用使用hashtable這個數據容器，是因為hashtable太容易發生裝箱拆箱的問題。

使用雙向鏈表是因為查找到了當前元素，相當于也查找到了上個元素和下個元素，當前元素的刪除操作時間復雜度可以為O(1)

用戶訪問記錄的實體

 class UserViewInfo
    {
        //用戶ID
        public int UserId { get; set; }
        //訪問時間，utc時間戳
        public int Time { get; set; }
        //用戶姓名
        public string UserName { get; set; }
    }

用戶空間添加訪問記錄的代碼

class UserSpace
    {
        //緩存的最大數量
        const int CacheLimit = 1000;
        //這里用雙向鏈表來緩存用戶空間的訪問記錄
        LinkedList cacheUserViewInfo = new LinkedList();
        //這里用哈希表的變種Dictionary來存儲訪問記錄，實現快速訪問，同時設置容量大于緩存的數量限制，減小哈希沖突
        Dictionary dicUserView = new Dictionary(1250);

        //添加用戶的訪問記錄
        public void AddUserView(UserViewInfo uv)
        {
            //首先查找緩存列表中是否存在，利用hashtable來實現快速查找
            if (dicUserView.TryGetValue(uv.UserId, out UserViewInfo currentUserView))
            {
                //如果存在，則把該用戶訪問記錄從緩存當前位置移除，添加到頭位置
                cacheUserViewInfo.Remove(currentUserView);
                cacheUserViewInfo.AddFirst(currentUserView);
            }
            else
            {
                //如果不存在，則添加到緩存頭部 并添加到哈希表中
                cacheUserViewInfo.AddFirst(uv);
                dicUserView.Add(uv.UserId, uv);
            }
            //這里每次都判斷一下緩存是否超過限制
            if (cacheUserViewInfo.Count > CacheLimit)
            {
                //移除緩存最后一個元素，并從hashtable中刪除,理論上來說，dictionary的內部會兩個指針指向首元素和尾元素，所以查找這兩個元素的時間復雜度為O（1）
                var lastItem = cacheUserViewInfo.Last.Value;
                dicUserView.Remove(lastItem.UserId);
                cacheUserViewInfo.RemoveLast();
            }
        }
    }

添加關注，查看更精美版本，收獲更多精彩