哈希结构
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 阅读(1916)
评论(5) 编辑 收藏 引用