为什么哈希能让键值对数据的访问速度比原始数据对更快？

首先得先搞清楚不用哈希的情况下，键值对的访问是什么水平：
如果直接用原始key存储，要查询某个key对应的value时，无非两种实现方案：

1. 用无序结构存储：每次查询要遍历所有已存的键值对逐个匹配，时间复杂度O(n)，数据量过万之后性能就会出现明显下降
2. 用有序结构（比如平衡二叉树、跳表）存储：查询时间复杂度O(logn)，虽然比O(n)好很多，但性能还是会随着数据量增长持续下降

你说的没错，哈希函数的输出确实就是普通整数区间，但它解决了两个核心问题：

• 把任意类型的key转换成可直接用于数组寻址的下标：数组是内存中唯一支持*O(1)*时间随机访问的结构，只要你能拿到合法的数组下标，就能直接定位到对应内存地址，完全不需要遍历或者逐层查找。哈希函数的本质就是把字符串、浮点数、自定义对象这类没法直接当下标的原始key，转换成符合数组下标要求的整数。实际实现中一般还会对哈希值再做一次取模（或者位运算，性能更高），让结果落在当前存储数组的下标范围内。
• 统一所有key类型的处理逻辑：不管你的key是邮箱字符串、身份证号、二进制的文件内容，存储层都不需要关心原始key的格式，只要统一处理哈希输出的整数即可，整个键值对系统的实现逻辑可以高度复用。

举个最简单的字符串哈希实现示例：

def simple_str_hash(key: str, array_len: int) -> int:
    hash_val = 0
    for char in key:
        hash_val = hash_val * 31 + ord(char)
    # 数组长度为2的幂次时用位运算替代取模，性能更高
    return hash_val & (array_len - 1) if (array_len & (array_len - 1)) == 0 else hash_val % array_len

当然你可能会想到哈希冲突的问题：确实存在两个不同的原始key算出同一个哈希值的情况，但只要哈希函数设计合理，冲突概率极低，配合链式哈希、开放寻址这类成熟的冲突解决方案，平均访问复杂度仍然可以接近O(1)，性能远高于无哈希的实现方案。

举个实际的例子：假设你存了100万条用户数据，key是用户的11位手机号字符串，不用哈希的话最坏情况要做100万次字符串匹配才能查到结果；用哈希的话，只需要做1次哈希计算，直接定位到数组的对应位置，最多做1~2次冲突key的匹配就能拿到结果，性能差了好几个数量级。

内容的提问来源于stack exchange，提问作者pphero0287