哈希結(jié)構(gòu)
C++博客 Alex-Lee 2009-10-21
哈希結(jié)構(gòu)在處理大量數(shù)據(jù)時(shí)具有很好的優(yōu)勢(shì)，在插入，查詢，刪除等操作上具有常量的時(shí)間復(fù)雜度O(1)。使用范圍是數(shù)據(jù)集具有自然數(shù)上的關(guān)鍵字域（不是自然數(shù)也需要能夠轉(zhuǎn)為自然數(shù)域），通過哈希函數(shù)將關(guān)鍵字映射到尋址數(shù)組的槽。由于關(guān)鍵字域U[0...n]與尋址數(shù)組[0...m]中，總是n>m，也就是說，總有多個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)槽。這個(gè)碰撞就需要通過一些方法改變。可以通過拉鏈法（鏈表法）和開放地址法。對(duì)于拉鏈法中，鏈表不能太長，否則影響速度，最好控制在10個(gè)元素之內(nèi)，這樣就要去尋址數(shù)組長度m>= n/10，這樣就會(huì)多消耗些空間。為了讓每個(gè)鏈表長度基本一致，就需要選擇合適的關(guān)鍵字到槽的映射函數(shù)，即哈希函數(shù)。在選取哈希函數(shù)方面有3種方法：乘法、除法、全域法。乘法對(duì)m值選取上要求比較強(qiáng)，而除法對(duì)m值沒有特別要求，全域法則是在一組哈希函數(shù)中，運(yùn)行時(shí)每次隨機(jī)的選取一個(gè)哈希函數(shù)。因此，全域法在隨機(jī)上具有更好的均勻分布，性能最好。下面是拉鏈法的實(shí)現(xiàn)：
1，哈希節(jié)點(diǎn)：
1
typedef struct data_node
2
{
3
void *data;
4 int length;
5 int key;
6 struct data_node *prev,*next;
7
} DATA_NODE;
2，創(chuàng)建哈希表
1//拉鏈技術(shù)雜湊法
2static const int m = 100701;
3int hash_create(HASH_TABLE *pht)
4{
5 HASH_TABLE ht;
6 int i;
7 ht = (HASH_TABLE) LM_MALLOC(sizeof(DATA_NODE) * m);
8 if (!ht)
9
{
10 return -1;
11
}
12 for (i = 0; i < m;++i)
13 {
14 ht[i].data = 0;
15 ht[i].length = 0;
16 ht[i].key = -1;
17 ht[i].prev = 0;
18 ht[i].next = 0;
19 }
20 *pht = ht;
21 return 0;
22}
3，銷毀哈希表
1int hash_free(HASH_TABLE ht)
2{
3 int i ;
4 DATA_NODE *pd,*pq;
5 for (i = 0; i < m ; ++i)
6 {
7 pd = ht[i].next;
8 while(pd)
9 {
10 pq = pd->next;
11 LM_FREE(pd->data);
12 LM_FREE(pd);
13 pd = pq;
14 }
15 }
16 LM_FREE(ht);
17 return 0;
18}
4，插入元素
1int hash_insert(HASH_TABLE ht,DATA_NODE *pd)
2{
3 DATA_NODE *pq,*pb;
4 int slot;
5 slot = hash_all(pd->key);
6 pq = ht[slot].next;
7 pb = (DATA_NODE*)LM_MALLOC(sizeof(DATA_NODE));
8 if (!pb)
9 {
10 return -1;
11 }
12 pb->data = (char*)LM_MALLOC(sizeof(char)*pd->length);
13 if (!pb->data)
14 {
15 LM_FREE(pb);
16 return -1;
17 }
18 memcpy(pb->data,pd->data,pd->length);
19 pb->length = pd->length;
20 pb->prev = &ht[slot];
21 pb->next = pq;
22 pb->key = pd->key;
23 ht[slot].next = pb;
24 return 0;
25}
5，查詢
1DATA_NODE * hash_search(HASH_TABLE ht,int key)
2{
3 DATA_NODE *pq;
4 int slot;
5 slot = hash_all(key);
6 pq = ht[slot].next;
7 while(pq)
8 {
9 if (pq->key == key)
10 {
11 return pq;
12 }
13 pq = pq->next;
14 }
15 return 0;
16}
6，刪除
1int hash_delete(HASH_TABLE ht,int key)
2{
3 DATA_NODE *pq;
4 int slot;
5 slot = hash_all(key);
6 pq = ht[slot].next;
7 while(pq)
8 {
9 if (pq->key == key)
10 {
11 pq->prev->next = pq->next;
12 LM_FREE(pq->data);
13 LM_FREE(pq);
14 return 0;
15 }
16 pq = pq->next;
17 }
18 return -1;
19}
7，哈希函數(shù)
1//除法雜湊法
2int hash_div(int key)
3{
4 //h(k)=k mod m
5 //static const int m = 701;
6 return key % m;
7}
8//乘法雜湊法
9int hash_mul(int key)
10{
11 static const double A = 0.6180339887;
12 //static const int m = 701;
13 return (int)floor(m * fmod(key * A,1));
14}
15
16//全域雜湊法
17int hash_all(int key)
18{
19 return hash_mul(key);
20 //從雜湊法函數(shù)組中隨即選擇一個(gè)
21 if ((rand()%2) == 0)
22 {
23 return hash_div(key);
24 }
25 else
26 {
27 return hash_mul(key);
28 }
29}
8，測(cè)試
由于耗費(fèi)內(nèi)存比較大，測(cè)試100W整數(shù)的插入操作是4秒左右，查詢操作是2秒左右，刪除時(shí)0.4秒左右，1000w整數(shù)的上述操作分別是47s,22s,3.3s。
看起來效率還是不錯(cuò)。
算法實(shí)現(xiàn)代碼
posted on 2009-10-22 00:31
Alex-Lee 閱讀(1933)
評(píng)論(5) 編輯 收藏 引用