在C语言中编写字典通常涉及到使用哈希表(Hash Table)来实现高效的查找、插入和删除操作。哈希表通过哈希函数将键(Key)映射到数组中的一个位置,以便快速访问记录。然而,如果哈希函数设计不当或者哈希表的负载因子过高,可能会导致搜索结果出现误导性,即不同的键被映射到同一位置,这种现象称为哈希冲突。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 100
typedef struct Node {
char *key;
char *value;
struct Node *next;
} Node;
typedef struct HashTable {
Node *table[TABLE_SIZE];
} HashTable;
unsigned int hash(const char *key) {
unsigned int hash = 0;
for (int i = 0; key[i] != '\0'; i++) {
hash = (hash << 5) + key[i];
}
return hash % TABLE_SIZE;
}
HashTable *createHashTable() {
HashTable *ht = malloc(sizeof(HashTable));
memset(ht->table, 0, TABLE_SIZE * sizeof(Node *));
return ht;
}
void insert(HashTable *ht, const char *key, const char *value) {
unsigned int index = hash(key);
Node *newNode = malloc(sizeof(Node));
newNode->key = strdup(key);
newNode->value = strdup(value);
newNode->next = NULL;
if (ht->table[index] == NULL) {
ht->table[index] = newNode;
} else {
Node *current = ht->table[index];
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
}
char *search(HashTable *ht, const char *key) {
unsigned int index = hash(key);
Node *current = ht->table[index];
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
return current->value;
}
current = current->next;
}
return NULL;
}
int main() {
HashTable *ht = createHashTable();
insert(ht, "name", "Alice");
insert(ht, "age", "30");
printf("Name: %s\n", search(ht, "name"));
printf("Age: %s\n", search(ht, "age"));
return 0;
}
在这个示例中,我们使用了链地址法来处理哈希冲突。每个哈希表的槽位都是一个链表的头节点,当插入新元素时,如果发生冲突,新元素会被添加到链表的末尾。这样,即使不同的键映射到同一位置,也能保证每个键值对都能被正确存储和检索。
领取专属 10元无门槛券
手把手带您无忧上云