哈希函数与保序性

Question

有没有一种哈希函数可以生成唯一的哈希码（类似于MD5），并且能够保持顺序？

注意： 我不关心安全性，我需要它来进行排序，我有许多大小约为1MB的数据块，我想对它们进行排序，当然我可以使用索引排序，但我想减少比较时间。

理论上： 如果我有100万个大小为1MB（1,048,576字节）的数据块，并且它们所有的差异都在最后10个字节，则一个块与另一个块的比较时间将是O(n-10)。如果我使用快速排序（使~(nlog2(n))次比较），则总比较时间将为nlog2(n)*(k-10)（其中k是块大小） 1'000'000 * 20 * (1'048'576 - 10)

这就是为什么我想要生成固定大小（例如16字节）的具有顺序的哈希码，一次将数据块排序并保存结果（例如：在文件中）。

- Simon

---

你希望用这个哈希函数做什么？ - Persixty

哈希的唯一目的是洗牌，现在你想要保留顺序... - Jason Hu

我觉得这是一个 XY 问题。OP 在误导我们。 - Jason Hu

Answer 1

CHM是一个算法，它生成保留顺序的最小完美哈希函数（例如，如果A < B，则h(A) < h(B)）。每个键大约需要使用8个字节的存储空间。

参见：http://cmph.sourceforge.net/chm.html

- Brian Long

---

CHM需要预先知道密钥。 - amirouche

Answer 2

一般情况下，除非哈希的大小至少与对象的大小相同，否则不可能存在这样的函数。

这个论点很简单：如果有N个对象但M < N个哈希值，根据pigeonhole principle，两个不同的对象被映射到一个哈希值，因此它们的顺序不会被保留。

然而，如果我们保证对象具有附加属性或放宽要求，则可能出现自定义或概率解决方案。

- Gassa

---

是的，我知道，但16字节（128位）有非常大的空间，如果在范围340282366920938463463374607431768211456内有两个相同的哈希码，对我来说没问题 :) - Simon

为了确保在A < B的情况下hash(A) <= hash(B)，可以使用对象的前16个字节作为哈希。对于你的特定数据集来说，这16个字节有多大可能相等呢？也许你正在试图解决一个不存在的问题。 - Gassa

Gassa，感谢您的答复，但正如我上面所提到的一样理论上：可以有1'000'0000个大小为1MB（每个）的块，它们之间只有最后10个字节不同。 - Simon

在一般情况下是不可能的，但是无碰撞哈希也是如此，实际上我们不必担心碰撞的概率非常小。对原始问题的合理解释是针对一个严格保持顺序的哈希，只要没有碰撞。 - Ian Goldby

Answer 3

根据NIST（我不是专家）的说法，Pearson哈希可以保持顺序。该哈希使用辅助表。这样的表格可以（理论上）构建，以使得生成的哈希保持顺序。

但它并没有完全满足您的要求，因为它不能像您想要的那样缩小大小。我发布这个帖子，以防其他人正在寻找解决方案。

一些指针：

- NIST页面：http://xlinux.nist.gov/dads/HTML/pearsonshash.html - 维基百科：http://en.wikipedia.org/wiki/Pearson_hashing - 最初的Pearson Hash论文：http://cs.mwsu.edu/~griffin/courses/2133/downloads/Spring11/p677-pearson.pdf

- L. Blanc

---

@l-blanc 我认为皮尔逊不可能像你描述的那样轻易地被操纵。辅助表应该是完全随机的。如果你读过皮尔逊的论文，你会发现他试图通过反复试验来操纵表格以实现对仅有31个单词的完美哈希处理。而且所得到的哈希值只有1个字节长。我认为要将其扩展到一般情况（输出大于8位），几乎是不可能的。 - Paul Uszak

Answer 4

对于长度为K的N个字符串数组进行排序，可以通过O(NK)或O(N^2 + NK)次字符比较来完成。

例如，构建一个trie字典树。

或者进行一种插入排序。通过逐个添加字符串到已排序的字符串集合S中来构造它。对于每个新字符串P，遍历它，并维护在S中最大的字符串Q的（非递减）索引，使得Q <= P。当字符串P结束时，在Q之后将其插入到S中。每个O(N)的插入都可以在O(N+K)操作内完成：O(N)次增加索引分配到K。

---

当您拥有按排序顺序排列的字符串的索引时，只需将它们用于您的目的，而不是您想要的“哈希”即可。

- Gassa

Answer 5

让我们根据要求构建这样一个函数：

1. 您需要一个输出16字节哈希值的函数。因此，会存在碰撞。您无法保留完美的顺序，也不想这样做。您能做到的最好的是:

   H(x) < H(y) => x < y

   H(x) > H(y) => x > y

接近的值将具有相同的哈希值。

2. 对于每个x，存在一个i_x > 0，使得H(x) = H(x + i_x) < H(x + i_x + 1)。（除了末尾，因为x + i_x + 1会超出1MB的块。）

扩展后，您可以得到：对于任何n > 0，都有H(x) < H(x + i_x + n)。

另一方向上，j_x > 0的情况也适用于相同的论证。将它们结合起来，您就得到了：

H(x - j_x) == H(x - j_x + 1) == ... == H(x + i_x - 1) == H(x + i_x)

换句话说，对于每个哈希值，都有一个单独的段[a，b]映射到相同的值。在此段之外的任何值都不能具有相同的哈希值，否则将违反排序规则。

您的哈希函数可以由您选择的段来描述：

让a_i为1MB块，其中0 <= i < 256^16且a_i <= a_i+1。然后，您的哈希函数就被描述为：

H(x) = i where a_i <= x < a_i+1

3. 你需要一个更加均匀的哈希值分布。否则，某些哈希值会比其他值多得多，当命中这些值时，您将花费大量时间进行完全比较。因此，所有的段[a，b]应该大致相同大小。

要确保每个段的大小完全相同的唯一方法是使用：

a_i = i * 2 ^ (1MB - 16)

换句话说：H(x) = x的前16个字节。

任何其他保持顺序的哈希函数，其输出为16字节，对于随机输入块集合来说都不够高效。

是的，如果除了每个输入块的最后几位之外，所有其他位都相同，那么每个测试都会发生冲突。这是一种始终存在的最坏情况。如果您知道您的输入不是均匀随机的，则可以调整每个段的大小以具有相同的命中概率。但这需要了解可能的输入。

注意：如果您真的想要对1'000'000个1MB块进行排序，并担心这样的最坏情况，那么您可以使用桶排序，每次结果为1,000,000 * 1'048'576（字节）比较。如果您一次比较16位值，则其中一半仍具有合理数量的桶（65536）。

- Goswin von Brederlow

Answer 6

理论上不存在这样的事情。如果您想要，可以创建一个组合哈希：

索引：MD5

我认为这将解决您的需求。

- mihai.ciorobea

---

不要使用insex:md5(n)，因为这样将无法仅通过md5(n)搜索数据。 - Simon

我希望使用保留顺序的哈希表，因为我想能够根据某些条件搜索数据，例如：如果我想迭代大于N的数据，则可以通过哈希码大于哈希(N)来搜索和迭代数据。 - Simon