6

关于 SO 的另一个问题提出了一些语言的工具来散列字符串，以便在表中快速查找。这方面的两个示例是 .NET 中的字典<> 和 Python 中的 {} 存储结构。其他语言当然支持这种机制。C++ 有它的映射，LISP 有一个等价物，就像大多数其他现代语言一样。

在对字符串的哈希算法可以在恒定时间内进行的问题的答案中提出了争议，一位拥有 25 年编程经验的 SO 成员声称任何东西都可以在恒定时间内进行哈希处理。我个人的观点是，这不是真的，除非您的特定应用程序在字符串长度上设置了边界。这意味着某个常数 K 将决定字符串的最大长度。

我熟悉 Rabin-Karp 算法，它使用散列函数进行操作，但该算法并没有规定要使用特定的散列函数，作者建议的是 O(m)，其中 m 是哈希字符串。

我看到其他一些页面，例如这个（http://www.cse.yorku.ca/~oz/hash.html）显示一些哈希算法，但似乎每个页面都在字符串的整个长度上进行迭代达到它的价值。

从我对该主题的相对有限的阅读来看，似乎大多数字符串类型的关联数组实际上是使用散列函数创建的，该函数在引擎盖下使用某种树进行操作。这可能是指向键/值对中值元素位置的 AVL 树或红/黑树。

即使使用这种树结构，如果我们要保持在 theta(log(n)) 的顺序上，其中 n 是树中元素的数量，我们需要有一个恒定时间的哈希算法。否则，我们有迭代字符串的附加惩罚。即使对于包含许多字符串的索引，theta(m) 会被 theta(log(n)) 黯然失色，但如果我们处于这样一个域中，我们搜索的文本将非常大，我们也不能忽略它。

我知道后缀树/数组和 Aho-Corasick 可以将搜索降低到 theta(m) 以获得更大的内存开销，但我要特别问的是，对于任意长度的字符串是否存在恒定时间哈希方法由其他 SO 成员声明。

谢谢。

4

7 回答 7

7

哈希函数不必（也不能）为每个字符串返回唯一值。

您可以使用前 10 个字符来初始化随机数生成器，然后使用它从字符串中提取 100 个随机字符，然后对其进行哈希处理。这将是恒定的时间。

您也可以只返回常量值 1。严格来说，这仍然是一个哈希函数，虽然不是很有用。

于 2009-12-07T18:39:20.380 回答
5

一般来说，我相信任何完整的字符串哈希都必须使用字符串的每个字符，因此对于 n 个字符需要增长为 O(n)。但是我认为对于实际的字符串哈希，您可以使用可以轻松为 O(1) 的近似哈希。

考虑一个始终使用 Min(n, 20) 个字符来计算标准哈希的字符串哈希。显然，这随着字符串大小的增加而增长为 O(1)。它会可靠地工作吗？这取决于您的域...

于 2009-12-07T18:39:57.697 回答
3

如果不冒严重的哈希冲突的风险，您将无法轻松地为字符串实现通用的恒定时间哈希算法。

对于恒定时间，您将无法访问字符串中的每个字符。作为一个简单的例子，假设我们取前 6 个字符。然后有人来尝试散列 URL 数组。has 函数将看到每个字符串的“http://”。

其他字符选择方案可能会出现类似的情况。您可以根据前一个字符的值伪随机地选择字符，但是如果字符串由于某种原因具有“错误”模式并且许多最终具有相同的哈希值，您仍然冒着失败的风险。

于 2009-12-07T18:50:24.260 回答
1

如果您使用绳索而不是字符串并且共享允许您跳过一些计算，您可以希望渐近小于线性哈希时间。但显然哈希函数不能分离它没有读取的输入，所以我不会太认真地对待“所有东西都可以在恒定时间内进行哈希处理”。

在散列函数的质量和它所需要的计算量之间妥协是可能的，而且长字符串上的散列函数无论如何都必须有冲突。

如果散列函数只查看前缀，您必须确定算法中可能出现的字符串是否会经常发生冲突。

于 2009-12-07T18:39:36.263 回答
1

虽然我无法想象无限长度字符串的固定时间哈希函数，但实际上没有必要。

使用散列函数背后的想法是生成散列值的分布，这使得许多字符串不太可能发生冲突- 对于所考虑的域。该密钥将允许直接访问数据存储。这两个组合导致平均时间查找是恒定的。

如果发生这样的冲突，查找算法将退回到更灵活的查找子策略。

于 2009-12-07T18:50:11.673 回答
1

当然，这是可行的，只要您确保所有字符串都被“留存”，然后再将它们传递给需要散列的东西。实习是将字符串插入字符串表的过程，这样所有具有相同值的实习字符串实际上都是同一个对象。然后，您可以简单地将（固定长度）指针散列到内部字符串，而不是散列字符串本身。

于 2009-12-08T16:02:07.177 回答
1

您可能对我去年提出的以下数学结果感兴趣。

考虑将无限数量的键（例如任意长度的所有字符串的集合）散列到 {1,2,…,b} 中的数字集合的问题。随机散列首先在 H 函数族中随机选取一个散列函数 h。

I will show that there is always an infinite number of keys that are certain to collide over all H functions, that is, they always have the same hash value for all hash functions.

Pick any hash function h: there is at least one hash value y such that the set A={s:h(s)=y} is infinite, that is, you have infinitely many strings colliding. Pick any other hash function h‘ and hash the keys in the set A. There is at least one hash value y‘ such that the set A‘={s is in A: h‘(s)=y‘} is infinite, that is, there are infinitely many strings colliding on two hash functions. You can repeat this argument any number of times. Repeat it H times. Then you have an infinite set of strings where all strings collide over all of your H hash functions. CQFD.

Further reading: Sensible hashing of variable-length strings is impossible http://lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/

于 2010-12-10T14:45:35.250 回答