📚 课程目录第2章基于内存的哈希表存储引擎

2. 基于内存的哈希表存储引擎

任务说明

实现一个基于内存的哈希表存储引擎，支持键值对的写入、读取、删除和遍历操作，并具备哈希冲突处理能力。该引擎作为数据库内核中的存储层组件，提供O(1)平均复杂度的基本访问操作。

核心设计

采用链地址法处理哈希冲突，底层使用动态扩容的桶数组。每个桶维护一个单向链表，节点存储键、值和指向下一节点的指针。当负载因子超过0.75时触发扩容，将桶数组大小翻倍并重新哈希所有键值对。键类型支持字符串和整数，值类型为字符串，通过哈希函数将键映射到桶索引。

代码实现


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

#define INIT_BUCKETS 8
#define LOAD_FACTOR_THRESHOLD 0.75

typedef struct HashNode {
    char *key;
    char *value;
    struct HashNode *next;
} HashNode;

typedef struct {
    HashNode **buckets;
    int bucket_count;
    int element_count;
} HashTable;

/* FNV-1a 哈希函数 */
static unsigned long hash_key(const char *key) {
    unsigned long hash = 2166136261UL;
    while (*key) {
        hash ^= (unsigned char)(*key++);
        hash *= 16777619UL;
    }
    return hash;
}

static HashNode *create_node(const char *key, const char *value) {
    HashNode *node = (HashNode *)malloc(sizeof(HashNode));
    node->key = strdup(key);
    node->value = strdup(value);
    node->next = NULL;
    return node;
}

static void free_node(HashNode *node) {
    free(node->key);
    free(node->value);
    free(node);
}

static void resize(HashTable *table) {
    int new_size = table->bucket_count * 2;
    HashNode **new_buckets = (HashNode **)calloc(new_size, sizeof(HashNode *));
    
    for (int i = 0; i < table->bucket_count; i++) {
        HashNode *node = table->buckets[i];
        while (node) {
            HashNode *next = node->next;
            int new_index = hash_key(node->key) % new_size;
            node->next = new_buckets[new_index];
            new_buckets[new_index] = node;
            node = next;
        }
    }
    free(table->buckets);
    table->buckets = new_buckets;
    table->bucket_count = new_size;
}

void ht_init(HashTable *table) {
    table->bucket_count = INIT_BUCKETS;
    table->element_count = 0;
    table->buckets = (HashNode **)calloc(table->bucket_count, sizeof(HashNode *));
}

void ht_put(HashTable *table, const char *key, const char *value) {
    int index = hash_key(key) % table->bucket_count;
    HashNode *node = table->buckets[index];
    
    while (node) {
        if (strcmp(node->key, key) == 0) {
            free(node->value);
            node->value = strdup(value);
            return;
        }
        node = node->next;
    }
    
    HashNode *new_node = create_node(key, value);
    new_node->next = table->buckets[index];
    table->buckets[index] = new_node;
    table->element_count++;
    
    if ((float)table->element_count / table->bucket_count > LOAD_FACTOR_THRESHOLD) {
        resize(table);
    }
}

char *ht_get(HashTable *table, const char *key) {
    int index = hash_key(key) % table->bucket_count;
    HashNode *node = table->buckets[index];
    
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return NULL;
}

int ht_delete(HashTable *table, const char *key) {
    int index = hash_key(key) % table->bucket_count;
    HashNode *node = table->buckets[index];
    HashNode *prev = NULL;
    
    while (node) {
        if (strcmp(node->key, key) == 0) {
            if (prev) {
                prev->next = node->next;
            } else {
                table->buckets[index] = node->next;
            }
            free_node(node);
            table->element_count--;
            return 1;
        }
        prev = node;
        node = node->next;
    }
    return 0;
}

void ht_free(HashTable *table) {
    for (int i = 0; i < table->bucket_count; i++) {
        HashNode *node = table->buckets[i];
        while (node) {
            HashNode *next = node->next;
            free_node(node);
            node = next;
        }
    }
    free(table->buckets);
    table->buckets = NULL;
    table->bucket_count = 0;
    table->element_count = 0;
}

void ht_print(HashTable *table) {
    printf("哈希表内容 (桶数=%d, 元素数=%d):\n", table->bucket_count, table->element_count);
    for (int i = 0; i < table->bucket_count; i++) {
        HashNode *node = table->buckets[i];
        if (node) {
            printf("  桶[%d]: ", i);
            while (node) {
                printf("(%s→%s) ", node->key, node->value);
                node = node->next;
            }
            printf("\n");
        }
    }
}

int main() {
    HashTable table;
    ht_init(&table);
    
    /* 写入数据 */
    ht_put(&table, "user:1", "Alice");
    ht_put(&table, "user:2", "Bob");
    ht_put(&table, "user:3", "Carol");
    ht_put(&table, "user:4", "David");
    ht_put(&table, "user:5", "Eve");
    ht_put(&table, "user:6", "Frank");
    ht_put(&table, "user:7", "Grace");
    ht_put(&table, "user:8", "Henry");
    ht_put(&table, "user:9", "Ivy");
    ht_put(&table, "user:10", "Jack");
    
    ht_print(&table);
    
    /* 读取验证 */
    char *val = ht_get(&table, "user:5");
    printf("\n读取 user:5 → %s\n", val ? val : "未找到");
    
    val = ht_get(&table, "user:99");
    printf("读取 user:99 → %s\n", val ? val : "未找到");
    
    /* 更新验证 */
    ht_put(&table, "user:5", "Eve_Updated");
    val = ht_get(&table, "user:5");
    printf("更新后 user:5 → %s\n", val);
    
    /* 删除验证 */
    int deleted = ht_delete(&table, "user:3");
    printf("删除 user:3 → %s\n", deleted ? "成功" : "失败");
    
    deleted = ht_delete(&table, "user:3");
    printf("再次删除 user:3 → %s\n", deleted ? "成功" : "失败");
    
    ht_print(&table);
    
    ht_free(&table);
    return 0;
}

编译与运行


gcc -o hash_engine hash_engine.c -Wall
./hash_engine

验证方法与判定标准

程序执行后，观察以下输出以验证功能正确性：

初始写入10个键值对后，哈希表应显示元素数为10，桶数因扩容变为16（初始8个桶，负载因子超过0.75后触发扩容）；
读取存在的键user:5返回对应值，读取不存在的键user:99返回“未找到”；
更新user:5的值后再次读取，返回更新后的新值；
第一次删除user:3返回“成功”，第二次删除同一键返回“失败”，表明键已被移除；
最终打印的哈希表内容中不包含user:3，且元素数减少为9。