1. 散列函數(shù)構(gòu)造方法
直接定址法：H(key) = a * key + b
這種方法計(jì)算最簡(jiǎn)單蟀拷，而且不會(huì)產(chǎn)生沖突制市，但是如果關(guān)鍵字分布不連續(xù)志衍，空位較多暖庄，浪費(fèi)空間。適用于楼肪，關(guān)鍵字分布基本連續(xù)情況培廓。除留余數(shù)法：H(key) = key % p
核心：選好p使得每一個(gè)關(guān)鍵字通過該函數(shù)轉(zhuǎn)換后等概率地映射到散列空間的任一地址。
p的選法：假定散列表表長(zhǎng)為m取一個(gè)不大于m但最接近或等于m的質(zhì)數(shù)p數(shù)字分析法
設(shè)關(guān)鍵字是r進(jìn)制數(shù)春叫，選取數(shù)字在上面出現(xiàn)頻率比較均勻的若干位作為散列地址肩钠，這種方法適用于已知關(guān)鍵字集合。平方取中法
取關(guān)鍵字平方中間的幾位作為散列地址暂殖，適用于關(guān)鍵字每一位取值都不夠均勻或均小于散列地址所需位數(shù)价匠。折疊法
把關(guān)鍵字分割成幾個(gè)位數(shù)相同的部分，然后相加的和作為散列地址呛每。適用于踩窖，關(guān)鍵字位數(shù)很多，每一位數(shù)字分布大致均勻晨横。
2. 沖突處理
缺點(diǎn)：刪除記錄的時(shí)候不能把空間騰出洋腮，要留一個(gè)標(biāo)記。因?yàn)橐虻刂窙_突的關(guān)鍵字尋址手形，需要尋得它前面一個(gè)沖突的關(guān)鍵字地址啥供。
開放定址法
Hi = (H(key) + di) % m
di為增量序列線性探測(cè)法：di = 1，2库糠，3伙狐，4....,m - 1
按順序往后逐一保存，可能造成把一個(gè)區(qū)域的位置填滿曼玩，導(dǎo)致很多關(guān)鍵字保存時(shí)出現(xiàn)沖突鳞骤，只好往后移，大量元素在相鄰的散列地址上“聚集”起來黍判。平方探測(cè)法：di = 1^2, -1^2, 2^2, -2^2,..., k^2, -k^2豫尽，其中k <= m / 2 ，m必須可表示成 4k + 3
缺點(diǎn)：不能探測(cè)到所有單元顷帖，但是至少可以探測(cè)一半再散列法：再用一個(gè)哈希函數(shù)求增量美旧，di = Hash2(key)
偽隨機(jī)序列法：di 是已保存的偽隨機(jī)序列
- 拉鏈法
存儲(chǔ)單元保存指針渤滞，指針指向鏈表，所有地址一樣的關(guān)鍵字保存在鏈表上榴嗅。
3. 散列查找
- 使用哈希函數(shù)計(jì)算找到地址妄呕，地址為空則查找失敗
- 找到地址，出現(xiàn)沖突嗽测，通過處理沖突方法找到下一個(gè)地址绪励，如果仍是沖突，重復(fù)上一步唠粥，直到找到或者存儲(chǔ)單元為空
4. 性能分析
- 平均查找長(zhǎng)度是度量：根據(jù)散列表長(zhǎng)度疏魏，元素個(gè)數(shù)，散列函數(shù)晤愧，解決沖突方法大莫，計(jì)算查找成功的平均查找長(zhǎng)度，查找不成功的平均查找長(zhǎng)度官份。
- 裝填因子 = 表中記錄數(shù) / 散列表長(zhǎng)度
