当前位置：首页 > article >正文

大白话“讲”哈希表

article 2025/2/24 13:13:44

一、哈希表：像快递柜一样存取数据的神器

想象你有一个能秒找快递的智能柜子：

每个包裹都有唯一取件码（哈希函数生成）
柜子分成1000个小格子（数组存储）
取件码=格子编号（如9527号包裹放在527格）
偶尔多个包裹挤一个格子（哈希碰撞）
解决方法：要么在隔壁找空位（开放寻址），要么在格子里挂多个挂钩（链式存储）

这就是哈希表！它让数据存取快到飞起，平均只要1步就能找到目标，比翻字典快N倍。

二、三大核心部件白话解读

1. 哈希函数：数据界的身份证生成器

把各种类型数据变成数字

# 比如字符串转数字 
"张三" ➔ 2598（假设哈希值）
"李四" ➔ 7365

好函数的标准：
- 不同数据尽量不同号（少撞号）
- 算得快（像扫码枪一样"滴"就出结果）

2. 数组：整齐排列的快递柜

场景：用Python字典统计水果销量

三、真实世界中的哈希表演示

提前准备N个格子（数组长度）
哈希值对N取余就是格子号
```
2598号数据 ➔ 2598%1000=598号格子 
```
3. 冲突处理：格子满了怎么办？
链式法（格子挂挂钩）
开放寻址法（找隔壁空位）

1.场景：用Python字典统计水果销量

fruit_sales = {}
 
# 存数据（自动计算哈希）
fruit_sales["apple"] = 50    # "apple"的哈希假设是2837 
fruit_sales["banana"] = 30   # 哈希值假设是6654 
fruit_sales["orange"] = 20   # 哈希值假设是2837（碰撞了！）
 
# 底层实际存储示意图 
[
 ..., 
 2837: [("apple",50), ("orange",20)],  # 链表存储 
 6654: ("banana",30),
 ...
]

四、为什么说哈希表是万金油？

1. 查的快：直接从格子拿数据

数组下标访问 → O(1)时间复杂度
比遍历数组（O(n)）、二分查找（O(logn)）快得多

2. 用的广：程序员必备技能

去重：快速判断元素是否存在
缓存：Redis的核心数据结构
计数：统计词频/点击量
索引：数据库加速查询

3. 内存省：按需分配空间

传统数组要预分配超大空间
哈希表动态扩容（负载因子超0.75自动翻倍）

五、使用时必须知道的坑

1. 哈希碰撞攻击

恶意制造大量碰撞 → 查询退化为链表 → 服务器瘫痪
防御：改用更安全的哈希算法（如SHA-256）

2. 对象修改导致失踪

Map<User, Integer> scores = new HashMap<>();
User u = new User("张三");  // 哈希值=1234 
scores.put(u,  95);
 
u.setName(" 李四");         // 哈希值变成5678 
scores.get(u);             // 找不到！因为去5678格子找了

3. 线程安全问题

多线程同时修改可能丢数据
解决方案：用ConcurrentHashMap（分段锁技术）

六、手把手实现迷你哈希表

class SimpleHashTable:
    def __init__(self):
        self.size  = 8          # 初始8个格子 
        self.table  = [[] for _ in range(self.size)]   # 每个格子是列表 
    
    def _hash(self, key):
        return hash(key) % self.size   # Python内置哈希函数 
    
    def put(self, key, value):
        idx = self._hash(key)
        for item in self.table[idx]:   # 遍历链表 
            if item[0] == key:
                item[1] = value      # 更新已有键 
                return 
        self.table[idx].append([key,  value])  # 新增键值对 
    
    def get(self, key):
        idx = self._hash(key)
        for item in self.table[idx]: 
            if item[0] == key:
                return item[1]
        return None 
 
# 测试我们的迷你哈希表 
ht = SimpleHashTable()
ht.put("apple",  10)
ht.put("banana",  20)
print(ht.get("apple"))   # 输出10