基于比較的的查找方法，查找效率依賴比較次數(shù)，其實理想的查找是希望不經比較，一次存取便能得到所查記錄。這樣就必須在記錄的存儲位置和它的關鍵字之間建立一個確定
的對應關系f，查找k時,只要根據這個對應關系f找到給定值k的像f(k)。這種對應關系f叫哈希（hash）函數(shù)。按這種思想建立的表叫哈希表（也叫散
列表）。
哈希表存取方便但存儲時容易沖突（collision）：即不同的關鍵字可以對應同一哈希地址。如何確定哈希函數(shù)和解決沖突是哈希表查找的關鍵。
1.哈希函數(shù)的構造方法
構造哈希函數(shù)的方法有很多，這里介紹幾種常用的。
直接定址法:H(k)=k 或H(k)=a*k+b(線形函數(shù))
如:人口數(shù)字統(tǒng)計表
| 地址 |
1 |
2 |
3 |
... |
100 |
| 年齡 |
1 |
2 |
3 |
... |
100 |
| 人數(shù) |
67 |
3533 |
244 |
... |
4 |
數(shù)字分析法:取關鍵字的若干數(shù)位組成哈希地址
如：關鍵字如下：若哈希表長為100則可取中間兩位10進制數(shù)作為哈希地址。
| 81346532 |
81372242 |
81387422 |
81301367 |
81322817 |
81338967 |
81354157 |
81368537 |
平方取中法：關鍵字平方后取中間幾位數(shù)組成哈希地址
折疊法：將關鍵數(shù)字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）然后取幾部分的疊加和（舍去進位）作為哈希地址。
除留余數(shù)法：取關鍵字被某個不大于表長m的數(shù)p除后所得的余數(shù)為哈希地址。
H(k)=k mod p p<=m
隨機數(shù)法：H(k)=rondom(k)。
2.處理沖突的方法
假設地址集為0..n-1,由關鍵字得到的哈希地址為j(0<=j<=n-1)的位置已存有記錄,處理沖突就是為該關鍵字的記錄找到另一個"
空"的哈希地址。在處理中可能得到一個地址序列Hi i=1，2，...k
0<=Hi<=n-1),即在處理沖突時若得到的另一個哈希地址H1仍發(fā)生沖突,再求下一地址H2,若仍沖突,再求H3...。怎樣得到Hi
呢？
開放定址法：Hi=(H(k)+di) mod m （H(k)為哈希函數(shù)；m為哈希表長；di為增量序列）
當di=1，2，3，... m-1 時叫線性探測再散列。
當di=12，-12，22，-22，32，-32，...,k2,-k2時叫二次探測再散列。
當di=random（m）時叫偽隨機探測序列。
例：長度為11的哈希表關鍵字分別為17，60，29，哈希函數(shù)為H(k)=k mod 11,第四個記錄的關鍵字為38，分別按上述方法添入哈希表的地址為8，4，3（隨機數(shù)=9）。---為什么不是6，5，7呢
再哈希法：Hi=RHi(key) i=1,2,...,k,其中RHi均為不同的哈希函數(shù)。
鏈地址法：這種方法很象基數(shù)排序，相同的地址的關鍵字值均鏈入對應的鏈表中。
建立公益區(qū)法：另設一個溢出表，不管得到的哈希地址如何，一旦發(fā)生沖突，都填入溢出表。
3.哈希表的查找
例:如下一組關鍵字按哈希函數(shù)H(k)=k mod 13和線性探測處理沖突所得的哈希表a[0..15]:
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| |
14 |
01 |
68 |
27 |
55 |
19 |
20 |
84 |
79 |
23 |
11 |
10 |
|
|
|
當給定值k=84,則首先和a[6]比，再依次和a[7],a[8]比，結果a[8]=84查找成功。
當給定值k=38,則首先和a[12]比,再和a[13]比,由于a[13]沒有,查找不成功,表中不存在關鍵字等于38的記錄。
from：
http://www.coood.com/postfile/2006-12-31/20061231174649.shtml
others will be appended later
posted on 2010-03-07 23:24
chatler 閱讀(294)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm