c 遍历哈希表
时间: 2023-08-04 16:20:08 浏览: 68
哈希表是一种高效的数据结构,用于存储键值对。在哈希表中,键通过哈希函数转换为索引,然后存储在相应的索引位置上。
在C语言中,哈希表的实现可以使用数组和链表结合的方式。数组用于存储哈希表的桶,每个桶对应一个索引位置。链表用于解决哈希冲突的问题,当多个键通过哈希函数映射到同一个索引位置时,它们可以存储在同一个桶内的链表中。
遍历哈希表可以通过遍历每个桶内的链表实现。以下是一个简单的遍历哈希表的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_SIZE 100
// 哈希表节点结构体
typedef struct hash_node {
char *key; // 键
void *value; // 值
struct hash_node *next; // 下一个节点
} hash_node_t;
// 哈希表结构体
typedef struct hash_table {
hash_node_t **buckets; // 桶
size_t size; // 大小
} hash_table_t;
// 哈希函数
unsigned long hash(const char *str) {
unsigned long hash = 5381;
int c;
while ((c = *str++))
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
// 创建哈希表
hash_table_t *hash_create(size_t size) {
hash_table_t *table = malloc(sizeof(hash_table_t));
table->buckets = calloc(size, sizeof(hash_node_t *));
table->size = size;
return table;
}
// 插入键值对
void hash_insert(hash_table_t *table, const char *key, void *value) {
unsigned long index = hash(key) % table->size;
hash_node_t *node = malloc(sizeof(hash_node_t));
node->key = strdup(key);
node->value = value;
node->next = table->buckets[index];
table->buckets[index] = node;
}
// 查找键值对
void *hash_lookup(hash_table_t *table, const char *key) {
unsigned long index = hash(key) % table->size;
hash_node_t *node = table->buckets[index];
while (node) {
if (strcmp(node->key, key) == 0)
return node->value;
node = node->next;
}
return NULL;
}
// 删除键值对
void hash_delete(hash_table_t *table, const char *key) {
unsigned long index = hash(key) % table->size;
hash_node_t *node = table->buckets[index], *prev = NULL;
while (node) {
if (strcmp(node->key, key) == 0) {
if (prev)
prev->next = node->next;
else
table->buckets[index] = node->next;
free(node->key);
free(node);
return;
}
prev = node;
node = node->next;
}
}
// 遍历哈希表
void hash_traverse(hash_table_t *table) {
for (size_t i = 0; i < table->size; i++) {
hash_node_t *node = table->buckets[i];
while (node) {
printf("%s: %p\n", node->key, node->value);
node = node->next;
}
}
}
// 销毁哈希表
void hash_destroy(hash_table_t *table) {
for (size_t i = 0; i < table->size; i++) {
hash_node_t *node = table->buckets[i];
while (node) {
hash_node_t *next = node->next;
free(node->key);
free(node);
node = next;
}
}
free(table->buckets);
free(table);
}
int main() {
hash_table_t *table = hash_create(HASH_SIZE);
// 插入键值对
hash_insert(table, "key1", (void *)0x12345678);
hash_insert(table, "key2", (void *)0xabcdef01);
hash_insert(table, "key3", (void *)0xdeadbeef);
// 遍历哈希表
hash_traverse(table);
// 删除键值对
hash_delete(table, "key2");
// 查找键值对
void *value = hash_lookup(table, "key1");
printf("key1: %p\n", value);
// 销毁哈希表
hash_destroy(table);
return 0;
}
```
该代码实现了一个简单的哈希表,并提供了插入、查找、删除、遍历和销毁操作。在遍历哈希表时,我们遍历每个桶内的链表,并打印出键和值。