C语言怎么实现哈希表?
哈希表是一种非常常见且高效的数据结构,它将key-value对映射到一个固定大小的数组中。在哈希表中,通过计算每个key的哈希值来确定其在数组中的位置。由于哈希值具有唯一性,因此可以快速查找和插入数据。
C语言中可以使用结构体来实现哈希表。下面是一个简单的示例代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 100
typedef struct {
char* key;
int value;
} HashNode;
typedef struct {
HashNode* nodes[TABLE_SIZE];
} HashTable;
int hash(char* key) {
int sum = 0;
for (int i = 0; i < strlen(key); i++) {
sum += key[i];
}
return sum % TABLE_SIZE;
}
void insert(HashTable* table, char* key, int value) {
int index = hash(key);
HashNode* node = malloc(sizeof(HashNode));
node->key = strdup(key);
node->value = value;
if (table->nodes[index] == NULL) {
table->nodes[index] = node;
} else {
HashNode* current = table->nodes[index];
while (current->next != NULL) {
current = current->next;
}
current->next = node;
}
}
int get(HashTable* table, char* key) {
int index = hash(key);
HashNode* current = table->nodes[index];
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
return current->value;
}
current = current->next;
}
return -1; // key not found
}
int main() {
HashTable table;
memset(&table, 0, sizeof(table));
insert(&table, "apple", 5);
insert(&table, "banana", 10);
printf("%d\n", get(&table, "apple"));
printf("%d\n", get(&table, "banana"));
printf("%d\n", get(&table, "orange")); // should print -1
}
```
在这个示例代码中,我们定义了两个结构体:HashNode表示哈希表的每个节点,包含一个key和对应的value;HashTable表示整个哈希表,存储多个HashNode。
我们使用hash函数将每个key映射到数组中的位置。在insert函数中,我们首先计算key的哈希值,并将其与TABLE_SIZE取模得到数组下标。然后我们创建一个新的HashNode并将其插入到哈希表中。如果该位置已经有节点,则我们需要遍历链表并将新节点添加到链表的末尾。
在get函数中,我们也使用hash函数来计算key的哈希值,并遍历该位置上的链表,查找目标key的节点。
最后,在main函数中,我们演示了如何向哈希表中插入数据并通过get函数查找数据。
总之,哈希表是一种非常高效的数据结构,可以快速查找和插入数据。在C语言中,我们可以使用结构体来实现哈希表,并通过hash函数和链表来管理数据。
![](https://www.xuedaoniu.com/wp-content/themes/xuedaoniu/assets//img/xuexi/qrs_rgzn2.jpg)