哈希結構
C++博客 Alex-Lee 2009-10-21
哈希結構在處理大量數據時具有很好的優勢，在插入，查詢，刪除等操作上具有常量的時間復雜度O(1)。使用范圍是數據集具有自然數上的關鍵字域（不是自然數也需要能夠轉為自然數域），通過哈希函數將關鍵字映射到尋址數組的槽。由于關鍵字域U[0...n]與尋址數組[0...m]中，總是n>m，也就是說，總有多個關鍵字對應一個槽。這個碰撞就需要通過一些方法改變。可以通過拉鏈法（鏈表法）和開放地址法。對于拉鏈法中，鏈表不能太長，否則影響速度，最好控制在10個元素之內，這樣就要去尋址數組長度m>= n/10，這樣就會多消耗些空間。為了讓每個鏈表長度基本一致，就需要選擇合適的關鍵字到槽的映射函數，即哈希函數。在選取哈希函數方面有3種方法：乘法、除法、全域法。乘法對m值選取上要求比較強，而除法對m值沒有特別要求，全域法則是在一組哈希函數中，運行時每次隨機的選取一個哈希函數。因此，全域法在隨機上具有更好的均勻分布，性能最好。下面是拉鏈法的實現：
1，哈希節點：
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，創建哈希表
1//拉鏈技術雜湊法
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，哈希函數
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 //從雜湊法函數組中隨即選擇一個
21 if ((rand()%2) == 0)
22 {
23 return hash_div(key);
24 }
25 else
26 {
27 return hash_mul(key);
28 }
29}
8，測試
由于耗費內存比較大，測試100W整數的插入操作是4秒左右，查詢操作是2秒左右，刪除時0.4秒左右，1000w整數的上述操作分別是47s,22s,3.3s。
看起來效率還是不錯。
算法實現代碼
posted on 2009-10-22 00:31
Alex-Lee 閱讀(1933)
評論(5) 編輯 收藏 引用