一、哈希表

哈希表（hash table），又称散列表，它通过建立键key与值value之间的映射，实现高效的元素查询。

元素查询效率对比

数组 链表 哈希表
查找元素 O(n) O(n) O(1)
添加元素 O(1) O(1) O(1)
删除元素 O(n) O(n) O(1)

观察发现，在哈希表中进行增删查改的时间复杂度都是 O(1) ，非常高效。

1、哈希表常用操作

哈希表的常见操作包括：初始化、查询操作、添加键值对和删除键值对等，示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 初始化哈希表
hmap: dict = {}

# 添加元素
hmap[1] = "小明"
hmap[2] = "小红"
hmap[3] = "小绿"

# 查询元素
name: str = hmap[1]

# 删除元素
hmap.pop(2)

# 遍历哈希表
for k, v in hmap.items():
    print(f'{k} = {v}')
2、哈希冲突与扩容

从本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况。

容易想到，哈希表容量 n 越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，我们可以通过扩容哈希表来减少哈希冲突。

负载因子（load factor）是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。例如在 Java 中，当负载因子超过 0.75 时，系统会将哈希表扩容至原先的 2 倍。

二、哈希冲突

1、链式地址

在原始哈希表中，每个桶仅能存储一个键值对。链式地址（separate chaining）将单个元素转换为链表，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中。

链式地址

链式地址存在以下局限性。

  • 占用空间增大
  • 查询效率降低：因为需要线性遍历链表来查找对应元素。
2、开放寻址
  1. 线性探测
  2. 平方探测
  3. 多次哈希

详情见：哈希冲突

三、哈希算法

1、常见哈希算法
MD5 SHA-1 SHA-2 SHA-3
推出时间 1992 1995 2002 2008
输出长度 128 bit 160 bit 256/512 bit 224/256/384/512 bit
哈希冲突 较多 较多 很少 很少
安全等级 低，已被成功攻击 低，已被成功攻击 高 高
应用 已被弃用，仍用于数据完整性检查 已被弃用 加密货币交易验证、数字签名等 可用于替代 SHA-2

2、数据结构的哈希值

以 Python 为例，我们可以调用 hash() 函数来计算各种数据类型的哈希值。

  • 整数和布尔量的哈希值就是其本身。
  • 浮点数和字符串的哈希值计算较为复杂，有兴趣的读者请自行学习。
  • 元组的哈希值是对其中每一个元素进行哈希，然后将这些哈希值组合起来，得到单一的哈希值。
  • 对象的哈希值基于其内存地址生成。通过重写对象的哈希方法，可实现基于内容生成哈希值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
num = 2
print(hash(num))

bol = True
print(hash(bol))

dec = 3.1415926
print(hash(dec))

s = "哈希算法"
print(hash(s))

tup = (1, 2, 3)
print(hash(tup))

obj = ListNode(1)
print(hash(obj))

只有不可变对象才可以作为哈希表的key

对象的哈希值通常是基于内存地址生成的

Python解释器在每次启动时，都会为字符串哈希函数加入一个随机的盐（salt）值。