Hashing定義了一種將字符組成的字符串轉(zhuǎn)換為固定長度(一般是更短長度)的數(shù)值或索引值的方法,稱為散列法,也叫哈希法。由于通過更短的哈希值比用原始值進(jìn)行數(shù)據(jù)庫搜索更快,這種方法一般用來在數(shù)據(jù)庫中建立索引并進(jìn)行搜索,同時還用在各種解密算法中。
設(shè)所有可能出現(xiàn)的關(guān)鍵字集合記為U(簡稱全集)。實際發(fā)生(即實際存儲)的關(guān)鍵字集合記為K(|K|比|U|小得多)。|K|是集合K中元素的個數(shù)。
散列方法是使用函數(shù)hash將U映射到表T[0..m-1]的下標(biāo)上(m=O(|U|))。這樣以U中關(guān)鍵字為自變量,以h為函數(shù)的運算結(jié)果就是相應(yīng)結(jié)點的存儲地址。從而達(dá)到在O(1)時間內(nèi)就可完成查找。
其中:
① hash:U→{0,1,2,…,m-1} ,通常稱h為散列函數(shù)(Hash Function)。散列函數(shù)h的作用是壓縮待處理的下標(biāo)范圍,使待處理的|U|個值減少到m個值,從而降低空間開銷。
② T為散列表(Hash Table)。
③ hash(Ki)(Ki∈U)是關(guān)鍵字為Ki結(jié)點存儲地址(亦稱散列值或散列地址)。
④ 將結(jié)點按其關(guān)鍵字的散列地址存儲到散列表中的過程稱為散列(Hashing).
比如:有一組數(shù)據(jù)包括用戶名字、電話、住址等,為了快速的檢索,我們可以利用名字作為關(guān)鍵碼,hash規(guī)則就是把名字中每一個字的拼音的第一個字母拿出來,把該字母在26個字母中的順序值取出來加在一塊作為改記錄的地址。比如張三,就是Z+S=26+19=45。就是把張三存在地址為45處。
但是這樣存在一個問題,比如假如有個用戶名字叫做:周四,那么計算它的地址時也是Z+S=45,這樣它與張三就有相同的地址,這就是沖突,也叫作碰撞!
沖突:兩個不同的關(guān)鍵字,由于散列函數(shù)值相同,因而被映射到同一表位置上。該現(xiàn)象稱為沖突(Collision)或碰撞。發(fā)生沖突的兩個關(guān)鍵字稱為該散列函數(shù)的同義詞(Synonym)。
沖突基本上不可避免的,除非數(shù)據(jù)很少,我們只能采取措施盡量避免沖突,或者尋找解決沖突的辦法。影響沖突的因素
沖突的頻繁程度除了與h相關(guān)外,還與表的填滿程度相關(guān)。
設(shè)m和n分別表示表長和表中填人的結(jié)點數(shù),則將α=n/m定義為散列表的裝填因子(Load Factor)。α越大,表越滿,沖突的機(jī)會也越大。通常取α≤1。
----散列函數(shù)的構(gòu)造方法:----
1、散列函數(shù)的選擇有兩條標(biāo)準(zhǔn):簡單和均勻。
簡單指散列函數(shù)的計算簡單快速;
均勻指對于關(guān)鍵字集合中的任一關(guān)鍵字,散列函數(shù)能以等概率將其映射到表空間的任何一個位置上。也就是說,散列函數(shù)能將子集K隨機(jī)均勻地分布在表的地址集{0,1,…,m-1}上,以使沖突最小化。
2、常用散列函數(shù)
(1)直接定址法:比如在一個0~100歲的年齡統(tǒng)計表,我們就可以把年齡作為地址。
(2)平方取中法
具體方法:先通過求關(guān)鍵字的平方值擴(kuò)大相近數(shù)的差別,然后根據(jù)表長度取中間的幾位數(shù)作為散列函數(shù)值。又因為一個乘積的中間幾位數(shù)和乘數(shù)的每一位都相關(guān),所以由此產(chǎn)生的散列地址較為均勻。
(3)除留余數(shù)法
取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址。
該方法的關(guān)鍵是選取m。選取的m應(yīng)使得散列函數(shù)值盡可能與關(guān)鍵字的各位相關(guān)。m最好為素數(shù)
(4)隨機(jī)數(shù)法
選擇一個隨機(jī)函數(shù),取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址,即h(key)=random(key)
其中random為偽隨機(jī)函數(shù),但要保證函數(shù)值是在0到m-1之間。
----處理沖突的方法:---- 1、開放定址法
Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
其中m為表長,di為增量序列
如果di值可能為1,2,3,...m-1,稱線性探測再散列。
如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
稱二次探測再散列。
如果di取值可能為偽隨機(jī)數(shù)列。稱偽隨機(jī)探測再散列。
開放地址法堆裝填因子的要求
開放定址法要求散列表的裝填因子α≤l,實用中取α為0.5到0.9之間的某個值為宜。
2、二次探查法(Quadratic Probing)
二次探查法的探查序列是:
hi=(h(key)+i*i)%m 0≤i≤m-1 //即di=i2
即探查序列為d=h(key),d+12,d+22,…,等。
該方法的缺陷是不易探查到整個散列空間。
3、雙重散列法(Double Hashing)
該方法是開放定址法中最好的方法之一,它的探查序列是:
hi=(h(key)+i*h1(key))%m 0≤i≤m-1 //即di=i*h1(key)
即探查序列為:
d=h(key),(d+h1(key))%m,(d+2h1(key))%m,…,等。
該方法使用了兩個散列函數(shù)h(key)和h1(key),故也稱為雙散列函數(shù)探查法。
3、拉鏈法
拉鏈法解決沖突的做法是:將所有關(guān)鍵字為同義詞的結(jié)點鏈接在同一個單鏈表中。若選定的散列表長度為m,則可將散列表定義為一個由m個頭指針組成的指針數(shù)組T[0..m-1]。凡是散列地址為i的結(jié)點,均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應(yīng)為空指針。在拉鏈法中,裝填因子α可以大于1,但一般均取α≤1。
4、建立一個公共溢出區(qū)
假設(shè)哈希函數(shù)的值域為[0,m-1],則設(shè)向量HashTable[0..m-1]為基本表,另外設(shè)立存儲空間向量OverTable[0..v]用以存儲發(fā)生沖突的記錄。
----性能分析----
插入和刪除的時間均取決于查找,故下面只分析查找操作的時間性能。
雖然散列表在關(guān)鍵字和存儲位置之間建立了對應(yīng)關(guān)系,理想情況是無須關(guān)鍵字的比較就可找到待查關(guān)鍵字。但是由于沖突的存在,散列表的查找過程仍是一個和關(guān)鍵字比較的過程,不過散列表的平均查找長度比順序查找、二分查找等完全依賴于關(guān)鍵字比較的查找要小得多。
(1)查找成功的ASL
散列表上的查找優(yōu)于順序查找和二分查找。
(2)查找不成功的ASL
對于不成功的查找,順序查找和二分查找所需進(jìn)行的關(guān)鍵字比較次數(shù)僅取決于表長,而散列查找所需進(jìn)行的關(guān)鍵字比較次數(shù)和待查結(jié)點有關(guān)。因此,在等概率情況下,也可將散列表在查找不成功時的平均查找長度,定義為查找不成功時對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)。
注意:
①由同一個散列函數(shù)、不同的解決沖突方法構(gòu)造的散列表,其平均查找長度是不相同的。
②散列表的平均查找長度不是結(jié)點個數(shù)n的函數(shù),而是裝填因子α的函數(shù)。因此在設(shè)計散列表時可選擇α以控制散列表的平均查找長度。
③ α的取值
α越小,產(chǎn)生沖突的機(jī)會就小,但α過小,空間的浪費就過多。只要α選擇合適,散列表上的平均查找長度就是一個常數(shù),即散列表上查找的平均時間為O(1)。
④ 散列法與其他查找方法的區(qū)別
除散列法外,其他查找方法有共同特征為:均是建立在比較關(guān)鍵字的基礎(chǔ)上。其中順序查找是對無序集合的查找,每次關(guān)鍵字的比較結(jié)果為"="或"!="兩種可能,其平均時間為O(n);其余的查找均是對有序集合的查找,每次關(guān)鍵字的比較有"="、"<"和">"三種可能,且每次比較后均能縮小下次的查找范圍,故查找速度更快,其平均時間為O(lgn)。而散列法是根據(jù)關(guān)鍵字直接求出地址的查找方法,其查找的期望時間為O(1)。
例子:
選取哈希函數(shù)H(K)=(3K)%11,用線性探測再散列法處理沖突。
試在0~10的散列地址空間中,對關(guān)鍵序列22,41,53,46,30,13,01,67構(gòu)造哈希表,并求等概率情況下查找不成功的平均查找長度ASL。
/**//*--------------------------------------------------------
* hashtable.cpp
* Describe : example for hashing
* author : JackRain
* date : 08-13-2005
* E_mail : jack.fandlr@gmail.com
* Test with C-Free3.5
---------------------------------------------------------*/
#include <iostream>
#define addr_scope 11
int hash(int key)
{
return(key*3)%11;
}
typedef int KeyType,DataType,Status;
//typedef int DataType;
//typedef int Status;
typedef struct {
KeyType key;
// DataType data;
Status stat; //1 = over; 0
}Element;
class HashTable
{
public:
HashTable(int n);
~HashTable();
bool insert(int e);
bool search(int e, int *pos);
void display();
private:
Element *elem;
int hash_size;
int dataNum;
};
HashTable::HashTable(int n):hash_size(n),dataNum(0)
{
// hash_size = n;
// dataNum = 0;
elem = new Element[n];
for(int i=0;i < n;i++)
{
elem[i].key = 0;
elem[i].stat = 0;
}
}
HashTable::~HashTable()
{
delete[] elem;
}
bool HashTable::insert(int e)
{
if(dataNum == hash_size)
{
cout<<"OverFlow!"<<endl;
return false;
}
int pos = hash(e),pos1;
pos1 = pos;
for(int i = 1; i < hash_size; i ++)
{
if(elem[pos].stat==0)
{
//success
elem[pos].key = e;
elem[pos].stat = 1;
dataNum++;
cout<<"Insert Value Success!The value is:"<<e<<";the addr is:"<<pos<<endl;
return true;
}
pos = (pos1+i)%hash_size;
}
cout<<"Insert Value Faliure"<<endl;
return false;
}
bool HashTable::search(int key, int* pos)
{
int hashvalue = hash(key);
for(int i = 1; i< hash_size; i ++)
{
if(elem[hashvalue].stat==1&&elem[hashvalue].key == key)
{
cout<<"Search Success!Search Nums="<<i<<endl;
*pos = hashvalue;
return true;
}
hashvalue = (hashvalue+1)%hash_size;
}
cout<<"Not found"<<endl;
return false;
}
void HashTable::display()
{
if(dataNum == 0)
{
cout<<"The Table is NULL"<<endl;
return;
}
cout<<"************HashTable*************"<<endl;
cout<<"addr value"<<endl;
for(int i = 0; i<hash_size;i++)
{
if(elem[i].stat == 0)
continue;
else
cout.width(4);
cout<<elem[i].key;
cout<<" ";
cout.width(5);
cout<<i<<endl;
}
cout<<"************************************"<<endl;
}
int main()
{
int array[]= {22, 41, 53, 46, 30,13, 01,67};
HashTable hTable(addr_scope);
for(int i =0;i < 8;i++)
hTable.insert(array[i]);
hTable.display();
return 0;
}
查找不成功的平均查找長度ASL=(2+1+8+7+6+5+4+3+2+1+1)/11≈3.63