2.1. 散列函数原理¶

散列通常接收键值来自很大范围的记录， 并把这些记录存储到一个槽数相对较少的表中。 当两条记录散列到表中的同一个槽时，就发生了冲突。 如果在选择散列函数时我们足够仔细—或者足够幸运—， 那么实际发生的冲突数量就会很少。 不幸的是，即使在最好的情况下，冲突也几乎无法避免。 为了说明这一点，考虑一个坐满学生的教室。 某一对学生具有相同生日（即一年中的同一天，不必是同一年）的概率是多少？ 如果有 23 名学生，那么有两人生日相同的概率大约是一半。 尽管学生可能有生日的天数为 365 天（忽略闰年）。 在大多数日子里，班里没有学生过生日。 学生越多，生日相同的概率就越大。 根据生日把学生映射到日子，类似于用生日作为散列函数把记录分配到大小为 365 的表中的槽里。 注意，这一观察并没有告诉我们 哪些 学生生日相同， 也没有告诉我们是 哪几天 出现了生日相同的情况。

自己动手试试。 你可以使用这个计算器查看发生冲突的概率。 默认值设置为：房间里的人数使得出现重复生日的概率略高于 50%。 但你可以设置任意表长度和任意记录数，来确定在这些条件下的冲突概率。

使用计算器回答以下问题。

1. 房间里至少需要多少人，才能有两人生日相同的概率至少为 60%？

2. 我们需要向一个具有 1000 个槽的表中散列至少多少个项，才能有至少 50% 的概率发生冲突？

为了实用，由散列组织的数据库必须把记录存储在一个不会大到浪费空间的散列表中。 为了在时间与空间效率之间取得平衡，这意味着散列表应当 装填到约一半 。 由于在这些条件下冲突极有可能发生（偶然情况下，插入到半满表中的任何记录都有一半的概率发生冲突）， 这是否意味着我们不必担心散列函数在避免冲突方面表现得好不好呢？ 绝对不是。 在实践中，使用好的散列函数与使用差的散列函数， 在查找或插入表中时必须检查的记录数量上差别很大。 严格来说，任何把所有可能的键值映射到散列表中某个槽的函数都是散列函数。 在极端情况下，即使把所有记录都映射到数组中同一个槽的函数也是散列函数， 但它在查找操作中对我们找到记录毫无帮助。

我们希望选择一个散列函数，它把键映射到槽的方式， 能使散列表中每个槽在实际使用的键集合下具有相同的被填充概率。 不幸的是，对于给定数据库或集合中实际记录的键值分布，我们通常无法控制。 因此，任何特定散列函数表现得好不好， 取决于允许的键范围内实际使用的键分布。 在某些情况下，输入数据在其键范围内分布良好。 例如，如果输入是从键范围中均匀选取的一组随机数， 那么任何把键范围划分得使散列表中每个槽分到相等份额的散列函数， 很可能也会把输入记录均匀地分布到表中。 然而，在许多应用中，输入记录高度聚集或以其他方式分布不佳。 当输入记录在整个键范围内分布不好时， 很难设计出一个能把记录良好地分布到整个表中的散列函数， 尤其是在事先不知道输入分布的情况下。

数据值分布不佳的原因有很多。

1. 自然频率分布往往遵循一种常见模式：少数实体频繁出现， 而大多数实体出现得相对稀少。 例如，考虑美国 100 个最大城市的人口。 如果把这些人口画在数轴上，其中大多数会聚集在偏低的一侧， 少数离群值位于偏高的一侧。 这是 Zipf 分布的一个例子。 换个角度看，某个人来自某个特定大城市的可能性， 远高于来自某个特定小城镇的可能性。

2. 收集到的数据很可能以某种方式偏斜。 实地样本可能被舍入到比如最接近的 5（即所有数字都以 5 或 0 结尾）。

3. 如果输入是一组常见英语单词，首字母的分布会很差。

注意，对于本列表中的第 2 项和第 3 项， 键的高位或低位比特分布都很差。

在设计散列函数时，我们通常面临以下两种情况之一：

1. 我们对输入键的分布一无所知。 在这种情况下，我们希望选择一个散列函数， 把键范围均匀地分布到散列表上， 同时避免明显的聚集机会， 例如对键值的高位或低位比特敏感的散列函数。

2. 我们对输入键的分布有所了解。 在这种情况下，我们应当使用依赖分布的散列函数， 避免把相键值的聚集分配到同一个散列表槽中。 例如，如果对英语单词进行散列，我们应当 不 对首字符的值进行散列， 因为它很可能分布不均。

在下一个模块中，你将看到几个散列函数的例子，它们说明了这些要点。