前言

使用哈希表可以進行非常快速的查找操作。但是，哈希表究竟是什麼玩意兒？很多人避而不談，雖然知道經常用到，很多語言的內置數據結構像<code>python/<code>中的字典，<code>java/<code>中的<code>HashMap/<code>，都是基於哈希表實現。但哈希表究竟是啥？

哈希是什麼？

<code>散列（hashing）是電腦科學中一種對資料的處理方法，通過某種特定的函數/算法（稱為散列函數/算法）將要檢索的項與用來檢索的索引（稱為散列，或者散列值）關聯起來，生成一種便於搜索的數據結構（稱為散列表）。也譯為散列。舊譯哈希（誤以為是人名而採用了音譯）。它也常用作一種資訊安全的實作方法，由一串資料中經過散列算法（Hashing algorithms）計算出來的資料指紋（data fingerprint），經常用來識別檔案與資料是否有被竄改，以保證檔案與資料確實是由原創者所提供。/<code> ----Wikipedia

哈希函數

所有的哈希函數都具有如下一個基本特性：如果兩個散列值是不相同的（根據同一函數），那麼這兩個散列值的原始輸入也是不相同的。這個特性是散列函數具有確定性的結果，具有這種性質的散列函數稱為單向散列函數。

哈希表

• 若關鍵字為<code>k/<code>，則其值存放在<code>f(k)/<code>的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關係f為散列函數，按這個思想建立的表為散列表。

• 對不同的關鍵字可能得到同一散列地址，即<code>k1≠k2/<code>，而<code>f(k1)=f(k2)/<code>，這種現象稱為衝突。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。綜上所述，根據散列函數<code>f(k)/<code>和處理衝突的方法將一組關鍵字映射到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址。

• 若對於關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為均勻散列函數（<code>Uniform Hash function/<code>），這就是使關鍵字經過散列函數得到一個“隨機的地址”，從而減少衝突。

建立哈希表

總的來說，哈希表就是一個具備映射關係的表，你可以通過映射關係由鍵找到值。有沒有現成的例子？當然有，不過你直接用就沒意思了。

反正就是要實現<code>f(k)/<code>，即實現<code>key-value/<code>的映射關係。我們試著自己實現一下：

class Map: def __init__(self): self.items=[] def put(self,k,v): self.items.append((k,v)) def get(self,k): for key,value in self.items: if(k==key): return value

這樣實現的<code>Map/<code>，查找的時間複雜度為<code>O(n)/<code>。 “這太簡單了，看上去與<code>key/<code>沒什麼關係啊，這不是順序查找麼，逗我呢？” 這只是一個熱身，好吧，下面我們根據定義，來搞一個有映射函數的：

class Map: def __init__(self): self.items=[None]*100 def hash(self,a): return a*1+0 def put(self,k,v): self.items[hash(k)]=v def get(self,k): hashcode=hash(k) return self.items[hashcode]

“這<code>hash/<code>函數有點簡單啊” 是的，它是簡單，但簡單不妨礙它成為一個哈希函數，事實上，它叫直接定址法，是一個線性函數： hash(k)= a*k+b

“為啥初始化就指定了<code>100/<code>容量？” 必須要指出的是，這個是必須的。你想通過下標存儲並訪問，對於數組來說，這不可避免。在<code>JDK/<code>源碼裡，你也可以看到，<code>Java/<code>的<code>HashMap/<code>的初始容量設成了<code>16/<code>。你可能說，你這<code>hash/<code>函數，我只要<code>key/<code>設為<code>100/<code>以上，這程序就廢了。是啊，它並不完美。這涉及到擴容的事情，稍後再講。

直接定址法的優點很明顯，就是它不會產生重複的<code>hash/<code>值。但由於它與鍵值本身有關係，所以當鍵值分佈很散的時候，會浪費大量的存儲空間。所以一般是不會用到直接定址法的。

處理衝突

假如某個hash函數產生了一堆哈希值，而這些哈希值產生了衝突怎麼辦（實際生產環境中經常發生）？在各種哈希表的實現裡，處理衝突是必需的一步。 比如你定義了一個<code>hash/<code>函數：hash(k)=k mod 10 假設<code>key/<code>序列為：<code>[15,1,24,32,55,64,42,93,82,76]/<code>

<table><thead>0123456789/<thead><tbody>13293241576426455 82/<tbody>/<table>

一趟下來，衝突的元素有四個，下面有幾個辦法。

開放定址法

開放定址法就是產生衝突之後去尋找下一個空閒的空間。函數定義為：

其中，<code>hash(key)/<code>是哈希函數，<code>di/<code>是增量序列，<code>i/<code>為已衝突的次數。

• 線性探測法

• 

即<code>di=i/<code>，或者其它線性函數。相當於逐個探測存放地址的表，直到查找到一個空單元，然後放置在該單元。

[15,1,24,32,55,64,42,93,82,76]

可以看到，在<code>55/<code>之前都還沒衝突：

<table><thead>0123456789/<thead><tbody>1322415 /<tbody>/<table>

此時插入<code>55/<code>，與<code>15/<code>衝突，應用線性探測，此時<code>i=1/<code>，可以得到：

<table><thead>0123456789/<thead><tbody>132241555/<tbody>/<table>

再插入<code>64/<code>，衝突不少，要取到<code>i=3/<code>：

<table><thead>0 123456789/<thead><tbody>13224155564/<tbody>/<table>

插入<code>42/<code>，<code>i=1/<code>：

<table><thead>01234 56789/<thead><tbody>1324224155564/<tbody>/<table>

插入<code>93/<code>，<code>i=5/<code>：

<table><thead>01234567 89/<thead><tbody>132422415556493/<tbody>/<table>

插入<code>82/<code>，<code>i=7/<code>：

<table><thead>0123456789/<thead><tbody> 13242241555649382/<tbody>/<table>

插入<code>76/<code>，<code>i=4/<code>：

<table><thead>0123456789/<thead><tbody>76132 42241555649382/<tbody>/<table>

發現越到後面，衝突的越來越離譜。所以，表的大小選擇也很重要，此例中選擇了<code>10/<code>作為表的大小，所以容易產生衝突。一般來講，越是質數，mod取餘就越可能分佈的均勻。

• 平方探測

這稱作平方探測法，一個道理，也是查找到一個空單元然後放進去。這裡就不一步一步說明了=。=

• 偽隨機探測 <code>di/<code>是一個隨機數序列。 “隨機數？那get的時候咋辦？也是隨機數啊，怎麼確保一致？” 所以說了，是偽隨機數。其實我們在計算機裡接觸的幾乎都是偽隨機數，只要是由確定算法生成的，都是偽隨機。只要種子確定，生成的序列都是一樣的。序列都一樣，那不就可以了麼=。=

鏈表法

這是另外一種類型解決衝突的辦法，散列到同一位置的元素，不是繼續往下探測，而是在這個位置是一個鏈表，這些元素則都放到這一個鏈表上。<code>java/<code>的<code>HashMap/<code>就採用的是這個。

再散列

如果一次不夠，就再來一次，直到衝突不再發生。

建立公共溢出區

將哈希表分為基本表和溢出表兩部分，凡是和基本表發生衝突的元素，一律填入溢出表(注意：在這個方法裡面是把元素分開兩個表來存儲)。

說了這麼一堆，舉個例子，用開放地址法（線性探測）：

class Map: def __init__(self): self.hash_table=[[None,None]for i in range(11)] def hash(self,k,i): h_value=(k+i)%11 if self.hash_table[h_value][0]==k: return h_value if self.hash_table[h_value][0]!=None: i+=1 h_value=self.hash(k,i) return h_value def put(self,k,v): hash_v=self.hash(k,0) self.hash_table[hash_v][0]=k self.hash_table[hash_v][1]=v def get(self,k): hash_v=self.hash(k,0) return self.hash_table[hash_v][1]

“能不能不要定死長度？11個完全不夠用啊”

這是剛才的問題，所以有了另外一個概念，叫做載荷因子（<code>load factor/<code>）。載荷因子的定義為：α= 已有的元素個數/表的長度

由於表長是定值， α與“填入表中的元素個數”成正比，所以， α越大，表明填入表中的元素越多，產生衝突的可能性就越大；反之，α越小，表明填入表中的元素越少，產生衝突的可能性就越小。實際上，散列表的平均查找長度是載荷因子 <code>α/<code>的函數，只是不同處理衝突的方法有不同的函數。

所以當到達一定程度，表的長度是要變的，即<code>resize/<code>=。=像<code>java/<code>的<code>HashMap/<code>，載荷因子被設計為<code>0.75/<code>；超過<code>0.8/<code>，<code>cpu/<code>的<code>cache missing/<code>會急劇上升。可以看下這篇討論：www.zhihu.com/question/22…

具體擴容多少，一般選擇擴到已插入元素數量的兩倍，<code>java/<code>也是這麼做的。

接著上面，再升級一下我們的<code>map/<code>：

class Map: def __init__(self): self.capacity=11 self.hash_table=[[None,None]for i in range(self.capacity)] self.num=0 self.load_factor=0.75 def hash(self,k,i): h_value=(k+i)%self.capacity if self.hash_table[h_value][0]==k: return h_value if self.hash_table[h_value][0]!=None: i+=1 h_value=self.hash(k,i) return h_value def resize(self): self.capacity=self.num*2 #擴容到原有元素數量的兩倍 temp=self.hash_table[:] self.hash_table=[[None,None]for i in range(self.capacity)] for i in temp: if(i[0]!=None): #把原來已有的元素存入 hash_v=self.hash(i[0],0) self.hash_table[hash_v][0]=i[0] self.hash_table[hash_v][1]=i[1] def put(self,k,v): hash_v=self.hash(k,0) self.hash_table[hash_v][0]=k self.hash_table[hash_v][1]=v self.num+=1 #暫不考慮key重複的情況，具體自己可以優化 if(self.num/len(self.hash_table)>self.load_factor):# 如果比例大於載荷因子 self.resize() def get(self,k): hash_v=self.hash(k,0) return self.hash_table[hash_v][1] 

看上面的函數，可以看到<code>resize/<code>是一個比較耗時的操作，因為只是原理教學，所以並沒有什麼奇淫技巧在裡面。可以去看一下<code>Java/<code>的<code>HashMap/<code>的<code>hash/<code>方法和<code>resize/<code>方法，還有處理衝突時的設計（<code>jdk8/<code>及之後的<code>HashMap/<code>用到了紅黑樹），其中的思路要精妙的多。

關於哈希表，原理的東西都基本差不多了。可以看到，它本質要解決的是查找時間的問題。如果順序查找的話，時間複雜度為<code>O(n)/<code>；而哈希表，時間複雜度則為<code>O(1)/<code>！直接甩了一個次元，這也就是為什麼在大量數據存儲查找的時候，哈希表得到大量應用的原因。