基本概念

? ? ? ?根據(jù)設(shè)定的哈希函數(shù)Hash(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映像到一個(gè)有限的、地址連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的像作為相應(yīng)記錄在表中的存儲位置，這種表被稱為哈希表，這一映像的過程亦被稱為哈希。
哈希法查找必須研究兩個(gè)主要問題：
（1）構(gòu)造一個(gè)計(jì)算簡單而且沖突盡量少的哈希函數(shù)；
（2）確定一個(gè)解決沖突的辦法。

構(gòu)造哈希表的方法

1.直接定址法
? ? ? ?取關(guān)鍵字本身或關(guān)鍵字的某個(gè)線性函數(shù)值作為哈希表地址，即
Hash(key)=key 或 Hash(key)=a*key + b (a,b為常數(shù))
2.數(shù)字分析法
? ? ? ?從關(guān)鍵字中選出分布較均勻的幾位作為哈希函數(shù)的結(jié)果，即關(guān)鍵字的存儲地址。
3.平均取中法
? ? ? ?將關(guān)鍵字先平方，然后取其中幾位為哈希地址。
4.折疊法
? ? ? ?將關(guān)鍵字分割成位數(shù)相等的幾部分（最后一部分位數(shù)可以不等），然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址。折疊法又分移位疊加和間界疊加，移位疊加是將各部分的最低位對齊，然后相加；間界疊加是從一端向另一端沿分割線來回折疊，然后對齊相加。
5.除留余數(shù)法
找出一個(gè)盡可能大且不大于哈希表表長的合適的正整數(shù)p,為避免沖突，一般取p為素?cái)?shù)，取關(guān)鍵字除以p作為哈希函數(shù)的值，即
? ? ? ?Hash（key）= key % p (p<=m,m為表的長度)
一般選p為小于或等于哈希表長度m的某個(gè)最大素?cái)?shù)較好。
6.隨機(jī)數(shù)法
取關(guān)鍵字的某個(gè)隨機(jī)函數(shù)值作為它的哈希地址，即 Hash(key) = Random(key)，式中，Random為隨機(jī)函數(shù)。