哈希表

什么是哈希表
哈希函数
冲突与解决方案
查询数据
性能与填装因子
应用案例

什么是哈希表

哈希表（也叫散列表）是一种通过哈希函数将键映射到数组位置，从而实现快速查找的数据结构。它可能是最有用的复杂数据结构——Python 的字典（dict）、Java 的 HashMap、JavaScript 的对象都是哈希表。

哈希表存储的是键值对（key-value），比如：

键(key)    值(value)
─────────  ─────────
"apple"  → 0.67
"milk"   → 1.49
"avocado"→ 1.49

哈希函数

哈希函数是哈希表的核心。它接收一个键，返回一个数字（数组索引）。好的哈希函数满足两个要求：

一致的：同样的输入总是返回同样的数字
映射均匀：不同的输入尽量映射到不同的位置

存储过程（以 5 个箱子的数组为例）：

第1步: 计算键的哈希值
  Hash("Joe") = 4928

第2步: 用哈希值对数组长度取余（mod 运算），得到存储位置
  4928 mod 5 = 3

第3步: 存入 3 号箱子

  箱子:  0    1     2    3      4
       [   ] [   ] [   ] [Joe M] [   ]
                              ↑
                           存入这里

重复这个过程存储其他数据：

  箱子:  0    1      2    3      4
       [   ] [Sue F] [   ] [Joe M] [Dan M]

冲突与解决方案

几乎不可能编写出完全不冲突的哈希函数。当两个键映射到同一个位置时，就发生了冲突。

Nell 的哈希值为 6276，6276 mod 5 = 1
但 1 号箱子已经有 Sue 了！

  箱子:  0    1        2    3      4
       [   ] [Sue F]  [   ] [Joe M] [Dan M]
              ↑
          Nell 也要放这里 → 冲突！

链地址法：在冲突的位置存储一个链表。

  箱子:  0    1              2    3                   4
       [   ] [Sue → Nell]   [   ] [Joe → Ally → Bob]  [Dan]
              ↑ 链表               ↑ 链表

开放地址法：冲突时计算下一个候补位置，直到找到空位。

查询数据

查询 Dan 的性别：

1. Hash("Dan") = 1539, 1539 mod 5 = 4
2. 查看 4 号箱子 → 键是 Dan → 找到了！值是 M

查询 Ally 的性别：

1. Hash("Ally") = 9143, 9143 mod 5 = 3
2. 查看 3 号箱子 → 键是 Joe，不是 Ally
3. 顺着链表找 → Joe → Ally → 找到了！值是 F

性能与填装因子

操作	平均情况	最糟情况
查找	O(1)	O(n)
插入	O(1)	O(n)
删除	O(1)	O(n)

平均情况下，哈希表的各种操作都是 O(1)——常量时间，不管表有多大都一样快。最糟情况（所有键都映射到同一位置）退化为 O(n)。

填装因子 = 元素数 / 位置总数。

填装因子 = 0.4（5个位置中用了2个）→ 比较空，冲突少

  [   ] [■] [   ] [■] [   ]

经验规则：一旦填装因子超过 0.7，就该调整散列表的长度（通常增长一倍），然后重新哈希所有元素。

应用案例

模拟映射关系：电话簿（姓名→电话）、DNS 解析（网址→IP）

phone_book = {}
phone_book["jenny"] = 8675309
phone_book["emergency"] = 911
print(phone_book["jenny"])  # 8675309

防止重复：投票站检查是否已投票

voted = {}
def check_voter(name):
    if voted.get(name):
        print("kick them out!")
    else:
        voted[name] = True
        print("let them vote!")

缓存：网站将计算结果记住，避免重复计算

cache = {}
def get_page(url):
    if cache.get(url):
        return cache[url]      # 直接返回缓存
    data = get_data_from_server(url)
    cache[url] = data          # 存入缓存
    return data

小结

哈希表 = 哈希函数 + 数组，用键快速定位值
冲突不可避免，用链地址法或开放地址法解决
平均情况下查找、插入、删除都是 O(1)
填装因子超过 0.7 就需要扩容
适合模拟映射、防止重复、缓存数据

哈希表

#哈希表

#什么是哈希表

#哈希函数

#冲突与解决方案

#查询数据

#性能与填装因子

#应用案例

#小结

哈希表