hash表定義:hashing定義了一種将字元組成的字元串轉換為固定長度(一般是更短長度)的數值或索引值的方法,稱為散列法,也叫哈希法。由于通過更短的哈希值比用原始值進行資料庫搜尋更快,這種方法一般用來在資料庫中建立索引并進行搜尋,同時還用在各種解密算法中。
設所有可能出現的關鍵字集合記為u(簡稱全集)。實際發生(即實際存儲)的關鍵字集合記為k(|k|比|u|小得多)。|k|是集合k中元素的個數。
散列方法是使用函數hash将u映射到表t[0..m-1]的下标上(m=o(|u|))。這樣以u中關鍵字為自變量,以h為函數的運算結果就是相應結點的存儲位址。進而達到在o(1)時間内就可完成查找。
其中:
① hash:u→{0,1,2,…,m-1} ,通常稱h為散列函數(hash function)。散列函數h的作用是壓縮待處理的下标範圍,使待處理的|u|個值減少到m個值,進而降低空間開銷。
② t為散清單(hash table)。
③ hash(ki)(ki∈u)是關鍵字為ki結點存儲位址(亦稱散列值或散列位址)。
④ 将結點按其關鍵字的散列位址存儲到散清單中的過程稱為散列(hashing).
比如:有一組資料包括使用者名字、電話、住址等,為了快速的檢索,我們可以利用名字作為關鍵碼,hash規則就是把名字中每一個字的拼音的第一個字母拿出來,把該字母在26個字母中的順序值取出來加在一塊作為該記錄的位址。比如張三,就是z+s=26+19=45。就是把張三存在位址為45處。
但是這樣存在一個問題,比如假如有個使用者名字叫做:周四,那麼計算它的位址時也是z+s=45,這樣它與張三就有相同的位址,這就是沖突,也叫作碰撞(hash碰撞)。
沖突:兩個不同的關鍵字,由于散列函數值相同,因而被映射到同一表位置上。該現象稱為沖突(collision)或碰撞。發生沖突的兩個關鍵字稱為該散列函數的同義詞(synonym)。
沖突基本上不可避免的,除非資料很少,我們隻能采取措施盡量避免沖突,或者尋找解決沖突的辦法。影響沖突的因素
沖突的頻繁程度除了與h相關外,還與表的填滿程度相關。
設m和n分别表示表長和表中填入的結點數,則将α=n/m定義為散清單的裝填因子(load factor)。α越大,表越滿,沖突的機會也越大。通常取α≤1。
簡單實作程式如下:
其中hash_i()為hash函數,提供兩種處理沖突的方法線性探測法和雙重散列法。用的測試資料為100000以内的不重複随機數,
裝填因子α=9000/11000,也就是9000個數放到11000個盒子裡;
測試結果:資料較少時,雙重散列法偏優,α=9000/11000時兩種處理沖突方法得到的平均查找長度基本相當。
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <hash_map.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
using namespace std;
#define ARRAY_SIZE 9000
#define HASH_LENGTH 11000
int hash_i(int i) {
return (3*i)%HASH_LENGTH;
}
//template<class T>
int main(int argc, char* argv[]) {
//int ai[]={22,41,53,46,30,13,01,67,32};
//constractor the test random array ai[]
srand((int)time(NULL));
int ai[ARRAY_SIZE]={0};
int i=0;
int *hashtable = (int*)malloc(sizeof(int)*(HASH_LENGTH+1));
for(i = 0; i < ARRAY_SIZE; i++) {
int t = rand()%100000;
int k;
for(k = 0; k < ARRAY_SIZE; k++) {
if(t == ai[k])
break;
}
if(k != ARRAY_SIZE) continue;
ai[i]=t;
}
//initial hashtable[]
for(i=0; i< HASH_LENGTH; i++) {
hashtable[i]=-1;
}
int k=1;
int m = 1;
for(i = 0;i < ARRAY_SIZE ;i++ ) {
int n;
printf("hash value%d=%d\n",i,n=hash_i(ai[i]));
if( hashtable[n] == -1 ) {
hashtable[n]=ai[i];
}
else {
int tmp1,tmp2;
#ifndef DOUBLE_HASHING
//線性探測法
//探測序列從不成功hash值後面逐個加1比較,即n,n+1,...HASH_LENGTH-1,0,1,..n-1
do {
tmp2 = (n+m)%HASH_LENGTH;
if(hashtable[tmp2] == -1) {
hashtable[tmp2] = ai[i];
printf("tmp2=%d,try again total %d times\n",tmp2,k++);
break;
}
}while( tmp2 != n ,m++);
#else
//雙重散列法(double hashing)
//h(key)為hash(key)
//h1=(h(key)+i*i)%m
//hi=(h(key)+i*h1(key))%m
//m為hash表長,hi為第i次的散列值
for(m = 0; m < HASH_LENGTH ;m++) {
tmp1 = (n+m*m)%HASH_LENGTH;
tmp2 = (n+m*tmp1)%HASH_LENGTH;
if(hashtable[tmp2] == -1) {
hashtable[tmp2]=ai[i];
printf("tmp2=%d,try again total %d times\n",tmp2,k++);
break;
}
}
#endif
if(m == HASH_LENGTH)
printf("table is full!\n");
}
}
for(i = 0; i < HASH_LENGTH ;i++)
printf("hashtable[%d]=%d\n",i,hashtable[i]);
printf("不成功的asl=%.2f\n",(k-1)*1.0/ARRAY_SIZE);
if(hashtable) {
free(hashtable);
hashtable = NULL;
}
return 0;
}