基本概念
散列表查找(K -- V)约谈。
存儲位置 = f(關(guān)鍵字) 查找的時候根據(jù)key的映射f(key)找到值存儲的位置番刊。
構(gòu)造散列函數(shù)子房。
- 直接定制法狭莱。
f(key) = a x key + b（a b 為常數(shù)）
-
數(shù)字分析法。
通常適合處理關(guān)鍵字位數(shù)比較大的情況皆愉，如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均勻嗜价。
平方取中法艇抠。
比較適合不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況久锥。
if key == 1234;
key^2 == 1522756
address = 227
- 折疊法家淤。
適合關(guān)鍵字位數(shù)比較多的情況。
以適當(dāng)?shù)奈粩?shù)分割整個關(guān)鍵字奴拦，然后分割出來的數(shù)進行相加媒鼓。
- 除留取余數(shù)發(fā)。
f(key) = key mod p (p<=m)
若散列表表長為m错妖，通常p為小雨或等于表長的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)。
解決散列沖突
- 開放定址法疚沐。
- 再散列函數(shù)法暂氯。
- 鏈地址發(fā)。
- 公共溢出區(qū)法亮蛔。
