哈希函数与哈希表

复习

　　前面查找数据，要么一个个看（O(n)），要么依赖有序后二分（O(log n)）。有没有可能一步就找到？

　　有，只要能让数据“按计算出的位置放，也按计算出的位置取”。这就是哈希表（hash table）。

　　哈希表的核心是一个哈希函数（hash function）：输入一个键（key），输出一个位置（通常是数组下标）。

　　举个最朴素的例子：把键对一个固定的表长取模，余数就是位置。

位置 = 键 除以 表长 的余数

　　存的时候，按算出的位置放；查的时候，同样按算出的位置取。中间没有比较、没有遍历，直接跳过去。

　　如果键各不相同、算出的位置也各不相同，那么存入和查找都只要一步——这就是 O(1) 的由来。它的速度，靠的正是“由键直接算位置”这件事。

　　理想很丰满，现实却总有麻烦：不同的键，可能算出同一个位置。这叫冲突（collision）。

　　冲突几乎是必然的。因为位置的数量是有限的（就那么多格子），而可能的键是无限的（名字、号码、任意字符串）。把无数种可能，塞进有限个格子，撞车在所难免。

　　所以，哈希表真正的工程设计，大半都在解决冲突：

　　这两种办法，下一章和下下章分别讲。

　　一个好的哈希函数，应该尽量让键均匀地散落到各个位置，避免大量键挤在一处。

　　同时它还要算得快——毕竟每次存取都要算一遍。如果算位置比直接查找还慢，那就本末倒置了。

　　这里也埋着一个隐患：如果哈希函数设计得不好，或者运气太差，很多键都落到同一个位置，那么查找就会退化，最坏情况下甚至退回到 O(n)。哈希表的 O(1) 是“平均”而言的，不是无条件的保证。

思考题 1

　　哈希表为什么能接近 O(1) 地查找？

思考题 2

　　为什么“冲突”在哈希表里难以完全避免？

　　因为它不靠逐个比较，而是用哈希函数从键直接算出存放位置，一步跳过去。只要冲突不多，存取都能在常数步内完成，因此平均接近 O(1)。

　　因为可用的位置数量是有限的，而可能的键是无限的，把无限多的键映射进有限的位置，必然会有不同的键落到同一位置。冲突无法根除，只能通过机制去处理和降低影响。

设计师 | 南国微雪