作者:
tianshi0253
鏈接：
http://tianshi0253.javaeye.com/blog/204640
發(fā)表時間: 2008年06月17日
聲明：本文系JavaEye網(wǎng)站發(fā)布的原創(chuàng)博客文章，未經(jīng)作者書面許可，嚴禁任何網(wǎng)站轉(zhuǎn)載本文，否則必將追究法律責任！
下面引用一些別的地方
1 基本原理
我們使用一個下標范圍比較大的數(shù)組來存儲元素。可以設計一個函數(shù)（哈希函數(shù)， 也叫做散列函數(shù)），使得每個元素的關鍵字都與一個函數(shù)值（即數(shù)組下標）相對應，于是用這個數(shù)組單元來存儲這個元素；也可以簡單的理解為，按照關鍵字為每一個元素"分類"，然后將這個元素存儲在相應"類"所對應的地方。
但是，不能夠保證每個元素的關鍵字與函數(shù)值是一一對應的，因此極有可能出現(xiàn)對于不同的元素，卻計算出了相同的函數(shù)值，這樣就產(chǎn)生了"沖突"，換句話說，就是把不同的元素分在了相同的"類"之中。后面我們將看到一種解決"沖突"的簡便做法。
總的來說，"直接定址"與"解決沖突"是哈希表的兩大特點。
2 函數(shù)構(gòu)造
構(gòu)造函數(shù)的常用方法（下面為了敘述簡潔，設 h(k) 表示關鍵字為 k 的元素所對應的函數(shù)值）：
a) 除余法：
選擇一個適當?shù)恼麛?shù) p ，令 h(k ) = k mod p
這里， p 如果選取的是比較大的素數(shù)，效果比較好。而且此法非常容易實現(xiàn)，因此是最常用的方法。
b) 數(shù)字選擇法：
如果關鍵字的位數(shù)比較多，超過長整型范圍而無法直接運算，可以選擇其中數(shù)字分布比較均勻的若干位，所組成的新的值作為關鍵字或者直接作為函數(shù)值。
3 沖突處理
線性重新散列技術易于實現(xiàn)且可以較好的達到目的。令數(shù)組元素個數(shù)為 S ，則當 h(k) 已經(jīng)存儲了元素的時候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲單元為止（或者從頭到尾掃描一圈仍未發(fā)現(xiàn)空單元，這就是哈希表已經(jīng)滿了，發(fā)生了錯誤。當然這是可以通過擴大數(shù)組范圍避免的）。
4 支持運算
哈希表支持的運算主要有：初始化(makenull)、哈希函數(shù)值的運算(h(x))、插入元素(insert)、查找元素(member)。
設插入的元素的關鍵字為 x ，A 為存儲的數(shù)組。
初始化比較容易，例如
const empty=maxlongint; // 用非常大的整數(shù)代表這個位置沒有存儲元素
p=9997; // 表的大小
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;
哈希函數(shù)值的運算根據(jù)函數(shù)的不同而變化，例如除余法的一個例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;
我們注意到，插入和查找首先都需要對這個元素定位，即如果這個元素若存在，它應該存儲在什么位置，因此加入一個定位的函數(shù) locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//當這個循環(huán)停下來時，要么找到一個空的存儲單元，要么找到這個元
//素存儲的單元，要么表已經(jīng)滿了
locate:=(orig+i) mod S;
end;
插入元素
procedure insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函數(shù)的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即為發(fā)生了錯誤，當然這是可以避免的
end;
查找元素是否已經(jīng)在表中
procedure member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;
這些就是建立在哈希表上的常用基本運算。
本文的討論也很精彩，瀏覽討論>>
JavaEye推薦
文章來源:
http://tianshi0253.javaeye.com/blog/204640
posted on 2008-06-17 12:11
姚文超 閱讀(260)
評論(0) 編輯 收藏