引子

当构造数组变得不实用或困难，尤其又要增删查找时。一种动态集合结构（至少支持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;
}

参考