#创作计划# 哈希表
2025-07-08 15:00:19
发布于：福建
一、基本概念
定义
哈希表是一种通过键（Key）直接访问值（Value）的数据结构，基于哈希函数将键映射到存储位置（桶/槽）。
核心组成
哈希函数：将任意长度的键转换为固定长度的哈希值（如 hash(key) -> index）。
数组（桶数组）：存储实际数据的连续内存空间。
冲突解决机制：处理不同键映射到同一位置的情况。
二、哈希函数设计
设计要求
确定性：相同键始终映射到同一位置。
均匀性：键应均匀分布以减少冲突。
高效性：计算复杂度低（通常O(1)）。
常见哈希函数
除法取余法：hash(key) = key % size
乘法散列法：利用浮点数运算和取小数部分。
加密哈希函数（如MD5、SHA-1，适用于安全场景。
三、冲突解决方法
开放定址法
线性探测：冲突后顺序查找下一个空槽。
二次探测：按平方增量跳跃探测。
双重哈希：使用第二个哈希函数计算步长。
链地址法
每个桶存储链表或树结构，冲突元素追加到同一桶中（如Java的HashMap）。
再哈希法
冲突时换用另一个哈希函数重新计算。
四、性能分析
时间复杂度
理想情况：插入、删除、查找均为O(1)。
最坏情况（全冲突）：退化为链表O(n)。
负载因子（Load Factor）
定义：元素数量/桶数量（通常阈值设为0.75，超过时触发扩容）。
扩容与Rehash
动态扩容（如翻倍桶数量）并重新映射所有元素。
五、优化与变种
布谷鸟哈希
使用两个哈希函数，冲突时“踢出”原元素重新放置。
完美哈希
无冲突的静态哈希表（适用于固定数据集）。
一致性哈希
分布式系统中减少节点变动的影响（如Redis集群）。
六、应用场景
1.数据库索引（如MySQL的哈希索引）。
2.缓存系统（如Redis、Memcached）。
3.语言内置数据结构（Python字典、C++ unordered_map）。
4.密码学（校验数据完整性）。
七。基础插入和查询功能+删除操作和模板化键值类型
使用使用标准库实现链地址法冲突解决
#include <vector>
#include <list>
#include <functional>
#include <stdexcept>
template<typename K, typename V>
class HashTable {
private:
struct Node {
K key;
V value;
Node(const K& k, const V& v) : key(k), value(v) {}
};
std::vector<std::list<Node>> table;
size_t capacity;
size_t size;
size_t hashFunction(const K& key) const {
return std::hash<K>{}(key) % capacity;
}
public:
HashTable(size_t cap = 101) : capacity(cap), size(0) {
table.resize(capacity);
}
void insert(const K& key, const V& value) {
size_t index = hashFunction(key);
for (auto& node : table[index]) {
if (node.key == key) {
node.value = value;
return;
}
}
table[index].emplace_back(key, value);
size++;
}
V& get(const K& key) {
size_t index = hashFunction(key);
for (auto& node : table[index]) {
if (node.key == key) {
return node.value;
}
}
throw std::out_of_range("Key not found");
}
bool contains(const K& key) const {
size_t index = hashFunction(key);
for (const auto& node : table[index]) {
if (node.key == key) {
return true;
}
}
return false;
}
bool remove(const K& key) {
size_t index = hashFunction(key);
for (auto it = table[index].begin(); it != table[index].end(); ++it) {
if (it->key == key) {
table[index].erase(it);
size--;
return true;
}
}
return false;
}
size_t getSize() const { return size; }
bool isEmpty() const { return size == 0; }
};
这里空空如也
有帮助，赞一个