perfect-hash 0.4.3

安装

最小完美哈希函数生成器是用纯Python编写的，可以使用以下命令安装：

$ pip install perfect-hash

代码支持Python 2.7和Python 3.5或更高版本。但是，一些示例不再支持Python 2。

简介

某个键集合S的完美哈希函数是一种将S中的所有键映射到不同数字的哈希函数。这意味着对于集合S，哈希函数是无碰撞的，或完美的。此外，当完美哈希函数将N个键映射到N个连续整数时，通常在0到N-1的范围内，称为“最小”完美哈希函数。

用法

给定一组键，这些键是字符字符串，程序返回一个最小完美哈希函数。默认情况下，该哈希函数以Python代码的形式返回。假设我们有一个包含键的文件

# 'animals.txt'
Elephant
Horse
Camel
Python
Dog
Cat

解析此文件的精确方式可以通过命令行选项指定，例如，可以只从包含每行不同项的文件中读取一列。程序可以这样调用

$ perfect-hash animals.txt
# =======================================================================
# ================= Python code for perfect hash function ===============
# =======================================================================

G = [0, 3, 6, 0, 4, 1, 5]

def hash_f(key, T):
    return sum(ord(T[i % 8]) * ord(c) for i, c in enumerate(key)) % 7

def perfect_hash(key):
    return (G[hash_f(key, "1mmhoNMG")] +
            G[hash_f(key, "gf53KKbH")]) % 7

# ============================ Sanity check =============================

K = ["Elephant", "Horse", "Camel", "Python", "Dog", "Cat"]
assert len(K) == 6

for h, k in enumerate(K):
    assert perfect_hash(k) == h

程序的工作方式是通过将计算参数填充到代码模板中。程序可以接收以文件形式存在的模板，并填充计算参数，这允许在任何编程语言中生成完美的哈希函数。哈希函数非常简单，不需要在目标语言中难以实现的特定于机器或语言的字节级别操作。模板中可用以下参数

由于所有编程语言的数组语法都不相同，因此可以通过命令行选项调整一些特定的内容。创建上述代码的内置模板是

G = [$G]

def hash_f(key, T):
    return sum(ord(T[i % $NS]) * ord(c) for i, c in enumerate(str(key))) % $NG

def perfect_hash(key):
    return (G[hash_f(key, "$S1")] +
            G[hash_f(key, "$S2")]) % $NG

使用代码模板，使此程序非常灵活。源代码库包括几个完整的C语言示例。在实现静态哈希表时，人们面临许多选择：参数列表是否放入单独的头文件？表API是否只包含哈希值，而不是映射的对象？等等。所有这些选择都是可能的，因为模板只是简单地填充了参数，无论模板内部还有什么。

哈希函数类型

perfect-hash 命令提供的一个重要选项是 --hft，代表“哈希函数类型”。有两种类型可供选择

1. 随机生成哈希函数，使用随机字符串作为其盐。这是默认选项。由于生成的随机哈希函数不包括足够大的输出以满足大量键（超过10,000），因此对于如此大的键，完美的哈希函数生成将失败。然而，此哈希函数的实现非常简单且快速。

2. 随机生成哈希函数，使用随机整数作为其盐。使用此选项将始终成功，但需要两个额外的整数数组（除了始终存在的数组G）。

示例

源代码库包含许多有用的示例（在examples/），说明了如何使用perfect-hash命令，以及作为库的python_hash.py。

输出许可证

perfect-hash是在BSD许可证下发布的。然而，这并不意味着perfect-hash生成的输出是在BSD下。原因是输出中只包含直接来自perfect-hash源代码的少量文本 - 如果使用默认模板，则少于10行长，这更多地用于说明目的 - 太小，不足以成为重要部分。因此，输出不是“基于perfect-hash的作品”。

perfect-hash生成的输出包含几乎所有输入数据。因此，输出是输入的“派生作品”（在美国版权法意义上的）；其版权状态取决于输入的版权。对于大多数软件许可证，结果是输出与传递给perfect-hash的输入具有相同的许可证和相同的版权所有者。

致谢

部分代码基于A.M. Kuchling编写的程序：[http://www.amk.ca/python/code/perfect-hash](http://www.amk.ca/python/code/perfect-hash)

此库基于的算法在论文“最优的最小完美哈希算法”中描述，作者为Z. J. Czech, G. Havas和B.S. Majewski。[http://cmph.sourceforge.net/papers/chm92.pdf](http://cmph.sourceforge.net/papers/chm92.pdf)

我尝试说明该算法以及它是如何工作的：[http://ilan.schnell-web.net/prog/perfect-hash/algo.html]