首页 > 代码库 > C语言-简单哈希表（hash table）
C语言-简单哈希表（hash table）
腾讯三面的时候，叫我写了个哈希表，当时紧张没写好···结果跪了···
回来后粪发涂墙，赶紧写了一个！
什么都不说了···先让我到厕所里面哭一会···
%>_<%
果然现场发挥，以及基础扎实才是important的！
用链地址法解决冲突的哈希表（C语言，VS2008编写、测试）：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <math.h> 4 #include <string.h> 5 6 struct node { 7 int count; // count the same value 8 char *value; 9 node *next; 10 }; 11 12 // 使用链地址法解决冲突 13 struct hash_table { 14 int size; // table size 15 node **list; // 链表队列一条链为一个散列位置 16 }; 17 18 //==================================================// 19 // declare 20 21 int hash_func(char *str, int tableSize); 22 hash_table *hash_table_init(int tableSize); 23 node *hash_table_new_node(char *str, int len); 24 int hash_table_insert(char *str, struct hash_table * head); 25 node *hash_table_find(char *str, struct hash_table * head); 26 void hash_table_clear(struct hash_table * head); 27 void hash_table_print(hash_table *head); 28 29 //==================================================// 30 // realize 31 32 // hash function: return the position of str in the hash table 33 int hash_func(char *str, int tableSize) { 34 unsigned int hashVal = 0; 35 36 while (*str != ‘\0‘) 37 hashVal += (hashVal << 5) + *str++; 38 39 return hashVal % tableSize; 40 } 41 42 // init & create hash table 43 hash_table *hash_table_init(int tableSize) { 44 hash_table *head; 45 46 head = (hash_table *)malloc(sizeof(hash_table)); 47 if (NULL == head) 48 return NULL; 49 // 元素总数量尽可能为素数，以保证mod尽可能均匀 50 head->size = tableSize; 51 52 // 链表队列中，一条链为一个散列位置 53 head->list = (node **)malloc(sizeof(node *) * tableSize); 54 55 // initialize each hash list 56 int i; 57 for (i = 0; i < head->size; i++) 58 head->list[i] = NULL; 59 60 return head; 61 } 62 63 // return one new node 64 node *hash_table_new_node(char *str, int len) { 65 node *newNode = (node *)malloc(sizeof(node)); 66 newNode->count = 1; 67 newNode->next = NULL; 68 newNode->value = http://www.mamicode.com/(char *)malloc(len + 1); 69 memset(newNode->value, 0, len + 1); 70 memcpy(newNode->value, str, len); 71 72 return newNode; 73 } 74 75 // insert one node into hash table 76 int hash_table_insert(char *str, hash_table *head) { 77 int len = strlen(str); 78 // get str‘s position in the hash table 79 int pos = hash_func(str, head->size); 80 81 printf("[insert] %s at pos: %d\n", str, pos); 82 83 // locate list 84 node *q = head->list[pos], *p = head->list[pos]; 85 for ( ; p != NULL; p = p->next) { 86 if (memcmp(p->value, str, len) == 0) { 87 p->count++; // found the same value, count+1 88 return pos; 89 } 90 q = p; // store the previous node 91 } 92 93 // if not found, then insert one new node 94 node *newNode = hash_table_new_node(str, len); 95 /* 96 //===================================================================// 97 // method 1: 98 // TODO: 如果是字符串不同，但是哈希值一样呢？？？貌似没考虑到这种情况 99 // insert into the head of list100 newNode->next = head->list[pos];101 head->list[pos] = newNode;102 */103 //===================================================================//104 // method 2:105 // insert into the tail of list106 // 由于p指向了NULL，所以要插入链表尾的话，就必须增加一个变量q记录p前一个节点位置107 if (NULL == q) {108 newNode->next = head->list[pos];109 head->list[pos] = newNode;110 } else {111 q->next = newNode;112 newNode->next = NULL;113 }114 115 return pos;116 }117 118 // find the node which stored str & return it119 node *hash_table_find(char *str, hash_table *head) {120 if (NULL == head)121 return NULL;122 123 int pos = hash_func(str, head->size);124 node *p = head->list[pos];125 126 int len = strlen(str);127 128 for ( ; p != NULL; p = p->next) 129 if (memcmp(p->value, str, len) == 0) 130 break;//return p; // found & return131 132 return p; //return NULL;133 }134 135 // clear the whole hash table136 void hash_table_clear(hash_table *head) {137 if (NULL == head)138 return;139 140 node *p = NULL, *q = NULL;141 142 int i;143 for (i = 0; i < head->size; i++) {144 p = head->list[i]; 145 while (p != NULL) {146 p->count = 0; // TODO: test147 q = p->next;148 // free value149 if (p->value) {150 free(p->value);151 p->value =http://www.mamicode.com/ NULL;152 }153 // free current node154 if (p) {155 free(p);156 p = NULL;157 }158 // point to next node159 p = q;160 } 161 }162 // free list163 if (head->list) {164 free(head->list);165 head->list = NULL;166 }167 // free head168 if (head) {169 free(head);170 head = NULL;171 }172 }173 174 // print the whole hash table175 void hash_table_print(hash_table *head) {176 if (NULL == head) {177 printf("hash table is NULL! \n");178 return;179 }180 181 int i;182 node *p = NULL;183 184 for ( i = 0; i < head->size; i++) {185 p = head->list[i];186 printf("//============list %d============//\n", i);187 while (p != NULL) { 188 if (p->value)189 printf("%s:%d ", p->value, p->count);190 else191 printf("(NULL):(0) ");192 p = p->next;193 }194 printf("\n");195 }196 }197 198 // test199 int main() {200 // create201 hash_table *head = hash_table_init(10);202 203 // insert204 hash_table_insert("test 1", head);205 hash_table_insert("test 2", head);206 hash_table_insert("test 2", head);207 hash_table_insert("test 3", head);208 hash_table_insert("test 4", head);209 210 hash_table_print(head);211 212 // find213 node *find = hash_table_find("test 2", head);214 printf("\n[Find] %s:%d\n\n", find->value, find->count);215 216 // clear217 hash_table_clear(head);218 219 hash_table_print(head);220 221 // create222 head = hash_table_init(6);223 224 // insert225 hash_table_insert("test 1", head);226 hash_table_insert("test 2", head);227 hash_table_insert("test 2", head);228 hash_table_insert("test 3", head);229 hash_table_insert("test 4", head);230 231 hash_table_print(head);232 233 return 0;234 }
C语言-简单哈希表（hash table）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。