C 语言字典实现

介绍

字典（也称为关联数组或哈希表）是一种高效的数据结构，用于存储键值对（key-value pairs）。在C语言中，字典可以通过多种方式实现，包括使用数组、链表、平衡二叉搜索树或哈希表。本文将重点介绍基于哈希表的字典实现，因其在平均情况下具有O(1)的查找、插入和删除时间复杂度。

字典的核心功能包括：

• 插入（Insert）：添加一个新的键值对。
• 查找（Lookup）：根据键查找对应的值。
• 删除（Delete）：移除指定的键值对。

哈希表基础

哈希表是字典的常见实现方式，其核心思想是通过哈希函数将键映射到数组的特定索引位置。理想情况下，哈希函数应均匀分布键，以减少冲突（即多个键映射到同一索引的情况）。

冲突处理

当冲突发生时，常见的解决方法有：

• 链地址法（Chaining）：使用链表存储同一索引下的所有键值对。
• 开放寻址法（Open Addressing）：在发生冲突时，探测数组中的下一个空闲位置。

本文将以链地址法为例实现字典。

字典实现步骤

以下是C语言中字典的完整实现步骤。

1. 定义键值对结构

每个键值对包含一个键（key）、一个值（value）和一个指向下一个键值对的指针（用于链地址法）。

typedef struct KeyValuePair {
    char *key;
    int value;
    struct KeyValuePair *next;
} KeyValuePair;

2. 定义字典结构

字典包含一个固定大小的数组（哈希表）和一个记录当前元素数量的变量。

#define TABLE_SIZE 100

typedef struct Dictionary {
    KeyValuePair *table[TABLE_SIZE];
    int count;
} Dictionary;

3. 哈希函数

哈希函数将字符串键转换为数组索引。这里使用简单的乘法哈希：

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];
    }
    return hash_value % TABLE_SIZE;
}

4. 字典初始化

初始化字典时，将所有数组元素设为NULL。

void dictionary_init(Dictionary *dict) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        dict->table[i] = NULL;
    }
    dict->count = 0;
}

5. 插入键值对

插入时，先计算哈希值，然后检查是否已存在相同键。若存在则更新值，否则添加到链表头部。

void dictionary_insert(Dictionary *dict, const char *key, int value) {
    unsigned int index = hash(key);
    KeyValuePair *current = dict->table[index];

    // 检查键是否已存在
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            current->value = value; // 更新值
            return;
        }
        current = current->next;
    }

    // 创建新键值对
    KeyValuePair *new_pair = malloc(sizeof(KeyValuePair));
    new_pair->key = strdup(key);
    new_pair->value = value;
    new_pair->next = dict->table[index];
    dict->table[index] = new_pair;
    dict->count++;
}

6. 查找键值对

查找时，先计算哈希值，然后遍历链表查找匹配的键。

int dictionary_lookup(Dictionary *dict, const char *key, int *value) {
    unsigned int index = hash(key);
    KeyValuePair *current = dict->table[index];

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            *value = current->value;
            return 1; // 找到
        }
        current = current->next;
    }
    return 0; // 未找到
}

7. 删除键值对

删除时，先找到键值对，然后从链表中移除并释放内存。

int dictionary_delete(Dictionary *dict, const char *key) {
    unsigned int index = hash(key);
    KeyValuePair *current = dict->table[index];
    KeyValuePair *prev = NULL;

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            if (prev == NULL) {
                dict->table[index] = current->next;
            } else {
                prev->next = current->next;
            }
            free(current->key);
            free(current);
            dict->count--;
            return 1; // 删除成功
        }
        prev = current;
        current = current->next;
    }
    return 0; // 未找到键
}

8. 清理字典

释放所有动态分配的内存。

void dictionary_free(Dictionary *dict) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        KeyValuePair *current = dict->table[i];
        while (current != NULL) {
            KeyValuePair *temp = current;
            current = current->next;
            free(temp->key);
            free(temp);
        }
    }
    dict->count = 0;
}

示例代码与输出

以下是一个完整的示例程序，展示字典的插入、查找和删除操作。

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

// 上述所有结构体和函数定义

int main() {
    Dictionary dict;
    dictionary_init(&dict);

    // 插入键值对
    dictionary_insert(&dict, "apple", 10);
    dictionary_insert(&dict, "banana", 20);
    dictionary_insert(&dict, "orange", 30);

    // 查找键值对
    int value;
    if (dictionary_lookup(&dict, "banana", &value)) {
        printf("banana: %d\n", value); // 输出: banana: 20
    }

    // 删除键值对
    dictionary_delete(&dict, "banana");

    // 再次查找
    if (!dictionary_lookup(&dict, "banana", &value)) {
        printf("banana not found\n"); // 输出: banana not found
    }

    dictionary_free(&dict);
    return 0;
}

实际应用场景

字典在以下场景中非常有用：

• 配置文件解析：存储配置项（如键值对）。
• 缓存系统：快速查找缓存数据。
• 数据库索引：加速记录查找。

性能优化

为提高字典性能，可考虑以下优化：

• 动态扩容：当元素数量超过阈值时，扩大哈希表大小并重新哈希所有键。
• 更好的哈希函数：如MurmurHash或CityHash，减少冲突概率。
• 平衡树替代链表：在冲突较多时，使用红黑树代替链表（如Java的HashMap）。

复杂度分析

哈希表字典的平均时间复杂度如下：

操作	平均时间复杂度	最坏时间复杂度
插入	O(1)	O(n)
查找	O(1)	O(n)
删除	O(1)	O(n)

总结

本文详细介绍了C语言中基于哈希表的字典实现，包括结构定义、哈希函数、冲突处理和核心操作。通过代码示例和实际应用场景，读者可以深入理解字典的工作原理及其在程序中的高效使用方式。