保序散列函数
Hash Function with Order Preserving
是否有任何具有 uniq 哈希码（如 MD5）且保留顺序的哈希函数？
注意：
我不关心安全性，我需要它来排序，我有很多块（~1MB 大小），我想对它们进行排序，当然我可以使用索引排序，但我想减少比较时间
理论上：
如果我有 1'000'000 个大小为 1MB（1'048'576 字节）的块，并且所有块在最后 10 个字节中都有差异，那么一个块与另一个块的比较时间将为 O(n-10)，如果我将使用 QuictSort（进行 ~(nlog2(n)) 比较）然后比较的总时间将为 nlog2(n)*(k-10)（其中 k 是块大小)
1'000'000 * 20 * (1'048'576 - 10)
这就是为什么我想生成一次固定大小（例如 16 字节）的顺序保留哈希码，然后对块进行排序并保存结果（例如：在文件中）
一般情况下，这样的函数是不可能的，除非散列的大小至少是对象的大小。
这个论点很简单：如果有 N 个对象但 M < N 哈希值，根据 pigeonhole principle，两个不同的对象映射到一个哈希值，因此它们的顺序不被保留。
但是，如果我们保证了对象的其他属性或放宽了要求，则自定义或概率解决方案可能成为可能。
理论上是没有的。如果需要，您可以创建一个组合哈希：
index:md5
我认为这将解决您的需求。
对每个长度为 K 的 N 个字符串数组进行排序只需 O (NK) 或 O (N^2 + NK) 个字符比较即可完成。
例如构造一个trie.
或者做一种插入排序。通过向其中一个接一个地添加字符串来构建已排序字符串集 S。对于每个新字符串 P，遍历它，维护 S 中最大字符串 Q 的（非递减）索引，使得 Q <= P。当字符串 P 结束时，将其插入 S 紧跟在 Q 之后。每个 O(N) 插入都可以在 O(N+K) 操作中完成： O(N) 次增加索引分布到 K.
当您有按排序顺序排列的字符串索引时，只需将它们用于您的目的，而不是您想要的 "hashes"。
根据 NIST（我不是专家），Pearson 散列可以保序。哈希使用辅助table。这样的 table 可以（理论上）构造成使得生成的散列保持顺序。
虽然它不能满足您的全部要求，因为它没有按照您的意愿减小尺寸。我发布这个以防其他人正在寻找解决方案。
一些建议：
CHM（Z.J. Czech, G. Havas, and B.S. Majewski）是一种生成最小完美散列的算法，该散列保留顺序（例如，如果 A < B，则 h( A) < h(B))。每个密钥使用大约 8 个字节的存储空间。
让我们根据需求构造这样一个函数：
您需要一个输出 16 字节散列的函数。所以你会有碰撞。你无法保持完美的秩序，你也不想这样做。你能做的最好的是：
H(x) < H(y) => x < y
H(x) > H(y) => x > y
彼此接近的值将具有相同的哈希值。
- 对于每个 x 都有一个 i_x > 0，因此
H(x) = H(x + i_x) < H(x + i_x + 1)。 （除了 x + i_x + 1 会溢出您的 1MB 块的结尾。）
扩展你得到：H(x) < H(x + i_x + n) 任何 n > 0。
相同的参数适用于 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
- 您希望散列值的分布更均匀或更不均匀。否则，一个人会比另一个人发生更多的碰撞，并且当该值被击中时，您将花费所有时间进行全面比较。所以所有段 [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)。
是否有任何具有 uniq 哈希码（如 MD5）且保留顺序的哈希函数？
注意： 我不关心安全性，我需要它来排序，我有很多块（~1MB 大小），我想对它们进行排序，当然我可以使用索引排序，但我想减少比较时间
理论上： 如果我有 1'000'000 个大小为 1MB（1'048'576 字节）的块，并且所有块在最后 10 个字节中都有差异，那么一个块与另一个块的比较时间将为 O(n-10)，如果我将使用 QuictSort（进行 ~(nlog2(n)) 比较）然后比较的总时间将为 nlog2(n)*(k-10)（其中 k 是块大小) 1'000'000 * 20 * (1'048'576 - 10)
这就是为什么我想生成一次固定大小（例如 16 字节）的顺序保留哈希码，然后对块进行排序并保存结果（例如：在文件中）
一般情况下，这样的函数是不可能的，除非散列的大小至少是对象的大小。
这个论点很简单：如果有 N 个对象但 M < N 哈希值，根据 pigeonhole principle，两个不同的对象映射到一个哈希值，因此它们的顺序不被保留。
但是，如果我们保证了对象的其他属性或放宽了要求，则自定义或概率解决方案可能成为可能。
理论上是没有的。如果需要，您可以创建一个组合哈希：
index:md5
我认为这将解决您的需求。
对每个长度为 K 的 N 个字符串数组进行排序只需 O (NK) 或 O (N^2 + NK) 个字符比较即可完成。
例如构造一个trie.
或者做一种插入排序。通过向其中一个接一个地添加字符串来构建已排序字符串集 S。对于每个新字符串 P，遍历它，维护 S 中最大字符串 Q 的（非递减）索引，使得 Q <= P。当字符串 P 结束时，将其插入 S 紧跟在 Q 之后。每个 O(N) 插入都可以在 O(N+K) 操作中完成： O(N) 次增加索引分布到 K.
当您有按排序顺序排列的字符串索引时，只需将它们用于您的目的，而不是您想要的 "hashes"。
根据 NIST（我不是专家），Pearson 散列可以保序。哈希使用辅助table。这样的 table 可以（理论上）构造成使得生成的散列保持顺序。
虽然它不能满足您的全部要求，因为它没有按照您的意愿减小尺寸。我发布这个以防其他人正在寻找解决方案。
一些建议：
CHM（Z.J. Czech, G. Havas, and B.S. Majewski）是一种生成最小完美散列的算法，该散列保留顺序（例如，如果 A < B，则 h( A) < h(B))。每个密钥使用大约 8 个字节的存储空间。
让我们根据需求构造这样一个函数：
您需要一个输出 16 字节散列的函数。所以你会有碰撞。你无法保持完美的秩序，你也不想这样做。你能做的最好的是：
H(x) < H(y) => x < y
H(x) > H(y) => x > y
彼此接近的值将具有相同的哈希值。
- 对于每个 x 都有一个 i_x > 0，因此
H(x) = H(x + i_x) < H(x + i_x + 1)。 （除了x + i_x + 1会溢出您的 1MB 块的结尾。）
扩展你得到：H(x) < H(x + i_x + n) 任何 n > 0。
相同的参数适用于 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
- 您希望散列值的分布更均匀或更不均匀。否则，一个人会比另一个人发生更多的碰撞，并且当该值被击中时，您将花费所有时间进行全面比较。所以所有段 [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)。