散列查找

在進行查找時，在記錄的存儲位置與它的關鍵字之間建立一個確定的對應關係h,以線性表中每個元素的關鍵字K為自變數，通過函式h(K)計算出該元素的存儲位置，我們將h函式稱為散列函式或哈希函式。這種查找方法稱為散列查找。

基本介紹

  • 中文名：散列查找
  • 意義：散列函式或哈希函式
  • 方法：通過函式h(K)計算
  • 原理：h函式
基本概念,散列函式,直接定址法,除留餘數法,數字分析法,平方取中法,摺疊法：,隨機乘數法：,基數轉換法：,處理衝突的方法,開放定址法,鍊表地址法,散列表的運算,

基本概念

散列函式
在進行查找時，在記錄的存儲位置與它的關鍵字之間建立一個確定的對應關係h,以線性表中每個元素的關鍵字K為自變數，通過函式h(K)計算出該元素的存儲位置，我們將h函式稱為散列函式或哈希函式。h(K)的值稱為散列地址或哈希地址。例：
假定一個線性表為A=(18,75,60,43,54,90,46)，選取散列函式為：
h(K)=K%m 取m=13
則得每個元素散列地址：
h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8 h(43)=43 % 13=4
h(54)=54 % 13=2 h(90)=90 % 13=12 h(46)=46 % 13=7
根據散列地址，實現元素的存儲映象H[m]：

0
1
2
3
4
5
6
7
8
9
10
11
12
H


54

43
18

46
60

75

90
衝突：在實際套用中，通常可能出現一個待插入元素的散列地址單元已被占用情況，使得該元素無法直接存入此單元，這種情況稱為衝突。
同義詞：具有不同關鍵字而具有相同散列地址的元素稱為同義詞，即key1≠key2，但h(key1)=h(key2)。由同義詞引起的衝突稱作同義詞衝突。
例：如向下表中再插入元素70時，70%13=5，則出現了衝突

0
1
2
3
4
5
6
7
8
9
10
11
12
H


54

43
18

46
60

75

90
裝填因子(α)：指散列表中已存入的元素數n與散列表空間大小m的比值,即：α=n/m。當α越小時，衝突可能性就越小，但同時，存儲空間利用率就越低。
散列表：根據設定的哈希函式及處理衝突的方法將一組關鍵字映象到一個有限的連續的地址集上，即把記錄存放在表中映象的位置上，這種表便稱為散列表(哈希表)。
一個散列表的好壞與三個因素有關：
1.裝填因子 2、所採用的散列函式 3、解決衝突的方法

散列函式

構造散列函式的目標是使散列地址儘可能均勻分布在散列空間上，同時使計算儘可能簡單，以節省計算時間。

直接定址法

以關鍵字K本身或關鍵字加上某個數值常量C作為散列地址的方法，對應的散列函式：
h(K)=K+C (C為常數)
例：有一個解放後出生的人口調查表，關鍵字是年份，h(K)=K+(-1948)，如表所示：
地址 01 02 03 … 22 …
年份
1949 1950 1951 … 1970 …
人數
… … … 15000 ...

除留餘數法

以關鍵字K除以散列長度m所得餘數作為散列地址的方法，對應的散列函式：
h(K)=K%m
m為散列表長，取m=13,得散列表：

0
1
2
3
4
5
6
7
8
9
10
11
12
H


54

43
18

46
60

75

90
取m為奇數比取m為偶數好確保m的值大於等於待散列的線性表的長度n當關鍵字K為字元串時，需轉換為整數(先求K長，接著把每個字元的ASCII碼累加到無符號整型量h上，並且每次累加前，h值左移3位，擴大8倍)
int Hash(char * K, int m)
{
//把字元串K轉換為0～m-1之間的一個值作為對應記錄的散列地址
int len=strlen(K); //求字元串K的長度
unsigned int h=0;
for(int i=0;i<len;i++)
{
//採用一種方法計算K所對應的整數
h<<=3; //h的值左移3位
h+=K[i];
}
return h%m;
}

數字分析法

當關鍵碼的位數很多時，可以通過對關鍵碼的各位進行分析，丟掉分布不均的位，留下分布均與的位作為散列值。數字分析法只適合於靜態的關鍵碼值集合，當關鍵碼值發生變化後，必須重新進行數字分析。這無疑限制了數字分析法在實際中的套用。
例：有一組關鍵字如下：
92326875
92739628
92343634
92706816
92774638
92381262
92394220
通過分析：每個關鍵字從左到右第1、2、3位和第6位取值較集中，不宜作散列地址，其餘的第4、5、7、8位取值分散，可以選擇，若取最後兩位作散列地址，得：
(2,75,28,34,16,38,62,20)

平方取中法

取關鍵字平方的中間幾位作為散列地址的方法，由平方取中法得到的散列地址同關鍵字的每一位都有關，使得散列地址有較好分散性。
它適用於關鍵字中每一位取值都不夠分散或者較分散的位數小於散列地址所需要的位數的情況。
例子：對下列關鍵碼值集合採用平方取中法計算散列值，取平方值中間的兩位：
key

Hash(key)
319426
102032968476
29
718309
629443
758615
919697
310329
515967819481
396198480249
572938783923
287438470282
239849810284
78
12
34
55
32
下面給出平方取中法的散列函式：
/*平方取中法三列函式，假設關鍵碼值是32位的整數，
散列函式 將返回key*key的中間10位*/
int Hash(int key)
{
key*=key;
key>>=11;
return key % 1024;
}

摺疊法：

首先將關鍵字分割成位數相同的幾段(最後一段位數可少一些)，然後將它們的疊加和(捨去最高位進位)作為散列地址的方法。
例：有一關鍵字：K=68242324，散列地址3位，將此關鍵字從左到右每三位一段劃分後相疊加得：

隨機乘數法：

隨機乘數法使用一個隨機實數f(0≤f<1)。成績f*key的分數部分在0―1之間，用這個分數部分的值與n（散列表的長度）相乘，乘積的整數部分就是對應的散列值，顯然這個散列值落在0—n-1之間。
例子：對下列關鍵碼值集合採用隨機乘數法計算散列值，隨機數f=0.103149002,散列表長度n=101。
key
f*key
n*((f*key)的小數部分)
Hash(key)
319426
32929.29313
29.89241
29
718309
629443
758615
919697
310329
49348.24351
73829.99024
89008.22413
68940.52641
90872.13715
24.98313
99.52341
22.98301
53.23949
14.39491
78
12
34
55
32

基數轉換法：

將關鍵碼值看成是在另一個基數數制上的書，然後把它轉化成原來基數上的數，再選擇其中的若干位作為散列值。一般取大於原來基數的數作為轉換的基數，並且兩個基數應該是互素的。
例子：採用基數轉換法，計算十進制關鍵碼值key=852422241的散列值，取轉換基數為13，則有：
=8*5*
取轉換後的數值的中間4為數字作為散列值，於是Hash(key)=0789。

處理衝突的方法

開放定址法

思路：從發生衝突的那個單元開始，按照一定次序，從散列表中查找出一個空閒的存儲單元，把發生衝突的待插入元素存入到該單元的一類處理衝突的方法。
在使用該方法處理衝突的散列表中，查找一個元素的過程是：先根據給定關鍵字K，利用與插入時使用的同一散列函式h(K)計算出散列地址(設下標為d),然後用K同d單元的關鍵字比較，若相等則查找成功，否則按插入時處理衝突的相同次序，依次用K同所查單元的關鍵字比較，直到查找成功或查找到一空單元(表明查找失敗)為止。
有三種常見的開放定址法
（1）線性探查法
是用開放定址法處理衝突的一種最簡單的探查方法。
從發生衝突的d單元起,依次探查下一個單元,直到碰到一個空閒單元或探查完所有單元為止探查時,當達到下標為m-1的表尾單元時,下一個探查的單元是下標為0的表首單元。
探查序列為d,d+1,d+2……，表示為(d+i)%m (0≤i≤m-1)。
例如：構取m=13,線性表為A=(18,75,60,43,54,90,46)，構造的散列表如下：

0
1
2
3
4
5
6
7
8
9
10
11
12
H


54

43
18

46
60

75

90
現向表中再插入關鍵字為31和58的兩個元素,用線性探查法解決衝突。
先插入31，h(31)=31%13=5,因H[5]被占用，探查下一個即下標為6的單元，空閒，插入31。

0
1
2
3
4
5
6
7
8
9
10
11
12
H


54

43
18
31
46
60

75

90
再插入58，h(58)=58%13=6,因H[6]被占用，探查下一個即下標為7的單元，因H[7]仍不空閒，再接著向下探查，當探查到下標為9的單元時，空閒，插入58。

0
1
2
3
4
5
6
7
8
9
10
11
12
H


54

43
18
31
46
60
58
75

90
利用線性探查法處理衝突易造成元素的“堆積”(聚集)

0
1
2
3
4
5
6
7
8
9
10
11
12
H


54

43
18

46
60

75

90
向散列表中插入一個元素：
int Insert (hashlist1 HT,int m,ElemType item)
{
//向長度為m的散列表HT中插入一個元素
int d=H(item.key,m); //可選一種合適的構造散列函式的方法，計算散列地址
int temp=d;
while(HT[d].key != NullTag)
{
//當d單元不空時繼續向後查找空位置
d=(d+1)%m;
if(d==temp) return 0;
}
HT[d]=item; //將新元素插入到下標為d的位置
return 1;
}
從散列表中查找一個元素：
int Search (hashlist1 HT,int m, ElemType item)
{
//從長度為m的散列表HT中查找
int d=H(item.key, m);
int temp=d;
while(HT[d].key!=NullTag)
{
//當散列地址中的關鍵字域不為空則循環
if(HT[d].key==item.key) return d;
else d=(d+1)%m;
if(d==temp) return -1;
}
return -1;
}
（2）平方探查法
探查序列為d,d+1,d+2……,表示為(d+i2)%m(0≤i≤m-1)。遞推公式為：
優點：它是一種較好的處理衝突的方法，可以較好避免堆積現象
缺點：不能探查到散列表上所有單元。
例：當d0=5,m=17時，只能探查到下標依次為5、6、9、14、4、13、7、3、1的單元。
d0=5;
d1=(5 +2*1-1)%17=6; d2=(6 +2*2-1)%17=9;
d3=(9 +2*3-1)%17=14; d4=(14 +2*4-1)%17=4;
d5=(4 +2*5-1)%17=13; d6=(13 +2*6-1)%17=7;
d7=(7 +2*7-1)%17=3; d8=(3 +2*8-1)%17=1; d9=(1 +2*9-1)%17=1;
（3）雙散列函式探查法
思路：
該方法使用兩個散列函式h1和h2，其中h1和前面的h(K)一樣，以關鍵字為自變數，產生一個0～m-1之間的數作散列地址;h2也以關鍵字為自變數，產生一個1～m-1之間的、並和m互素的數作散列地址。它的探查序列為：
利用雙散列法，按一定的距離，跳躍式地尋找“下一個”桶，減少了“堆積”的機會，最多經過m-1次探查，它會遍歷表中所有位置，回到H0 位置。
例：給出一組表項關鍵碼{22,41,53,46,30,13,01,67}。散列表為HT[0..10]，m = 11。
散列函式為：
Hash(x)=(3x) % 11
再散列函式為：
ReHash(x) = (7x) % 10 +1
Hi = ( Hi-1 + (7x) % 10 +1 ) % 11, i = 1, 2,
H0(22) = 0 H0(41) = 2 H0(53) = 5 H0(46) = 6
H0(30) = 2 衝突H1 = (2+1) = 3 ,H0(13) = 6 衝突H1 = (6+2) = 8
H0(01) = 3 衝突H1 = (3+8) = 0 ,H2 = (0+8) = 8 H3 = (8+8) = 5
H4 =(5+8)=2 H5 =(2+8)=10,H0(67)=3 衝突, H1 = (3+10) = 2 H2 = (2+10) = 1
搜尋成功的平均搜尋長度：
連結法
思路：就是把發生衝突的同義詞元素(結點)用單鍊表連結起來的方法。
例：假定一個線性表B為：B=(18,75,60,43,54,90,46,31,58,73,15,34)。
設採用的散列函式為h(K)=K%13,採用連結法處理：
在該例中，查找成功時平均查找長度為：
ASL=(8×1+3×2+1×3)/12≈1.42
若線性探查法處理衝突進行散列存儲，得到：
查找成功時平均查找長度為：
ASL=(7×1+1×2+1×4+1×4+1×2+1×6)/12≈2.1
多種方法分析
在散列表的插入和查找算法中，平均查找長度與表的大小m無關，只與選取的散列函式、α值和處理衝突的方法有關,若假定所選取的散列函式能夠使任一關鍵字等機率地映射到散列空間的任一地址上，理論上證明：
當採用線性探查法處理衝突時，ASL=
當採用鏈地址法處理衝突時，ASL=
當採用平方探查法、雙散列函式法處理衝突時，ASL=
散列存儲優缺點
插入與查找的速度相當快根據關鍵字計算散列地址需要開銷一定計算時間占用存儲空間較多在散列表中只能按關鍵字查找元素線性表中元素的邏輯關係無法在散列表中體現。

鍊表地址法

鍊表地址法為散列表的每個表象建立一個單鍊表，用於連結同義詞表，為此需要給每個表項增加一個指針域。
關於同義詞表的建立，有兩種方法。一種方法是在散列表的基本存儲區域外開闢一個新的區域用於存儲同義詞表，這種方法稱為“分離的同義詞子表法”，或稱“獨立鍊表地址法”，這個分離的同義詞子表所在的區域稱為“溢出區”。另一種方法是不建立溢出區，而是將同義詞子表存儲在散列表所在的基本存儲區域裡，例如，可以再基本存儲區域裡從後向前探測空閒表項，找到後就將其連結到同義詞子表中，這個方法稱為“結合的同義詞子表法”，或稱為“公共鍊表地址法”。
獨立鍊表地址法是查找效率最好的解決衝突的方法，速度要快於開放地址法，因為獨立鍊表地址法在進行散列查找時僅需搜尋同義詞表。開放地址法要求表長時固定的，而地理鍊表法中的表項則是動態分配的，其表長僅受記憶體空間的限制。鍊表法的主要缺點是需要為每個表項（包括分離的同義子表的每個節點）設立一個指針域。
總之，獨立鍊表地址法的動態結構使它成為散列法中解決衝突的首選方法。

散列表的運算

設用HashMaxSize常量表示待定義的散列表類型的長度。假定採用開放定址法,其散列表類型用hashlist1表示,類型定義為：
typedef ElemType hashlist1[HashMaxSize];
若採用連結表，其散列表類型用hashlist2表示
Lnode 定義如下：
struct Lnode
{
ElemType data;
Lnode *next;
}
在類型為hashlist1的散列表上進行的運算
初始化散列表
void InitHashList (hashlist1 HT)
{
//把散列表HT中每一單元的關鍵字key域都置空
for(int i=0;i<HashMaxSize;i++)
HT[i].key=NullTag; //NullTag常量表示空標誌，
}
清空一個散列表
void ClearHashList (hashlist1 HT)
{
//把散列表HT中每一單元的關鍵字key域都置空
for(int i=0;i<HashMaxSize;i++)
HT[i].key=NullTag;
}
向散列表中插入一個元素
int Insert (hashlist1 HT,int m,ElemType item)
{
//向長度為m的散列表HT中插入一個元素item
int d=H(item.key,m);
int temp=d;
while(HT[d].key != NullTag)
{
//當d單元不空時繼續向後查找空位置
d=(d+1)%m;
if(d==temp) return 0;
}
HT[d]=item; //將新元素插入到下標為d的位置
return 1;
} //返回1表示插入成功
從散列表中查找一個元素
int Search (hashlist1 HT,int m, ElemType item)
{
//從長度為m的散列表HT中查找關鍵字為item.key的一個元素
int d=H(item.key, m);
int temp=d;
while(HT[d].key!=NullTag)
{
//當散列地址中的關鍵字域不為空則循環
if(HT[d].key==item.key) return d; //查找成功則反回下標d
else d=(d+1)%m;
if(d==temp) return -1; //查找失敗反回-1
}
return -1;
}
從散列表中刪除一個元素
int Delete (hashlist1 HT,int m, ElemType item)
{
//從長度為m的散列表HT中刪除關鍵字為item.key的一個元素
int d=H(item.key, m);
int temp=d;
while(HT[d].key!=NullTag)
{
if(HT[d].key==item.key)
{
HT[d].key=DeleteTag;//DeleteTag常量為一刪除標記
return 1;
}
else d=(d+1)%m; //繼續向後探查
if(d==temp) return 0;
}
return 0; //刪除失敗返回0
}
在類型為hashlist2的散列表上進行的運算
類型定義：
struct Lnode
{
ElemType data;
Lnode *next;
}
typedef LNode * hashlist2[HashMaxSize];
初始化散列表
void InitHashList(hashlist2 HT)
{
//把散列表HT中每一元素均置為空標誌
for(int i=0;i<HashMaxSize;i++)
HT[i].i=NULL;
}
清空一個散列表
void ClearHashList(hashlist2 HT)
{
//清除HT散列表,即回收每個單鍊表中的結點
LNode * p;
for(int i=0;i<HashMaxSize;i++)
{
p=HT[i];
while(p!=NULL)
{
HT[i]=p->next;
delete p;
p=HT[i];
}
}
}
向散列表中插入一個元素
int Insert(hashlist2 HT,int m,ElemType item)
{
//向長度為m的帶連線的散列表HT中插入一個元素item
int d=Hash(item.key,m);
LNode *p=new LNode;//為新元素分配存儲結點
if(p==NULL) return0;
p->data=item;//把新結點插入到d單鍊表的表頭
p->next=HT[d];
HT[d]=p;
return 1;
}
從散列表中查找一個元素
ElemType* Search(hashlist2 HT,int m,ElemType item)
{
//從長度為m的帶連結的散列表HT中查找元素
int d=Hash(item.key,m);
LNode* p=HT[d];
while(p!=NULL)
{
if(p->data.key==item.key) return &(p->data);
else p=p->next;
}
return NULL; //查找失敗返回空指針
}
從散列表中刪除一個元素
int Delete(hashlist2 HT,int m,ElemType item)
{
//從長度為m的帶連結的散列表HT中刪除元素
int d=Hash(item.kye,m);
LNode* p=HT[d],* q;
if (p==NULL) return 0;
if (p->data.key==item.key)
{
HT[d]=p->next;
delete p;
return 1;
}
//從第二個結點起查找被刪除的元素
q=p->next;
while(q!=NULL)
{
if(q->data.key)==item.key）
{
p->next=q->next;
delete q;
return 1;
}
else
{
p=q;q=q->next;
}
}
//返回0表示刪除失敗;
return 0;
}

相關詞條

熱門詞條

聯絡我們