algorithm - 有序字符串到整数哈希函数保留其参数的字典顺序

Question

假设我们有一个字节字符串集合，像往常一样按字典顺序排序。我们想要定义一个哈希函数，将字符串映射到整数，以便哈希值的排序在足够程度上保留字符串的排序。也就是说，给定字符串 A 小于或等于字符串 B，H(A) 应该始终产生一个小于或等于 H(B) 的值。

显然，这种不太好的哈希函数是可能的。例如，我们可以采用每个字符串的固定前缀(例如 8 个字节)并将其假装为大端无符号 int64。生成的整数将按所需的顺序排序。这种方法甚至适用于较短的字符串:我们可以在短字符串中附加一些 0，使其至少为前缀字节长(但前提是我们可以假设 0 不是有效的字节值)。

不幸的是，这种潜在的解决方案虽然快速且简单，但也有很大的缺点。在字符串往往具有相当大的公共(public)前缀的情况下，它变得相当无用。当“0x00”是有意义的字节并且我们希望将较短的字符串排在较长的字符串之前时，它无法处理比所选前缀短的字符串。

所以问题是是否可以做得更好？一些算术(或者更确切地说 Knuth 的“具体数学”之类)技巧可以考虑字符串的所有字节并产生适当排序的哈希值？

Answer 1

您能做的最好的事情就是应用订单保留 arithmetic encoding ，基于您能想到的最佳字符串统计模型，然后采用其前缀来形成“哈希”代码。

根据该统计模型，每个哈希码的可能性都相同。

如果您的模型只是所有字符串都具有相同的可能性，那么这会简化为您的“仅采用前缀想法”...所以这是否对您有用实际上取决于您对字符串的了解程度以及您需要这段代码有多好。

另请注意，许多现实模型也将允许更简单的编码方案。 “只需要一个前缀”也是一个例子。

人们可能认为他们想要用这样的“哈希代码”做的大多数事情都是不切实际的——您可能最终会做其他事情。也许您想询问真正的问题，以便我们可以通过其他方式帮助解决。