1. 散列表基礎(chǔ)：
用途：對于數(shù)據(jù)項查找，時間復(fù)雜度為O(1)，用于快速查找定位
結(jié)構(gòu)：哈希表每一個儲存位置成為slot夸政，將數(shù)據(jù)項存儲在槽里
。
散列方法1：求余數(shù)榴徐，將數(shù)據(jù)項除于散列表大小守问，將得到的余數(shù)作為槽號。將每個數(shù)映射至不同槽內(nèi)箕速。（完美散列函數(shù)）
沖突：不同的數(shù)據(jù)都可能進(jìn)入相同的槽酪碘，引起collision
Python中的庫：
import hashlib
包括MD5與SHA系列函數(shù)
2. 散列函數(shù)設(shè)計
- 折疊法：
通過將數(shù)據(jù)項按照位數(shù)分為幾段，再將幾段相加后對散列表總體大小求余盐茎，得到散列值兴垦，放入槽內(nèi)
（有時對某一段值進(jìn)行反轉(zhuǎn)） - 平方取中法：
對數(shù)據(jù)項平方，取平方數(shù)的中間兩個數(shù)據(jù)項，求余探越。
注意：字符串可用ASCII表示狡赐，字符順序可加入權(quán)重因子進(jìn)行區(qū)分。
3沖突解決方案
-
開放定址法：對沖突的數(shù)據(jù)項往后再找一個空槽存放數(shù)據(jù)項钦幔。
image.png
為了防止聚集出現(xiàn)枕屉，也可每隔一定的間隔進(jìn)行存放沖突的數(shù)據(jù)項
（線性探測、跳躍式探測鲤氢、二次探測）
1. rehash(pos) = (pos+1) % sizeoftable
2. rehash(pos) = (pos+gap) % sizeoftable
3. for i in range(N):
rehash(pos) = (pos+gap) % sizeoftable
注意散列表大小取為素數(shù)搀擂，這樣不被gap整除，就可以取到所有值卷玉。
-
數(shù)據(jù)項鏈法
將有沖突的槽擴展為容納數(shù)據(jù)項的集合哨颂，或者增加鏈表的引用。這樣就不會占據(jù)其他槽相种，槽可以容納多個數(shù)據(jù)項威恼。
image.png
會犧牲時間復(fù)雜度。O(1)~O(N)
應(yīng)用：字典
實現(xiàn)ADT Map
代碼：
class HashTable:
def __init__(self):
self.size = 11
# 素數(shù)
self.slots = [None] * self.size
self.data = [None] * self.size
def hashfunction(self, key):
return key % self.size
def rehash(self, oldhash):
return (oldhash + 1) % self.size
def put(self, key, data):
hashvalue = self.hashfunction(key)
if self.slots[hashvalue] is None:
self.slots[hashvalue] = key
self.data[hashvalue] = data
# 如果取到槽為空槽寝并，將數(shù)據(jù)項放入槽內(nèi)箫措，并在數(shù)據(jù)表對應(yīng)槽的位置放入數(shù)據(jù)
else:
if self.slots[hashvalue] == key:
self.data[key] = data
# 如果該槽已有記錄，在對應(yīng)數(shù)據(jù)表位置修改數(shù)據(jù)
else:
nextslot = self.rehash(hashvalue)
while self.slots[nextslot] is not None and self.slots[nextslot] != key:
nextslot = self.rehash(nextslot)
# 如果出現(xiàn)沖突衬潦，則線性探測下一個槽
if self.slots[nextslot] is None:
self.slots[nextslot] = key
self.data[nextslot] = data
# 如果探測的新槽是空槽斤蔓，則放入該數(shù)據(jù)項
else:
self.data[nextslot] = data
# 如果新槽已被記錄，則修改數(shù)據(jù)項
def get(self, key):
hashvalue = self.hashfunction(key)
startslot = hashvalue
found = False
stop = False
data = None
pos = hashvalue
while self.slots[pos] is not None and not found and not stop:
if self.slots[pos] == key:
data = self.data[pos]
found = True
# 如果找到了對應(yīng)的槽镀岛，把數(shù)據(jù)表中的對應(yīng)數(shù)據(jù)項返回
else:
pos = self.rehash(pos)
if pos == startslot:
stop = True
# 沒找到槽：1. 進(jìn)行線性探測附迷，找到了就返回數(shù)據(jù)項 2. 線性探測后回到初始位置，仍沒有對應(yīng)數(shù)據(jù)項哎媚，返回None
return data
時間復(fù)雜度注意：
① 線性探測解決沖突：查找比對次數(shù)在1/2（1+1/(λ-1)) ~ 1/2（1+1/((λ-1)^2))
② 數(shù)據(jù)鏈：查找次數(shù)：1+λ/2 ~ λ
（其中負(fù)載因子λ代表沖突情況）
