C语言实现哈希表：解决数据存储与检索的高效利器_c语言对表的存储搜索遍历

引子

当构造数组变得不实用或困难，尤其又要增删查找时。一种动态集合结构（至少支持INSERT、SEARCH和DELETE等字典操作）就被恨恨期待了——散列表就是一种实现字典操作的数据结构。

1. 初识哈希表

[[哈希]]表（Hash Table，又称散列表），可根据关键字（key）直接访问的数据结构。哈希表通过哈希函数把关键字映射到表中的一个位置，存储位置与关键字间产生一种对应关系 h ，使得每个 key 对应一个存储位置f(key)。查找时根据给定的关键字 key，通过f(key)确定包含key的记录在存储空间中的位置。

3. C语言实现

/*
 *@create: 2024-02-04
 *@authro: jytang@stu.ecnu.edu.cn
 *@descri: Hash Table实现
*/
/*---------- 头文件 -----------*/
#include <string.h>
/*---------- 宏定义 -----------*/
#define FAILURE (-1)
#define TRUE    (0)
#define FALSE   (1)
/*--------- 数据结构 ----------*/
typedef struct {
    char *key;
    int value;
    struct HashNode *next;
} HashNode;  // 哈希表节点

typedef struct {
    int tableSize;
    HashNode **table;
} HashTable;  // 哈希表结构
/*----------函数定义-----------*/
/*
 *@descri: 哈希函数
 *@parame: IN *key --键值
           IN table_size --哈希表大小
 *@return: 哈希值
*/
unsigned int HashFunction(const char *key, int table_size)
{
    unsigned int hash = 0;
    while (*key) {
        hash = (hash * 31) + *key;
        key++;
    }
    return hash % table_size;
}
/*
 *@descri: 创建哈希表
 *@parame: IN size --哈希表大小
 *@return: 哈希表指针
*/
HashTable *HashTable_Create(int size)
{
    HashTable *hashTable = (HashTable *)malloc(sizeof(HashTable));
    hashTable->tableSize = size;
    hashTable->table = (HashNode **)calloc(size, sizeof(HashNode *));
    return hashTable;
}
/*
 *@descri: 数据入槽
 *@parame: IN *hashTable --哈希表指针
 *@parame: IN *key --键值
 *@parame: IN size --哈希表大小
 *@return: 哈希表指针
*/
void HashTable_Insert(HashTable *hashTable, const char *key, int size)
{
    unsigned int index = HashFunction(key, hashTable->tableSize);
    HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));
    newNode->key = _strdup(key);
    newNode->value = size;
    newNode->next = NULL;
    newNode->next = hashTable->table[index];
    hashTable->table[index] = newNode;
}
/*
 *@descri: 查找哈希表
 *@parame: IN *hashTable --哈希表指针
 *@parame: IN *key --键值
 *@return: 哈希表指针
*/
int HashTable_Search(HashTable *hashTable, const char *key)
{
    unsigned int index = HashFunction(key, hashTable->tableSize);
    HashNode *current = hashTable->table[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }
    return FAILURE;
}
/*
 *@descri: 数据出槽
 *@parame: IN *hashTable --哈希表指针
 *@parame: IN *key --键值
 *@return: 哈希表指针
*/
void HashTable_RemoveItem(HashTable *hashTable, const char *key)
{
    unsigned int index = HashFunction(key, hashTable->tableSize);
    HashNode *current = hashTable->table[index];
    HashNode *prev = NULL;
    // 遍历链表查找键
    while (current != NULL && strcmp(current->key, key) != 0) {
        prev = current;
        current = current->next;
    }
    // 如果找到键，删除节点
    if (current != NULL) {
        if (prev != NULL) {
            prev->next = current->next;
        } else {
            hashTable->table[index] = current->next;
        }
        free(current->key);
        free(current);
    }
}
/*
 *@descri: 销毁哈希表
 *@parame: IN *hashTable --哈希表指针
*/
void HashTable_Destroy(HashTable *hashTable)
{
    free(hashTable->table);
    free(hashTable);
}
/*
 *@descri: test
*/
int main(void)
{
    HashTable *hashTable = HashTable_Create(10);
    HashTable_Insert(hashTable, "apple", 5);
    HashTable_Insert(hashTable, "banana", 3);
    HashTable_Insert(hashTable, "orange", 8);
    printf("Value for key 'apple': %d\n", HashTable_Search(hashTable, "apple"));
    printf("Value for key 'banana': %d\n", HashTable_Search(hashTable, "banana"));
    printf("Value for key 'orange': %d\n", HashTable_Search(hashTable, "orange"));
    // 删除键为 "banana" 的节点
    HashTable_RemoveItem(hashTable, "banana");
    // 测试是否成功删除
    printf("Value for key 'banana': %d\n", HashTable_Search(hashTable, "banana"));
    HashTable_Destroy(hashTable);
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

参考