C语言hashtable如何实现高效查找？-C语言-盈思创科技

哈希表基本原理

哈希表的核心思想是使用一个哈希函数，将任意长度的键映射到一个固定大小的数组（我们称之为“桶”或“槽”）的索引上。

（图片来源网络，侵删）

存储：要插入一个键值对 (key, value)，首先通过哈希函数计算 key 的哈希值，然后通过某种方式（通常是取模）将哈希值转换成数组的索引 index，然后将 (key, value) 存储在 table[index] 的位置。
查找：要查找一个 key 对应的 value，同样用哈希函数计算 key 的索引，然后直接访问 table[index] 即可。

核心组件与挑战

在 C 语言中实现哈希表，我们需要解决以下几个核心问题：

1 哈希函数

哈希函数需要满足：

确定性：相同的 key 必须产生相同的哈希值。
高效性：计算速度要快。
均匀性：哈希值应尽可能均匀地分布在数组中，以减少冲突。

对于字符串类型的 key，一个简单且常用的哈希函数是“加权求和”。

unsigned int hash(const char *key, int table_size) {
    unsigned long int hash_value = 0;
    int i = 0;
    while (key && key[i]) {
        // 将字符的ASCII码乘以一个权重（i的幂次）并累加
        hash_value = (hash_value << 5) + key[i]; // 左移5位相当于乘以32
        i++;
    }
    return hash_value % table_size;
}

2 冲突解决

当两个不同的 key 经过哈希函数计算出相同的索引时，就会发生冲突，解决冲突是哈希表实现的关键，常见的解决方法有两种：

（图片来源网络，侵删）

链地址法
- 原理：将哈希表的每个槽看作一个链表的头部，当发生冲突时，新的键值对被添加到对应索引的链表末尾。
- 优点：实现简单，内存利用率高。
- 缺点：当冲突严重时，链表会变长，导致查找效率下降到 O(n)。
开放地址法
- 原理：当发生冲突时，按照某种规则（如线性探测、二次探测）寻找下一个“空槽”来存储键值对。
- 优点：缓存友好性好，在负载因子较低时性能很高。
- 缺点：删除操作比较复杂（不能直接删除，需要标记为“已删除”），容易产生聚集现象。

我们将在这里实现更常见的链地址法。

3 动态扩容

当哈希表中的元素数量（负载因子 = 元素数量 / 桶的数量）超过某个阈值（0.75）时，哈希表的性能会急剧下降，我们需要进行扩容：

（图片来源网络，侵删）

创建一个更大的新桶数组（通常是容量的 2 倍）。
重新计算所有现有键值对的哈希值,并将它们插入到新的桶数组中。
释放旧的桶数组。

这个过程叫做再哈希。

C 语言完整实现（链地址法）

下面是一个完整的、可运行的 C 语言哈希表实现，包含了创建、插入、查找、删除和销毁功能。

1 定义数据结构

我们需要定义两个结构体：

HashTableEntry：存储单个键值对，以及指向下一个节点的指针（用于链表）。
HashTable：哈希表本身，包含桶数组、桶的数量和当前存储的元素数量。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义一个键值对节点
typedef struct HashTableEntry {
    char *key;          // 键
    int value;          // 值
    struct HashTableEntry *next; // 指向下一个节点的指针，用于解决冲突
} HashTableEntry;
// 定义哈希表
typedef struct {
    int size;           // 桶的数量
    int count;          // 当前存储的元素数量
    HashTableEntry **entries; // 桶数组，每个元素是一个指向链表头节点的指针
} HashTable;

2 辅助函数

哈希函数（上面已展示）和创建新节点的函数。

// 哈希函数
unsigned int hash(const char *key, int table_size) {
    unsigned long int hash_value = 0;
    int i = 0;
    while (key && key[i]) {
        hash_value = (hash_value << 5) + key[i];
        i++;
    }
    return hash_value % table_size;
}
// 创建一个新的键值对节点
HashTableEntry* create_entry(const char *key, int value) {
    HashTableEntry *entry = (HashTableEntry*)malloc(sizeof(HashTableEntry));
    if (!entry) return NULL; // 内存分配失败
    entry->key = strdup(key); // 为键分配内存并复制
    if (!entry->key) {
        free(entry);
        return NULL;
    }
    entry->value = value;
    entry->next = NULL;
    return entry;
}

3 核心操作函数

3.1 创建哈希表

HashTable* create_table(int size) {
    HashTable *table = (HashTable*)malloc(sizeof(HashTable));
    if (!table) return NULL;
    table->size = size;
    table->count = 0;
    // 为桶数组分配内存
    table->entries = (HashTableEntry**)calloc(size, sizeof(HashTableEntry*));
    if (!table->entries) {
        free(table);
        return NULL;
    }
    return table;
}

3.2 插入或更新键值对

这是最复杂的函数之一,需要处理：

计算索引。
处理该索引处已有链表的情况。
如果键已存在,则更新值。
如果键不存在,则创建新节点并插入链表头部。
检查是否需要扩容。

void insert(HashTable *table, const char *key, int value) {
    // 检查是否需要扩容 (负载因子 > 0.75)
    if (table->count >= table->size * 0.75) {
        resize_table(table);
    }
    unsigned int index = hash(key, table->size);
    HashTableEntry *entry = table->entries[index];
    HashTableEntry *prev = NULL;
    // 遍历链表，查找是否已存在该键
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            // 键已存在，更新值并返回
            entry->value = value;
            return;
        }
        prev = entry;
        entry = entry->next;
    }
    // 键不存在，创建新节点
    HashTableEntry *new_entry = create_entry(key, value);
    if (!new_entry) {
        fprintf(stderr, "Memory allocation failed for new entry.\n");
        return;
    }
    // 将新节点插入到链表头部
    if (prev == NULL) {
        // 链表为空，直接插入
        table->entries[index] = new_entry;
    } else {
        // 链表不为空，插入到头部
        new_entry->next = table->entries[index];
        table->entries[index] = new_entry;
    }
    table->count++;
}

3.3 查找键值对

int search(HashTable *table, const char *key) {
    unsigned int index = hash(key, table->size);
    HashTableEntry *entry = table->entries[index];
    // 遍历链表查找
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            return entry->value; // 找到，返回值
        }
        entry = entry->next;
    }
    return -1; // 未找到，返回-1 (假设-1不是一个有效的值)
}

3.4 删除键值对

删除操作也需要遍历链表,并处理删除的是头节点还是中间节点的情况。

void delete(HashTable *table, const char *key) {
    unsigned int index = hash(key, table->size);
    HashTableEntry *entry = table->entries[index];
    HashTableEntry *prev = NULL;
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            // 找到要删除的节点
            if (prev == NULL) {
                // 删除的是头节点
                table->entries[index] = entry->next;
            } else {
                // 删除的是中间或尾节点
                prev->next = entry->next;
            }
            // 释放内存
            free(entry->key);
            free(entry);
            table->count--;
            return;
        }
        prev = entry;
        entry = entry->next;
    }
}

3.5 扩容函数（再哈希）

这是保持哈希表高效的关键。

void resize_table(HashTable *table) {
    int new_size = table->size * 2;
    HashTableEntry **new_entries = (HashTableEntry**)calloc(new_size, sizeof(HashTableEntry*));
    if (!new_entries) {
        fprintf(stderr, "Memory allocation failed for resizing table.\n");
        return;
    }
    // 重新哈希所有现有条目
    for (int i = 0; i < table->size; i++) {
        HashTableEntry *entry = table->entries[i];
        while (entry != NULL) {
            HashTableEntry *next = entry->next; // 保存下一个节点
            // 计算在新表中的索引
            unsigned int new_index = hash(entry->key, new_size);
            // 将节点插入到新表的链表头部
            entry->next = new_entries[new_index];
            new_entries[new_index] = entry;
            entry = next;
        }
    }
    // 释放旧桶数组的内存（注意：不释放节点本身，它们已被移动到新数组）
    free(table->entries);
    // 更新哈希表信息
    table->entries = new_entries;
    table->size = new_size;
}

3.6 释放哈希表内存

必须释放所有动态分配的内存,包括桶数组和每个键值对节点。

void free_table(HashTable *table) {
    for (int i = 0; i < table->size; i++) {
        HashTableEntry *entry = table->entries[i];
        while (entry != NULL) {
            HashTableEntry *temp = entry;
            entry = entry->next;
            free(temp->key);
            free(temp);
        }
    }
    free(table->entries);
    free(table);
}

4 主函数示例

int main() {
    // 创建一个初始大小为5的哈希表
    HashTable *ht = create_table(5);
    if (!ht) {
        fprintf(stderr, "Failed to create hash table.\n");
        return 1;
    }
    // 插入一些键值对
    insert(ht, "apple", 10);
    insert(ht, "banana", 20);
    insert(ht, "orange", 30);
    insert(ht, "grape", 40);
    insert(ht, "pear", 50); // 这个插入可能会触发扩容
    // 查找并打印
    printf("Value for 'apple': %d\n", search(ht, "apple"));    // 应该输出 10
    printf("Value for 'banana': %d\n", search(ht, "banana"));  // 应该输出 20
    printf("Value for 'nonexistent': %d\n", search(ht, "nonexistent")); // 应该输出 -1
    // 更新一个键的值
    insert(ht, "apple", 100);
    printf("Value for 'apple' after update: %d\n", search(ht, "apple")); // 应该输出 100
    // 删除一个键
    delete(ht, "banana");
    printf("Value for 'banana' after deletion: %d\n", search(ht, "banana")); // 应该输出 -1
    // 打印当前状态
    printf("Current table size: %d, count: %d\n", ht->size, ht->count);
    // 释放哈希表
    free_table(ht);
    return 0;
}

这个 C 语言哈希表实现涵盖了所有核心要素：

数据结构：使用结构体 HashTable 和 HashTableEntry。
哈希函数：一个简单的字符串哈希函数。
冲突解决：采用链地址法，每个桶是一个链表。
动态扩容：当负载因子过高时，自动进行扩容和再哈希，以保持性能。
内存管理：正确地分配和释放所有动态内存，避免内存泄漏。

这个实现是教学和实际应用中一个很好的起点,你可以基于此进行扩展，

使用更复杂的哈希函数（如 DJB2, MurmurHash）。
实现开放地址法。
使用泛型编程（void*）来支持任意类型的键和值。
添加迭代器功能。

C语言hashtable如何实现高效查找？

哈希表基本原理

核心组件与挑战

1 哈希函数

2 冲突解决

3 动态扩容

C 语言完整实现（链地址法）

1 定义数据结构

2 辅助函数

3 核心操作函数

3.1 创建哈希表

3.2 插入或更新键值对

3.3 查找键值对

3.4 删除键值对

3.5 扩容函数（再哈希）

3.6 释放哈希表内存

4 主函数示例

相关文章

目录[+]