算法打基础——HashⅡ: 全域哈希与完美哈希

在算法打基础——HashⅠ: 哈希表一文中，我们介绍了哈希表这种数据结构的基本思想及其应用。然而，在实际应用中，哈希表也会遇到一些问题，例如哈希冲突和哈希函数不尽如人意等，这些问题会降低哈希表的效率和准确性，因此需要更加高效和安全的哈希方法来解决这些问题。

本文将介绍两种高效的哈希方法：全域哈希和完美哈希。

全域哈希

全域哈希是一种构建哈希函数的方法。我们可以从一个所有可能的关键字集合中选择一个随机的哈希函数，这样就可以让我们期望任意两个值不同的元素被映射到不同的桶中。全域哈希具有较好的散列性能，能够避免意外的哈希冲突，并且对于每一个关键字，全域哈希函数的宽度是相等的。

例如下面是一个简单的全域哈希函数：

def random_hash(k, a, b, p):
    return ((a * k + b) % p) % m

其中，k是关键字，随机选取的参数a和b用于控制哈希函数的形状和随机化，p是一个较大的质数，防止哈希溢出。这样就可以将关键字k映射到哈希表H[0...m-1]中的某个位置。

然而，全域哈希并非没有缺点，例如该方法需要耗费大量的时间和空间来进行随机化计算，同时算法的性能也取决于选取的哈希函数的随机性质，如果随机性不好，那么哈希冲突的概率会增加，降低哈希表的效率。

完美哈希

另一种常见的哈希方法是完美哈希。与全域哈希不同，完美哈希可以确保每个关键字都被映射到不同的桶中，并且不需要进行随机化计算，因此具有优秀的效率和准确性。

完美哈希的基本思想是通过一个两级哈希函数来对关键字进行哈希映射。首先使用一个哈希函数h将关键字哈希成一个整数，然后使用另一个哈希函数g将整数哈希到哈希表的某个位置。需要注意的是，关键字集合中的每个元素都必须按照相同的顺序进行哈希，以便能够构建完美哈希函数。

完美哈希的创建方法有几种，例如基于静态矩阵的 perfect hashing 和使用动态哈希表的 cuckoo hashing 等。其中，在静态哈希表中完美哈希通常比较容易构建和实现，而在动态哈希表中完美哈希则复杂一些，需要用到更高级的技术。

结语

哈希方法是一种重要的算法和数据结构，能够在实际应用中提高程序的效率和可靠性。全域哈希和完美哈希是两种常见的哈希方法，各有优缺点，应该根据具体应用场景进行选择和计算。