哈希函数 -- 来自 - 数学天地

哈希函数将来自包含许多（甚至无限数量）成员的集合的值投影到来自包含固定数量（较少）成员的集合的值。哈希函数是不可逆的。例如，哈希函数可以定义为，其中，，并且是向下取整函数。

哈希函数可以用于确定两个对象是否相等（可能具有固定的平均错误数）。哈希函数的其他常见用途包括对大量数据进行校验和（例如，循环冗余校验 [CRC]）以及通过键值在数据库中查找条目。UNIX c-shell (csh) 使用哈希表来存储可执行程序的位置。因此，在用户的搜索路径中添加新的可执行程序需要使用以下命令重新生成哈希表rehash命令，然后才能在不指定完整路径的情况下执行这些程序。

为了说明哈希函数在数据库查找中的应用，请考虑一个数据库，该数据库由一个包含索引、名称和电话号码的数组组成，名称以任意顺序排列。

	名称	号码
0	Parker	12345
1	(空)
2	Davis	43534
3	Harris	32452
4	Corea	46532
5	Hancock	96562
6	Brecker	37811
7	(空)
	Marsalis	54323

要在此数组中查找 Hancock，您需要从数组的开头开始，比较名称，然后尝试下一个，直到名称匹配。这种非常简单的算法可以在 1 到步内找到任何条目，平均查找时间为。因此，查找时间与成正比。如果数据库已排序，通常可以获得更快的速度。

	名称
0	Brecker
1	Corea
2	Davis
3	Hancock
4	Harris
5	Marsalis
6	Parker
7	(空)
	(空)

在这种排序数组上的高效算法首先检查条目，然后递归地使用二分法检查区间或中的条目，具体取决于最近查找的名称是在要查找的名称之前还是之后。此过程的平均查找时间与成正比。

在此处使用哈希函数的想法是，尽管名称中字符组合的可能数量非常大，但在实践中通常只找到其中的一个子集（即，像“Kwqrst”这样的名称远不如像“Jones”这样的名称常见）。因此，当您将条目插入数据库中的索引时，该索引可以使用键来计算（在您搜索它时也可以使用该键），您稍后可能会在您检查的第一个位置找到它。

考虑以下简单示例，其中哈希函数只是名称中字符的 ASCII 代码之和（假设全部为小写），计算结果模。

名称
Brecker	6
Corea	2
Davis	2
Hancock	12
Harris	12
Marsalis	2
Parker	8

上面的例子说明了哈希函数对于不同的键可以给出相同的结果。通常通过引入第二个哈希函数来规避这个困难，该哈希函数的结果被设计为与的结果完全不同。为了说明目的，让为 1 加上名称中所有代码的按位异或（再次全部取小写）模。

名称
Brecker	11
Corea	3
Davis	10
Hancock	4
Harris	8
Marsalis	3
Parker	8

然后可以将新索引计算为第一个索引和的总和（模），直到找到可以存储新数据的空槽。请注意，当使用作为偏移量来遍历数据库时，通常不能保证任何键最终都会到达任何槽。但是，对于的某些值，即素数，确实保证了这种行为，因此始终被选择为素数。在使用（（素数））计算后，对于按字母顺序添加的名称，上面的电话列表将如下所示。