哈希表核心原理、冲突解决策略与多语言实现
哈希表基础与映射原理
哈希表（Hash Table）是一种基于键值对（Key-Value）进行高效数据存取的数据结构。其核心思想是通过哈希函数（Hash Function）将任意类型的键映射为数组的索引，从而实现理想状态下 $O(1)$ 时间复杂度的插入、查找和删除操作。
与传统的顺序查找或二分查找不同，哈希查找跳过了元素间的直接比较过程。它建立了一种数学映射关系 $f(key) = index$，直接计算出目标数据在连续内存空间（即哈希表）中的物理地址。
哈希函数的设计策略
一个优秀的哈希函数应当计算简单且能将键值均匀分布到哈希表中，以最小化冲突。常见的构造方法包括：
- 直接定址法：取关键字的线性函数值作为地址，即 $f(key) = a \cdot key + b$。适用于键值范围小且连续的场景，不会产生冲突。
- 除留余数法：最常用的方法。公式为 $f(key) = key \pmod p$。关键在于选择合适的 $p$，通常 $p$ 应为小于或等于哈希表长度的最大素数。
- 随机数法：使用伪随机函数生成地址，适用于关键字长度不等的场景。
哈希冲突及其解决机制
由于哈希函数的输出空间通常小于输入空间，不同的键映射到同一索引（即哈希冲突）是不可避免的。主流的冲突处理方案分为两类：
1. 链地址法（Separate Chaining）
在哈希表的每个槽位（Slot）维护一个链表。所有哈希值相同的元素都被追加到该槽位对应的链表中。这种方法实现简单，且对负载因子（Load Factor）的容忍度较高，但需要额外的指针存储空间，且在链表过长时会退化为 $O(N)$ 的查找效率。
2. 开放寻址法（Open Addressing）
当发生冲突时，按照某种探测序列在哈希表中寻找下一个空闲位置。所有元素都直接存储在哈希表的数组中。常见的探测策略包括：
- 线性探测：冲突时依次检查下一个位置（$index + 1, index + 2 \dots$）。容易产生"聚集（Clustering）"现象。
- 二次探测：按平方步长进行探测（$index + 1^2, index - 1^2, index + 2^2 \dots$），有效缓解聚集问题。
- 双重哈希：引入第二个哈希函数来计算探测步长，进一步减少冲突。
动态扩容与再哈希（Rehashing）
随着元素的不断插入，哈希表的负载因子（已存元素数 / 表容量）会逐渐升高，导致冲突加剧、性能下降。当负载因子超过预设阈值（如 0.75）时，需要触发扩容机制：申请一个更大的数组（通常是原容量的两倍），并将所有现有元素重新计算哈希值并插入新表中。Python 内置的字典（dict）底层正是采用了开放寻址法结合动态再哈希的机制来保障高效性能。
多语言代码实现
以下分别使用 C 和 C++ 演示链地址法与开放寻址法（线性探测）的核心实现。代码经过了结构优化与逻辑重构，修复了原生实现中常见的内存泄漏与探测链断裂问题，以提升可读性与健壮性。
C 语言实现：链地址法
// chained_hash.h
#ifndef CHAINED_HASH_H
#define CHAINED_HASH_H
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TABLE_CAPACITY 11
typedef struct HashNode {
int key;
struct HashNode* next;
} HashNode;
typedef struct ChainedHashMap {
HashNode** buckets;
int size;
} ChainedHashMap;
ChainedHashMap* create_map();
void destroy_map(ChainedHashMap* map);
void map_insert(ChainedHashMap* map, int key);
bool map_contains(ChainedHashMap* map, int key);
bool map_remove(ChainedHashMap* map, int key);
void map_display(ChainedHashMap* map);
#endif
// chained_hash.c
#include "chained_hash.h"
static int compute_hash(int key) {
// 使用除留余数法，兼容处理负数键
return (key % TABLE_CAPACITY + TABLE_CAPACITY) % TABLE_CAPACITY;
}
ChainedHashMap* create_map() {
ChainedHashMap* map = (ChainedHashMap*)malloc(sizeof(ChainedHashMap));
map->buckets = (HashNode**)calloc(TABLE_CAPACITY, sizeof(HashNode*));
map->size = 0;
return map;
}
void destroy_map(ChainedHashMap* map) {
for (int i = 0; i < TABLE_CAPACITY; i++) {
HashNode* current = map->buckets[i];
while (current) {
HashNode* temp = current;
current = current->next;
free(temp);
}
}
free(map->buckets);
free(map);
}
void map_insert(ChainedHashMap* map, int key) {
int idx = compute_hash(key);
// 检查是否已存在
HashNode* curr = map->buckets[idx];
while (curr) {
if (curr->key == key) return;
curr = curr->next;
}
// 头插法插入新节点
HashNode* new_node = (HashNode*)malloc(sizeof(HashNode));
new_node->key = key;
new_node->next = map->buckets[idx];
map->buckets[idx] = new_node;
map->size++;
}
bool map_contains(ChainedHashMap* map, int key) {
int idx = compute_hash(key);
HashNode* curr = map->buckets[idx];
while (curr) {
if (curr->key == key) return true;
curr = curr->next;
}
return false;
}
bool map_remove(ChainedHashMap* map, int key) {
int idx = compute_hash(key);
HashNode* curr = map->buckets[idx];
HashNode* prev = NULL;
while (curr) {
if (curr->key == key) {
if (prev) prev->next = curr->next;
else map->buckets[idx] = curr->next;
free(curr);
map->size--;
return true;
}
prev = curr;
curr = curr->next;
}
return false;
}
void map_display(ChainedHashMap* map) {
for (int i = 0; i < TABLE_CAPACITY; i++) {
printf("Bucket[%02d]: ", i);
HashNode* curr = map->buckets[i];
if (!curr) printf("EMPTY");
while (curr) {
printf("%d -> ", curr->key);
curr = curr->next;
}
printf("NULL\n");
}
}
C 语言实现：开放寻址法（线性探测）
// linear_probing.h
#ifndef LINEAR_PROBING_H
#define LINEAR_PROBING_H
#include <stdbool.h>
#define LP_CAPACITY 13
#define EMPTY_SLOT -1
#define DELETED_SLOT -2
typedef struct LinearProbingMap {
int* slots;
int count;
} LinearProbingMap;
LinearProbingMap* lp_create();
void lp_destroy(LinearProbingMap* map);
bool lp_insert(LinearProbingMap* map, int key);
bool lp_search(LinearProbingMap* map, int key);
bool lp_delete(LinearProbingMap* map, int key);
void lp_display(LinearProbingMap* map);
#endif
// linear_probing.c
#include "linear_probing.h"
#include <stdio.h>
#include <stdlib.h>
static int lp_hash(int key) {
return (key % LP_CAPACITY + LP_CAPACITY) % LP_CAPACITY;
}
LinearProbingMap* lp_create() {
LinearProbingMap* map = (LinearProbingMap*)malloc(sizeof(LinearProbingMap));
map->slots = (int*)malloc(LP_CAPACITY * sizeof(int));
for (int i = 0; i < LP_CAPACITY; i++) {
map->slots[i] = EMPTY_SLOT;
}
map->count = 0;
return map;
}
void lp_destroy(LinearProbingMap* map) {
free(map->slots);
free(map);
}
bool lp_insert(LinearProbingMap* map, int key) {
if (map->count >= LP_CAPACITY * 0.75) {
// 实际应用中此处应触发扩容和再哈希
return false;
}
int idx = lp_hash(key);
while (map->slots[idx] != EMPTY_SLOT && map->slots[idx] != DELETED_SLOT) {
if (map->slots[idx] == key) return false; // 已存在
idx = (idx + 1) % LP_CAPACITY;
}
map->slots[idx] = key;
map->count++;
return true;
}
bool lp_search(LinearProbingMap* map, int key) {
int idx = lp_hash(key);
while (map->slots[idx] != EMPTY_SLOT) {
if (map->slots[idx] == key) return true;
idx = (idx + 1) % LP_CAPACITY;
}
return false;
}
bool lp_delete(LinearProbingMap* map, int key) {
int idx = lp_hash(key);
while (map->slots[idx] != EMPTY_SLOT) {
if (map->slots[idx] == key) {
map->slots[idx] = DELETED_SLOT; // 懒删除，保证探测链不断裂
map->count--;
return true;
}
idx = (idx + 1) % LP_CAPACITY;
}
return false;
}
void lp_display(LinearProbingMap* map) {
for (int i = 0; i < LP_CAPACITY; i++) {
printf("Slot[%02d]: ", i);
if (map->slots[i] == EMPTY_SLOT) printf("EMPTY\n");
else if (map->slots[i] == DELETED_SLOT) printf("DELETED\n");
else printf("%d\n", map->slots[i]);
}
}
C++ 实现：泛型链地址法与动态扩容
#include <iostream>
#include <vector>
#include <memory>
#include <stdexcept>
template <typename K, typename V>
class SeparateChainingMap {
private:
struct Entry {
K key;
V value;
std::unique_ptr<Entry> next;
Entry(K k, V v) : key(k), value(v), next(nullptr) {}
};
std::vector<std::unique_ptr<Entry>> table;
size_t item_count;
size_t capacity;
double max_load_factor;
size_t hash_function(const K& key) const {
std::hash<K> hasher;
return hasher(key) % capacity;
}
void rehash() {
size_t new_capacity = capacity * 2;
std::vector<std::unique_ptr<Entry>> new_table(new_capacity);
for (auto& head : table) {
auto current = std::move(head);
while (current) {
auto next_node = std::move(current->next);
size_t new_idx = std::hash<K>{}(current->key) % new_capacity;
current->next = std::move(new_table[new_idx]);
new_table[new_idx] = std::move(current);
current = std::move(next_node);
}
}
table = std::move(new_table);
capacity = new_capacity;
}
public:
SeparateChainingMap(size_t init_cap = 8, double load_fac = 0.75)
: table(init_cap), item_count(0), capacity(init_cap), max_load_factor(load_fac) {}
void put(const K& key, const V& value) {
if (item_count >= capacity * max_load_factor) {
rehash();
}
size_t idx = hash_function(key);
auto* curr = table[idx].get();
while (curr) {
if (curr->key == key) {
curr->value = value; // 更新已有键
return;
}
curr = curr->next.get();
}
// 头插新节点
auto new_entry = std::make_unique<Entry>(key, value);
new_entry->next = std::move(table[idx]);
table[idx] = std::move(new_entry);
item_count++;
}
V get(const K& key) const {
size_t idx = hash_function(key);
auto* curr = table[idx].get();
while (curr) {
if (curr->key == key) return curr->value;
curr = curr->next.get();
}
throw std::out_of_range("Key not found");
}
bool remove(const K& key) {
size_t idx = hash_function(key);
auto* curr = table[idx].get();
Entry* prev = nullptr;
while (curr) {
if (curr->key == key) {
if (prev) {
prev->next = std::move(curr->next);
} else {
table[idx] = std::move(curr->next);
}
item_count--;
return true;
}
prev = curr;
curr = curr->next.get();
}
return false;
}
};
C++ 实现：泛型开放寻址法（线性探测）
#include <iostream>
#include <vector>
#include <optional>
template <typename T>
class LinearProbingSet {
private:
enum class SlotState { EMPTY, OCCUPIED, DELETED };
struct Slot {
T data;
SlotState state;
Slot() : state(SlotState::EMPTY) {}
};
std::vector<Slot> table;
size_t num_elements;
size_t cap;
const double LOAD_THRESHOLD = 0.7;
size_t get_hash(const T& val) const {
std::hash<T> hasher;
return hasher(val) % cap;
}
void expand_and_rehash() {
size_t new_cap = cap * 2 + 1;
std::vector<Slot> old_table = std::move(table);
table.assign(new_cap, Slot());
cap = new_cap;
num_elements = 0;
for (auto& slot : old_table) {
if (slot.state == SlotState::OCCUPIED) {
insert(slot.data);
}
}
}
public:
LinearProbingSet(size_t initial_cap = 11) : table(initial_cap), num_elements(0), cap(initial_cap) {}
bool insert(const T& val) {
if (num_elements >= cap * LOAD_THRESHOLD) {
expand_and_rehash();
}
size_t idx = get_hash(val);
while (table[idx].state == SlotState::OCCUPIED) {
if (table[idx].data == val) return false;
idx = (idx + 1) % cap;
}
table[idx].data = val;
table[idx].state = SlotState::OCCUPIED;
num_elements++;
return true;
}
bool contains(const T& val) const {
size_t idx = get_hash(val);
while (table[idx].state != SlotState::EMPTY) {
if (table[idx].state == SlotState::OCCUPIED && table[idx].data == val) {
return true;
}
idx = (idx + 1) % cap;
}
return false;
}
bool erase(const T& val) {
size_t idx = get_hash(val);
while (table[idx].state != SlotState::EMPTY) {
if (table[idx].state == SlotState::OCCUPIED && table[idx].data == val) {
table[idx].state = SlotState::DELETED;
num_elements--;
return true;
}
idx = (idx + 1) % cap;
}
return false;
}
};
