數(shù)據(jù)結(jié)構(gòu)子目錄http://www.reibang.com/p/a344fa483655
哈希表
在了解哈希表之前，我們要先認(rèn)識一下直接尋址表狠毯。
什么是直接尋址表
我們確定key值就在某個范圍之內(nèi)嚼松，那么直接尋址就是一個很有效的辦法献酗。
這個圖確定了key值只能在0--9之內(nèi)罕偎，就可以建立一個0--9的列表，用來存儲相應(yīng)的key與value的指針京闰。
直接尋址表的缺點(diǎn)
當(dāng)U很大時颜及，會消耗很大的內(nèi)存终议，不實(shí)際凸主。
當(dāng)U很大，key很小時，很大的空間將會被浪費(fèi)损敷。
無法處理key不是數(shù)字的情況。
改進(jìn)直接尋址表
將直接尋址表的key通過函數(shù)h()處理后放在h(key)的位置上沟沙，他將域映射在了表T上面嗡呼。
這種處理就是哈希處理，哈希處理后的表反浓，就是哈希表萌丈。
什么是哈希表
哈希表是一個通過哈希函數(shù)計(jì)算數(shù)據(jù)存儲位置的數(shù)據(jù)結(jié)構(gòu)。
哈希表雷则，又稱散列表辆雾，是一種線性數(shù)據(jù)結(jié)構(gòu)月劈，哈希表是由一個直接尋址表和一個哈希函數(shù)組成的惭墓，哈希函數(shù)h(k)將key作為自變量，返回元素的存儲下標(biāo)钧萍。
簡單的例子
除法哈希：h(k)=k mod m
乘法哈希：h(k)=floor（m(kA mod 1)）
假設(shè)有一個長度為7的列表，哈希函數(shù)是h(k)=k mod 7弛秋，那么列表[5,3,22,14]的存儲方式是：
[14,22,3,,5,,_]
然后現(xiàn)在思考一個問題，我們再把7存進(jìn)去， 7 mod 7 該把他放在0這個位置意敛，但是0這個位置已經(jīng)有元素了钓猬。這就是哈希沖突综膀。
哈希沖突
為了解決哈希沖突橄登，引入了一個方法：開放尋址法。
如果哈希函數(shù)返回到位置已經(jīng)有值了面褐，則可以向后探查新的位置來存儲這個值。
線性探查：如果i被占用觉痛，則探查i+1，i+2...
二度探查：如果i被占用俐芯，則探查i+12唠雕，i-12,i+22，i-22...
二度哈希：有n個哈希函數(shù)，當(dāng)h1哈希后有沖突邓夕，則嘗試h2净薛，h3.
但是開放尋址之后痴腌，那么哈希表的作用就被無限弱化了，如果我要存的元素經(jīng)過哈希后都在一個位置上呢？
這就有了第二個方法：拉鏈法。
哈希表的每一個位置都連接著一個鏈表慈缔，當(dāng)沖突發(fā)生時娱节，沖突的元素將被放到鏈表的最后。
代碼
class HashMap(object):
def __init__(self):
# 初始化總表為，容量為2的表格（含兩個子表）
self.maps = BetterMap(2)
self.num = 0 # 表中數(shù)據(jù)個數(shù)
def get(self,k):
return self.maps.get(k)
def add(self, k, v):
# 若當(dāng)前元素?cái)?shù)量達(dá)到臨界值（子表總數(shù)）時，進(jìn)行重排操作
# 對總表進(jìn)行擴(kuò)張纠炮，增加子表的個數(shù)為當(dāng)前元素個數(shù)的兩倍穷躁！
if self.num == len(self.maps.maps):
self.resize()
# 往重排過后的 self.map 添加新的元素
self.maps.add(k, v)
self.num += 1
def resize(self):
#重排操作梳虽，添加新表, 注意重排需要線性的時間
# 先建立一個新的表,子表數(shù) = 2 * 元素個數(shù)
new_maps = BetterMap(self.num * 2)
for m in self.maps.maps: # 檢索每個舊的子表
for k,v in m.items: # 將子表的元素復(fù)制到新子表
new_maps.add(k, v)
self.maps = new_maps # 令當(dāng)前的表為新表
