哈希函数与哈希表

正如本章引言中所述，在机器学习 (machine learning)中，高效处理大量数据是一项常规要求。设想一下，您可能需要快速查找配置参数 (parameter)、存储特征计数，或者检查特定数据点是否已被处理。在数百万甚至数十亿条数据中快速完成这些操作，需要专门的数据结构。正是在这种情况下，哈希函数和哈希表发挥作用，提供了一种高效的数据访问方法。

什么是哈希函数？

其本质是，哈希函数是一种数学函数，它接收一个输入项（可以是数字、字符串，甚至是复杂对象），并从中计算出一个固定大小的数值。这个输出值被称为哈希码或简称哈希值。

可以把它想象成根据学生ID为每位学生（输入项）分配一个独特的储物柜号码（哈希码）。目的是快速查找学生的物品存放在哪里。

一个好的哈希函数通常具有以下特征：

1. 确定性： 相同的输入项必须始终生成相同的哈希码。如果今天对'user_id_123'进行哈希处理得到42，那么它必须总是得到42。
2. 计算高效： 哈希函数应快速计算。我们不希望找到“储物柜号码”的过程比遍历所有储物柜耗时更长！
3. 均匀分布： 哈希函数应尽可能均匀地将输入项分布到所有可能的哈希码范围内。这有助于减少冲突，我们很快就会探讨这一点。其目的是避免将许多项聚集到少数几个哈希码中，而让其他哈希码空着。

例如，一个针对非负整数的非常简单的哈希函数可能会使用模运算符：

def simple_hash(key, table_size):
  """一个使用模运算符的基本哈希函数。"""
  return key % table_size

如果我们的table_size是10，键123将哈希到 $123 \pmod{10} = 3$，而键4567将哈希到 $4567 \pmod{10} = 7$。对于字符串，一种基本方法可能涉及对字符编码求和：

def simple_string_hash(key, table_size):
  """一个针对字符串的基本哈希函数。"""
  hash_value = 0
  for char in key:
    hash_value += ord(char) # ord() 返回 ASCII/Unicode 值
  return hash_value % table_size

尽管简单，这些示例可能不会非常均匀地分布键。数据结构和库中使用的哈希函数更为精密，以确保更好的分布特性。Python 内置的 hash() 函数为对象提供了通用哈希码，适合在单个进程中用于字典和集合。然而，请注意，出于安全原因（哈希随机化），其输出在不同 Python 版本之间，甚至在不同运行之间都可能改变，因此它不适用于需要持久化或分布式哈希的应用（例如跨多个服务器的一致性哈希或加密用途）。"

哈希表：哈希函数的应用

哈希表（在不同语言中常被称为哈希映射、字典或关联数组）是一种数据结构，它采用哈希函数高效地将键映射到值。它将哈希函数与底层数组（常称为桶或槽）结合使用。

存储或检索键值对的过程如下：

1. 哈希处理： 键通过哈希函数处理，生成哈希码。
2. 索引生成： 该哈希码被转换为底层数组中的有效索引。一种常见方法是 index = hash_code % array_size。
3. 存储/检索： 键（如果存储，则及其关联值）被放置或检索自计算所得索引处的数组槽位。

使用哈希函数和取模运算，将一个键（'user_id_123'）映射到哈希表数组中的一个索引（7）。

哈希表的主要优势在于其速度。如果哈希函数均匀分布键，且表足够大，那么键的插入、删除和查找的平均时间复杂度非常快：$O(1)$，即常数时间。这意味着即使您向表中添加更多项目，所需时间也不会显著增加。与在未排序列表中查找（$O(n)$）或甚至平衡二叉搜索树中查找（$O(\log n)$）相比，这是一个重要的提升。

常见数据结构的平均时间复杂度。请注意，Y轴上的对数刻度显示了哈希表（$O(1)$）在这些操作中与线性（$O(n)$）和对数（$O(\log n)$）结构的效率对比。

不可避免的问题：冲突

如果两个不同的键哈希到同一个索引会怎样？例如，使用simple_hash且table_size = 10时，键123和53都会哈希到索引3。这被称为冲突。

冲突在实践中是无法避免的，特别是当可能键的数量远大于哈希表中槽的数量时（通常就是这种情况）。这与抽屉原理有关：如果您有更多的鸽子（键）比鸽笼（数组槽）多，那么至少一个鸽笼必须包含不止一只鸽子。

哈希表如何处理冲突对其性能的保持非常重要。如果冲突过于频繁或处理效率低下，性能会显著下降，有时甚至在最坏情况下（例如，所有键都哈希到同一个索引）接近简单列表的 $O(n)$ 行为。

在 Python 中，内置的 dict（字典）和 set 类型是使用精密的哈希表实现的。它们在查找、插入和删除方面的普遍出色表现直接来源于底层的哈希表结构和高效的冲突处理机制。

我们现在已经明确了基本要点：哈希函数将键映射到索引，哈希表使用这些索引在数组中进行快速访问。下一个重要步骤是了解如何有效管理不可避免的冲突，这将在下一节中介绍。