我們使用壹個下標範圍很大的數組來存儲元素。妳可以設計壹個函數(hash function,也叫hash function),使每個元素的關鍵字都對應壹個函數值(即數組下標),所以這個數組單元用來存儲這個元素;也可以簡單理解為根據關鍵字對每個元素進行“分類”,然後將該元素存儲在相應“類”的相應位置。
但是,不能保證每個元素的關鍵字和函數值是壹壹對應的,因此很有可能為不同的元素計算相同的函數值,從而產生“沖突”。換句話說,不同的元素被劃分到同壹個“類”中。稍後我們將看到解決“沖突”的簡單方法。
壹般來說,“直接尋址”和“沖突解決”是哈希表的兩個特征。
2功能構建
構造函數的常用方法(為簡潔起見,讓h(k)表示關鍵字為k的元素對應的函數值):
a)劃分方法:
選擇壹個合適的正整數p使得h(k)= k mod p。
這裏,如果P選擇更大的素數,效果會更好。而且這種方法非常容易實現,所以是最常用的方法。
b)號碼選擇方法:
如果關鍵字的數量太大而無法直接計算,則可以選擇多個均勻分布的數字組成壹個新值作為關鍵字或直接作為函數值。
3沖突處理
線性重散列技術易於實現,可以很好地實現目標。設數組中元素的個數為s,那麽當h(k)已經存儲了元素時,依次probe(h(k)+I)mod s,i = 1,2,3...直到找到壹個空的存儲單元(或者哈希表已滿並且發生了錯誤)。當然,這可以通過擴大數組範圍來避免)。
4支持操作
哈希表支持以下操作:初始化(makenull)、散列函數值操作(h(x))、插入元素(insert)和查找元素(member)。
設插入元素的鍵為x,a為存儲數組。
例如,初始化相對容易
const empty = maxlongint//使用壹個非常大的整數來指示此位置沒有存儲元素。
p = 9997//表格的大小
過程makenull
var i:整數;
開始
對於i:=0至p-1 do
a【I】:=空;
結束;
散列函數值的運算根據不同的函數而變化,例如除法的例子:
函數h(x:longint):整數;
開始
h:= x mod p;
結束;
我們註意到插入和搜索都需要首先定位這個元素,也就是說,如果這個元素存在,它應該存儲在哪裏,因此我們添加了壹個定位函數locate。
函數定位(x:longint):整數;
var orig,I:整數;
開始
orig:= h(x);
I:= 0;
while(我& ltS)和(A【(orig+I)mod S】& lt;& gtx)和(A【(orig+I)mod S】& lt;& gt空的)做
inc(壹);
//當此循環停止時,要麽找到壹個空存儲單元,要麽找到此元素。
//主要存儲單元,或者表已滿。
locate:=(orig+I)mod S;
結束;
插入元素
過程插入(x:longint);
var posi:整數;
開始
posi:= locate(x);//定位函數的返回值
如果A【posi】=空,則A【posi】:= x
else錯誤;//error表示發生了錯誤,可以避免。
結束;
查明該元素是否已經在表中。
過程成員(x:longint):boolean;
var posi:整數;