1. 哈希表的基本概念

哈希表（Hash Table），也叫散列表，是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过把键值通过一个函数的计算，映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数叫做哈希函数（Hash Function），存放记录的数组叫做哈希表。

• 键（Key）: 用于计算哈希值的输入。
• 哈希函数（Hash Function）: 将键映射到哈希表中索引的函数。
• 哈希值（Hash Value）/ 散列值: 哈希函数计算得到的结果，即数组的索引。
• 冲突（Collision）: 不同的键通过哈希函数计算得到了相同的哈希值。
• 桶（Bucket）: 哈希表中存储一个或多个记录的位置。

2. 哈希函数的设计

一个好的哈希函数应具备以下特点：

0. 计算简单高效: 哈希函数的计算不能太复杂，否则会影响效率。
1. 分布均匀: 哈希值应尽可能均匀地分布在哈希表的地址空间上，以减少冲突。
2. 与键相关: 哈希值应依赖于键的所有部分，而不仅仅是其中一部分。

常见的哈希函数构造方法：

• 直接定址法: 取关键字的某个线性函数值为哈希地址。H(key) = a * key + b
• 除留余数法: 取关键字被某个不大于哈希表表长m的数p除后所得的余数为哈希地址。H(key) = key % p (p通常取小于等于m的质数)
• 数字分析法: 适用于关键字位数较多，且关键字中某些位的数字分布均匀的情况。
• 平方取中法: 取关键字平方后的中间几位作为哈希地址。
• 折叠法: 将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为哈希地址。

3. 冲突处理方法

冲突是哈希表中不可避免的问题。常见的冲突处理方法有：

• 开放定址法: 当发生冲突时，按照某种规则去寻找哈希表中的下一个空的存储单元。
• 线性探测法: Hi = (H(key) + di) % m，其中 di = 1, 2, 3, ..., m-1。容易产生“一次聚集”现象。
• 二次探测法: Hi = (H(key) + di) % m，其中 di = 1^2, -1^2, 2^2, -2^2, ...。可以减轻一次聚集。
• 伪随机探测法: Hi = (H(key) + RNi) % m，其中 RNi 是一个随机序列。
• 链地址法（拉链法）: 将所有哈希地址相同的记录存储在同一线性链表中。这是最常用的冲突解决方法。

4. 哈希表的实现 (C语言示例 - 链地址法)

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 #define TABLE_SIZE 10 // 哈希表的大小，可以根据实际情况调整
 
 // 哈希表结点定义 (用于链地址法)
 typedef struct HashNode {
     char* key;          // 键 (假设为字符串)
     int value;          // 值
     struct HashNode *next; // 指向下一个具有相同哈希值的结点
 } HashNode;
 
 // 哈希表定义
 typedef struct HashTable {
     HashNode* table[TABLE_SIZE]; // 指针数组，每个元素是一个链表的头指针
 } HashTable;
 
 // 创建哈希结点
 HashNode* createHashNode(const char* key, int value) {
     HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
     if (!newNode) {
         perror("Memory allocation failed for HashNode");
         exit(EXIT_FAILURE);
     }
     newNode->key = strdup(key); // 复制键字符串
     if (!newNode->key) {
         perror("Memory allocation failed for key string");
         free(newNode);
         exit(EXIT_FAILURE);
     }
     newNode->value = value;
     newNode->next = NULL;
     return newNode;
 }
 
 // 创建哈希表
 HashTable* createHashTable() {
     HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
     if (!ht) {
         perror("Memory allocation failed for HashTable");
         exit(EXIT_FAILURE);
     }
     for (int i = 0; i < TABLE_SIZE; i++) {
         ht->table[i] = NULL;
     }
     return ht;
 }
 
 // 简单的哈希函数 (示例：字符串ASCII码和对表大小取模)
 unsigned int hashFunction(const char* key) {
     unsigned long hash = 0;
     int c;
     while ((c = *key++))
         hash = c + (hash << 6) + (hash << 16) - hash; // 一种常用的字符串哈希算法
     return hash % TABLE_SIZE;
 }
 
 // 向哈希表中插入键值对
 void insert(HashTable* ht, const char* key, int value) {
     unsigned int hashIndex = hashFunction(key);
     HashNode* newNode = createHashNode(key, value);
 
     // 如果该索引处没有链表，则新结点成为头结点
     if (ht->table[hashIndex] == NULL) {
         ht->table[hashIndex] = newNode;
     } else {
         // 否则，将新结点插入到链表头部 (或尾部，或保持有序)
         HashNode* current = ht->table[hashIndex];
         // 检查键是否已存在，如果存在则更新值 (可选行为)
         while (current != NULL) {
             if (strcmp(current->key, key) == 0) {
                 current->value = value; // 更新已存在键的值
                 free(newNode->key);
                 free(newNode);
                 return;
             }
             current = current->next;
         }
         // 插入到头部
         newNode->next = ht->table[hashIndex];
         ht->table[hashIndex] = newNode;
     }
     printf("Inserted key: '%s', value: %d at index %u\n", key, value, hashIndex);
 }
 
 // 从哈希表中查找键对应的值
 int search(HashTable* ht, const char* key) {
     unsigned int hashIndex = hashFunction(key);
     HashNode* current = ht->table[hashIndex];
     while (current != NULL) {
         if (strcmp(current->key, key) == 0) {
             return current->value;
         }
         current = current->next;
     }
     return -1; // 表示未找到 (或抛出异常/返回特定错误码)
 }
 
 // 从哈希表中删除键值对
 void deleteKey(HashTable* ht, const char* key) {
     unsigned int hashIndex = hashFunction(key);
     HashNode* current = ht->table[hashIndex];
     HashNode* prev = NULL;
 
     while (current != NULL && strcmp(current->key, key) != 0) {
         prev = current;
         current = current->next;
     }
 
     if (current == NULL) {
         printf("Key '%s' not found for deletion.\n", key);
         return;
     }
 
     if (prev == NULL) { // 要删除的是头结点
         ht->table[hashIndex] = current->next;
     } else {
         prev->next = current->next;
     }
     printf("Deleted key: '%s' from index %u\n", current->key, hashIndex);
     free(current->key);
     free(current);
 }
 
 // 释放哈希表内存
 void freeHashTable(HashTable* ht) {
     if (!ht) return;
     for (int i = 0; i < TABLE_SIZE; i++) {
         HashNode* current = ht->table[i];
         while (current != NULL) {
             HashNode* temp = current;
             current = current->next;
             free(temp->key);
             free(temp);
         }
     }
     free(ht);
 }
 
 int main() {
     HashTable* ht = createHashTable();
 
     insert(ht, "apple", 10);
     insert(ht, "banana", 20);
     insert(ht, "orange", 30);
     insert(ht, "grape", 40); // 可能与apple冲突，取决于哈希函数和TABLE_SIZE
     insert(ht, "mango", 50);
 
     printf("\nSearching for keys:\n");
     printf("Value for 'apple': %d\n", search(ht, "apple"));
     printf("Value for 'orange': %d\n", search(ht, "orange"));
     printf("Value for 'watermelon': %d (expected -1 if not found)\n", search(ht, "watermelon"));
 
     printf("\nUpdating key 'apple':\n");
     insert(ht, "apple", 15); // 更新apple的值
     printf("New value for 'apple': %d\n", search(ht, "apple"));
 
     printf("\nDeleting keys:\n");
     deleteKey(ht, "banana");
     deleteKey(ht, "grape");
     deleteKey(ht, "papaya"); // 尝试删除不存在的键
 
     printf("\nFinal state of 'apple': %d\n", search(ht, "apple"));
     printf("Final state of 'banana': %d (expected -1 after deletion)\n", search(ht, "banana"));
 
     freeHashTable(ht);
 
     return 0;
 }

5. 哈希表的应用

• 编译器中的符号表
• 数据库索引
• 缓存系统 (如 Web 缓存)
• 集合与字典的实现 (如 Python 的 dict 和 set)
• 密码存储 (存储密码的哈希值而非原文)

总结

哈希表是一种非常高效的数据结构，能够在平均情况下实现O(1)时间的插入、删除和查找操作。理解其基本原理、哈希函数的设计以及冲突处理方法对于编写高性能的程序至关重要。