c语言线性探索再散列构建哈希表
时间: 2023-07-31 18:05:25 浏览: 51
哈希表是一种常见的数据结构,可以快速地进行查找、插入和删除操作。哈希表的核心思想是将数据元素通过哈希函数映射到一个固定大小的数组中,每个数据元素在数组中对应一个位置,通过查询这个位置可以快速地访问该元素。
线性探测再散列是一种解决哈希冲突的方法。当两个不同的数据元素映射到同一个数组位置时,线性探测再散列会尝试在数组中找到另一个空位置,并将冲突的数据元素插入到该空位置中。如果没有找到空位置,线性探测再散列会重新计算哈希函数,并尝试将数据元素插入到新的位置中。
下面是一个基于C语言实现的线性探测再散列哈希表的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_TABLE_SIZE 100
typedef struct _hash_node {
char *key;
char *value;
} hash_node;
typedef struct _hash_table {
hash_node **nodes;
int size;
} hash_table;
unsigned long hash_function(char *key) {
unsigned long hash = 5381;
int c;
while ((c = *key++)) {
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
}
return hash;
}
hash_table *create_hash_table(int size) {
hash_table *table = (hash_table *) malloc(sizeof(hash_table));
table->nodes = (hash_node **) calloc(size, sizeof(hash_node *));
table->size = size;
return table;
}
void destroy_hash_table(hash_table *table) {
int i;
for (i = 0; i < table->size; i++) {
if (table->nodes[i]) {
free(table->nodes[i]->key);
free(table->nodes[i]->value);
free(table->nodes[i]);
}
}
free(table->nodes);
free(table);
}
void insert_hash_table(hash_table *table, char *key, char *value) {
unsigned long hash = hash_function(key) % table->size;
int i = 0;
while (table->nodes[hash] && strcmp(table->nodes[hash]->key, key) != 0) {
i++;
hash = (hash + i) % table->size;
}
if (table->nodes[hash]) {
free(table->nodes[hash]->value);
table->nodes[hash]->value = strdup(value);
} else {
table->nodes[hash] = (hash_node *) malloc(sizeof(hash_node));
table->nodes[hash]->key = strdup(key);
table->nodes[hash]->value = strdup(value);
}
}
char *lookup_hash_table(hash_table *table, char *key) {
unsigned long hash = hash_function(key) % table->size;
int i = 0;
while (table->nodes[hash] && strcmp(table->nodes[hash]->key, key) != 0) {
i++;
hash = (hash + i) % table->size;
}
if (table->nodes[hash]) {
return table->nodes[hash]->value;
} else {
return NULL;
}
}
int main() {
hash_table *table = create_hash_table(HASH_TABLE_SIZE);
insert_hash_table(table, "foo", "bar");
insert_hash_table(table, "baz", "qux");
printf("%s\n", lookup_hash_table(table, "foo")); /* bar */
printf("%s\n", lookup_hash_table(table, "baz")); /* qux */
printf("%s\n", lookup_hash_table(table, "quux")); /* (null) */
destroy_hash_table(table);
return 0;
}
```
在该代码中,我们定义了一个`hash_node`结构体表示哈希表中的一个节点,其中包含了一个键值对。我们还定义了一个`hash_table`结构体表示哈希表本身,其中包含了一个节点数组和哈希表的大小。
我们使用`hash_function`函数来计算键的哈希值,并使用`create_hash_table`函数来创建一个指定大小的哈希表。`destroy_hash_table`函数用于销毁哈希表。
我们使用`insert_hash_table`函数来向哈希表中插入一个键值对,该函数先计算键的哈希值,然后在哈希表中查找是否已经存在该键,如果存在则更新其值,否则创建一个新的节点。当出现哈希冲突时,我们使用线性探测再散列来寻找下一个空位置。
我们使用`lookup_hash_table`函数来查找哈希表中指定键的值,该函数先计算键的哈希值,然后在哈希表中查找该键。
最后,在`main`函数中,我们创建了一个哈希表,向其中插入两个键值对,并且使用`lookup_hash_table`函数查找指定键的值。