C 语言哈希表

C语言哈希表

哈希表（Hash Table）是一种高效的数据结构，用于存储键值对（Key-Value Pairs），并通过哈希函数（Hash Function）快速查找、插入和删除数据。在C语言中，哈希表通常使用数组和链表（或其他冲突处理方法）实现，广泛应用于数据库索引、缓存系统、编译器符号表等场景。

基本概念

哈希表的核心思想是通过哈希函数将键（Key）映射到数组的某个索引位置，从而实现快速访问。理想情况下，哈希函数应均匀分布键，减少冲突（Collision），即不同键映射到同一索引的情况。

哈希函数

哈希函数的设计直接影响哈希表的性能。常见的哈希函数包括：

• 除法哈希法：$h(k)=kmodm$，其中$m$是哈希表大小。
• 乘法哈希法：$h(k)=\lfloor m\cdot (k\cdot Amod1)\rfloor$，其中$A$是一个常数（如黄金比例0.618）。

冲突处理

当两个键映射到同一索引时，需采用冲突处理方法：

• 链地址法（Chaining）：使用链表存储同一索引的键值对。
• 开放地址法（Open Addressing）：通过探测（如线性探测、二次探测）寻找下一个空闲位置。

C语言实现示例

以下是一个使用链地址法实现哈希表的C语言代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10

// 哈希表节点结构
typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

// 哈希表结构
typedef struct HashTable {
    Node *table[TABLE_SIZE];
} HashTable;

// 哈希函数（简单示例）
unsigned int hash(const char *key) {
    unsigned int hash_value = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        hash_value = (hash_value * 31 + key[i]) % TABLE_SIZE;
    }
    return hash_value;
}

// 初始化哈希表
HashTable *create_hash_table() {
    HashTable *ht = malloc(sizeof(HashTable));
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->table[i] = NULL;
    }
    return ht;
}

// 插入键值对
void insert(HashTable *ht, const char *key, int value) {
    unsigned int index = hash(key);
    Node *new_node = malloc(sizeof(Node));
    new_node->key = strdup(key);
    new_node->value = value;
    new_node->next = ht->table[index];
    ht->table[index] = new_node;
}

// 查找键值对
int 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 -1; // 未找到
}

// 主函数测试
int main() {
    HashTable *ht = create_hash_table();
    insert(ht, "apple", 10);
    insert(ht, "banana", 20);

    printf("apple: %d\n", search(ht, "apple")); // 输出: apple: 10
    printf("banana: %d\n", search(ht, "banana")); // 输出: banana: 20
    printf("orange: %d\n", search(ht, "orange")); // 输出: orange: -1

    return 0;
}

输入与输出

输入：插入键值对（"apple", 10）和（"banana", 20），然后查询"apple"、"banana"和"orange"的值。 输出：

apple: 10
banana: 20
orange: -1

实际应用案例

哈希表在以下场景中广泛应用： 1. 数据库索引：加速记录的查找。 2. 缓存系统（如Redis）：存储键值对以减少数据库访问。 3. 编译器符号表：快速查找变量和函数的信息。

案例：单词频率统计

统计一段文本中每个单词的出现次数：

void count_word_frequency(const char *text) {
    HashTable *ht = create_hash_table();
    char *token = strtok((char *)text, " ");
    while (token != NULL) {
        int count = search(ht, token);
        if (count == -1) {
            insert(ht, token, 1);
        } else {
            insert(ht, token, count + 1);
        }
        token = strtok(NULL, " ");
    }
    // 打印结果（示例）
    for (int i = 0; i < TABLE_SIZE; i++) {
        Node *current = ht->table[i];
        while (current != NULL) {
            printf("%s: %d\n", current->key, current->value);
            current = current->next;
        }
    }
}

性能分析

哈希表的平均时间复杂度为：

• 插入：$O(1)$（无冲突时）
• 查找：$O(1)$（无冲突时）
• 删除：$O(1)$（无冲突时）

最坏情况下（所有键冲突），时间复杂度退化为$O(n)$。

可视化哈希表结构

graph LR subgraph 哈希表 0 -->|"key1, value1"| Node1 1 -->|"key2, value2"| Node2 2 --> NULL 3 -->|"key3, value3"| Node3 -->|"key4, value4"| Node4 end

总结

哈希表是C语言中高效存储和检索数据的重要工具。通过合理设计哈希函数和处理冲突，可以显著提升程序性能。初学者应从链地址法入手，逐步掌握更复杂的实现技巧。