哈希表（Hash Table)

一、哈希表及相关名词介绍

1. 哈希表
   哈希表（Hash Table）是一种非常高效的数据结构，它通过哈希函数将键（key）映射到数组的某个索引位置，从而实现快速的插入、查找和删除操作。是一种存储键值对的高效数据结构
2. 键（key）
   键是你用来查找数据的标识符，可以是数字、字符串等
3. 值（value）
   值就是与键关联的数据内容
4. 键值对（key-value pair）
   键值对就是一个键和它对应的值组成的组合。在程序中通常以结构体形式存储，比如：

struct
{
	char* key;
	int value;
};

5. 哈希函数（Hsah Function）
   哈希函数是一个将键转换为一个整数（通常是数组下标）的函数。

它的作用具体表现为：把任意类型的键，比如字符串 “apple”，通过一定的算法计算出一个整数索引，用来决定这个键值对应该存放在哈希表的哪个位置（桶）
6. 哈希值（Hash Value）
哈希函数计算出来的整数值，通常是数组索引
7. 哈希冲突（Hash Collision）
当两个不同的键，经过哈希函数计算后，得到了相同的哈希值（即同一个数组位置），就称为哈希冲突

• 发生原因：哈希表大小有限，但是键的数量无限，冲突无法避免
• 解决方法：
  • 链地址法（Separate Chaining）：每个数组位置挂一个链表，冲突的键值对都放到这个链表中 (常用)
  • 开放寻址法（Open Addressing）：发生冲突时，按照某种规则找下一个空位置

8. 桶（Bucket）
   哈希表中的每一个数组位置就叫做一个桶，每个桶可以存放一个或多个键值对。

比喻：可以把哈希表想象成一个有很多格子的盒子（数组），每个格子就是一个桶，格子上的序号是哈希值，格子里面放的东西就是键值对

9. 链地址法
   这是一种解决哈希冲突的常见方法。具体做法为：每个桶（数组位置）不直接存一个键值对，而是存一个链表，所有哈希到这个位置上的键值对，都放到这个链表中。在链地址法中，每个桶是一个链表的头，链表中可以挂多个键值对
10. 开放寻址法
    这是另一种用于解决哈希冲突的方法。具体做法为：如果某个位置已经被占用（冲突了），就按照某种规则（如线性探测、二次探测）去寻找下一个空位置，把键值对放到那里

开放地址法与链地址法的区别是：开放寻址法冲突了就另找空位放，链地址法冲突了就“拉链”（用链表）

二、哈希表工作流程简单总结

假设我们有一个哈希表，大小为10，哈希函数是简单的取模：hash(key) = key对应的数字（如果key本身不是数字）% 10
步骤：

1. 你提供一个键，比如 “apple”
2. 哈希函数计算 "apple"→ 得到一个数字，比如 7
3. 哈希表中索引为 7的位置（第 8 个桶，因为从 0 开始），就是存放这个键值对的地方
4. 如果这个位置是空的，直接放入
5. 如果这个位置已经有数据了（冲突了），就用开放寻址法、链地址法等方式处理

三、用C语言实现哈希表（以链地址法为例）

将实现以下功能：

• 支持字符串作为键（key），整数作为值（value）
• 支持插入（insert）、查找（search）、删除（delete）
• 使用链表解决冲突

代码实现：

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

// -------------------------------
// 定义哈希表中每一个键值对的节点
// -------------------------------
typedef struct Node {
    char* key;          // 键，字符串类型
    int value;          // 值，整数类型
    struct Node* next;  // 指向下一个节点（用于处理冲突——链地址法）
} Node;

// -------------------------------
// 定义哈希表结构
// -------------------------------
#define TABLE_SIZE 100  // 哈希表大小，可以调整

typedef struct {
    Node* table[TABLE_SIZE];  // 一个数组，每个元素是一个链表头指针
} HashTable;

// -------------------------------
// 哈希函数：将字符串 key 转为哈希值（数组下标）
// 这里使用一个简单的 djb2 哈希算法
// -------------------------------
unsigned int hash_function(const char* key) {
    unsigned long hash = 5381;  // 初始值
    int c;
    while ((c = *key++)) {
        hash = ((hash << 5) + hash) + c;  // hash * 33 + c
    }
    return hash % TABLE_SIZE;  // 取模得到数组索引
}

// -------------------------------
// 创建一个新的节点
// -------------------------------
Node* create_node(const char* key, int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (!new_node) {
        perror("Failed to allocate memory for new node");
        exit(EXIT_FAILURE);
    }
    new_node->key = _strdup(key);  // 复制字符串
    if (!new_node->key) {
        perror("Failed to duplicate key");
        free(new_node);
        exit(EXIT_FAILURE);
    }
    new_node->value = value;
    new_node->next = NULL;
    return new_node;
}

// -------------------------------
// 初始化哈希表
// -------------------------------
HashTable* create_hash_table() {
    HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
    if (!ht) {
        perror("Failed to allocate memory for hash table");
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->table[i] = NULL;  // 每个桶初始化为空
    }
    return ht;
}

// -------------------------------
// 插入键值对（如果已存在则更新值）
// -------------------------------
void insert(HashTable* ht, const char* key, int value) {
    unsigned int index = hash_function(key);

    Node* current = ht->table[index];

    // 先查找是否已经存在该 key
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            current->value = value;  // 更新值
            return;
        }
        current = current->next;
    }

    // 若不存在，则创建新节点并插入到链表头部
    Node* new_node = create_node(key, value);
    new_node->next = ht->table[index];
    ht->table[index] = new_node;
}

// -------------------------------
// 查找键对应的值，找不到返回 -1
// -------------------------------
int search(HashTable* ht, const char* key) {
    unsigned int index = hash_function(key);
    Node* current = ht->table[index];

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }

    return -1;  // 表示没找到
}

// -------------------------------
// 删除键值对
// -------------------------------
void delete(HashTable* ht, const char* key) {
    unsigned int index = hash_function(key);
    Node* current = ht->table[index];
    Node* prev = NULL;

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            if (prev == NULL) {
                // 要删除的是链表的第一个节点
                ht->table[index] = current->next;
            }
            else {
                prev->next = current->next;
            }
            free(current->key);  // 释放字符串内存
            free(current);       // 释放节点内存
            return;
        }
        prev = current;
        current = current->next;
    }
}

// -------------------------------
// 释放整个哈希表的内存
// -------------------------------
void free_hash_table(HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Node* current = ht->table[i];
        while (current != NULL) {
            Node* temp = current;
            current = current->next;
            free(temp);
        }
    }
    free(ht);
}

// -------------------------------
// 测试代码
// -------------------------------
int main() {
    HashTable* ht = create_hash_table();

    // 插入一些键值对
    insert(ht, "apple", 10);
    insert(ht, "banana", 20);
    insert(ht, "orange", 30);

    // 查找并打印
    printf("apple: %d\n", search(ht, "apple"));    // 10
    printf("banana: %d\n", search(ht, "banana"));  // 20
    printf("grape: %d\n", search(ht, "grape"));    // -1（未找到）

    // 更新值
    insert(ht, "apple", 100);
    printf("apple (updated): %d\n", search(ht, "apple"));  // 100

    // 删除
    delete(ht, "banana");
    printf("banana (after delete): %d\n", search(ht, "banana"));  // -1

    // 释放哈希表
    free_hash_table(ht);

    return 0;
}
//output：
//apple: 10
//banana: 20
//grape: -1
//apple (updated): 100
//banana (after delete): -1

注意：

1. 每个哈希桶（table[index]）是一个链表头指针，指向第一个 Node。如果有多个键被哈希到同一个位置（即冲突），它们会以链表的形式连接起来
2. 相同的key对应相同的value
3. 在插入新键值对、查找键值对、删除键值对的时候都是先要判断key值在链表中是否已经存在，即：if(strcmp(current->key,key) == 0)
4. 创建新节点create_node的时候，一定记得用strdup拷贝key，即：new_node->key = strdup(key)
5. 删除键值对delete部分中的prev是一个指针，指向current前一个节点，初始化为NULL。如果要删除的是链表的第一个节点，即prev == NULL，直接让链表头节点指向current->next，跳current,即：table[index]->next = current->next,如果要删除的不是链表的第一个节点即 prev != NULL, 则让current的前一个节点指向current的后一个节点，即：prev->next = current->next