哈希表的C语言简单实现

哈希表

1.为什么需要哈希表？

从一个实际问题开始，比如在10万条学生记录中，如何通过学号快速找到某个学生的信息？

• 如果用数组，需要遍历，O(n)时间复杂度，太慢
• 如果用链表，同样需要遍历
• 如果学号直接作为数组下标呢？但如果学号是字符串（如'S20240001'）或者范围很大（如0-10亿），直接作为下标会浪费巨大内存

这时，我们需要一种结构，既能像数组一样通过'下标'快速访问，又能灵活处理各种类型的键并节省空间。这就是哈希表

2. 哈希表的核心思想

• 核心概念： 将任意长度的键（Key）通过一个哈希函数 映射到一个固定范围的数组下标。
• 工作流程：
  1. 存储（Put）：键(Key) -> 哈希函数 -> 数组索引(Index) -> 在索引处存储值(Value)
  2. 查找（Get）：键(Key) -> 哈希函数 -> 数组索引(Index) -> 从索引处读取值(Value)
• 哈希表的要素：

要素	作用（解释）
键（key）	节点编号
值（value)	节点信息
索引（index）	数组的下标，用以快速定位和检索数据
哈希桶	保存索引的数组（链表），数组成员为每一个索引值相同的多个元素
哈希函数	将一个较大的输入空间映射到一个较小的输出空间，即将节点编号映射到索引上，采用求余法

3. 哈希冲突

• 什么是哈希冲突？

两个不同的键，经过哈希函数计算后，得到了相同的数组索引，这就是哈希冲突

• 解决方案：
  1. 链地址法：
     • 思想：数组的每一个元素不是一个值，而是一个链表（或其他结构）的头指针。所有映射到同一索引的键值对都放在这个链表里
     • 优缺点:
       • 优点：简单有效，易于实现
       • 缺点：需要额外的指针存储空间
  2. 开放地址法：
     • 思想：当发生冲突时，按照某种探测序列在哈希表中寻找下一个空闲位置
     • 探测方法:
       • 线性探测：index = (hash(key) + i) % table_size
       • 二次探测：index = (hash(key) + i²) % table_size
       • 双重散列：index = (hash1(key) + i * hash2(key)) % table_size
     • 优缺点：
       • 优点：所以数据都存储在数组中
       • 缺点：删除操作复杂

4. C语言实现简单哈希表

4.1 定义

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

//定义哈希表节点
typedef struct HashNode {
    int key; // 键
    int value; // 值
    struct HashNode* next; // 下一节点
} HashNode;

//定义哈希表
typedef struct {
    HashNode** table; // 存储哈希表中各个桶的头指针 (指针的指针）
    int size; // 哈希表大小
    int count; // 元素个数
} HashTable;

4.2 创建哈希表

//创建哈希表
HashTable* createHashTable(int size) {
    if (size <= 0) {
        printf("哈希表大小必须大于0\n");
        return NULL;
    }
    HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));
    if (hashTable == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    hashTable->size = size;
    hashTable->count = 0; // 初始化元素数量
    hashTable->table = (HashNode**)malloc(sizeof(HashNode*) * size);
    if (hashTable->table == NULL) {
        printf("内存分配失败\n");
        free(hashTable);
        return NULL;
    }
    // 初始化所有桶为空
    for (int i = 0; i < size; i++) {
        hashTable->table[i] = NULL;
    }
    printf("创建哈希表成功，大小为：%d\n", size);
    return hashTable;
}

代码说明：

• 函数声明，返回 HashTable 指针，参数 size 为哈希表大小，即哈希桶的个数
• 分配 HashTable 结构体的内存空间，初始化哈希表：
  • size：设置哈希表的大小（哈希桶的数量）
  • count：当前哈希表内的元素数量初始化为0
• 再为哈希桶分配内存（每个桶都是一个 HashNode* 的指针）：遍历所有桶，将每个桶都初始化为 NULL
• 最后，返回创建好的哈希表指针

4.3 哈希函数

//哈希函数
int hashFunction(HashTable* hashTable, int key) {
    return abs(key) % hashTable->size;
}

代码说明：

• 计算并返回哈希值
  • 取 key 的绝对值，避免负数导致计算出的哈希值为负数（数组索引不能为负数）
  • 取模：将 key 映射到 [0, hashTable->size - 1] 的范围内，确保哈希值在哈希表的有效索引范围内

4.4 插入哈希表

//插入哈希表
int insertHash(HashTable* hashTable, int key, int value) {
    if (hashTable == NULL) {
        printf("哈希表为空，无法插入\n");
        return 0; // 插入失败
    }
    int hashIndex = hashFunction(hashTable, key);
    // 检查键是否已经存在
    HashNode* curNode = hashTable->table[hashIndex];
    while (curNode != NULL) {
        if (curNode->key == key) {
            curNode->value = value;
            printf("更新键：%d\n", key);
            return 2; // 更新操作
        }
        curNode = curNode->next;
    }
    // 创建新节点
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return 0;
    }
    newNode->key = key;
    newNode->value = value;
    // 插入到链表头部
    newNode->next = hashTable->table[hashIndex];
    hashTable->table[hashIndex] = newNode;
    hashTable->count++;
    printf("插入成功：键=%d, 值=%d\n", key, value);
    return 1; // 插入成功
}

代码说明：

• 首先，检查哈希表指针是否为空，若为空，则插入失败，返回0
• 接着，计算哈希索引：
  • 调用前面的哈希函数 HashFunction，根据 key 计算应该存储在哪个桶里
  • 检查键是否存在：
    • 获取对应桶的链表头指针
    • 遍历链表
    • 若找到相同的 key：更新 value 值，返回2，表示更新；若未找到，则说明 key 不存在，需要插入新节点
• 创建新节点，设置新节点的键值对，再将其插入链表头部（头插法）
• 最后增加哈希表的元素个数，返回1，表示插入成功

4.5 查找哈希表

//查找哈希表
int searchHash(HashTable* hashTable, int key, int* value) {
    if (hashTable == NULL || value == NULL) {
        return 0;
    }
    int hashIndex = hashFunction(hashTable, key);
    HashNode* curNode = hashTable->table[hashIndex];
    while (curNode != NULL) {
        if (curNode->key == key) {
            *value = curNode->value;
            return 1; // 找到
        }
        curNode = curNode->next;
    }
    return 0; // 没找到
}

代码说明：

• 该函数中的参数分别为：哈希表指针 HashTable* hashTable、要查找的目标键 int key、输出参数，用来存储找到的值 int* value
• 检查哈希表指针和输出参数指针是否为空
• 接着，计算哈希索引：
  • 调用 hashFunction 函数
  • 计算 key 对应的桶索引
  • 获取对应桶的链表头指针，直接访问哈希表的桶数组
• 遍历链表，找到匹配的 key，将值赋给输出参数 *value

4.6 删除哈希表

//删除哈希表
int DeleteHash(HashTable* hashTable, int key) {
    if (hashTable == NULL) {
        printf("哈希表为空，无法删除\n");
        return 0; // 删除失败
    }
    int hashIndex = hashFunction(hashTable, key);
    HashNode* curNode = hashTable->table[hashIndex];
    HashNode* prevNode = NULL;
    while (curNode != NULL) {
        if (curNode->key == key) {
            if (prevNode == NULL) { // 删除头节点
                hashTable->table[hashIndex] = curNode->next;
            } else { // 删除中间或尾部节点
                prevNode->next = curNode->next;
            }
            free(curNode);
            hashTable->count--;
            printf("删除成功\n");
            return 1; // 删除成功
        }
        prevNode = curNode;
        curNode = curNode->next;
    }
    printf("删除失败\n");
    return 0; // 未找到键，删除失败
}

代码说明：

• 检查哈希表指针是否为空
• 计算哈希索引：
  • 调用 hashFunction 函数
  • 计算 key 对应的桶索引
• 遍历链表查找目标键：
  • curNode：当前节点指针，初始化为链表头；prevNode：前驱节点指针，初始化为 NULL
  • 循环直到链表末尾
  • 检查当前节点的 key 是否匹配目标 key
• 找到后，进行删除操作：
  • 删除头节点（prevNode == NULL）
    • 将桶的头指针指向当前节点的下一个节点
    • 直接跳过要删除的节点
  • 删除中间或尾部节点
    • 将前驱节点的 next 指针指向当前节点的下一个节点
    • 跳过要删除的节点
  • 删除：
    • free(curNode)：释放被删除节点的内存
    • hashTable->count--：减少哈希表元素个数

4.7 释放哈希表

//释放哈希表
void freeHash(HashTable* hashTable) {
    if (hashTable == NULL) {
        return;
    }
    for (int i = 0; i < hashTable->size; i++) {
        HashNode* curNode = hashTable->table[i];
        while (curNode != NULL) {
            HashNode* temp = curNode;
            curNode = curNode->next;
            free(temp);
        }
    }
    free(hashTable->table);
    free(hashTable);
}

代码说明：

• 检查哈希表指针是否为空
• 遍历所有桶----->遍历当前桶的链表----->释放所有节点
• 释放桶数组内存
• 释放哈希表结构体内存

4.8 完整测试

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

//定义哈希表节点
typedef struct HashNode {
    int key; // 键
    int value; // 值
    struct HashNode* next; // 下一节点
} HashNode;

//定义哈希表
typedef struct {
    HashNode** table; // 存储哈希表中各个桶的头指针 (指针的指针）
    int size; // 哈希表大小
    int count; // 元素个数
} HashTable;

//创建哈希表
HashTable* createHashTable(int size) {
    if (size <= 0) {
        printf("哈希表大小必须大于0\n");
        return NULL;
    }
    HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));
    if (hashTable == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    hashTable->size = size;
    hashTable->count = 0; // 初始化元素数量
    hashTable->table = (HashNode**)malloc((HashNode*) * size);
     (hashTable->table == ) {
        ();
        (hashTable);
         ;
    }
    
     ( i = ; i < size; i++) {
        hashTable->table[i] = ;
    }
    (, size);
     hashTable;
}


  {
     (key) % hashTable->size;
}


  {
     (hashTable == ) {
        ();
         ; 
    }
     hashIndex = hashFunction(hashTable, key);
    
    HashNode* curNode = hashTable->table[hashIndex];
     (curNode != ) {
         (curNode->key == key) {
            curNode->value = value;
            (, key);
             ; 
        }
        curNode = curNode->next;
    }
    
    HashNode* newNode = (HashNode*)((HashNode));
     (newNode == ) {
        ();
         ;
    }
    newNode->key = key;
    newNode->value = value;
    
    newNode->next = hashTable->table[hashIndex];
    hashTable->table[hashIndex] = newNode;
    hashTable->count++;
    (, key, value);
     ; 
}


  {
     (hashTable ==  || value == ) {
         ;
    }
     hashIndex = hashFunction(hashTable, key);
    HashNode* curNode = hashTable->table[hashIndex];
     (curNode != ) {
         (curNode->key == key) {
            *value = curNode->value;
             ; 
        }
        curNode = curNode->next;
    }
     ; 
}


  {
     (hashTable == ) {
        ();
         ; 
    }
     hashIndex = hashFunction(hashTable, key);
    HashNode* curNode = hashTable->table[hashIndex];
    HashNode* prevNode = ;
     (curNode != ) {
         (curNode->key == key) {
             (prevNode == ) { 
                hashTable->table[hashIndex] = curNode->next;
            }  { 
                prevNode->next = curNode->next;
            }
            (curNode);
            hashTable->count--;
            (, key);
             ; 
        }
        prevNode = curNode;
        curNode = curNode->next;
    }
    (, key);
     ; 
}


  {
     (hashTable == ) {
        ();
        ;
    }
    ();
    (, hashTable->size, hashTable->count);
     ( i = ; i < hashTable->size; i++) {
         (hashTable->table[i] != ) {
            (, i);
            HashNode* curNode = hashTable->table[i];
             (curNode != ) {
                (, curNode->key, curNode->value);
                 (curNode->next != ) {
                    ();
                }
                curNode = curNode->next;
            }
            ();
        }
    }
    ();
}


  {
     (hashTable == ) {
        ;
    }
     ( i = ; i < hashTable->size; i++) {
        HashNode* curNode = hashTable->table[i];
         (curNode != ) {
            HashNode* temp = curNode;
            curNode = curNode->next;
            (temp);
        }
    }
    (hashTable->table);
    (hashTable);
    ();
}


  {
    ();
    
    HashTable* ht = createHashTable();
     (ht == ) {
         ;
    }
    
    ();
    insertHash(ht, , );
    insertHash(ht, , ); 
    insertHash(ht, , ); 
    insertHash(ht, , );
    insertHash(ht, , );
    
    printHashTable(ht);
    
    ();
    insertHash(ht, , ); 
    printHashTable(ht);
    
    ();
     value;
     (searchHash(ht, , &value)) {
        (, value);
    }  {
        ();
    }
     (searchHash(ht, , &value)) {
        (, value);
    }  {
        ();
    }
    
    ();
    DeleteHash(ht, );
    DeleteHash(ht, ); 
    printHashTable(ht);
    
    ();
    insertHash(ht, , ); 
    insertHash(ht, , ); 
    printHashTable(ht);
    
    freeHash(ht);
     ;
}

结果：

===== 哈希表测试程序 ===== 创建哈希表成功，大小为：5 1. 测试插入操作：插入成功：键=1, 值=100 插入成功：键=6, 值=200 插入成功：键=11, 值=300 插入成功：键=2, 值=400 插入成功：键=3, 值=500 === 哈希表状态 === 大小：5, 元素个数：5 桶 [1]: (11:300) -> (6:200) -> (1:100) 桶 [2]: (2:400) 桶 [3]: (3:500) ================= 2. 测试更新操作：更新键：1 === 哈希表状态 === 大小：5, 元素个数：5 桶 [1]: (11:300) -> (6:200) -> (1:150) 桶 [2]: (2:400) 桶 [3]: (3:500) ================= 3. 测试查找操作：找到键 6, 值为：200 未找到键 99 4. 测试删除操作：删除键 6 成功 删除失败，未找到键：99 === 哈希表状态 === 大小：5, 元素个数： 桶 : (:) > (:) 桶 : (:) 桶 : (:) ================= . 测试负键值：插入成功：键=, 值= 插入成功：键=, 值= === 哈希表状态 === 大小：, 元素个数： 桶 : (:) > (:) 桶 : (:) 桶 : (:) 桶 : (:) > (:) ================= 哈希表已释放