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 = (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 list
100     newNode->next = head->list[pos];
101     head->list[pos] = newNode;
102     */
103     //===================================================================//
104     // method 2:
105     // insert into the tail of list
106     // 由于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 it
119 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 & return
131 
132     return p; //return NULL;
133 }
134 
135 // clear the whole hash table
136 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: test
147             q = p->next;
148             // free value
149             if (p->value) {
150                 free(p->value);
151                 p->value = NULL;
152             }
153             // free current node
154             if (p) {
155                 free(p);
156                 p = NULL;
157             }
158             // point to next node
159             p = q;
160         }        
161     }
162     // free list
163     if (head->list) {
164         free(head->list);
165         head->list = NULL;
166     }
167     // free head
168     if (head) {
169         free(head);
170         head = NULL;
171     }
172 }
173 
174 // print the whole hash table
175 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             else
191                 printf("(NULL):(0) ");
192             p = p->next;
193         }
194         printf("\n");
195     }
196 }
197 
198 // test
199 int main() {
200     // create
201     hash_table *head = hash_table_init(10);
202 
203     // insert
204     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     // find
213     node *find = hash_table_find("test 2", head);
214     printf("\n[Find] %s:%d\n\n", find->value, find->count);
215 
216     // clear
217     hash_table_clear(head);
218 
219     hash_table_print(head);
220 
221     // create
222     head = hash_table_init(6);
223 
224     // insert
225     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 }