作者: tianshi0253  鏈接：http://tianshi0253.javaeye.com/blog/204640  發表時間: 2008年06月17日

聲明：本文系JavaEye網站發布的原創博客文章，未經作者書面許可，嚴禁任何網站轉載本文，否則必將追究法律責任！

下面引用一些別的地方
1 基本原理

我們使用一個下標范圍比較大的數組來存儲元素。可以設計一個函數（哈希函數， 也叫做散列函數），使得每個元素的關鍵字都與一個函數值（即數組下標）相對應，于是用這個數組單元來存儲這個元素；也可以簡單的理解為，按照關鍵字為每一個元素"分類"，然后將這個元素存儲在相應"類"所對應的地方。

但是，不能夠保證每個元素的關鍵字與函數值是一一對應的，因此極有可能出現對于不同的元素，卻計算出了相同的函數值，這樣就產生了"沖突"，換句話說，就是把不同的元素分在了相同的"類"之中。后面我們將看到一種解決"沖突"的簡便做法。

總的來說，"直接定址"與"解決沖突"是哈希表的兩大特點。

2 函數構造

構造函數的常用方法（下面為了敘述簡潔，設 h(k) 表示關鍵字為 k 的元素所對應的函數值）：

a) 除余法：

選擇一個適當的正整數 p ，令 h(k ) = k mod p
這里， p 如果選取的是比較大的素數，效果比較好。而且此法非常容易實現，因此是最常用的方法。

b) 數字選擇法：

如果關鍵字的位數比較多，超過長整型范圍而無法直接運算，可以選擇其中數字分布比較均勻的若干位，所組成的新的值作為關鍵字或者直接作為函數值。

3 沖突處理

線性重新散列技術易于實現且可以較好的達到目的。令數組元素個數為 S ，則當 h(k) 已經存儲了元素的時候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲單元為止（或者從頭到尾掃描一圈仍未發現空單元，這就是哈希表已經滿了，發生了錯誤。當然這是可以通過擴大數組范圍避免的）。

4 支持運算

哈希表支持的運算主要有：初始化(makenull)、哈希函數值的運算(h(x))、插入元素(insert)、查找元素(member)。
設插入的元素的關鍵字為 x ，A 為存儲的數組。
初始化比較容易，例如
const empty=maxlongint; // 用非常大的整數代表這個位置沒有存儲元素
p=9997; // 表的大小
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;

哈希函數值的運算根據函數的不同而變化，例如除余法的一個例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;

我們注意到，插入和查找首先都需要對這個元素定位，即如果這個元素若存在，它應該存儲在什么位置，因此加入一個定位的函數 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);
//當這個循環停下來時，要么找到一個空的存儲單元，要么找到這個元
//素存儲的單元，要么表已經滿了
locate:=(orig+i) mod S;
end;
插入元素
procedure insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函數的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即為發生了錯誤，當然這是可以避免的
end;

查找元素是否已經在表中
procedure member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;

這些就是建立在哈希表上的常用基本運算。

本文的討論也很精彩，瀏覽討論>>


JavaEye推薦

• 北京: 千橡集團暨校內網誠聘軟件研發工程師
• 立刻報名，免費獲取門票，參加SOA技術論壇(廣州6月19日)
• Oracle專區上線，有Oracle最新文章，重要下載及知識庫等精彩內容，歡迎訪問。
• 搜狐網站誠聘Java、PHP和C++工程師

文章來源:http://tianshi0253.javaeye.com/blog/204640