22、动态哈希表：简单哈希表的设计、动态扩容与缩容

哈希表，说白了就是“用空间换时间”的典型代表。你给它一个键，它直接算出位置，一步到位。但这里有个坑——算出来的位置可能撞车，也就是哈希冲突。更麻烦的是，表太小了频繁撞车，表太大了又浪费内存。怎么办？动态扩容和缩容就是解药。

我个人习惯把哈希表比作一个停车场。车多了车位不够，就得扩建；车少了空着大片车位，就得缩小。今天我们就来手写一个能自己长大的哈希表。

22.1 哈希表的核心结构

先搭个架子。一个动态哈希表至少需要三样东西：

• 桶数组：存数据的槽位
• 哈希函数：把键映射到桶下标
• 负载因子：决定什么时候扩容/缩容

我在项目中遇到过最蠢的bug——哈希函数写得稀烂，所有键都挤到同一个桶里，哈希表直接退化成链表。所以选哈希函数要慎重。

下面是一个简单的哈希表结构定义：

typedef struct Entry {
    char* key;
    int value;
    struct Entry* next;  // 链地址法解决冲突
} Entry;

typedef struct HashTable {
    Entry** buckets;     // 桶数组
    int size;            // 当前元素个数
    int capacity;        // 桶的数量
    float load_factor;   // 负载因子阈值
} HashTable;

这里用了链地址法处理冲突。每个桶其实是一个链表的头指针。插入时先算哈希，再挂到对应链表的头部。

22.2 哈希函数与插入逻辑

哈希函数要尽量均匀。我常用的一个简单版本：

int hash(const char* key, int capacity) {
    unsigned long h = 5381;
    int c;
    while ((c = *key++)) {
        h = ((h << 5) + h) + c;  // djb2算法
    }
    return h % capacity;
}

这个djb2算法是我从一本老书上抄来的，效果出奇的好。你想想看，它只用移位和加法，速度飞快，而且分布很均匀。

插入时先检查负载因子，超了就扩容。然后算哈希，挂到链表头：

void insert(HashTable* table, const char* key, int value) {
    // 检查是否需要扩容
    if ((float)(table->size + 1) / table->capacity > table->load_factor) {
        resize(table, table->capacity * 2);
    }

    int index = hash(key, table->capacity);
    Entry* new_entry = malloc(sizeof(Entry));
    new_entry->key = strdup(key);
    new_entry->value = value;
    new_entry->next = table->buckets[index];
    table->buckets[index] = new_entry;
    table->size++;
}

22.3 动态扩容与缩容

扩容和缩容的核心逻辑是一样的：申请新桶数组，重新计算每个元素的位置，然后释放旧数组。区别只是新容量的大小。

扩容时容量翻倍，缩容时容量减半。但要注意，缩容不能低于初始容量。我一般设个最小值，比如16。

void resize(HashTable* table, int new_capacity) {
    Entry** new_buckets = calloc(new_capacity, sizeof(Entry*));
    // 遍历旧桶，重新哈希
    for (int i = 0; i < table->capacity; i++) {
        Entry* entry = table->buckets[i];
        while (entry) {
            Entry* next = entry->next;
            int new_index = hash(entry->key, new_capacity);
            entry->next = new_buckets[new_index];
            new_buckets[new_index] = entry;
            entry = next;
        }
    }
    free(table->buckets);
    table->buckets = new_buckets;
    table->capacity = new_capacity;
}

缩容的触发条件我放在删除操作里。每次删除后检查负载因子，如果低于0.25就缩容。嗯，这里要注意，频繁的扩容缩容会导致性能抖动。我一般会加个“冷却”机制——两次调整之间至少间隔一定数量的操作。

22.4 查找与删除

查找很简单：算哈希，然后遍历链表。删除稍微麻烦点，要处理链表节点的摘除。

int lookup(HashTable* table, const char* key) {
    int index = hash(key, table->capacity);
    Entry* entry = table->buckets[index];
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            return entry->value;
        }
        entry = entry->next;
    }
    return -1;  // 没找到
}

void delete(HashTable* table, const char* key) {
    int index = hash(key, table->capacity);
    Entry* entry = table->buckets[index];
    Entry* prev = NULL;
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            if (prev) prev->next = entry->next;
            else table->buckets[index] = entry->next;
            free(entry->key);
            free(entry);
            table->size--;

            // 检查是否需要缩容
            if (table->capacity > 16 &&
                (float)table->size / table->capacity < 0.25) {
                resize(table, table->capacity / 2);
            }
            return;
        }
        prev = entry;
        entry = entry->next;
    }
}

删除时别忘了释放内存。我见过有人只删了指针没free，内存泄漏到怀疑人生。

22.5 整体流程可视化

下面这张图展示了动态哈希表的核心流程：插入时触发扩容，删除时触发缩容，所有操作都经过哈希函数映射到桶。

22.6 性能与注意事项

操作	平均时间复杂度	最坏情况	触发条件
插入	O(1)	O(n)	负载因子 > 阈值 → 扩容
查找	O(1)	O(n)	无
删除	O(1)	O(n)	负载因子 < 0.25 → 缩容
扩容/缩容	O(n)	O(n)	手动或自动触发

最后说一句，动态哈希表不是银弹。如果你的数据量是固定的，静态哈希表更简单高效。但如果你不确定数据规模，动态版本能帮你省很多心。

好了，这一章就到这里。代码都在上面了，你可以直接拿去用。记得测试边界情况——空表、满表、反复插入删除。嗯，实践出真知。