C/C++语言进阶-哈希表＜哈希表完全解析：从算法原理到C语言实战，一次彻底搞懂Hash！＞

csyys1

614人浏览 · 2025-10-15 22:09:44

csyys1 · 2025-10-15 22:09:44 发布

哈希表完全解析：从算法原理到C语言实战，一次彻底搞懂Hash！
内容较多，但非常全面，内容涵盖了哈希表从算法原理 → 代码实现 → 实际应用 → 面试考点的全流程，非常适合做学习资料或面试复盘。

本文将带你从零开始，深入理解哈希算法的原理与实现，掌握链地址法、开放寻址法、负载控制与扩容机制，并通过完整C语言示例代码构建自己的哈希库。
无论你是准备面试、写底层代码，还是做嵌入式内存优化，这都是一篇你读完就能上手实战的 Hash 全指南。

一、哈希（Hash）算法

哈希算法（Hash Function）的作用是：

把“任意长度的输入数据”转换成“固定长度的整数值”。

这个整数值称为哈希值（Hash Value）或散列值。
哈希算法的核心目标是：

快速查找（O(1) 平均时间）
快速插入 / 删除
避免冲突（Collision）

二、哈希表（Hash Table）

哈希表是一种根据键（key）快速访问值（value）的数据结构。
它的实现原理是：

使用哈希函数计算出 key 的哈希值；
把哈希值对数组长度取模，得到存放位置；
将数据存入这个位置。

例如：

index = hash("apple") % table_size;
table[index] = "red";

这样，下次查找 "apple" 时，只需要一次哈希计算，就能直接定位。

三、基本思想（原理）

哈希表主要由三部分组成：

哈希函数 (Hash Function)
把“键”变成一个数字（索引）。
比如字符串 "apple" → 计算得到哈希值 1234567。
再用 % 表的大小 → 比如 % 127 = 5，那么就放进第 5 号桶。
桶（Bucket）数组
整个哈希表其实就是一堆“桶”。
每个桶里装若干 key-value 对。
如果两个 key 算出来的哈希值一样（叫哈希冲突），它们就会放在同一个桶里。
解决冲突
当两个键算出来的位置一样时，怎么办？
常见两种方法：
- 链表法（拉链法）：每个桶里放一个链表。
- 开放寻址法：找下一个空位。

四、哈希函数算法

哈希函数是可以自定义、根据不同数据类型或场景变化的。
它的核心目标只有一个：

把任意键值（key）尽量均匀地映射到一个有限范围内的整数（索引）。

所以具体算法取决于：

你要哈希的键类型（数字 / 字符串 / 结构体等）
你要追求的速度 vs 分布均匀性
你表的大小和应用场景

1️⃣ 数值型 Key

如果 key 是整数：

hash = key % table_size;

简单直接，但可能分布不均。
改进方式：

使用乘法法（Knuth 推荐）

hash = (int)(table_size * (key * A - floor(key * A)));  // A为常数≈0.618

2️⃣ 字符串型 Key（最常见）

对于字符串（如 "apple"），常见几种方法：

（1）加权求和法（简单）

unsigned int hash = 0;
for (char *p = str; *p; p++) {
    hash += *p;  // 每个字符的ASCII累加
}
hash %= table_size;

👉 简单但容易冲突。

（2）乘法 + 累加法（经典）

unsigned int hash = 0;
for (char *p = str; *p; p++) {
    hash = 31 * hash + *p;  // 31可以换成131, 1313等质数
}
return hash % table_size;

✅ 这是 Java 的 String.hashCode() 原理。
它计算快、分布好。

（3）BKDR Hash（常用）

unsigned int BKDRHash(char *str) {
    unsigned int seed = 131; // 或 31, 1313, 13131 等
    unsigned int hash = 0;
    while (*str)
        hash = hash * seed + (*str++);
    return (hash & 0x7FFFFFFF);
}

✅ 常用于 C/C++ 程序，简单高效。

（4）DJB2 Hash（经典稳定）

unsigned int DJBHash(char *str) {
    unsigned int hash = 5381;
    while (*str)
        hash = ((hash << 5) + hash) + (*str++); // hash * 33 + c
    return hash;
}

✅ 分布好、实现简单，是 Linux/Redis 中常见算法。

3️⃣ 结构体 Key（多字段组合）

可以把多个字段的哈希混合：

hash = (hash_int(id) * 31 + hash_str(name)) % table_size;

或使用通用的“混合函数”（bit-mix）。

4️⃣ 工业级高性能哈希算法

在性能要求高的系统中（如数据库、哈希索引、语言运行时），
常用更复杂的散列算法，如：

算法名	特点	常见应用
MurmurHash	高速、均匀、非加密	Redis、LevelDB
CityHash / FarmHash	Google 出品，针对长字符串优化	Bigtable、TensorFlow
FNV-1 / FNV-1a	简单且效果好	HashMap, 文件校验
CRC32 / SHA-1 等	校验或安全性场景	Git、网络传输

🧩 补充：选择哈希函数时的考虑

目标	推荐算法
简单、教学用	乘法 + 累加法、DJB2
实际项目、性能优先	MurmurHash、FNV
安全要求高	SHA-256、MD5（不推荐用于安全）
小型嵌入式系统	BKDR、DJB2（运算轻）

五、解决冲突

🔄 1 链地址法（Separate Chaining，也叫拉链法）

💡 基本思想

每个桶（bucket）不只放一个元素，而是放一个**链表（或其他结构）**来存放所有哈希到同一个桶的键值对。

当发生冲突时，不找别的位置，而是在同一个桶的链表尾部插入。

📦 结构示意

哈希表（数组）：
[0] → NULL
[1] → ("apple", 5) → ("cat", 7) → NULL
[2] → ("banana", 8) → NULL
[3] → NULL
[4] → ("pear", 9) → NULL

比如：

“apple” → 哈希值 = 1
“cat” → 哈希值 = 1（冲突！）
→ 插到 [1] 的链表后面。

🧩 C语言示例

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

#define TABLE_SIZE 5

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

Node *hashTable[TABLE_SIZE] = {NULL};

unsigned int hash(char *key) {
    unsigned int hash = 0;
    while (*key)
        hash = (hash * 31) + (*key++);
    return hash % TABLE_SIZE;
}

void insert(char *key, int value) {
    unsigned int idx = hash(key);
    Node *newNode = malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->value = value;
    newNode->next = hashTable[idx];
    hashTable[idx] = newNode;
}

int search(char *key) {
    unsigned int idx = hash(key);
    Node *p = hashTable[idx];
    while (p) {
        if (strcmp(p->key, key) == 0)
            return p->value;
        p = p->next;
    }
    return -1;
}

✅ 优点：

实现简单。
表容量满了也能插入（只需链表加长）。
删除元素方便（直接操作链表）。

⚠️ 缺点：

需要额外的内存存储链表节点。
当冲突多时（链太长），查找效率降低。

🔄 2 开放寻址法（Open Addressing）

💡 基本思想

如果一个位置已经被占，就按照某种探查规则（探测序列），
继续寻找下一个空位直到找到为止。

所有元素都存在数组中，不使用链表。

📦 结构示意

假设表长 = 7，哈希函数为 hash(key) = key % 7

插入序列：14，21，28，35

14 → 0号位置
21 → 0冲突 → 1号位置
28 → 0冲突 → 1冲突 → 2号位置
35 → 0冲突 → 1冲突 → 2冲突 → 3号位置

🚀 探查方式（重点）

开放寻址法的区别主要在“探查序列”：

类型	规则	特点
线性探查 (Linear Probing)	i, i+1, i+2...	简单但容易“聚集”
二次探查 (Quadratic Probing)	i, i+1², i+2²...	减少聚集
双重哈希 (Double Hashing)	i, i+h2(key)	分布更随机

🧩 线性探查 C语言示例

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

#define TABLE_SIZE 7

typedef struct {
    int used;
    char *key;
    int value;
} Entry;

Entry table[TABLE_SIZE] = {0};

unsigned int hash(char *key) {
    unsigned int h = 0;
    while (*key)
        h = (h * 31) + (*key++);
    return h % TABLE_SIZE;
}

void insert(char *key, int value) {
    unsigned int idx = hash(key);
    while (table[idx].used) {
        idx = (idx + 1) % TABLE_SIZE;  // 线性探查
    }
    table[idx].key = key;
    table[idx].value = value;
    table[idx].used = 1;
}

int search(char *key) {
    unsigned int idx = hash(key);
    int start = idx;
    while (table[idx].used) {
        if (strcmp(table[idx].key, key) == 0)
            return table[idx].value;
        idx = (idx + 1) % TABLE_SIZE;
        if (idx == start) break;  // 避免死循环
    }
    return -1;
}

✅ 优点：

数据全在一块连续内存中（Cache 友好）。
不需要链表或指针，结构简单。

⚠️ 缺点：

表容易“变满”。
删除复杂（要标记“删除”而不能直接清空）。
当负载因子（装填率）高时性能迅速下降。

📊 两种方法对比总结

项目	链地址法	开放寻址法
存储结构	数组 + 链表	单一数组
空间利用率	较低（需指针）	较高
查找效率	冲突多时退化为链表	冲突多时退化为线性扫描
删除操作	简单	复杂（需特殊标记）
适合场景	动态插入删除多	数据较密、空间紧凑场景

链地址法： 冲突元素挂在链表上。
开放寻址法： 冲突元素找下一个空位。

六、C语言简单实现

1 简单示例（链地址法）

下面是一个简化的哈希表实现（key 为字符串，value 为整数）。

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

#define TABLE_SIZE 10

// 哈希表节点
typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

// 哈希表结构
typedef struct HashTable {
    Node *buckets[TABLE_SIZE];
} HashTable;

// 创建哈希表
HashTable* create_table() {
    HashTable *table = malloc(sizeof(HashTable));
    for (int i = 0; i < TABLE_SIZE; i++)
        table->buckets[i] = NULL;
    return table;
}

// 哈希函数（简单字符串哈希）
unsigned int hash(const char *key) {
    unsigned int hash = 0;
    while (*key) {
        hash = hash * 31 + *key++;
    }
    return hash % TABLE_SIZE;
}

// 插入键值对
void insert(HashTable *table, const char *key, int value) {
    unsigned int index = hash(key);
    Node *newNode = malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->value = value;
    newNode->next = table->buckets[index];
    table->buckets[index] = newNode;
}

// 查找值
int* search(HashTable *table, const char *key) {
    unsigned int index = hash(key);
    Node *curr = table->buckets[index];
    while (curr) {
        if (strcmp(curr->key, key) == 0)
            return &curr->value;
        curr = curr->next;
    }
    return NULL;
}

// 删除键
void delete(HashTable *table, const char *key) {
    unsigned int index = hash(key);
    Node *curr = table->buckets[index];
    Node *prev = NULL;

    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            if (prev) prev->next = curr->next;
            else table->buckets[index] = curr->next;
            free(curr->key);
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}

// 释放哈希表
void free_table(HashTable *table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Node *curr = table->buckets[i];
        while (curr) {
            Node *tmp = curr;
            curr = curr->next;
            free(tmp->key);
            free(tmp);
        }
    }
    free(table);
}

// 测试
int main() {
    HashTable *table = create_table();

    insert(table, "apple", 10);
    insert(table, "banana", 20);
    insert(table, "orange", 30);

    int *val = search(table, "banana");
    if (val)
        printf("banana => %d\n", *val);
    else
        printf("Not found\n");

    delete(table, "banana");

    val = search(table, "banana");
    if (val)
        printf("banana => %d\n", *val);
    else
        printf("Not found\n");

    free_table(table);
    return 0;
}

运行结果示例

banana => 20
Not found

2 C语言库（完整版）

hash.h

#ifndef HASHLIB_H

#define HASHLIB_H

#include <stddef.h>

#ifdef __cplusplus

extern "C" {

#endif

/* 哈希表键类型 */

typedef enum {

HASH_KEY_INT = 0, /* 整型键 */

HASH_KEY_STR = 1, /* 字符串键 */

HASH_KEY_PTR = 2 /* 指针键 */

} hash_key_type_t;

/* 哈希算法类型 */

typedef enum {

HASH_ALGO_DJB2 = 0, /* DJB2算法 */

HASH_ALGO_BKDR = 1, /* BKDR算法 */

HASH_ALGO_SDBM = 2, /* SDBM算法 */

HASH_ALGO_RS = 3 /* RS算法 */

} hash_algo_t;

/* 冲突解决方法 */

typedef enum {

COLLISION_CHAINING = 0, /* 链地址法 */

COLLISION_LINEAR = 1, /* 线性探测 */

COLLISION_QUADRATIC = 2 /* 二次探测 */

} collision_method_t;

/* 哈希表句柄 */

typedef struct hash_table hash_table_t;

/* 创建哈希表

* initial_size: 初始大小，0表示使用默认值

* key_type: 键类型

* algo: 哈希算法

* method: 冲突解决方法

*/

hash_table_t* hash_table_create(size_t initial_size,

hash_key_type_t key_type,

hash_algo_t algo,

collision_method_t method);

/* 销毁哈希表 */

void hash_table_destroy(hash_table_t* ht);

/* 插入键值对 */

int hash_table_put(hash_table_t* ht, const void* key, void* value);

/* 获取值 */

void* hash_table_get(hash_table_t* ht, const void* key);

/* 删除键值对 */

int hash_table_remove(hash_table_t* ht, const void* key);

/* 获取元素数量 */

size_t hash_table_size(hash_table_t* ht);

/* 判断是否为空 */

int hash_table_is_empty(hash_table_t* ht);

/* 清空哈希表 */

void hash_table_clear(hash_table_t* ht);

/* 遍历哈希表 */

int hash_table_foreach(hash_table_t* ht,

int (*callback)(const void* key, void* value, void* user_data),

void* user_data);

/* 获取负载因子 */

double hash_table_load_factor(hash_table_t* ht);

/* 重新哈希（扩容） */

int hash_table_rehash(hash_table_t* ht, size_t new_size);

/* 字符串哈希算法函数（可直接使用） */

unsigned long hash_djb2(const char* str);

unsigned long hash_bkdr(const char* str);

unsigned long hash_sdbm(const char* str);

unsigned long hash_rs(const char* str);

#ifdef __cplusplus

}

#endif

#endif /* HASHLIB_H */

hash.cpp

#include "hashlib.h"

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

#include <assert.h>

/* 默认质数表，用于哈希表大小 */

static const size_t PRIMES[] = {

53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,

49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469

};

#define PRIME_COUNT (sizeof(PRIMES) / sizeof(PRIMES[0]))

#define DEFAULT_LOAD_FACTOR 0.75

#define MAX_LOAD_FACTOR 0.85

/* 哈希表条目状态 */

typedef enum {

ENTRY_EMPTY = 0,

ENTRY_OCCUPIED = 1,

ENTRY_DELETED = 2

} entry_status_t;

/* 哈希表条目 */

typedef struct hash_entry {

void* key; /* 键 */

void* value; /* 值 */

entry_status_t status; /* 状态 */

struct hash_entry* next; /* 链地址法中的下一个条目 */

} hash_entry_t;

/* 哈希表结构 */

struct hash_table {

hash_entry_t* entries; /* 条目数组 */

size_t capacity; /* 容量 */

size_t size; /* 当前大小 */

hash_key_type_t key_type; /* 键类型 */

hash_algo_t algorithm; /* 哈希算法 */

collision_method_t method; /* 冲突解决方法 */

double max_load_factor; /* 最大负载因子 */

};

/* 选择最接近的质数 */

static size_t find_nearest_prime(size_t min_size) {

for (size_t i = 0; i < PRIME_COUNT; i++) {

if (PRIMES[i] >= min_size) {

return PRIMES[i];

}

}

return PRIMES[PRIME_COUNT - 1];

}

/* 字符串哈希算法 */

/* DJB2算法 */

unsigned long hash_djb2(const char* str) {

unsigned long hash = 5381;

int c;

while ((c = *str++)) {

hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

}

return hash;

}

/* BKDR算法 */

unsigned long hash_bkdr(const char* str) {

unsigned long hash = 0;

unsigned long seed = 131; /* 31, 131, 1313, 13131, 131313 etc. */

int c;

while ((c = *str++)) {

hash = hash * seed + c;

}

return hash;

}

/* SDBM算法 */

unsigned long hash_sdbm(const char* str) {

unsigned long hash = 0;

int c;

while ((c = *str++)) {

hash = c + (hash << 6) + (hash << 16) - hash;

}

return hash;

}

/* RS算法 */

unsigned long hash_rs(const char* str) {

unsigned long hash = 0;

unsigned long a = 63689;

unsigned long b = 378551;

int c;

while ((c = *str++)) {

hash = hash * a + c;

a = a * b;

}

return hash;

}

/* 根据算法类型计算哈希值 */

static unsigned long compute_hash(hash_table_t* ht, const void* key) {

if (ht->key_type == HASH_KEY_STR) {

const char* str = (const char*)key;

switch (ht->algorithm) {

case HASH_ALGO_DJB2: return hash_djb2(str);

case HASH_ALGO_BKDR: return hash_bkdr(str);

case HASH_ALGO_SDBM: return hash_sdbm(str);

case HASH_ALGO_RS: return hash_rs(str);

default: return hash_djb2(str);

}

} else if (ht->key_type == HASH_KEY_INT) {

int int_key = *(const int*)key;

/* 使用Knuth乘法哈希 */

return (unsigned long)(int_key * 2654435761u);

} else { /* HASH_KEY_PTR */

/* 直接使用指针地址 */

return (unsigned long)key;

}

}

/* 比较键 */

static int keys_equal(hash_table_t* ht, const void* key1, const void* key2) {

if (ht->key_type == HASH_KEY_STR) {

return strcmp((const char*)key1, (const char*)key2) == 0;

} else if (ht->key_type == HASH_KEY_INT) {

return *(const int*)key1 == *(const int*)key2;

} else { /* HASH_KEY_PTR */

return key1 == key2;

}

}

/* 复制键 */

static void* copy_key(hash_table_t* ht, const void* key) {

if (ht->key_type == HASH_KEY_STR) {

return strdup((const char*)key);

} else if (ht->key_type == HASH_KEY_INT) {

int* new_key = malloc(sizeof(int));

*new_key = *(const int*)key;

return new_key;

} else { /* HASH_KEY_PTR */

return (void*)key; /* 指针不需要复制 */

}

}

/* 释放键 */

static void free_key(hash_table_t* ht, void* key) {

if (ht->key_type == HASH_KEY_STR) {

free(key);

} else if (ht->key_type == HASH_KEY_INT) {

free(key);

}

/* 指针键不需要释放 */

}

/* 计算索引 */

static size_t compute_index(hash_table_t* ht, unsigned long hash) {

return hash % ht->capacity;

}

/* 链地址法：查找条目 */

static hash_entry_t* chaining_find_entry(hash_table_t* ht, size_t index, const void* key) {

hash_entry_t* entry = &ht->entries[index];

/* 检查第一个条目 */

if (entry->status == ENTRY_OCCUPIED && keys_equal(ht, entry->key, key)) {

return entry;

}

/* 检查链表中的其他条目 */

entry = entry->next;

while (entry != NULL) {

if (keys_equal(ht, entry->key, key)) {

return entry;

}

entry = entry->next;

}

return NULL;

}

/* 链地址法：插入条目 */

static int chaining_insert_entry(hash_table_t* ht, size_t index, void* key, void* value) {

hash_entry_t* entry = &ht->entries[index];

/* 如果第一个条目为空，直接使用 */

if (entry->status != ENTRY_OCCUPIED) {

entry->key = key;

entry->value = value;

entry->status = ENTRY_OCCUPIED;

entry->next = NULL;

ht->size++;

return 1;

}

/* 检查是否已存在相同键 */

if (keys_equal(ht, entry->key, key)) {

entry->value = value;

free_key(ht, key); /* 释放复制的键 */

return 0;

}

/* 查找链表末尾 */

hash_entry_t* prev = entry;

while (prev->next != NULL) {

if (keys_equal(ht, prev->next->key, key)) {

prev->next->value = value;

free_key(ht, key);

return 0;

}

prev = prev->next;

}

/* 创建新条目并添加到链表末尾 */

hash_entry_t* new_entry = malloc(sizeof(hash_entry_t));

if (new_entry == NULL) {

return -1;

}

new_entry->key = key;

new_entry->value = value;

new_entry->status = ENTRY_OCCUPIED;

new_entry->next = NULL;

prev->next = new_entry;

ht->size++;

return 1;

}

/* 开放地址法：查找下一个索引 */

static size_t open_address_next_index(hash_table_t* ht, size_t index, int probe) {

if (ht->method == COLLISION_LINEAR) {

return (index + probe) % ht->capacity;

} else { /* COLLISION_QUADRATIC */

return (index + probe * probe) % ht->capacity;

}

}

/* 开放地址法：查找条目 */

static hash_entry_t* open_address_find_entry(hash_table_t* ht, size_t index, const void* key) {

int probe = 0;

size_t current_index = index;

while (ht->entries[current_index].status != ENTRY_EMPTY) {

if (ht->entries[current_index].status == ENTRY_OCCUPIED &&

keys_equal(ht, ht->entries[current_index].key, key)) {

return &ht->entries[current_index];

}

probe++;

current_index = open_address_next_index(ht, index, probe);

/* 防止无限循环 */

if (probe > ht->capacity) {

break;

}

}

return NULL;

}

/* 开放地址法：插入条目 */

static int open_address_insert_entry(hash_table_t* ht, size_t index, void* key, void* value) {

int probe = 0;

size_t current_index = index;

while (ht->entries[current_index].status == ENTRY_OCCUPIED) {

/* 检查是否已存在相同键 */

if (keys_equal(ht, ht->entries[current_index].key, key)) {

ht->entries[current_index].value = value;

free_key(ht, key); /* 释放复制的键 */

return 0;

}

probe++;

current_index = open_address_next_index(ht, index, probe);

/* 防止无限循环 */

if (probe > ht->capacity) {

return -1;

}

}

/* 找到空位或删除位 */

ht->entries[current_index].key = key;

ht->entries[current_index].value = value;

ht->entries[current_index].status = ENTRY_OCCUPIED;

ht->entries[current_index].next = NULL;

ht->size++;

return 1;

}

/* 初始化哈希表条目 */

static void init_entries(hash_entry_t* entries, size_t count) {

for (size_t i = 0; i < count; i++) {

entries[i].key = NULL;

entries[i].value = NULL;

entries[i].status = ENTRY_EMPTY;

entries[i].next = NULL;

}

}

/* 释放链地址法中的链表 */

static void free_chaining_list(hash_entry_t* entry) {

hash_entry_t* current = entry->next;

while (current != NULL) {

hash_entry_t* next = current->next;

free(current);

current = next;

}

entry->next = NULL;

}

/* 创建哈希表 */

hash_table_t* hash_table_create(size_t initial_size,

hash_key_type_t key_type,

hash_algo_t algo,

collision_method_t method) {

hash_table_t* ht = malloc(sizeof(hash_table_t));

if (ht == NULL) {

return NULL;

}

if (initial_size == 0) {

initial_size = PRIMES[0];

}

ht->capacity = find_nearest_prime(initial_size);

ht->entries = calloc(ht->capacity, sizeof(hash_entry_t));

if (ht->entries == NULL) {

free(ht);

return NULL;

}

init_entries(ht->entries, ht->capacity);

ht->size = 0;

ht->key_type = key_type;

ht->algorithm = algo;

ht->method = method;

ht->max_load_factor = DEFAULT_LOAD_FACTOR;

return ht;

}

/* 销毁哈希表 */

void hash_table_destroy(hash_table_t* ht) {

if (ht == NULL) {

return;

}

for (size_t i = 0; i < ht->capacity; i++) {

if (ht->entries[i].status == ENTRY_OCCUPIED) {

free_key(ht, ht->entries[i].key);

}

if (ht->method == COLLISION_CHAINING) {

free_chaining_list(&ht->entries[i]);

}

}

free(ht->entries);

free(ht);

}

/* 检查是否需要扩容 */

static int needs_resize(hash_table_t* ht) {

double load_factor = (double)ht->size / (double)ht->capacity;

return load_factor > ht->max_load_factor;

}

/* 重新哈希 */

static int resize_table(hash_table_t* ht) {

size_t new_capacity = find_nearest_prime(ht->capacity * 2);

hash_entry_t* old_entries = ht->entries;

size_t old_capacity = ht->capacity;

ht->entries = calloc(new_capacity, sizeof(hash_entry_t));

if (ht->entries == NULL) {

ht->entries = old_entries;

return -1;

}

init_entries(ht->entries, new_capacity);

ht->capacity = new_capacity;

ht->size = 0;

/* 重新插入所有条目 */

for (size_t i = 0; i < old_capacity; i++) {

if (old_entries[i].status == ENTRY_OCCUPIED) {

if (ht->method == COLLISION_CHAINING) {

/* 处理链地址法 */

hash_entry_t* entry = &old_entries[i];

while (entry != NULL && entry->status == ENTRY_OCCUPIED) {

hash_table_put(ht, entry->key, entry->value);

hash_entry_t* next = entry->next;

if (entry != &old_entries[i]) {

free(entry);

}

entry = next;

}

} else {

/* 处理开放地址法 */

hash_table_put(ht, old_entries[i].key, old_entries[i].value);

}

}

}

free(old_entries);

return 0;

}

/* 插入键值对 */

int hash_table_put(hash_table_t* ht, const void* key, void* value) {

if (ht == NULL || key == NULL) {

return -1;

}

/* 检查是否需要扩容 */

if (needs_resize(ht)) {

if (resize_table(ht) != 0) {

return -1;

}

}

unsigned long hash = compute_hash(ht, key);

size_t index = compute_index(ht, hash);

void* key_copy = copy_key(ht, key);

if (key_copy == NULL) {

return -1;

}

int result;

if (ht->method == COLLISION_CHAINING) {

result = chaining_insert_entry(ht, index, key_copy, value);

} else {

result = open_address_insert_entry(ht, index, key_copy, value);

}

if (result < 0) {

free_key(ht, key_copy);

}

return result;

}

/* 获取值 */

void* hash_table_get(hash_table_t* ht, const void* key) {

if (ht == NULL || key == NULL) {

return NULL;

}

unsigned long hash = compute_hash(ht, key);

size_t index = compute_index(ht, hash);

hash_entry_t* entry;

if (ht->method == COLLISION_CHAINING) {

entry = chaining_find_entry(ht, index, key);

} else {

entry = open_address_find_entry(ht, index, key);

}

return (entry != NULL) ? entry->value : NULL;

}

/* 删除键值对 */

int hash_table_remove(hash_table_t* ht, const void* key) {

if (ht == NULL || key == NULL) {

return 0;

}

unsigned long hash = compute_hash(ht, key);

size_t index = compute_index(ht, hash);

if (ht->method == COLLISION_CHAINING) {

hash_entry_t* entry = &ht->entries[index];

hash_entry_t* prev = NULL;

/* 查找要删除的条目 */

while (entry != NULL) {

if (entry->status == ENTRY_OCCUPIED && keys_equal(ht, entry->key, key)) {

free_key(ht, entry->key);

if (prev == NULL) {

/* 删除第一个条目 */

if (entry->next == NULL) {

entry->status = ENTRY_EMPTY;

} else {

/* 用下一个条目替换当前条目 */

hash_entry_t* next = entry->next;

entry->key = next->key;

entry->value = next->value;

entry->next = next->next;

free(next);

}

} else {

/* 删除链表中的条目 */

prev->next = entry->next;

free(entry);

}

ht->size--;

return 1;

}

prev = entry;

entry = entry->next;

}

} else {

/* 开放地址法：标记为删除 */

hash_entry_t* entry = open_address_find_entry(ht, index, key);

if (entry != NULL) {

free_key(ht, entry->key);

entry->status = ENTRY_DELETED;

entry->key = NULL;

entry->value = NULL;

ht->size--;

return 1;

}

}

return 0;

}

/* 获取元素数量 */

size_t hash_table_size(hash_table_t* ht) {

return (ht != NULL) ? ht->size : 0;

}

/* 判断是否为空 */

int hash_table_is_empty(hash_table_t* ht) {

return (ht == NULL) || (ht->size == 0);

}

/* 清空哈希表 */

void hash_table_clear(hash_table_t* ht) {

if (ht == NULL) {

return;

}

for (size_t i = 0; i < ht->capacity; i++) {

if (ht->entries[i].status == ENTRY_OCCUPIED) {

free_key(ht, ht->entries[i].key);

ht->entries[i].key = NULL;

ht->entries[i].value = NULL;

ht->entries[i].status = ENTRY_EMPTY;

}

if (ht->method == COLLISION_CHAINING) {

free_chaining_list(&ht->entries[i]);

}

}

ht->size = 0;

}

/* 遍历哈希表 */

int hash_table_foreach(hash_table_t* ht,

int (*callback)(const void* key, void* value, void* user_data),

void* user_data) {

if (ht == NULL || callback == NULL) {

return -1;

}

for (size_t i = 0; i < ht->capacity; i++) {

if (ht->entries[i].status == ENTRY_OCCUPIED) {

if (ht->method == COLLISION_CHAINING) {

/* 遍历链表 */

hash_entry_t* entry = &ht->entries[i];

while (entry != NULL && entry->status == ENTRY_OCCUPIED) {

if (callback(entry->key, entry->value, user_data) != 0) {

return 0;

}

entry = entry->next;

}

} else {

/* 开放地址法 */

if (callback(ht->entries[i].key, ht->entries[i].value, user_data) != 0) {

return 0;

}

}

}

}

return 0;

}

/* 获取负载因子 */

double hash_table_load_factor(hash_table_t* ht) {

return (ht != NULL) ? (double)ht->size / (double)ht->capacity : 0.0;

}

/* 重新哈希 */

int hash_table_rehash(hash_table_t* ht, size_t new_size) {

if (ht == NULL) {

return -1;

}

size_t new_capacity = find_nearest_prime(new_size);

if (new_capacity <= ht->capacity) {

return -1; /* 新容量必须大于当前容量 */

}

return resize_table(ht);

}

main.c或test_main.c

验证哈希库功能的正确性和稳定性

特点：

1. 全面性测试：覆盖所有哈希算法（DJB2、BKDR、SDBM、RS）和冲突解决方法（链地址法、线性探测、二次探测）
2. 边界测试：测试各种边界情况，如空表、满表、删除操作等
3. 性能测试：包含大数据集测试（1000个条目）
4. 错误处理：验证错误情况的正确处理
5. 自动化验证：自动检查测试结果是否正确
输出特点：详细的测试过程和验证结果，主要用于开发调试

#include "hashlib.h"

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <assert.h>

/* 测试回调函数 */

int print_callback(const void* key, void* value, void* user_data) {

int* count = (int*)user_data;

(*count)++;

printf(" Entry %d: ", *count);

/* 假设键类型为字符串进行测试 */

printf("Key='%s', Value=%p\n", (const char*)key, value);

return 0;

}

/* 测试整型键哈希表 */

void test_int_hash_table() {

printf("=== Testing Integer Key Hash Table ===\n");

/* 测试不同算法和冲突解决方法 */

hash_algo_t algorithms[] = {HASH_ALGO_DJB2, HASH_ALGO_BKDR, HASH_ALGO_SDBM, HASH_ALGO_RS};

collision_method_t methods[] = {COLLISION_CHAINING, COLLISION_LINEAR, COLLISION_QUADRATIC};

for (int algo_idx = 0; algo_idx < 4; algo_idx++) {

for (int method_idx = 0; method_idx < 3; method_idx++) {

printf("\n--- Algorithm %d, Method %d ---\n", algo_idx, method_idx);

hash_table_t* ht = hash_table_create(10, HASH_KEY_INT,

algorithms[algo_idx],

methods[method_idx]);

assert(ht != NULL);

/* 插入测试数据 */

int keys[] = {1, 2, 3, 100, 200, 300, 1000, 2000, 3000};

int values[] = {10, 20, 30, 1000, 2000, 3000, 10000, 20000, 30000};

for (int i = 0; i < 9; i++) {

int result = hash_table_put(ht, &keys[i], &values[i]);

assert(result >= 0);

printf("Inserted: key=%d, value=%d\n", keys[i], values[i]);

}

/* 验证插入数量 */

assert(hash_table_size(ht) == 9);

printf("Size: %lu\n", (unsigned long)hash_table_size(ht));

printf("Load factor: %.3f\n", hash_table_load_factor(ht));

/* 测试查找 */

for (int i = 0; i < 9; i++) {

int* found_value = (int*)hash_table_get(ht, &keys[i]);

assert(found_value != NULL);

assert(*found_value == values[i]);

printf("Found: key=%d, value=%d\n", keys[i], *found_value);

}

/* 测试不存在的键 */

int not_found_key = 9999;

void* not_found = hash_table_get(ht, &not_found_key);

assert(not_found == NULL);

printf("Not found key %d as expected\n", not_found_key);

/* 测试删除 */

int remove_key = 100;

int remove_result = hash_table_remove(ht, &remove_key);

assert(remove_result == 1);

printf("Removed key %d\n", remove_key);

assert(hash_table_size(ht) == 8);

/* 测试遍历 */

printf("Hash table contents:\n");

int count = 0;

hash_table_foreach(ht, print_callback, &count);

hash_table_destroy(ht);

printf("Test passed for algorithm %d, method %d\n", algo_idx, method_idx);

}

}

printf("=== Integer Key Hash Table Tests Completed ===\n\n");

}

/* 测试字符串键哈希表 */

void test_string_hash_table() {

printf("=== Testing String Key Hash Table ===\n");

/* 重点测试BKDR和DJB2算法 */

hash_algo_t algorithms[] = {HASH_ALGO_DJB2, HASH_ALGO_BKDR};

collision_method_t methods[] = {COLLISION_CHAINING, COLLISION_LINEAR};

for (int algo_idx = 0; algo_idx < 2; algo_idx++) {

for (int method_idx = 0; method_idx < 2; method_idx++) {

printf("\n--- Algorithm %s, Method %d ---\n",

(algorithms[algo_idx] == HASH_ALGO_DJB2) ? "DJB2" : "BKDR",

method_idx);

hash_table_t* ht = hash_table_create(10, HASH_KEY_STR,

algorithms[algo_idx],

methods[method_idx]);

assert(ht != NULL);

/* 插入测试数据 */

const char* keys[] = {

"apple", "banana", "cherry", "date", "elderberry",

"fig", "grape", "honeydew", "kiwi", "lemon"

};

int values[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

for (int i = 0; i < 10; i++) {

int result = hash_table_put(ht, keys[i], &values[i]);

assert(result >= 0);

printf("Inserted: key='%s', value=%d\n", keys[i], values[i]);

}

/* 验证插入数量 */

assert(hash_table_size(ht) == 10);

printf("Size: %lu\n", (unsigned long)hash_table_size(ht));

printf("Load factor: %.3f\n", hash_table_load_factor(ht));

/* 测试哈希算法函数 */

if (algorithms[algo_idx] == HASH_ALGO_DJB2) {

unsigned long hash1 = hash_djb2("test");

unsigned long hash2 = hash_djb2("test");

assert(hash1 == hash2);

printf("DJB2 hash consistency test passed\n");

} else {

unsigned long hash1 = hash_bkdr("test");

unsigned long hash2 = hash_bkdr("test");

assert(hash1 == hash2);

printf("BKDR hash consistency test passed\n");

}

/* 测试查找 */

for (int i = 0; i < 10; i++) {

int* found_value = (int*)hash_table_get(ht, keys[i]);

assert(found_value != NULL);

assert(*found_value == values[i]);

printf("Found: key='%s', value=%d\n", keys[i], *found_value);

}

/* 测试不存在的键 */

const char* not_found_key = "mango";

void* not_found = hash_table_get(ht, not_found_key);

assert(not_found == NULL);

printf("Not found key '%s' as expected\n", not_found_key);

/* 测试删除 */

const char* remove_key = "banana";

int remove_result = hash_table_remove(ht, remove_key);

assert(remove_result == 1);

printf("Removed key '%s'\n", remove_key);

assert(hash_table_size(ht) == 9);

/* 测试更新 */

int new_value = 99;

int update_result = hash_table_put(ht, "apple", &new_value);

assert(update_result == 0); /* 0表示更新，1表示插入 */

int* updated_value = (int*)hash_table_get(ht, "apple");

assert(updated_value != NULL);

assert(*updated_value == 99);

printf("Updated 'apple' to value %d\n", *updated_value);

hash_table_destroy(ht);

printf("Test passed for algorithm %s, method %d\n",

(algorithms[algo_idx] == HASH_ALGO_DJB2) ? "DJB2" : "BKDR",

method_idx);

}

}

printf("=== String Key Hash Table Tests Completed ===\n\n");

}

/* 测试结构体键哈希表 */

void test_struct_hash_table() {

printf("=== Testing Struct Key Hash Table ===\n");

/* 定义测试结构体 */

typedef struct {

int id;

char name[20];

} test_struct_t;

/* 使用指针作为键 */

hash_table_t* ht = hash_table_create(10, HASH_KEY_PTR,

HASH_ALGO_DJB2,

COLLISION_CHAINING);

assert(ht != NULL);

/* 创建测试结构体 */

test_struct_t structs[5];

int values[] = {100, 200, 300, 400, 500};

for (int i = 0; i < 5; i++) {

structs[i].id = i + 1;

snprintf(structs[i].name, sizeof(structs[i].name), "struct_%d", i + 1);

int result = hash_table_put(ht, &structs[i], &values[i]);

assert(result >= 0);

printf("Inserted: struct{id=%d, name='%s'}, value=%d\n",

structs[i].id, structs[i].name, values[i]);

}

/* 验证插入数量 */

assert(hash_table_size(ht) == 5);

printf("Size: %lu\n", (unsigned long)hash_table_size(ht));

/* 测试查找 */

for (int i = 0; i < 5; i++) {

int* found_value = (int*)hash_table_get(ht, &structs[i]);

assert(found_value != NULL);

assert(*found_value == values[i]);

printf("Found: struct{id=%d, name='%s'}, value=%d\n",

structs[i].id, structs[i].name, *found_value);

}

/* 测试清空 */

hash_table_clear(ht);

assert(hash_table_size(ht) == 0);

assert(hash_table_is_empty(ht));

printf("Hash table cleared successfully\n");

hash_table_destroy(ht);

printf("=== Struct Key Hash Table Tests Completed ===\n\n");

}

/* 测试性能和大数据量 */

void test_performance() {

printf("=== Testing Performance with Large Dataset ===\n");

/* 测试链地址法 */

hash_table_t* ht_chaining = hash_table_create(100, HASH_KEY_STR,

HASH_ALGO_BKDR,

COLLISION_CHAINING);

assert(ht_chaining != NULL);

/* 插入1000个字符串键值对 */

int inserted_count = 0;

for (int i = 0; i < 1000; i++) {

char key[20];

snprintf(key, sizeof(key), "key_%d", i);

int* value = malloc(sizeof(int));

*value = i * 10;

if (hash_table_put(ht_chaining, key, value) >= 0) {

inserted_count++;

}

}

printf("Inserted %d entries with chaining method\n", inserted_count);

printf("Final size: %lu\n", (unsigned long)hash_table_size(ht_chaining));

printf("Final load factor: %.3f\n", hash_table_load_factor(ht_chaining));

/* 验证所有插入的数据 */

int verified_count = 0;

for (int i = 0; i < 1000; i++) {

char key[20];

snprintf(key, sizeof(key), "key_%d", i);

int* found_value = (int*)hash_table_get(ht_chaining, key);

if (found_value != NULL && *found_value == i * 10) {

verified_count++;

}

}

printf("Verified %d entries\n", verified_count);

/* 清理内存 */

for (int i = 0; i < 1000; i++) {

char key[20];

snprintf(key, sizeof(key), "key_%d", i);

int* value = (int*)hash_table_get(ht_chaining, key);

if (value != NULL) {

free(value);

}

}

hash_table_destroy(ht_chaining);

/* 测试开放地址法 */

hash_table_t* ht_open = hash_table_create(100, HASH_KEY_INT,

HASH_ALGO_DJB2,

COLLISION_LINEAR);

assert(ht_open != NULL);

/* 插入500个整型键值对 */

inserted_count = 0;

for (int i = 0; i < 500; i++) {

int key = i * 2; /* 使用偶数键 */

int* value = malloc(sizeof(int));

*value = i * 5;

if (hash_table_put(ht_open, &key, value) >= 0) {

inserted_count++;

}

}

printf("Inserted %d entries with open addressing method\n", inserted_count);

printf("Final size: %lu\n", (unsigned long)hash_table_size(ht_open));

printf("Final load factor: %.3f\n", hash_table_load_factor(ht_open));

/* 清理内存 */

for (int i = 0; i < 500; i++) {

int key = i * 2;

int* value = (int*)hash_table_get(ht_open, &key);

if (value != NULL) {

free(value);

}

}

hash_table_destroy(ht_open);

printf("=== Performance Tests Completed ===\n\n");

}

/* 测试哈希算法函数 */

void test_hash_functions() {

printf("=== Testing Hash Functions ===\n");

const char* test_strings[] = {

"hello", "world", "hash", "table", "test",

"algorithm", "djb2", "bkdr", "sdbm", "rs"

};

printf("Testing hash functions consistency:\n");

for (int i = 0; i < 10; i++) {

unsigned long djb2_1 = hash_djb2(test_strings[i]);

unsigned long djb2_2 = hash_djb2(test_strings[i]);

unsigned long bkdr_1 = hash_bkdr(test_strings[i]);

unsigned long bkdr_2 = hash_bkdr(test_strings[i]);

unsigned long sdbm_1 = hash_sdbm(test_strings[i]);

unsigned long sdbm_2 = hash_sdbm(test_strings[i]);

unsigned long rs_1 = hash_rs(test_strings[i]);

unsigned long rs_2 = hash_rs(test_strings[i]);

assert(djb2_1 == djb2_2);

assert(bkdr_1 == bkdr_2);

assert(sdbm_1 == sdbm_2);

assert(rs_1 == rs_2);

printf(" '%s': DJB2=%lu, BKDR=%lu, SDBM=%lu, RS=%lu\n",

test_strings[i], djb2_1, bkdr_1, sdbm_1, rs_1);

}

printf("All hash functions show consistent results\n");

printf("=== Hash Functions Tests Completed ===\n\n");

}

int main() {

printf("Starting Hash Library Tests...\n\n");

/* 运行所有测试 */

test_hash_functions();

test_int_hash_table();

test_string_hash_table();

test_struct_hash_table();

test_performance();

printf("All tests completed successfully!\n");

printf("Hash library is working correctly.\n");

return 0;

}

example.c

主要目的：展示哈希库的实际使用方法和应用场景

特点：

1. 实用示例：提供6个实际应用场景
2. 展示如何正确使用API函数
3. 场景化：每个示例针对特定使用场景
- 字符串键与价格管理
- 整型键与学生成绩管理
- 结构体键与几何点管理
- 遍历功能与人口统计
- 重新哈希与性能优化
- 哈希算法比较
4. 用户友好：输出结果易于理解，展示实际应用价值

#include "hashlib.h"

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

/* 示例1：使用字符串键和BKDR算法 */

void example_string_keys() {

printf("=== Example 1: String Keys with BKDR Algorithm ===\n");

/* 创建哈希表 */

hash_table_t* ht = hash_table_create(0, HASH_KEY_STR, HASH_ALGO_BKDR, COLLISION_CHAINING);

/* 插入一些水果和它们的价格 */

int apple_price = 5;

int banana_price = 3;

int cherry_price = 8;

hash_table_put(ht, "apple", &apple_price);

hash_table_put(ht, "banana", &banana_price);

hash_table_put(ht, "cherry", &cherry_price);

printf("Inserted 3 fruits with prices\n");

printf("Current size: %lu\n", (unsigned long)hash_table_size(ht));

printf("Load factor: %.3f\n", hash_table_load_factor(ht));

/* 查找价格 */

int* price = (int*)hash_table_get(ht, "apple");

if (price) {

printf("Price of apple: %d\n", *price);

}

price = (int*)hash_table_get(ht, "banana");

if (price) {

printf("Price of banana: %d\n", *price);

}

/* 尝试查找不存在的键 */

price = (int*)hash_table_get(ht, "mango");

if (!price) {

printf("Mango not found (as expected)\n");

}

hash_table_destroy(ht);

printf("\n");

}

/* 示例2：使用整型键和线性探测 */

void example_int_keys() {

printf("=== Example 2: Integer Keys with Linear Probing ===\n");

/* 创建哈希表 */

hash_table_t* ht = hash_table_create(10, HASH_KEY_INT, HASH_ALGO_DJB2, COLLISION_LINEAR);

/* 插入学生ID和成绩 */

int student_grades[] = {85, 92, 78, 96, 88};

int student_ids[] = {1001, 1002, 1003, 1004, 1005};

for (int i = 0; i < 5; i++) {

hash_table_put(ht, &student_ids[i], &student_grades[i]);

}

printf("Inserted 5 student records\n");

/* 查找特定学生的成绩 */

int search_id = 1003;

int* grade = (int*)hash_table_get(ht, &search_id);

if (grade) {

printf("Student %d grade: %d\n", search_id, *grade);

}

/* 更新成绩 */

int new_grade = 82;

hash_table_put(ht, &search_id, &new_grade);

grade = (int*)hash_table_get(ht, &search_id);

if (grade) {

printf("Updated student %d grade: %d\n", search_id, *grade);

}

hash_table_destroy(ht);

printf("\n");

}

/* 示例3：使用结构体作为键 */

void example_struct_keys() {

printf("=== Example 3: Struct Keys ===\n");

/* 定义坐标结构体 */

typedef struct {

int x;

int y;

} Point;

/* 创建哈希表 */

hash_table_t* ht = hash_table_create(0, HASH_KEY_PTR, HASH_ALGO_SDBM, COLLISION_CHAINING);

/* 创建一些点 */

Point p1 = {1, 2};

Point p2 = {3, 4};

Point p3 = {5, 6};

char* descriptions[] = {

"First point", "Second point", "Third point"

};

hash_table_put(ht, &p1, descriptions[0]);

hash_table_put(ht, &p2, descriptions[1]);

hash_table_put(ht, &p3, descriptions[2]);

printf("Inserted 3 points with descriptions\n");

/* 查找点的描述 */

char* desc = (char*)hash_table_get(ht, &p2);

if (desc) {

printf("Point (%d, %d): %s\n", p2.x, p2.y, desc);

}

hash_table_destroy(ht);

printf("\n");

}

/* 示例4：遍历哈希表 */

void example_traversal() {

printf("=== Example 4: Hash Table Traversal ===\n");

/* 创建哈希表 */

hash_table_t* ht = hash_table_create(0, HASH_KEY_STR, HASH_ALGO_BKDR, COLLISION_CHAINING);

/* 插入一些数据 */

char* countries[] = {"China", "USA", "Japan", "Germany", "France"};

int populations[] = {1441, 331, 126, 83, 68}; // 百万

for (int i = 0; i < 5; i++) {

hash_table_put(ht, countries[i], &populations[i]);

}

printf("Country populations (in millions):\n");

/* 定义遍历回调函数 */

int print_population(const void* key, void* value, void* user_data) {

int* total = (int*)user_data;

(*total) += *(int*)value;

printf(" %s: %d million\n", (const char*)key, *(int*)value);

return 0; // 继续遍历

}

int total_population = 0;

hash_table_foreach(ht, print_population, &total_population);

printf("Total population: %d million\n", total_population);

hash_table_destroy(ht);

printf("\n");

}

/* 示例5：性能测试和重新哈希 */

void example_rehashing() {

printf("=== Example 5: Rehashing and Performance ===\n");

/* 创建小容量的哈希表 */

hash_table_t* ht = hash_table_create(5, HASH_KEY_STR, HASH_ALGO_DJB2, COLLISION_CHAINING);

printf("Initial load factor: %.3f\n", hash_table_load_factor(ht));

/* 插入多个条目触发重新哈希 */

for (int i = 0; i < 20; i++) {

char key[20];

snprintf(key, sizeof(key), "item_%d", i);

int* value = malloc(sizeof(int));

*value = i * 10;

hash_table_put(ht, key, value);

}

printf("After inserting 20 items:\n");

printf("Size: %lu\n", (unsigned long)hash_table_size(ht));

printf("Load factor: %.3f\n", hash_table_load_factor(ht));

/* 手动重新哈希到更大容量 */

printf("\nManual rehashing to capacity 50...\n");

hash_table_rehash(ht, 50);

printf("After rehashing:\n");

printf("Load factor: %.3f\n", hash_table_load_factor(ht));

/* 清理内存 */

for (int i = 0; i < 20; i++) {

char key[20];

snprintf(key, sizeof(key), "item_%d", i);

int* value = (int*)hash_table_get(ht, key);

if (value) {

free(value);

}

}

hash_table_destroy(ht);

printf("\n");

}

/* 示例6：比较不同哈希算法 */

void example_hash_comparison() {

printf("=== Example 6: Hash Algorithm Comparison ===\n");

const char* test_strings[] = {

"hello", "world", "programming", "algorithm", "data"

};

printf("Hash values for test strings:\n");

printf("String\t\tDJB2\t\tBKDR\t\tSDBM\t\tRS\n");

printf("------\t\t----\t\t----\t\t----\t\t--\n");

for (int i = 0; i < 5; i++) {

unsigned long djb2 = hash_djb2(test_strings[i]);

unsigned long bkdr = hash_bkdr(test_strings[i]);

unsigned long sdbm = hash_sdbm(test_strings[i]);

unsigned long rs = hash_rs(test_strings[i]);

printf("%s\t%lu\t%lu\t%lu\t%lu\n",

test_strings[i], djb2, bkdr, sdbm, rs);

}

printf("\n");

}

int main() {

printf("Hash Library Examples\n");

printf("====================\n\n");

/* 运行所有示例 */

example_string_keys();

example_int_keys();

example_struct_keys();

example_traversal();

example_rehashing();

example_hash_comparison();

printf("All examples completed successfully!\n");

return 0;

}

七、面试常见问题

1. 哈希表的基本原理是什么？

回答要点：
- 哈希表是一个用于快速查找、插入和删除数据的容器结构。
- 核心是通过哈希函数将键值映射到数组的索引位置。处理冲突有两种常见方法：链地址法（Separate Chaining）和开放寻址法（Open Addressing）。

2. 哈希表如何处理冲突？

回答要点：
- 链地址法（拉链法）：每个桶维护一个链表（或其他数据结构）来存储冲突的元素。
- 开放寻址法：当冲突发生时，探查下一个空位置来插入元素，常见策略有线性探查、二次探查、双重哈希等。

3. 哈希函数的作用及常见的哈希算法有哪些？

回答要点：
- 哈希函数将数据的键映射到哈希表的索引位置。
- 常见哈希算法：DJB2（针对字符串），MurmurHash，SHA系列（适用于更复杂的数据集），以及整型数据常用的Knuth乘法哈希。
- 哈希函数需要满足：快速计算、均匀分布、避免碰撞。

4. 哈希表的负载因子是什么？如何影响哈希表性能？

回答要点：
- 元素个数指的是哈希表中实际存储的键值对的数量，而不是哈希表的桶的数量。
  
  具体来说：元素个数（即 nentries）是哈希表中存储的有效数据项的数量。每个键值对都会占用一个桶中的位置，可能会有冲突，但每个有效的键值对都算作一个元素。在哈希表的扩容或缩容过程中，通常会根据当前的元素个数来决定是否需要进行重新哈希（rehash），即扩展哈希表的大小。举个例子：假设你有一个哈希表大小为 10 的桶数组（nbuckets = 10），当你插入了 7 个元素时，哈希表的元素个数就是 7，即：哈希表中的 元素个数：7 哈希表的 桶数组大小：10
- 负载因子 = 元素个数 / 哈希表（桶数组）大小。较高的负载因子意味着哈希表中的元素较多，可能会导致性能下降。
- 当负载因子达到一定阈值时，通常会进行扩容（rehash），以保持性能。

5. 哈希表的扩容是如何实现的？

回答要点：
- 扩容时，哈希表大小通常会翻倍（或选择下一个质数）。扩容后，需要重新计算每个元素的哈希值并重新分配到新表中。

6. 哈希表在嵌入式开发中如何优化内存和性能？

回答要点：
- 内存优化：在嵌入式开发中，通常需要限制内存使用。可以选择较小的哈希表大小和合适的负载因子（通常在0.6到0.75之间），并使用固定大小的桶数组来避免内存碎片。
- 目标（在嵌入式中的优先级）
- 最小化运行时堆/碎片，尽量使用静态/一次性分配。
- 保证查找性能可预测（避免最坏情况长时间阻塞）。
- 核心策略概览（优先级从高到低）
- 优先静态分配（固定大小）：bucket 数组 + entry 池，避免运行时 malloc/free。
- 选择合适的冲突解决方式：嵌入式常用 开放寻址法（线性/二次/双哈希） 或 链式 + 预分配节点池（intrusive 链表）。开放寻址通常内存更紧凑、cache 友好；链式对删除更友好、但需指针开销。
- 降低每条记录的内存开销：使用紧凑结构（按需字段、用索引替代指针、短整型等）。
- 避免频繁扩容 / 禁用自动 rehash：在嵌入式常设定固定容量或只允许手动 rehash。
- 合理选择负载因子：开放寻址建议 ≤ 0.6；链式可稍高（0.75~1.0）。
- 使用字符串驻留或索引池：若键为字符串，避免 strdup 每次分配，使用字符串池或只存索引/指针到常量区。
- 使用内存池 / slab 分配器：如果必须动态分配，使用固定大小对象池避免碎片。
- 对齐与 packing：用 packed 或显式字段顺序减少 padding；但留意性能影响。
- 避免递归/复杂对象在哈希表内：存储简单指针或数值，复杂对象放外部管理。
- 尽量计算内存占用公式并在编译期/启动时验证。
- 内存使用可估算、可控（便于通过linker map 评估）。
- 允许必要时牺牲一点灵活性（例如不自动扩容）换取内存确定性。
- 性能优化：使用高效的哈希算法（如DJB2），并考虑冲突处理方法。在某些情况下，使用开放寻址法可能更节省内存。
- 避免过度扩容：使用合适的扩容策略，避免频繁的re-hash操作。

7. 哈希表的空间复杂度和时间复杂度是多少？

回答要点：
- 空间复杂度：O(n)，n是元素个数。每个元素占用一定的内存空间，哈希表的桶数组也占用内存。
- 时间复杂度：
  - 查找、插入、删除：O(1)（平均情况），最坏情况下可能达到O(n)（当所有元素都映射到同一个桶时）。
  - 扩容操作：O(n)（重哈希时需要重新计算所有元素的位置）。