點擊上方藍色字體，關注我們

菜菜呀，前幾天做的用戶空間，用戶反映有時候比較慢呀

CEO,CTO,CFO于一身的CXO

是嗎？

菜菜

我把你拉進用戶反饋群，你解決一下呀

CEO,CTO,CFO于一身的CXO

（完了，以后沒清凈時候了）我盡量吧，X總，我漲工資的事.....

菜菜

這不來年底了嗎，年會獎品可是很豐厚的，希望你抽個一等獎呀，你先出去吧！

CEO,CTO,CFO于一身的CXO

.........,那答應的年終獎的事？

菜菜

不是給你發了200元的京東卡嗎

CEO,CTO,CFO于一身的CXO

.............轉身默默離開，羊駝慢慢飄過....

菜菜

祝愿大家不要像菜菜這般苦逼，年中獎大大滴！！！

在沒有年終獎的日子里，工作依然還要繼續.....一張冰與火的圖盡顯無奈

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

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

散列表

散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表

????散列表其實可以約等于我們常說的Key-Value形式。散列表用的是數組支持按照下標隨機訪問數據的特性，所以散列表其實就是數組的一種擴展，由數組演化而來。可以說，如果沒有數組，就沒有散列表。為什么要用數組呢？因為數組按照下標來訪問元素的時間復雜度為O（1），不明白的同學可以參考菜菜以前的關于數組的文章。既然要按照數組的下標來訪問元素，必然也必須考慮怎么樣才能把Key轉化為下標。這就是接下來要談一談的散列函數。

散列函數

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

那一個散列函數有哪些要求呢？

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

2.??如果 key1 = key2，那hash(key1) == hash(key2)?

3.? 如果 key1 ≠ key2，那hash(key1) ≠ hash(key2)?

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

散列沖突

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

1. 尋址

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

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

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

2. 鏈地址法（拉鏈法）

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

3. 再散列法

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

4. 建立一個公共溢出區

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

擴展閱讀

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

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

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

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

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

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

?Net Core c# 代碼

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

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

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

3.? 使用雙向鏈表是因為查找到了當前元素，相當于也查找到了上個元素和下個元素，當前元素的刪除操作時間復雜度可以為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<UserViewInfo>?cacheUserViewInfo?=?new?LinkedList<UserViewInfo>();
????????//這里用哈希表的變種Dictionary來存儲訪問記錄，實現快速訪問，同時設置容量大于緩存的數量限制，減小哈希沖突
????????Dictionary<int,?UserViewInfo>?dicUserView?=?new?Dictionary<int,?UserViewInfo>(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();
????????????}
????????}
????}

●程序員修仙之路--設計一個實用的線程池●程序員修仙之路--數據結構之CXO讓我做一個計算器●程序猿修仙之路--數據結構之設計高性能訪客記錄系統●程序猿修仙之路--算法之快速排序到底有多快●程序猿修仙之路--數據結構之你是否真的懂數組？

●程序猿修仙之路--算法之希爾排序！

●程序員修仙之路--算法之插入排序！

●程序員修仙之路--算法之選擇排序！

互聯網之路，菜菜與君一同成長

長按識別二維碼關注

聽說轉發文章

會給你帶來好運

總結

以上是生活随笔為你收集整理的程序员修仙之路--把用户访问记录优化到极致的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。