哈希表（C语言）

dsyyyyy1101

497人浏览 · 2025-11-11 20:28:03

dsyyyyy1101 · 2025-11-11 20:28:03 发布

哈希表系统讲解

为什么引入哈希表？

传统数据结构的局限性

· 数组：通过索引直接访问，时间复杂度O(1)，但索引必须是整数且范围有限
· 链表：可以动态增长，但查找需要O(n)时间
哈希表的优势

哈希表通过哈希函数将任意类型的数据映射到固定范围的索引，实现近似O(1)时间复杂度的插入、删除和查找操作。

哈希表的好处

高效操作：平均情况下插入、删除、查找都是O(1)
灵活性：可以处理各种数据类型的键
空间效率：相比其他数据结构，在合理负载因子下空间利用率较高

哈希表的定义

哈希表是一种通过哈希函数将键(key)映射到表中位置来访问记录的数据结构，支持快速插入、删除和查找操作。

哈希函数是将任意大小的数据映射到固定大小值的函数。

基本实现逻辑

核心组件

哈希函数：计算键的哈希值
数组：存储数据的容器
冲突解决机制：处理哈希碰撞

基本操作流程

插入/查找键值对(key, value):
1. 计算哈希值: index = hash(key)
2. 定位到数组位置: array[index]
3. 处理冲突(如果有)
4. 执行操作(插入/查找/删除)

简单哈希表的C语言完整实现

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

#define TABLE_SIZE 100
#define DELETED_NODE (Node*)(0xFFFFFFFFFFFFFFFFUL)

// 哈希表节点
typedef struct Node {
    char* key;
    int value;
    struct Node* next;  // 用于链地址法
} Node;

// 哈希表
typedef struct {
    Node** table;
    int size;
    int count;
} HashTable;

基础哈希函数

// 字符串哈希函数 - DJB2算法
unsigned long hash_function(const char* key) {
    unsigned long hash = 5381;
    int c;
    
    while ((c = *key++)) {
        hash = ((hash << 5) + hash) + c;  // hash * 33 + c
    }
    
    return hash;
}

// 整数哈希函数
unsigned long hash_int(int key) {
    key = ((key >> 16) ^ key) * 0x45d9f3b;
    key = ((key >> 16) ^ key) * 0x45d9f3b;
    key = (key >> 16) ^ key;
    return key;
}

哈希表初始化

HashTable* create_hash_table(int size) {
    HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
    ht->size = size;
    ht->count = 0;
    ht->table = (Node**)calloc(size, sizeof(Node*));
    return ht;
}

冲突解决方法及优化

1. 开放地址法 (Open Addressing)

(1) 线性探测法 (Linear Probing)

// 线性探测插入
void linear_probing_insert(HashTable* ht, const char* key, int value) {
    if (ht->count >= ht->size) {
        printf("Hash table is full!\n");
        return;
    }
    
    unsigned long index = hash_function(key) % ht->size;
    int original_index = index;
    int i = 0;
    
    // 寻找空槽或已删除的槽
    while (ht->table[index] != NULL && ht->table[index] != DELETED_NODE) {
        if (strcmp(ht->table[index]->key, key) == 0) {
            // 键已存在，更新值
            ht->table[index]->value = value;
            return;
        }
        index = (original_index + ++i) % ht->size;
        
        if (i == ht->size) {
            printf("Cannot insert - table full\n");
            return;
        }
    }
    
    // 插入新节点
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->key = strdup(key);
    new_node->value = value;
    new_node->next = NULL;
    
    ht->table[index] = new_node;
    ht->count++;
}

// 线性探测查找
Node* linear_probing_search(HashTable* ht, const char* key) {
    unsigned long index = hash_function(key) % ht->size;
    int original_index = index;
    int i = 0;
    
    while (ht->table[index] != NULL) {
        if (ht->table[index] != DELETED_NODE && 
            strcmp(ht->table[index]->key, key) == 0) {
            return ht->table[index];
        }
        index = (original_index + ++i) % ht->size;
        
        if (i == ht->size || index == original_index) {
            break;
        }
    }
    
    return NULL;  // 未找到
}

优化技巧：

· 使用二次探测减少聚集
· 实现懒删除标记
· 动态调整表大小

(2) 二次探测法 (Quadratic Probing)

// 二次探测插入
void quadratic_probing_insert(HashTable* ht, const char* key, int value) {
    if (ht->count >= ht->size) {
        printf("Hash table is full!\n");
        return;
    }
    
    unsigned long index = hash_function(key) % ht->size;
    int original_index = index;
    int i = 0;
    
    while (ht->table[index] != NULL && ht->table[index] != DELETED_NODE) {
        if (strcmp(ht->table[index]->key, key) == 0) {
            ht->table[index]->value = value;
            return;
        }
        i++;
        index = (original_index + i * i) % ht->size;  // 二次探测公式
        
        if (i == ht->size) {
            printf("Cannot insert - table full\n");
            return;
        }
    }
    
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->key = strdup(key);
    new_node->value = value;
    new_node->next = NULL;
    
    ht->table[index] = new_node;
    ht->count++;
}

优势：减少线性探测的聚集问题

(3) 双重哈希法 (Double Hashing)

// 第二个哈希函数
unsigned long hash_function2(const char* key) {
    unsigned long hash = 0;
    int c;
    
    while ((c = *key++)) {
        hash = c + (hash << 6) + (hash << 16) - hash;
    }
    
    return hash;
}

// 双重哈希插入
void double_hashing_insert(HashTable* ht, const char* key, int value) {
    if (ht->count >= ht->size) {
        printf("Hash table is full!\n");
        return;
    }
    
    unsigned long h1 = hash_function(key) % ht->size;
    unsigned long h2 = hash_function2(key) % ht->size;
    unsigned long index = h1;
    int i = 0;
    
    while (ht->table[index] != NULL && ht->table[index] != DELETED_NODE) {
        if (strcmp(ht->table[index]->key, key) == 0) {
            ht->table[index]->value = value;
            return;
        }
        i++;
        index = (h1 + i * h2) % ht->size;  // 双重哈希公式
        
        if (i == ht->size) {
            printf("Cannot insert - table full\n");
            return;
        }
    }
    
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->key = strdup(key);
    new_node->value = value;
    new_node->next = NULL;
    
    ht->table[index] = new_node;
    ht->count++;
}

优势：提供更好的分布，减少聚集

2. 链地址法 (Separate Chaining)

// 链地址法插入
void chaining_insert(HashTable* ht, const char* key, int value) {
    unsigned long index = hash_function(key) % ht->size;
    
    // 检查键是否已存在
    Node* current = ht->table[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            current->value = value;  // 更新值
            return;
        }
        current = current->next;
    }
    
    // 创建新节点并插入到链表头部
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->key = strdup(key);
    new_node->value = value;
    new_node->next = ht->table[index];
    
    ht->table[index] = new_node;
    ht->count++;
}

// 链地址法查找
Node* chaining_search(HashTable* ht, const char* key) {
    unsigned long index = hash_function(key) % ht->size;
    Node* current = ht->table[index];
    
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current;
        }
        current = current->next;
    }
    
    return NULL;
}

总结对比

线性探测
优点：实现简单，缓存友好
缺点：容易产生聚集
适用场景：小规模数据，内存紧凑
二次探测
优点：减少聚集
缺点：可能无法找到空位
适用场景：中等规模数据
双重哈希
优点：分布均匀
缺点：计算成本高
适用场景：大规模数据，性能要求高
链地址法
优点：简单可靠，无聚集
缺点：指针开销，缓存不友好
适用场景：通用场景，动态数据

选择建议：

小数据集：线性探测或二次探测
大数据集：链地址法或双重哈希
内存敏感：开放地址法
性能优先：链地址法

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能