前言
使用哈希表可以進行非常快速的查找操作。但是，哈希表究竟是什麼玩意兒？很多人避而不談，雖然知道經常用到，很多語言的內置數據結構像
python中的字典，java中的HashMap，都是基於哈希表實現。但哈希表究竟是啥？哈希是什麼？
散列（hashing）是電腦科學中一種對資料的處理方法，通過某種特定的函數/算法（稱為散列函數/算法）將要檢索的項與用來檢索的索引（稱為散列，或者散列值）關聯起來，生成一種便於搜索的數據結構（稱為散列表）。也譯為散列。舊譯哈希（誤以為是人名而採用了音譯）。它也常用作一種資訊安全的實作方法，由一串資料中經過散列算法（Hashing algorithms）計算出來的資料指紋（data fingerprint），經常用來識別檔案與資料是否有被竄改，以保證檔案與資料確實是由原創者所提供。 ----Wikipedia
哈希函數
所有的哈希函數都具有如下一個基本特性：如果兩個散列值是不相同的（根據同一函數），那麼這兩個散列值的原始輸入也是不相同的。這個特性是散列函數具有確定性的結果，具有這種性質的散列函數稱為單向散列函數。
哈希表
若關鍵字為
k，則其值存放在f(k)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關係f為散列函數，按這個思想建立的表為散列表。對不同的關鍵字可能得到同一散列地址，即
k1≠k2，而f(k1)=f(k2)，這種現象稱為衝突。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。綜上所述，根據散列函數f(k)和處理衝突的方法將一組關鍵字映射到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址。若對於關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為均勻散列函數（
Uniform Hash function），這就是使關鍵字經過散列函數得到一個“隨機的地址”，從而減少衝突。
建立哈希表
總的來說，哈希表就是一個具備映射關係的表，你可以通過映射關係由鍵找到值。有沒有現成的例子？當然有，不過你直接用就沒意思了。
反正就是要實現f(k)，即實現key-value的映射關係。我們試著自己實現一下：
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
這樣實現的Map，查找的時間複雜度為O(n)。 “這太簡單了，看上去與key沒什麼關係啊，這不是順序查找麼，逗我呢？” 這只是一個熱身，好吧，下面我們根據定義，來搞一個有映射函數的：
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]
“這hash函數有點簡單啊” 是的，它是簡單，但簡單不妨礙它成為一個哈希函數，事實上，它叫直接定址法，是一個線性函數： hash(k)= a*k+b
“為啥初始化就指定了100容量？” 必須要指出的是，這個是必須的。你想通過下標存儲並訪問，對於數組來說，這不可避免。在JDK源碼裡，你也可以看到，Java的HashMap的初始容量設成了16。你可能說，你這hash函數，我只要key設為100以上，這程序就廢了。是啊，它並不完美。這涉及到擴容的事情，稍後再講。
直接定址法的優點很明顯，就是它不會產生重複的hash值。但由於它與鍵值本身有關係，所以當鍵值分佈很散的時候，會浪費大量的存儲空間。所以一般是不會用到直接定址法的。
處理衝突
假如某個hash函數產生了一堆哈希值，而這些哈希值產生了衝突怎麼辦（實際生產環境中經常發生）？在各種哈希表的實現裡，處理衝突是必需的一步。 比如你定義了一個
hash函數：hash(k)=k mod 10 假設key序列為：[15,1,24,32,55,64,42,93,82,76]| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 32 | 93 | 24 | 15 | 76 | ||||
| 42 | 64 | 55 | |||||||
| 82 |
一趟下來，衝突的元素有四個，下面有幾個辦法。
開放定址法
開放定址法就是產生衝突之後去尋找下一個空閒的空間。函數定義為：
其中，hash(key)是哈希函數，di是增量序列，i為已衝突的次數。
線性探測法
即di=i，或者其它線性函數。相當於逐個探測存放地址的表，直到查找到一個空單元，然後放置在該單元。
[15,1,24,32,55,64,42,93,82,76]
可以看到，在55之前都還沒衝突：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 32 | 24 | 15 |
此時插入55，與15衝突，應用線性探測，此時i=1，可以得到：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 32 | 24 | 15 | 55 |
再插入64，衝突不少，要取到i=3：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 32 | 24 | 15 | 55 | 64 |
插入42，i=1：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 32 | 42 | 24 | 15 | 55 | 64 |
插入93，i=5：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 32 | 42 | 24 | 15 | 55 | 64 | 93 |
插入82，i=7：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 32 | 42 | 24 | 15 | 55 | 64 | 93 | 82 |
插入76，i=4：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 76 | 1 | 32 | 42 | 24 | 15 | 55 | 64 | 93 | 82 |
發現越到後面，衝突的越來越離譜。所以，表的大小選擇也很重要，此例中選擇了10作為表的大小，所以容易產生衝突。一般來講，越是質數，mod取餘就越可能分佈的均勻。
平方探測
這稱作平方探測法，一個道理，也是查找到一個空單元然後放進去。這裡就不一步一步說明了=。=
偽隨機探測
di是一個隨機數序列。 “隨機數？那get的時候咋辦？也是隨機數啊，怎麼確保一致？” 所以說了，是偽隨機數。其實我們在計算機裡接觸的幾乎都是偽隨機數，只要是由確定算法生成的，都是偽隨機。只要種子確定，生成的序列都是一樣的。序列都一樣，那不就可以了麼=。=
鏈表法
這是另外一種類型解決衝突的辦法，散列到同一位置的元素，不是繼續往下探測，而是在這個位置是一個鏈表，這些元素則都放到這一個鏈表上。java的HashMap就採用的是這個。
再散列
如果一次不夠，就再來一次，直到衝突不再發生。
建立公共溢出區
將哈希表分為基本表和溢出表兩部分，凡是和基本表發生衝突的元素，一律填入溢出表(注意：在這個方法裡面是把元素分開兩個表來存儲)。
說了這麼一堆，舉個例子，用開放地址法（線性探測）：
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個完全不夠用啊”
這是剛才的問題，所以有了另外一個概念，叫做載荷因子（load factor ）。載荷因子的定義為：α= 已有的元素個數/表的長度
由於表長是定值， α與“填入表中的元素個數”成正比，所以， α越大，表明填入表中的元素越多，產生衝突的可能性就越大；反之，α越小，表明填入表中的元素越少，產生衝突的可能性就越小。實際上，散列表的平均查找長度是載荷因子 α的函數，只是不同處理衝突的方法有不同的函數。
所以當到達一定程度，表的長度是要變的，即resize=。=像java的HashMap，載荷因子被設計為0.75；超過0.8，cpu的cache missing會急劇上升。可以看下這篇討論：www.zhihu.com/question/22…
具體擴容多少，一般選擇擴到已插入元素數量的兩倍，java也是這麼做的。
接著上面，再升級一下我們的
map：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]
看上面的函數，可以看到resize是一個比較耗時的操作，因為只是原理教學，所以並沒有什麼奇淫技巧在裡面。可以去看一下Java的HashMap的hash方法和resize方法，還有處理衝突時的設計（jdk8及之後的HashMap用到了紅黑樹），其中的思路要精妙的多。
關於哈希表，原理的東西都基本差不多了。可以看到，它本質要解決的是查找時間的問題。如果順序查找的話，時間複雜度為O(n)；而哈希表，時間複雜度則為O(1)！直接甩了一個次元，這也就是為什麼在大量數據存儲查找的時候，哈希表得到大量應用的原因。
閱讀更多 java架構之路 的文章
