|
哈希表（Hash table，也叫散列表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。具體的介紹網(wǎng)上有很詳細(xì)的描述，如閑聊哈希表 ，這里就不再累述了；
哈希表在像Java、C#等語言中是與生俱來的?？墒窃贑的世界中，似乎只有自己動(dòng)手，豐衣足食；在網(wǎng)上google了一把，大致有幾個(gè)版本，我會(huì)一一來分析對(duì)比；
首先先來交代一下哈希表實(shí)現(xiàn)中需要注意的一些概念：
（主要參考：這里）
- 哈希函數(shù)
也叫散列函數(shù)，即：根據(jù)key,計(jì)算出key對(duì)應(yīng)記錄的儲(chǔ)存位置
position = f(key)
散列函數(shù)滿足以下的條件：
1、對(duì)輸入值運(yùn)算，得到一個(gè)固定長度的摘要(Hash value)；
2、不同的輸入值可能對(duì)應(yīng)同樣的輸出值；
以下的函數(shù)都可以認(rèn)為是一個(gè)散列函數(shù)：
f(x) = x mod 16; (1)
f(x) = (x2 + 10) * x; (2)
f(x) = (x | 0×0000FFFF) XOR (x >> 16); (3)
不過，僅僅滿足上面這兩條的函數(shù)，作為散列函數(shù)，還有不足的地方。我們還希望散列函數(shù)滿足下面幾點(diǎn)：
1、散列函數(shù)的輸出值盡量接近均勻分布；
2、x的微小變化可以使f(x)發(fā)生非常大的變化，即所謂“雪崩效應(yīng)”(Avalanche effect)；
上面兩點(diǎn)用數(shù)學(xué)語言表示，就是：
1， 輸出值y的分布函數(shù)F(y)=y/m, m為散列函數(shù)的最大值?；蛴洖閥~U[0, m]
2，|df(x)/dx| >> 1；
從上面兩點(diǎn)，大家看看，前面舉例的三個(gè)散列函數(shù)，哪個(gè)更好呢？對(duì)了，是第三個(gè)：
f(x) = (x | 0×0000FFFF) XOR (x >> 16);
它很完美地滿足“好的散列函數(shù)”的兩個(gè)附加條件。
2、哈希沖突（Hash collision）
也就是兩個(gè)不同輸入產(chǎn)生了相同輸出值的情況。首先，哈希沖突是無法避免的，因此，哈希算法的選擇直接決定了哈希沖突發(fā)送的概率；同時(shí)必須要對(duì)哈希沖突進(jìn)行處理，方法主要有以下幾種：
1， 鏈地址法
鏈地址法：對(duì)Hash表中每個(gè)Hash值建立一個(gè)沖突表，即將沖突的幾個(gè)記錄以表的形式存儲(chǔ)在其中
2， 開放地址法
下面就來看看每種方法的具體實(shí)現(xiàn)吧：
鏈地址法：
舉例說明： 設(shè)有 8 個(gè)元素 { a,b,c,d,e,f,g,h } ，采用某種哈希函數(shù)得到的地址分別為： {0 ， 2 ， 4 ， 1 ， 0 ， 8 ， 7 ， 2} ，當(dāng)哈希表長度為 10 時(shí)，采用鏈地址法解決沖突的哈希表如下圖所示。
 圖片及舉例引自：這里
 1 #include "stdafx.h"
2 #include <string.h>
3 #include <stdio.h>
4 #include <stdlib.h>
5
6 typedef struct _node{
7 char *name;
8 char *desc;
9 struct _node *next;
10 }node;
11
12 #define HASHSIZE 101
13 static node* hashtab[HASHSIZE];
14
15 void inithashtab(){
16 int i;
17 for(i=0;i<HASHSIZE;i++)
18 hashtab[i]=NULL;
19 }
20
21 unsigned int hash(char *s){
22 unsigned int h=0;
23 for(;*s;s++)
24 h=*s+h*31;
25 return h%HASHSIZE;
26 }
27
28 node* lookup(char *n){
29 unsigned int hi=hash(n);
30 node* np=hashtab[hi];
31 for(;np!=NULL;np=np->next){
32 if(!strcmp(np->name,n))
33 return np;
34 }
35
36 return NULL;
37 }
38
39 char* m_strdup(char *o){
40 int l=strlen(o)+1;
41 char *ns=(char*)malloc(l*sizeof(char));
42 strcpy(ns,o);
43 if(ns==NULL)
44 return NULL;
45 else
46 return ns;
47 }
48
49 char* get(char* name){
50 node* n=lookup(name);
51 if(n==NULL)
52 return NULL;
53 else
54 return n->desc;
55 }
56
57 int install(char* name,char* desc){
58 unsigned int hi;
59 node* np;
60 if((np=lookup(name))==NULL){
61 hi=hash(name);
62 np=(node*)malloc(sizeof(node));
63 if(np==NULL)
64 return 0;
65 np->name=m_strdup(name);
66 if(np->name==NULL) return 0;
67 np->next=hashtab[hi];
68 hashtab[hi]=np;
69 }
70 else
71 free(np->desc);
72 np->desc=m_strdup(desc);
73 if(np->desc==NULL) return 0;
74
75 return 1;
76 }
77
78 /* A pretty useless but good debugging function,
79 which simply displays the hashtable in (key.value) pairs
80 */
81 void displaytable(){
82 int i;
83 node *t;
84 for(i=0;i<HASHSIZE;i++){
85 if(hashtab[i]==NULL)
86 printf("()");
87 else{
88 t=hashtab[i];
89 printf("(");
90 for(;t!=NULL;t=t->next)
91 printf("(%s.%s) ",t->name,t->desc);
92 printf(".)");
93 }
94 }
95 }
96
97 void cleanup(){
98 int i;
99 node *np,*t;
100 for(i=0;i<HASHSIZE;i++){
101 if(hashtab[i]!=NULL){
102 np=hashtab[i];
103 while(np!=NULL){
104 t=np->next;
105 free(np->name);
106 free(np->desc);
107 free(np);
108 np=t;
109 }
110 }
111 }
112 }
113
114 main(){
115 int i;
116 char* names[]={"name","address","phone","k101","k110"};
117 char* descs[]={"Sourav","Sinagor","26300788","Value1","Value2"};
118
119 inithashtab();
120 for(i=0;i<5;i++)
121 install(names[i],descs[i]);
122
123 printf("Done");
124 printf("If we didnt do anything wrong..""we should see %s",get("k110"));
125
126 install("phone","9433120451");
127
128 printf("Again if we go right, we have %s and %s",get("k101"),get("phone"));
129
130 /*displaytable();*/
131 cleanup();
132 return 0;
133 }
（未完待續(xù)）
|
