散列函數(shù)：把查找表中的關(guān)鍵字映射成該關(guān)鍵字對應(yīng)的地址。
Hash(key)=Addr
這里的地址可以是數(shù)組下標谋作，索引或內(nèi)存地址等。
沖突：不同的關(guān)鍵字映射到同一地址（這些關(guān)鍵字稱為同義詞）
散列表：根據(jù)關(guān)鍵字而進行直接訪問的數(shù)據(jù)結(jié)構(gòu)堂淡。
散列函數(shù)的構(gòu)造方法
采用何種構(gòu)造散列函數(shù)的方法取決于關(guān)鍵字集合的情況教馆，目標是為了盡量降低產(chǎn)生沖突的可能性逊谋。
1.直接定址法
H(key)=axkey+b
計算簡單，不會產(chǎn)生沖突活玲。
適合關(guān)鍵字的分布基本連續(xù)的情況涣狗，若關(guān)鍵字分布不連續(xù)，空位較多舒憾，則會造成存儲空間的浪費镀钓。
2.除留余數(shù)法
假設(shè)散列表長m，取一個不大于m但最接近或等于m的質(zhì)數(shù)p
H(key)=key%p
選好p镀迂，使得每個關(guān)鍵字通過該函數(shù)轉(zhuǎn)換后等概率地映射到散列空間上的任一地址丁溅，從而減少沖突的可能性。
3.數(shù)字分析法
設(shè)關(guān)鍵字是r進制數(shù)探遵，而r個數(shù)碼（0窟赏，1，...箱季，r-1）在各位上出現(xiàn)的頻率不一定相同涯穷，可能在某些位上分布均勻一些，每種數(shù)碼出現(xiàn)的機會均等藏雏；而在某些位上分布不均勻拷况，只有某幾種數(shù)碼經(jīng)常出現(xiàn)。此時應(yīng)選取數(shù)碼分布較為均勻的若干位作為散列地址掘殴。
這種方法適合于已知的關(guān)鍵字集合赚瘦，若更換了關(guān)鍵字，則需重新構(gòu)造新的散列函數(shù)奏寨。
4.平方取中法
取關(guān)鍵字的平方值的中間幾位作為散列地址起意。
這種方法得到的散列地址與關(guān)鍵字的每位都有關(guān)系，因此使得散列地址分布比較均勻病瞳。
適用于關(guān)鍵字的每位取值都不夠均勻或均小于散列地址所需要的位數(shù)揽咕。
5.折疊法
將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以短一些）悲酷，然后取這幾部分的疊加作為散列地址。
適用于關(guān)鍵字位數(shù)很多心褐，且關(guān)鍵字中每位上的數(shù)字分布大致均勻時
處理沖突的方法
散列函數(shù)H(key)舔涎，Hi表示發(fā)生沖突后第i次探測的散列地址
1.開放定址法
可存放新表項的空閑地址即向它的同義詞表項開放，又向它的非同義詞表項開放
Hi=(H(key)+di)%m
i=0,1,2...,k(k<=m-1)
m為散列表表長
di為增量序列
線性探測法
di=0,1,2,...,m-1
沖突發(fā)生時逗爹，順序查看表中下一個單元
會造成大量元素在相鄰的散列地址上堆積起來，降低了查找效率
平方探測法（二次探測法）
di=02,12,-12,22,-22,...,k2,-k^2(k<=m/2)
m必須是一個可以表示成4k+3的素數(shù)
可以避免出現(xiàn)堆積問題嚎于，缺點是不能探測到散列表上所有單元掘而，但至少能探測到一半單元
再散列法（雙散列法）
di=Hash2(key)
Hi=(H(key)+ixHash2(key))%m
偽隨機序列法
di=偽隨機數(shù)序列
邏輯刪除？
2.鏈接法
把所有的同義詞存儲在一個線性鏈表中
適用于經(jīng)常進行插入和刪除的情況
散列查找及性能分析
裝填因子
α=表中記錄數(shù)n/散列表長度m
散列表的平均長度依賴于散列表的裝填因子α于购，而不直接依賴于n或m
