雲計算通俗講義

持續輸出技術幹貨，歡迎關注！

通過本文你将了解：

• 哈希表背景
• 哈希表概述特點
• 哈希算法分類
• 哈希表實現原理
• 哈希表有優缺點
• 散列函數
• 沖突解決
• 哈希表代碼實現
• 哈希表應用場景

假設某大學有10000名同學，每個人的學号是由學院-年級-班級-序号組成，例如學号為16140113表示是16系，14級1班的13号。為了快速查找到13号的成績信息，可以建立一張表，但是不能用學号作為下标，學号的數值實在太大。因此将學号除以1100100取餘，即得到編号作為該表的下标，那麼，要查找學号為16140113的成績的時候，隻要直接訪問表下标為13的數據即可。這就能夠在O(1)時間複雜度内完成成績查找。實際上這裡就用到了散列的思想。

理想散列表（哈希表）是一個包含關鍵字的具有固定大小的數組，它能夠以常數時間執行插入，删除和查找操作。

每個關鍵字被映射到0到數組大小N-1範圍，并且放到合适的位置，這個映射規則就叫散列函數/哈希(hash)函數。

理想情況下，兩個不同的關鍵字映射到不同的單元，然而由于數組單元有限，關鍵字範圍可能遠超數組單元，因此就會出現兩個關鍵字散列到同一個值得時候，這就是散列沖突。

注：那些元素間任何排序信息的操作将不會得到有效的支持，因此，諸如FindMin、FindMax以及線性時間将排過序的整個表進行打印的操作都是散列所不支持的。

特點：擁有固定slot（桶）數

如果數據是固定不變的，那麼靜态哈希較為實用。由于這些鍵固定不變，而且可以提前為靜态哈希算法所獲知，因此目錄中的主要頁面數量也會保持穩定。

動态哈希表通常是在發生沖突後slot數量翻倍增長，而增長後畢竟哈希函數也變了，所以還要把舊slot裡的元素重新放置。這種簡單的動态哈希(dynamic hash)算法便是SGI版的STL中hash_map的實現。

如果數據不固定，那麼靜态哈希的性能就比較低。這種類型的數據适合采用動态哈希技術來處理。

假設有一個大小為7的表，現在，要将13，18，19，50，20散列到表中。主要操作步驟：

1、選擇散列函數，例如使用hash(x)=x%7作為散列函數；

2、計算數據散列值，并放到合适的位置。

具體如下：

計算13 % 7得到6，因此将13放到下标為6的位置：

計算18 % 7得到4，因此将18放到下标為4的位置：

計算19 % 7得到5，因此将19放到下标為5的位置：

計算50 % 7得到1，因此将50放到下标為1的位置：

計算20 % 7得到6，因此将20放到下标為6的位置，但是此時6的位置已經被占用了，因此就産生了散列沖突。

将數據散列之後，如何從表中查找呢？例如，查找數值為50的數據位置，隻需要計算50 % 7，得到下标1，訪問下标1的位置即可。但是如果考慮散列沖突，就沒有那麼簡單了。

優點：

通過關鍵字實現一對一查找速度非常快。

缺點：

存在沖突。

構造散列函數的兩個基本原則：計算簡單 均勻分布

我們可以取關鍵字的某個線性函數值為散列地址，即f(key)=a*key b（通過關鍵字的加減乘除等運算計算地址）。

這種方法簡單均勻，但是我們需要事先知道關鍵字的分布情況，适合查找表比較小且連續的情況，比如按照年月日進行計算。

數字分析法通常适合處理關鍵字位數比較大的情況，例如我們現在要存儲某家公司員工登記表，如用手機号作為關鍵字，那麼我們發現抽樣後面的四位數字作為散列地址是不錯的選擇。

平方取中法是将關鍵字平方之後取中間若幹位數字作為散列地址。

比較适合于不知道關鍵字的分布且位數不是很大的情況。

折疊法是将關鍵字從左到右分割成位數相等的幾部分，然後将這幾部分疊加求和，并按散列表表長後幾位作為散列地址。

适合于不知道關鍵字分布且位數較多的情況。

除留餘數法為最常用的構造散列函數方法，對于散列表長為m的散列函數計算公式為：

f(key) = key mod p(p<=m)

注：p的選擇是關鍵！

選擇一個随機數，取關鍵字的随機函數值為它的散列地址。即：

f(key) = random(key)

這裡的random是随機函數，當關鍵字的長度不等時，采用這個方法構造散列函數是比較合适的。

在實際應用中，我們應該視不同的情況采用不同的散列函數，主要考慮：

1、 計算散列地址所需的時間；

2、 關鍵字的長度；

3、 散列表的大小；

4、 關鍵字的分布情況；

5、 記錄查找的頻率。

分離鍊接法/鍊地址法的做法是将同一個值的關鍵字（即哈希結果相同）保存在同一個單鍊表中。這種方法的特點是需要另外分配新的單元來存儲散列到同一個位置的數據。例如，對于前面：

如果再要插入元素20，則在下标為6的位置存儲表頭，而表的内容是13和20。

若選定的哈希表長度為m，則可将哈希表定義為一個長度為m的指針數組t[0…m-1]，指針數組中的每個指針指向哈希函數結果相同的單鍊表。

插入值：将元素value插入哈希表，若元素value的哈希函數值為hash_key，将value對應的節點的頭插法的方式插入到以t[hash_key]為頭指針的單鍊表中（采用頭插法插入每次都是插入到頭指針的next，這樣不需要遍曆鍊表，也不需要設置尾指針NULL，插入複雜度為O(1)）。

查找值：若元素value的哈希函數值為hash_key，遍曆以t[hash_key]為頭指針的單鍊表，查找鍊表各個節點的值域是否為value、

查找的時候，除了根據計算出來的散列值找到對應位置外，還需要在鍊表上進行搜索。而在單鍊表上的查找速度是很慢的。另外散列函數如果設計得好，沖突的概率其實也會很小。

分離鍊接散列算法的缺點是需要指針，由于給新單元分配地址需要時間，因此這就導緻算法的速度多少有些減慢，同時算法實際上還需要對另一種數據結構的實現。除了使用鍊表解決沖突外，開放定址散列法是另外一種用鍊表解決沖突的方法。在開放定址散列算法系統中，如果有沖突發生，那麼就要嘗試選擇另外的單元，直到找出空的單元為止。因為所有的數據都要置入表内，所以開放定址散列法所需要的表要比分離鍊接散列算法用表大。一般來說，對于開放定址散列算法來說，裝填因子應該低于λ=0.5。

開放定址法的思想是，如果沖突發生，就選擇另外一個可用/空的位置。隻要散列表足夠大，空的/可用的散列地址總能找到，并将記錄存入。

開放定址法中也有常見的幾種策略。

1、線性探測法

公式：

fi(key) = (s(key) di) MOD m (di=1,2,…,m-1)

還是以前面的為例：

如果此時再要插入20，則20 % 7 = 6，但是6的位置已有元素，因此探測下一個位置（6 1）%7，在這裡就是下标為0的位置。因此20的存儲位置如下：

但這種方式的一個問題是，可能造成一次聚集，因為一旦沖突發生，為了處理沖突就會占用下一個位置，而如果沖突較多時，就會出現數據都聚集在一塊區域。這樣就會導緻任何關鍵字都需要多次嘗試才可能解決沖突。

2、平方探測法

顧名思義，如果說前面的探測函數是f(i)= i % 7，那麼平方探測法就是f(i)= (i^2 )% 7。

可以修改di的取值方式，例如使用平方運算來盡量解決堆積問題：

fi(key) = (f(key) di) MOD m (di=12,-12,22,-22,…q2,-q2,q<=m/2)

但是平方探測法同樣會産生二次聚集問題。

3、雙散列

為了避免聚集，在探測時選擇跳躍式的探測，即再使用一個散列函數，用來計算探測的位置。

在沖突時，對于位移量di采用随機函數計算得到，我們稱之為随機探測法，公式：

fi(key) = (f(key) di) MOD m (di是由一個随機函數獲得的數列)

假設前面的散列函數為hash1(X)，用于探測的散列函數為hash2(X)，那麼一種流行的選擇是f(i) = i * hash2(X)，即第一次沖突時探測hash1(X) hash2(X)的位置，第二次探測hash1(X) 2hash2(X)的位置。

可以看到，無論是哪種開放定址法，它都要求表足夠大。

7.3 再散列函數法

散列表可以認為是具有固定大小的數組，那麼如果插入新的數據時散列表已滿，或者散列表所剩容量不多該怎麼辦？這個時候就需要再散列，常見做法是，建立一個是原來兩倍大小的散列表，将原來表中的關鍵字重新散列到新表中。

公式：

fi(key) = RHi(key) (1,2,3,…k)

注：RH為各種散列函數。

實際應用中真正構造哈希表的還是拉鍊法，其餘方法在沖突和平均複雜度方面不具備優勢。

分離鍊接法（separatechaining）是目前工程實踐中最好的一種方式。

#define HASHSIZE 12 #define NULLKEY -32768 typedef struct { int *elem; //數據元素的基址,動态分配數組(數據域) int count; //當前數據元素個數 }HashTable;

int InitHashTable(HashTable *H) { H->count = HASHSIZE; H->elem = (int *)malloc(HASHSIZE * sizeof()int); //也可以直接使用固定大小的數組，但是哈希表大小可能需要動态調整，使用指針比較合适 if(!H->elem) { return -1; } for(i=0;i<HASHSIZE;i ) { H->elem[i] = NULLKEY; } return 0; } //使用除留餘數法 int Hash(int key) { return key % HASHSIZE; }

//插入關鍵字到散列表 void InsertHash(HashTable *H, int key) { int addr; addr = Hash(key); while(H->elem[addr]!=NULLKEY) //如果不為空,則沖突出現(沖突處理) { addr = (addr 1)%HASHSIZE; //開放定址法線性探測(可采用多種方法) } H->elem[addr] = key; }

//散列表查找關鍵字 int SearchHash(HashTable H, int key, int *addr) { *addr = Hash(key); while(H.elem[*addr]!=key) { *addr = (*addr 1)%HASHSIZE; if(H.elem[*addr] == NULLKEY || *addr == Hash(key)) { return -1; } } }

散列表應用很廣泛。例如做文件校驗或數字簽名。當然還有快速查詢功能的實現。例如，redis中的字典結構就使用了散列表，使用MurmurHash算法來計算字符串的hash值，并采用拉鍊法處理沖突，，當散列表的裝載因子（關鍵字個數與散列表大小的比）接近某個大小時，進行再散列。

下面主要介紹哈希表在數據庫中的應用：

1、哈希查找

哈希查找，由于哈希算法能夠很好的把數據做比較均勻的分布，所以哈希查找的速度要比B Tree查找的速度要快。哈希查找的時間複雜度是O(1)，而B Tree的時間複雜度是O(h)。當然，B Tree的優勢是在範圍查找，不然也不會成為關系型數據庫的基本算法了。

SQL Server在做聯接(JOIN)的時候，如果兩個表都不是很小，而且沒有在關聯列上排序，就很可能使用哈希聯接。哈希聯接使用的就是哈希查找，它的性能并不差，但是要注意的一點是，哈希聯接需要先構造一個哈希表，而哈希表需要消耗不小的内存空間，如果數據庫服務器的内存不足的話，SQL Server就隻好使用“優雅的哈希聯接”(Grace HASH JOIN)或者遞歸哈希聯接(Recursive Hash Join)，這樣性能就會受到影響了。在設計數據庫的時候，我們應該注意建立/更新适當的索引和統計信息(STATISTICS)，以便SQL Server可以準确的估計聯接的輸入大小，以便選擇正确的算法。

2、HashMap

哈希表結構（鍊表散列：數組 鍊表）實現，結合數組和鍊表的優點。當鍊表長度超過8時，鍊表轉換為紅黑樹。

HashMap是基于哈希表實現的，每一個元素是一個key-value對，其内部通過單鍊表解決沖突問題，容量不足（超過了閥值）時，同樣會自動增長。

HashMap的存儲結構，如下圖所示：

圖中，紫色部分即代表哈希表，也稱為哈希數組，數組的每個元素都是一個單鍊表的頭節點，鍊表是用來解決沖突的，如果不同的key映射到了數組的同一位置處，就将其放入單鍊表中。

從HashMap的底層結構中我們可以看到，HashMap采用是數組 鍊表/紅黑樹的組合來作為底層結構，也就是開放地址法 鍊地址法的方式來實現HashMap。

3、一緻性哈希