哈希表(Hash table) [散列表] C语言简单实现

　　散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　------摘自百度百科

填充因子定义：

　　α=表中填充的元素数/哈希表的长度

hash函数计算方式：

1.直接寻址法

2.数字分析法

3.平方取中法

4.折叠法

5.随机数法

6.除留余数法

7.斐波那契数列

以上方法详情自行百度，这里不再赘述。

哈希表解决冲突有两种方式：

1.开放地址法 ： hi=(h(key)+di)%m ,1<=i<=m-1,di为增量序列，m为表长增量序列, di有不同方法生成 。 尽量填满每一个hash数组位，所以hash表长度>= 实际插入填充数量   即填充因子至少为1

2.链地址法:  把重复的hash值元素放在一个链表下。一般不会超过hash表长度，但是为了避免链表过长，当填充因子为7/10 时候，hash表大小扩种两倍

下面是C语言实现例子。hash函数主要采用 折叠法+除留余数法，解决冲突采用链地址法，暂时未添加自动扩充hash表长度。

  1 #include 
  2 #include <string.h>
  3 #include 
  4 
  5 // hash表默认长度
  6 #define HASH_TABLE_SIZE 16
  7 
  8 // hash表元素链表节点
  9 typedef struct __node{
 10     char *key;
 11     char *value;
 12     struct __node *next;
 13 }NODE, *PNODE, **PPNODE;
 14 
 15 // hash表结构
 16 typedef struct __hash_table{
 17     PPNODE table;
 18     unsigned total; // 总空间
 19     unsigned size;  // 已用空间
 20 }HASH_TABLE, *PHASH_TABLE;
 21 
 22 // 创建hash表中元素节点
 23 PNODE create_node(const char* key, const char *value)
 24 {
 25     PNODE pnode = (PNODE)malloc(sizeof(NODE));
 26     if(NULL == pnode) return NULL;
 27 
 28     pnode->next = NULL;
 29     if (NULL != key)
 30     {
 31         unsigned len = strlen(key) + 1;
 32         pnode->key = (char*)malloc(len);
 33         memcpy(pnode->key, key, len);
 34     }
 35 
 36     if (NULL != value)
 37     {
 38         unsigned len = strlen(value) + 1;
 39         pnode->value = (char*)malloc(len);
 40         memcpy(pnode->value, value, len);
 41     }
 42     return pnode;
 43 }
 44 
 45 // 创建hash表
 46 PHASH_TABLE create_hash_table(unsigned size)
 47 {
 48     if(size < 1) return NULL;
 49 
 50     PPNODE ppNodeTable = (PPNODE)malloc(sizeof(PNODE) * size);
 51     if (NULL == ppNodeTable) return NULL;
 52 
 53     for (unsigned i = 0; i < size; i++)
 54     {
 55         ppNodeTable[i] = NULL;
 56     }
 57     PHASH_TABLE pHashTable = (PHASH_TABLE)malloc(sizeof(HASH_TABLE));
 58     if(NULL == pHashTable) return NULL;
 59     pHashTable->table = ppNodeTable;
 60     pHashTable->total = size;
 61     pHashTable->size = 0;
 62     return pHashTable;
 63 }
 64 
 65 // hash函数 对叠法+除留余数法
 66 unsigned hash(const char* key, unsigned hash_size)
 67 {
 68     unsigned int h=0;
 69     for( ; *key != '\0'; ++key)
 70         h = *key + h * 31;
 71     return h%hash_size;
 72 }
 73 
 74 // 从hash表中获取key对应的value
 75 const char* get_hash_value(PHASH_TABLE pHashTable, const char* key)
 76 {
 77     if(NULL == key) return NULL;
 78 
 79     unsigned index = hash(key, pHashTable->total);
 80     PNODE pnode = pHashTable->table[index];
 81     if(NULL == pnode) return NULL;
 82 
 83     do
 84     {
 85         if(strcmp(pnode->key, key) == 0)
 86         {
 87             return pnode->value;
 88         }
 89 
 90         pnode = pnode->next;
 91     }while (pnode != NULL);    
 92 }
 93 
 94 // 插入hash表
 95 int insert_hash(PHASH_TABLE pHashTable ,const char *key, const char *value)
 96 {
 97     if(NULL == key) return 0;
 98     // 剩余空间不足
 99     if(pHashTable->size == pHashTable->total) return -1;
100 
101     if(get_hash_value(pHashTable, key) != NULL) return -1;
102 
103     
104     PNODE pnode = create_node(key, value);
105     if(NULL == pnode) return 0;
106 
107     unsigned index = hash(key,pHashTable->total);
108     if(NULL == pHashTable->table[index])
109     {
110         pHashTable->table[index] = pnode;
111         ++ pHashTable->size;
112     } else {
113         pnode->next = pHashTable->table[index];
114         pHashTable->table[index] = pnode;
115     }
116 
117     return index;
118 }
119 
120 // 释放hash表
121 void free_hash_table(PHASH_TABLE pHashTable)
122 {
123     if(NULL == pHashTable || pHashTable->size == 0) return;
124 
125     PNODE pnode = NULL;
126     for (unsigned i = 0; i < pHashTable->total; i++)
127     {
128         pnode = pHashTable->table[i];
129         if(pnode == NULL) continue;
130 
131         PNODE tmp = NULL;
132         while( pnode != NULL)
133         {
134             tmp = pnode;
135             pnode = pnode->next;
136             free(tmp->key);
137             free(tmp->value);
138             free(tmp);
139         }
140         pHashTable->table[i] = NULL;
141         pHashTable->size --;
142         if(pHashTable->size == 0) return;
143     }
144     
145     free(pHashTable->table);
146     free(pHashTable);
147 }
148 
149 // 打印hash表内容
150 void print_hash(PHASH_TABLE pHashTable)
151 {
152     if(NULL == pHashTable || 0 == pHashTable->size) return;
153 
154     for (unsigned i = 0; i < pHashTable->total; i++)
155     {
156         printf("%u ",i);
157         PNODE pnode = pHashTable->table[i];
158         while (pnode != NULL)
159         {
160             if(pnode->value != NULL)
161                 printf("[%s,%s] ",pnode->key, pnode->value);
162             else 
163                 printf("[%s,null] ",pnode->key);
164             pnode = pnode->next;
165         }
166         printf("\n");
167     }
168 }
169 
170 int main(int argc, char *argv[])
171 {
172    PHASH_TABLE pHashTable = create_hash_table(HASH_TABLE_SIZE);
173    insert_hash(pHashTable, "zs","张三");
174    insert_hash(pHashTable, "ls","李四");
175    insert_hash(pHashTable, "we","王二");
176    insert_hash(pHashTable, "mz","麻子");
177    insert_hash(pHashTable, "lb","刘备");
178    insert_hash(pHashTable, "gy","关羽");
179    insert_hash(pHashTable, "zf","张飞");
180    insert_hash(pHashTable, "cc","曹操");
181    insert_hash(pHashTable, "cp","曹丕");
182    insert_hash(pHashTable, "cz","曹植");
183    insert_hash(pHashTable, "cr","曹仁");
184 //    const char* value = get_hash_value(pHashTable,"mz");
185 //    if(value != NULL)
186 //    {
187 //        printf("mz->%s\n",value);
188 //    } else {
189 //        printf("没有找到zs\n");
190 //    }
191 
192     print_hash(pHashTable);
193     
194     free_hash_table(pHashTable);
195     return 0;
196 }