动态哈希表：从0到1解析C语言动态数组+链表冲突解决方案

#include <stdio.h>
#include "hash.h"

int main() {
    // 创建哈希表
    DynamicHashMap *map = hashmap_create();
    if (!map) {
        fprintf(stderr, "Failed to create hashmap.\n");
        return 1;
    }

    // 测试插入操作
    printf("Testing hashmap_put...\n");
    const char *key1 = "name";
    const char *val1 = "Alice";
    ValueType result1 = hashmap_put(map, (KeyType)key1, (ValueType)val1);
    if (result1) {
        printf("Inserted key: %s, value: %s\n", key1, result1);
    }
    else {
        printf("Failed to insert key: %s\n", key1);
    }

    const char *key2 = "age";
    const char *val2 = "25";
    ValueType result2 = hashmap_put(map, (KeyType)key2, (ValueType)val2);
    if (result2) {
        printf("Inserted key: %s, value: %s\n", key2, result2);
    }
    else {
        printf("Failed to insert key: %s\n", key2);
    }

    // 测试更新操作
    printf("\nTesting update...\n");
    const char *new_val1 = "Bob";
    ValueType update_result = hashmap_put(map, (KeyType)key1, (ValueType)new_val1);
    if (update_result) {
        printf("Updated key: %s, new value: %s\n", key1, update_result);
    }
    else {
        printf("Failed to update key: %s\n", key1);
    }

    // 测试查询操作
    printf("\nTesting hashmap_get...\n");
    ValueType get_result1 = hashmap_get(map, (KeyType)key1);
    if (get_result1) {
        printf("Got key: %s, value: %s\n", key1, get_result1);
    }
    else {
        printf("Key %s not found.\n", key1);
    }

    ValueType get_result2 = hashmap_get(map, (KeyType)key2);
    if (get_result2) {
        printf("Got key: %s, value: %s\n", key2, get_result2);
    }
    else {
        printf("Key %s not found.\n", key2);
    }

    // 测试删除操作
    printf("\nTesting hashmap_remove...\n");
    bool remove_result = hashmap_remove(map, (KeyType)key2);
    if (remove_result) {
        printf("Removed key: %s successfully.\n", key2);
    }
    else {
        printf("Failed to remove key: %s\n", key2);
    }

    // 再次查询已删除的键
    ValueType get_after_remove = hashmap_get(map, (KeyType)key2);
    if (get_after_remove) {
        printf("Got key: %s, value: %s\n", key2, get_after_remove);
    }
    else {
        printf("Key %s not found after removal (expected).\n", key2);
    }

    // 销毁哈希表
    printf("\nDestroying hashmap...\n");
    hashmap_destroy(map);
    printf("Hashmap destroyed.\n");

    return 0;
}

#include"hash.h"
#include <time.h>
#include <stdio.h>
#include <string.h>

// 辅助哈希函数（BKDRHash变种）
static uint32_t hash_function(DynamicHashMap *map, const char *key) {
    uint32_t hash = 0;
    while (*key) {
        hash = hash * map->hash_seed + (uint8_t)(*key++);
    }
    return hash % map->capacity;
}
// 创建一个固定容量的哈希表
DynamicHashMap *hashmap_create() {
    DynamicHashMap *map = (DynamicHashMap *)calloc(1, sizeof(DynamicHashMap));
    if (map == NULL) {
        perror("map create");
        exit(EXIT_FAILURE);
    }
    // 初始化参数
    map->capacity = 16;         // 初始容量
    map->size = 0;              // 初始键值对数量
    uint32_t hash_seed = (uint32_t)time(NULL); //种子值随机，减少哈希冲突
    map->buckets = (KeyValueNode **)calloc(map->capacity, sizeof(KeyValueNode *)); //给二重数组设置初始化桶
    if (!map->buckets) {
        perror("map->buckets creat");
        free(map);
        exit(EXIT_FAILURE);
    }
    return map;
}
// 销毁一个哈希表
void hashmap_destroy(DynamicHashMap *map) {
    if (map == NULL) {
        return;
    }
    
    for(int i=0;i<map->capacity;i++) {
        KeyValueNode *p = map->buckets[i];
        while (p != NULL) {
            KeyValueNode *next = p->next;
            free(p->key);
            free(p->val);
            free(p);
            p = next;
        }
    }
    free(map->buckets);  // 释放桶数组
    free(map);
}

// 扩容函数，更新桶容量，所以一个是capacity更新，一个是buckets更新
static bool hashmap_resize(DynamicHashMap *map) {
    KeyValueNode **new_buckets = (KeyValueNode **)calloc((2 * map->capacity), sizeof(KeyValueNode *));
    if (!new_buckets) {
        perror("new_buckets create");
        return false;
    }
    //保存旧数据
    KeyValueNode **old_buckets = map->buckets;
    int old_capacity = map->capacity;

    //更新哈希表参数
    map->capacity *= 2;
    map->buckets = new_buckets;
    //更新节点
    for (int i = 0; i < old_capacity; i++) {
        KeyValueNode *current = old_buckets[i];
        while (current) {
            KeyValueNode *next = current->next;
            int index= hash_function(map, current->key);

            current->next = map->buckets[index];
            map->buckets[index] = current;  //此处看做指针可能更好理解
            current = next;
        }
    }
    free(old_buckets);  // 释放旧桶数组
    return true;
}
// 复制字符串 strdup被禁用
static ValueType strdupp(const ValueType val) {
    size_t len = strlen(val) + 1;
    ValueType p = (ValueType)malloc(len);
    if (!p) {
        return NULL;
    }
    if (strcpy_s(p, len, val) != 0) {
        free(p);
        return NULL;
    }
    return p;
}
// 插入一个键值对
ValueType hashmap_put(DynamicHashMap *map, KeyType key, ValueType val) {
    if (!map || !key || !val) return NULL; //保证输出没问题
    int index = hash_function(map,key);
    //查找现有键值，没有就新建，有就顺序插入
    KeyValueNode *current = map->buckets[index];
    while (current) {
        if (strcmp(current->key, key) == 0) {
            // 找到重复键，更新值
            free(current->val);       // 释放旧值
            current->val = strdupp(val); // 存储新值副本,此处需要新函数，让旧值更新
            if (!current->val) return NULL; // 内存分配失败处理
            return current->val;
        }
        current = current->next;
    }
    //没有这个值，那就新建
    KeyValueNode *new_node = (KeyValueNode *)calloc(1,sizeof(KeyValueNode));
    if (!new_node) return NULL;
    new_node->key = strdupp(key);
    new_node->val = strdupp(val);
    if (!new_node->key || !new_node->val) { // 内存分配失败处理
        free(new_node->key);
        free(new_node->val);
        free(new_node);
        return NULL;
    }
    // 插入链表头部
    new_node->next = map->buckets[index];
    map->buckets[index] = new_node;
    map->size++;

    //检查负载因子
    float load_factor = (float)map->size / map->capacity;
    if (load_factor > 0.75) {
        if (!hashmap_resize(map)) {
            // 扩容失败时删除刚插入的节点（可选）
            hashmap_remove(map, key);
            return NULL;
        }
    }
    return new_node->val;
}
// 查询一个键值对，此处跟正常数组一样了
ValueType hashmap_get(DynamicHashMap *map, KeyType key) {
    if (!map || !key) {
        printf("没有这个值");
        return false;
    }
    int index = hash_function(map, key);
    KeyValueNode *current = map->buckets[index];
    while (current) {
        if (strcmp(current->key, key) == 0) {
            return current->val;
        }
        current=current->next;
    }
    printf("没有这个值");
    return NULL;
}
// 删除某个键值对
bool hashmap_remove(DynamicHashMap *map, KeyType key) {
    if (!map || !key) {
        printf("没有这个值");
        return false;
    }
    int index = hash_function(map, key);
    KeyValueNode *prev = NULL;
    KeyValueNode *current = map->buckets[index];
    while (current) {
        if (strcmp(current->key, key) == 0) {
            if (prev) {
                prev->next = current->next;
            }
            else {
                map->buckets[index] = current->next;  // 头节点删除
            }
            // 释放内存
            free(current->key);
            free(current->val);
            free(current);
            map->size--;
            return true;
        }
        prev = current;
        current = current->next;
    }
    return false;  // 未找到
}