简介
Hash table在C/C++中是一种将键映射到值的数据结构。哈希表使用_hash函数_来计算键的索引。您可以根据哈希表索引将该值存储在适当的位置。
使用哈希表的好处是它的访问时间非常快。通常情况下，时间复杂度(摊销时间complexity)是一个常数`O(1)‘访问时间。
如果两个不同的键获得相同的索引，则需要使用其他数据结构(存储桶)来解决这些冲突。如果您选择一个非常好的散列函数，冲突的可能性可以忽略不计。
C++STL(标准模板库)有std：：unordered_map()数据结构。
在本文中，您将从头开始构建一个哈希表，其中包括：
- 一个哈希函数，用于将键映射到值。
- 一种哈希表数据结构，支持
插入、搜索和删除操作。 - 用于说明键冲突的数据结构。
选择哈希函数
第一步是选择一个合理的、具有较低冲突几率的散列函数。但是，出于本教程的目的，我们将使用一个较差的散列函数来更好地说明散列冲突。这个有限的示例还将仅使用字符串(或C中的字符数组)。
1[label HashTable.cpp]
2#define CAPACITY 50000 // Size of the HashTable.
3
4unsigned long hash_function(char* str)
5{
6 unsigned long i = 0;
7
8 for (int j = 0; str[j]; j++)
9 i += str[j];
10
11 return i % CAPACITY;
12}
运行此代码并测试不同字符串的潜在冲突。例如，字符串Hel和Cau会冲突，因为它们具有相同的ASCII值。
此代码必须返回一个在哈希表容量范围内的数字。否则，它可能会访问未绑定的内存位置，从而导致错误。
定义哈希表数据结构
哈希表是由项组成的数组，它们是{key：value}对。
首先，定义项目结构：
1[label HashTable.cpp]
2// Defines the HashTable item.
3
4typedef struct Ht_item
5{
6 char* key;
7 char* value;
8} Ht_item;
现在，哈希表有一个指向Ht_item的指针数组，所以它是_双指针_。
1[label HashTable.cpp]
2// Defines the HashTable.
3typedef struct HashTable
4{
5 // Contains an array of pointers to items.
6 Ht_item** items;
7 int size;
8 int count;
9} HashTable;
您的哈希表需要使用count返回哈希表中的元素数量，并使用size返回哈希表的大小。
创建哈希表和哈希表项
接下来，创建用于分配内存和创建项的函数。
通过为键和值分配内存来创建项，并返回指向该项的指针：
1[label HashTable.cpp]
2Ht_item* create_item(char* key, char* value)
3{
4 // Creates a pointer to a new HashTable item.
5 Ht_item* item = (Ht_item*) malloc(sizeof(Ht_item));
6 item->key = (char*) malloc(strlen(key) + 1);
7 item->value = (char*) malloc(strlen(value) + 1);
8 strcpy(item->key, key);
9 strcpy(item->value, value);
10 return item;
11}
通过分配内存并设置size、Count、items来创建表：
1[label HashTable.cpp]
2HashTable* create_table(int size)
3{
4 // Creates a new HashTable.
5 HashTable* table = (HashTable*) malloc(sizeof(HashTable));
6 table->size = size;
7 table->count = 0;
8 table->items = (Ht_item**) calloc(table->size, sizeof(Ht_item*));
9
10 for (int i = 0; i < table->size; i++)
11 table->items[i] = NULL;
12
13 return table;
14}
前面的例子为包装器结构HashTable分配内存，并将所有项设置为NULL。
释放内存是C/C++的最佳实践。使用malloc（)和calloc（)释放在堆上分配的内存。
编写释放表项和整个表的函数。
1[label HashTable.cpp]
2void free_item(Ht_item* item)
3{
4 // Frees an item.
5 free(item->key);
6 free(item->value);
7 free(item);
8}
9
10void free_table(HashTable* table)
11{
12 // Frees the table.
13 for (int i = 0; i < table->size; i++)
14 {
15 Ht_item* item = table->items[i];
16
17 if (item != NULL)
18 free_item(item);
19 }
20
21 free(table->items);
22 free(table);
23}
添加print_table()，显示每一项的index、key、value：
1[label HashTable.cpp]
2void print_table(HashTable* table)
3{
4 printf("\nHash Table\n-------------------\n");
5
6 for (int i = 0; i < table->size; i++)
7 {
8 if (table->items[i])
9 {
10 printf("Index:%d, Key:%s, Value:%s\n", i, table->items[i] -> key, table->items[i]->value);
11 }
12 }
13
14 printf("-------------------\n\n");
15}
自定义哈希表的基本功能到此结束。现在，您将编写插入、搜索和删除函数。
插入哈希表
创建一个执行插入的函数ht_Insert()。
该函数以HashTable指针、key和value作为参数：
1void ht_insert(HashTable* table, char* key, char* value)
2{
3 ...
4}
现在，在ht_insert（)函数中涉及某些步骤。
- 根据
{key：Value}对创建条目。 - 根据哈希函数计算索引。
- 通过比较
key查看索引是否已被占用。 -如果没有被占用，可以直接插入index。 -否则，这是一个碰撞，你需要处理它。
本教程将解决在创建初始模型后处理碰撞的问题。
首先，创建项目：
1create_item(key, value)
然后，计算指数：
1int index = hash_function(key);
第一次插入密钥时，该项必须是NULL：
1[label HashTable.cpp]
2// Creates the item.
3Ht_item* item = create_item(key, value);
4
5// Computes the index.
6int index = hash_function(key);
7
8Ht_item* current_item = table->items[index];
9
10if (current_item == NULL)
11{
12 // Key does not exist.
13 if (table->count == table->size)
14 {
15 // HashTable is full.
16 printf("Insert Error: Hash Table is full\n");
17 free_item(item);
18 return;
19 }
20
21 // Insert directly.
22 table->items[index] = item;
23 table->count++;
24}
考虑这样的场景：因为哈希表中插入了相同的项，所以{key：Value}对已经存在。要解决此问题，代码必须将项值更新为新值：
1[label HashTable.cpp]
2if (current_item == NULL)
3{
4 ...
5}
6else {
7 // Scenario 1: Update the value.
8 if (strcmp(current_item->key, key) == 0)
9 {
10 strcpy(table->items[index] -> value, value);
11 return;
12 }
13}
考虑必须处理冲突的情况。为了解决这个问题，添加了一个占位符：
1[label HashTable.cpp]
2void handle_collision(HashTable* table, Ht_item* item)
3{
4}
5
6void ht_insert(HashTable* table, char* key, char* value)
7{
8 ...
9
10 if (current_item == NULL)
11 {
12 ...
13 }
14 else {
15 // Scenario 1: Update the value.
16 if (strcmp(current_item->key, key) == 0)
17 {
18 ...
19 }
20 else {
21 // Scenario 2: Handle the collision.
22 handle_collision(table, item);
23 return;
24 }
25 }
26}
现在，您的ht_ins()函数已经完成。
查找哈希表中的条目
创建一个函数ht_earch()，用于检查键是否存在，如果存在，则返回相应的值。
该函数以HashTable指针和key为参数：
1char* ht_search(HashTable* table, char* key)
2{
3 ...
4}
在HashTable中搜索带有key的项。如果在HashTable中找不到，则返回NULL。
1[label HashTable.cpp]
2char* ht_search(HashTable* table, char* key)
3{
4 // Searches for the key in the HashTable.
5 // Returns NULL if it doesn't exist.
6 int index = hash_function(key);
7 Ht_item* item = table->items[index];
8
9 // Provide only non-NULL values.
10 if (item != NULL)
11 {
12 if (strcmp(item->key, key) == 0)
13 return item->value;
14 }
15
16 return NULL;
17}
添加print_earch()，显示匹配key的条目：
1[label HashTable.cpp]
2void print_search(HashTable* table, char* key)
3{
4 char* val;
5
6 if ((val = ht_search(table, key)) == NULL)
7 {
8 printf("Key:%s does not exist\n", key);
9 return;
10 }
11 else {
12 printf("Key:%s, Value:%s\n", key, val);
13 }
14}
现在，您的ht_earch()函数已经完成。
冲突处理
有不同的方法来解决冲突。本教程将依赖于一种名为Separate Chaining的方法，该方法旨在为具有相同哈希索引的所有项创建独立的链。本教程中的实现将使用链表创建这些链。
每当发生冲突时，在同一索引上发生冲突的其他项被添加到_OVERFLOW存储桶列表_中。因此，您不必删除哈希表上的任何现有记录。
由于链表的插入、查找和删除的时间复杂度为O(N)‘，因此在发生冲突的情况下，最坏情况下的访问时间也是O(N)`。这种方法的优点是，如果您的哈希表的容量较低，则它是一个很好的选择。
执行溢出存储桶列表：
1[label HashTable.cpp]
2// Defines the LinkedList.
3typedef struct LinkedList {
4 Ht_item* item;
5 struct LinkedList* next;
6} LinkedList;;
7
8LinkedList* allocate_list()
9{
10 // Allocates memory for a LinkedList pointer.
11 LinkedList* list = (LinkedList*) malloc(sizeof(LinkedList));
12 return list;
13}
14
15LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item)
16{
17 // Inserts the item onto the LinkedList.
18 if (!list)
19 {
20 LinkedList* head = allocate_list();
21 head->item = item;
22 head->next = NULL;
23 list = head;
24 return list;
25 }
26 else if (list->next == NULL)
27 {
28 LinkedList* node = allocate_list();
29 node->item = item;
30 node->next = NULL;
31 list->next = node;
32 return list;
33 }
34
35 LinkedList* temp = list;
36
37 while (temp->next->next)
38 {
39 temp = temp->next;
40 }
41
42 LinkedList* node = allocate_list();
43 node->item = item;
44 node->next = NULL;
45 temp->next = node;
46 return list;
47}
48
49Ht_item* linkedlist_remove(LinkedList* list)
50{
51 // Removes the head from the LinkedList.
52 // Returns the item of the popped element.
53 if (!list)
54 return NULL;
55
56 if (!list->next)
57 return NULL;
58
59 LinkedList* node = list->next;
60 LinkedList* temp = list;
61 temp->next = NULL;
62 list = node;
63 Ht_item* it = NULL;
64 memcpy(temp->item, it, sizeof(Ht_item));
65 free(temp->item->key);
66 free(temp->item->value);
67 free(temp->item);
68 free(temp);
69 return it;
70}
71
72void free_linkedlist(LinkedList* list)
73{
74 LinkedList* temp = list;
75
76 while (list)
77 {
78 temp = list;
79 list = list->next;
80 free(temp->item->key);
81 free(temp->item->value);
82 free(temp->item);
83 free(temp);
84 }
85}
现在，将这些溢出的存储桶列表添加到您的HashTable中。每一项都有一个链，所以整个表是一个由LinkedList指针组成的数组。
1[label HashTable.cpp]
2typedef struct HashTable HashTable;
3
4// Defines the HashTable.
5struct HashTable
6{
7 // Contains an array of pointers to items.
8 Ht_item** items;
9 LinkedList** overflow_buckets;
10 int size;
11 int count;
12};
现在已经定义了overflow_buckets，添加函数来创建和删除它们。您还需要在create_table（)和free_table（)函数中说明它们。
1[label HashTable.cpp]
2LinkedList** create_overflow_buckets(HashTable* table)
3{
4 // Create the overflow buckets; an array of LinkedLists.
5 LinkedList** buckets = (LinkedList**) calloc(table->size, sizeof(LinkedList*));
6
7 for (int i = 0; i < table->size; i++)
8 buckets[i] = NULL;
9
10 return buckets;
11}
12
13void free_overflow_buckets(HashTable* table)
14{
15 // Free all the overflow bucket lists.
16 LinkedList** buckets = table->overflow_buckets;
17
18 for (int i = 0; i < table->size; i++)
19 free_linkedlist(buckets[i]);
20
21 free(buckets);
22}
23
24HashTable* create_table(int size)
25{
26 // Creates a new HashTable.
27 HashTable* table = (HashTable*) malloc(sizeof(HashTable));
28 table->size = size;
29 table->count = 0;
30 table->items = (Ht_item**) calloc(table->size, sizeof(Ht_item*));
31
32 for (int i = 0; i < table->size; i++)
33 table->items[i] = NULL;
34
35 table->overflow_buckets = create_overflow_buckets(table);
36
37 return table;
38}
39
40void free_table(HashTable* table)
41{
42 // Frees the table.
43 for (int i = 0; i < table->size; i++)
44 {
45 Ht_item* item = table->items[i];
46
47 if (item != NULL)
48 free_item(item);
49 }
50
51 // Free the overflow bucket lists and its items.
52 free_overflow_buckets(table);
53 free(table->items);
54 free(table);
55}
如果该物料的溢出时段列表不存在，请创建一个列表并将该物料添加到列表中。
针对插入内容更新Handle_Collision()：
1[label HashTable.cpp]
2void handle_collision(HashTable* table, unsigned long index, Ht_item* item)
3{
4 LinkedList* head = table->overflow_buckets[index];
5
6 if (head == NULL)
7 {
8 // Creates the list.
9 head = allocate_list();
10 head->item = item;
11 table->overflow_buckets[index] = head;
12 return;
13 }
14 else {
15 // Insert to the list.
16 table->overflow_buckets[index] = linkedlist_insert(head, item);
17 return;
18 }
19}
还有那通电话：
1[label HashTable.cpp]
2void ht_insert(HashTable* table, char* key, char* value)
3{
4 ...
5
6 if (current_item == NULL)
7 {
8 ...
9 }
10 else {
11 // Scenario 1: Update the value.
12 if (strcmp(current_item->key, key) == 0)
13 {
14 ...
15 }
16 else {
17 // Scenario 2: Handle the collision.
18 handle_collision(table, index, item);
19 return;
20 }
21 }
22}
现在，更新搜索方法以使用溢出存储桶：
1[label HashTable.cpp]
2char* ht_search(HashTable* table, char* key)
3{
4 // Searches for the key in the HashTable.
5 // Returns NULL if it doesn't exist.
6 int index = hash_function(key);
7 Ht_item* item = table->items[index];
8 LinkedList* head = table->overflow_buckets[index];
9
10 // Provide only non-NULL values.
11 if (item != NULL)
12 {
13 if (strcmp(item->key, key) == 0)
14 return item->value;
15
16 if (head == NULL)
17 return NULL;
18
19 item = head->item;
20 head = head->next;
21 }
22
23 return NULL;
24}
最后，冲突现在在插入()和搜索()中处理！
删除哈希表
现在，我们最后来看一下删除函数：
1void ht_delete(HashTable* table, char* key)
2{
3 ...
4}
同样，该方法类似于插入。
1.计算哈希索引，得到项目。
2.如果为NULL，则不要执行任何操作。
3.否则，在比较键之后，如果该索引没有冲突链，则从表中删除该项。
4.如果存在冲突链，请移除该元素并相应地移动链接。
1[label HashTable.cpp]
2void ht_delete(HashTable* table, char* key)
3{
4 // Deletes an item from the table.
5 int index = hash_function(key);
6 Ht_item* item = table->items[index];
7 LinkedList* head = table->overflow_buckets[index];
8
9 if (item == NULL)
10 {
11 // Does not exist.
12 return;
13 }
14 else {
15 if (head == NULL && strcmp(item->key, key) == 0)
16 {
17 // Collision chain does not exist.
18 // Remove the item.
19 // Set table index to NULL.
20 table->items[index] = NULL;
21 free_item(item);
22 table->count--;
23 return;
24 }
25 else if (head != NULL)
26 {
27 // Collision chain exists.
28 if (strcmp(item->key, key) == 0)
29 {
30 // Remove this item.
31 // Set the head of the list as the new item.
32 free_item(item);
33 LinkedList* node = head;
34 head = head->next;
35 node->next = NULL;
36 table->items[index] = create_item(node->item->key, node->item->value);
37 free_linkedlist(node);
38 table->overflow_buckets[index] = head;
39 return;
40 }
41
42 LinkedList* curr = head;
43 LinkedList* prev = NULL;
44
45 while (curr)
46 {
47 if (strcmp(curr->item->key, key) == 0)
48 {
49 if (prev == NULL)
50 {
51 // First element of the chain.
52 // Remove the chain.
53 free_linkedlist(head);
54 table->overflow_buckets[index] = NULL;
55 return;
56 }
57 else
58 {
59 // This is somewhere in the chain.
60 prev->next = curr->next;
61 curr->next = NULL;
62 free_linkedlist(curr);
63 table->overflow_buckets[index] = head;
64 return;
65 }
66 }
67
68 curr = curr->next;
69 prev = curr;
70 }
71 }
72 }
73}
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define CAPACITY 50000 // Size of the HashTable.
6
7unsigned long hash_function(char *str)
8{
9 unsigned long i = 0;
10
11 for (int j = 0; str[j]; j++)
12 i += str[j];
13
14 return i % CAPACITY;
15}
16
17// Defines the HashTable item.
18typedef struct Ht_item
19{
20 char *key;
21 char *value;
22} Ht_item;
23
24// Defines the LinkedList.
25typedef struct LinkedList
26{
27 Ht_item *item;
28 LinkedList *next;
29} LinkedList;
30
31// Defines the HashTable.
32typedef struct HashTable
33{
34 // Contains an array of pointers to items.
35 Ht_item **items;
36 LinkedList **overflow_buckets;
37 int size;
38 int count;
39} HashTable;
40
41LinkedList *allocate_list()
42{
43 // Allocates memory for a LinkedList pointer.
44 LinkedList *list = (LinkedList *)malloc(sizeof(LinkedList));
45 return list;
46}
47
48LinkedList *linkedlist_insert(LinkedList *list, Ht_item *item)
49{
50 // Inserts the item onto the LinkedList.
51 if (!list)
52 {
53 LinkedList *head = allocate_list();
54 head->item = item;
55 head->next = NULL;
56 list = head;
57 return list;
58 }
59 else if (list->next == NULL)
60 {
61 LinkedList *node = allocate_list();
62 node->item = item;
63 node->next = NULL;
64 list->next = node;
65 return list;
66 }
67
68 LinkedList *temp = list;
69
70 while (temp->next->next)
71 {
72 temp = temp->next;
73 }
74
75 LinkedList *node = allocate_list();
76 node->item = item;
77 node->next = NULL;
78 temp->next = node;
79 return list;
80}
81
82Ht_item *linkedlist_remove(LinkedList *list)
83{
84 // Removes the head from the LinkedList.
85 // Returns the item of the popped element.
86 if (!list)
87 return NULL;
88
89 if (!list->next)
90 return NULL;
91
92 LinkedList *node = list->next;
93 LinkedList *temp = list;
94 temp->next = NULL;
95 list = node;
96 Ht_item *it = NULL;
97 memcpy(temp->item, it, sizeof(Ht_item));
98 free(temp->item->key);
99 free(temp->item->value);
100 free(temp->item);
101 free(temp);
102 return it;
103}
104
105void free_linkedlist(LinkedList *list)
106{
107 LinkedList *temp = list;
108
109 while (list)
110 {
111 temp = list;
112 list = list->next;
113 free(temp->item->key);
114 free(temp->item->value);
115 free(temp->item);
116 free(temp);
117 }
118}
119
120LinkedList **create_overflow_buckets(HashTable *table)
121{
122 // Create the overflow buckets; an array of LinkedLists.
123 LinkedList **buckets = (LinkedList **)calloc(table->size, sizeof(LinkedList *));
124
125 for (int i = 0; i < table->size; i++)
126 buckets[i] = NULL;
127
128 return buckets;
129}
130
131void free_overflow_buckets(HashTable *table)
132{
133 // Free all the overflow bucket lists.
134 LinkedList **buckets = table->overflow_buckets;
135
136 for (int i = 0; i < table->size; i++)
137 free_linkedlist(buckets[i]);
138
139 free(buckets);
140}
141
142Ht_item *create_item(char *key, char *value)
143{
144 // Creates a pointer to a new HashTable item.
145 Ht_item *item = (Ht_item *)malloc(sizeof(Ht_item));
146 item->key = (char *)malloc(strlen(key) + 1);
147 item->value = (char *)malloc(strlen(value) + 1);
148 strcpy(item->key, key);
149 strcpy(item->value, value);
150 return item;
151}
152
153HashTable *create_table(int size)
154{
155 // Creates a new HashTable.
156 HashTable *table = (HashTable *)malloc(sizeof(HashTable));
157 table->size = size;
158 table->count = 0;
159 table->items = (Ht_item **)calloc(table->size, sizeof(Ht_item *));
160
161 for (int i = 0; i < table->size; i++)
162 table->items[i] = NULL;
163
164 table->overflow_buckets = create_overflow_buckets(table);
165
166 return table;
167}
168
169void free_item(Ht_item *item)
170{
171 // Frees an item.
172 free(item->key);
173 free(item->value);
174 free(item);
175}
176
177void free_table(HashTable *table)
178{
179 // Frees the table.
180 for (int i = 0; i < table->size; i++)
181 {
182 Ht_item *item = table->items[i];
183
184 if (item != NULL)
185 free_item(item);
186 }
187
188 // Free the overflow bucket lists and its items.
189 free_overflow_buckets(table);
190 free(table->items);
191 free(table);
192}
193
194void handle_collision(HashTable *table, unsigned long index, Ht_item *item)
195{
196 LinkedList *head = table->overflow_buckets[index];
197
198 if (head == NULL)
199 {
200 // Creates the list.
201 head = allocate_list();
202 head->item = item;
203 table->overflow_buckets[index] = head;
204 return;
205 }
206 else
207 {
208 // Insert to the list.
209 table->overflow_buckets[index] = linkedlist_insert(head, item);
210 return;
211 }
212}
213
214void ht_insert(HashTable *table, char *key, char *value)
215{
216 // Creates the item.
217 Ht_item *item = create_item(key, value);
218
219 // Computes the index.
220 int index = hash_function(key);
221
222 Ht_item *current_item = table->items[index];
223
224 if (current_item == NULL)
225 {
226 // Key does not exist.
227 if (table->count == table->size)
228 {
229 // HashTable is full.
230 printf("Insert Error: Hash Table is full\n");
231 free_item(item);
232 return;
233 }
234
235 // Insert directly.
236 table->items[index] = item;
237 table->count++;
238 }
239 else
240 {
241 // Scenario 1: Update the value.
242 if (strcmp(current_item->key, key) == 0)
243 {
244 strcpy(table->items[index]->value, value);
245 return;
246 }
247 else
248 {
249 // Scenario 2: Handle the collision.
250 handle_collision(table, index, item);
251 return;
252 }
253 }
254}
255
256char *ht_search(HashTable *table, char *key)
257{
258 // Searches for the key in the HashTable.
259 // Returns NULL if it doesn't exist.
260 int index = hash_function(key);
261 Ht_item *item = table->items[index];
262 LinkedList *head = table->overflow_buckets[index];
263
264 // Provide only non-NULL values.
265 if (item != NULL)
266 {
267 if (strcmp(item->key, key) == 0)
268 return item->value;
269
270 if (head == NULL)
271 return NULL;
272
273 item = head->item;
274 head = head->next;
275 }
276
277 return NULL;
278}
279
280void ht_delete(HashTable *table, char *key)
281{
282 // Deletes an item from the table.
283 int index = hash_function(key);
284 Ht_item *item = table->items[index];
285 LinkedList *head = table->overflow_buckets[index];
286
287 if (item == NULL)
288 {
289 // Does not exist.
290 return;
291 }
292 else
293 {
294 if (head == NULL && strcmp(item->key, key) == 0)
295 {
296 // Collision chain does not exist.
297 // Remove the item.
298 // Set table index to NULL.
299 table->items[index] = NULL;
300 free_item(item);
301 table->count--;
302 return;
303 }
304 else if (head != NULL)
305 {
306 // Collision chain exists.
307 if (strcmp(item->key, key) == 0)
308 {
309 // Remove this item.
310 // Set the head of the list as the new item.
311 free_item(item);
312 LinkedList *node = head;
313 head = head->next;
314 node->next = NULL;
315 table->items[index] = create_item(node->item->key, node->item->value);
316 free_linkedlist(node);
317 table->overflow_buckets[index] = head;
318 return;
319 }
320
321 LinkedList *curr = head;
322 LinkedList *prev = NULL;
323
324 while (curr)
325 {
326 if (strcmp(curr->item->key, key) == 0)
327 {
328 if (prev == NULL)
329 {
330 // First element of the chain.
331 // Remove the chain.
332 free_linkedlist(head);
333 table->overflow_buckets[index] = NULL;
334 return;
335 }
336 else
337 {
338 // This is somewhere in the chain.
339 prev->next = curr->next;
340 curr->next = NULL;
341 free_linkedlist(curr);
342 table->overflow_buckets[index] = head;
343 return;
344 }
345 }
346
347 curr = curr->next;
348 prev = curr;
349 }
350 }
351 }
352}
353
354void print_search(HashTable *table, char *key)
355{
356 char *val;
357
358 if ((val = ht_search(table, key)) == NULL)
359 {
360 printf("Key:%s does not exist\n", key);
361 return;
362 }
363 else
364 {
365 printf("Key:%s, Value:%s\n", key, val);
366 }
367}
368
369void print_table(HashTable *table)
370{
371 printf("\nHash Table\n-------------------\n");
372
373 for (int i = 0; i < table -> size; i++)
374 {
375 if (table -> items[i])
376 {
377 printf("Index:%d, Key:%s, Value:%s\n", i, table -> items[i] -> key, table -> items[i] -> value);
378 }
379 }
380
381 printf("-------------------\n\n");
382}
383
384int main()
385{
386 HashTable *ht = create_table(CAPACITY);
387 ht_insert(ht, (char *)"1", (char *)"First address");
388 ht_insert(ht, (char *)"2", (char *)"Second address");
389 ht_insert(ht, (char *)"Hel", (char *)"Third address");
390 ht_insert(ht, (char *)"Cau", (char *)"Fourth address");
391 print_search(ht, (char *)"1");
392 print_search(ht, (char *)"2");
393 print_search(ht, (char *)"3");
394 print_search(ht, (char *)"Hel");
395 print_search(ht, (char *)"Cau"); // Collision!
396 print_table(ht);
397 ht_delete(ht, (char *)"1");
398 ht_delete(ht, (char *)"Cau");
399 print_table(ht);
400 free_table(ht);
401 return 0;
402}
此代码将产生以下输出：
1[secondary_label Output]
2Key:1, Value:First address
3Key:2, Value:Second address
4Key:3 does not exist
5Key:Hel, Value:Third address
6Key:Cau does not exist
7
8Hash Table
9-------------------
10Index:49, Key:1, Value:First address
11Index:50, Key:2, Value:Second address
12Index:281, Key:Hel, Value:Third address
13-------------------
14
15Hash Table
16-------------------
17Index:50, Key:2, Value:Second address
18Index:281, Key:Hel, Value:Third address
19-------------------
ht_Insert()、ht_earch()、ht_delete的行为与预期一致。
结论
在本文中，您在C/C++中从头开始实现了一个哈希表。
尝试使用其他冲突处理算法和不同的散列函数。通过更多内容继续学习C++tutorials