数据离不开哈希

一、哈希核心概念

1. 哈希函数（Hash Function）

• 作用：将任意大小的输入数据映射为固定大小的输出值（哈希值）。
• 特性：
  • 确定性：相同输入 → 相同输出
  • 高效性：快速计算
  • 均匀性：输出值应均匀分布（减少冲突）
  • 抗碰撞性：难以找到不同输入但相同输出
• 常见哈希函数：MD5、SHA-256、MurmurHash

二、哈希表（Hash Table）数据结构

1. 结构组成

• 桶数组：存储数据的连续内存空间
• 哈希函数：index = hash(key) % array_size
• 操作：
  • 插入：计算索引 → 存储到对应桶
  • 查找：计算索引 → 访问桶获取值
  • 删除：计算索引 → 清空桶

三、哈希冲突（Collision）

当不同键映射到同一桶时发生冲突：

四、冲突解决方法

1. 链地址法（Separate Chaining）

• 原理：每个桶存储链表/树，冲突元素追加到链表
• 复杂度：查找平均 O(1)，最坏 O(n)

2. 开放寻址法（Open Addressing）

• 探测方法：
  • 线性探测：index = (hash + i) % size
  • 平方探测：index = (hash + i²) % size
  • 双重哈希：index = (hash1 + i*hash2) % size

五、哈希应用场景

1. 数据结构：哈希表（字典、集合）
2. 数据校验：文件完整性验证（MD5/SHA对比）
3. 密码存储：加盐哈希保护密码
4. 区块链：比特币的区块哈希链
5. 分布式系统：一致性哈希实现负载均衡

六、高级应用：一致性哈希

解决分布式缓存扩容问题：

• 原理：将节点和数据映射到虚拟环上
• 优势：节点增减时仅影响相邻数据，避免全局重哈希

七、哈希总结

通过合理设计哈希函数和冲突解决方案，哈希表能实现接近常数时间的快速数据存取，是现代系统中最核心的数据结构之一。