代码之家 › 专栏 › 技术社区 › San Jacinto

字符串的常量时间哈希?

string-algorithm associative-array string

San Jacinto · 技术社区 · 15 年前

关于这个问题的另一个问题提出了一些语言的工具来散列字符串,以便在表中快速查找它们。这方面的两个例子是.NET中的dictionary<gt;和python中的存储结构。其他语言当然支持这种机制。C++有它的映射,LISP与大多数其他现代语言一样具有等价性。

在回答这个问题时,有人争辩说,字符串上的散列算法可以在恒定时间内进行,其中一个SO成员在编程方面有25年的经验,声称任何东西都可以在恒定时间内散列。我个人的观点是,这不是真的,除非您的特定应用程序在字符串长度上设置了边界。这意味着某个常数k将指示字符串的最大长度。

我熟悉rabin-karp算法,它使用一个散列函数进行运算,但是这个算法没有指定要使用的特定散列函数,作者建议使用的是o(m),其中m是散列字符串的长度。

我看到一些其他的页面,比如这个( http://www.cse.yorku.ca/~oz/hash.html )这显示了一些散列算法,但似乎它们中的每一个都在字符串的整个长度上迭代以得到其值。

从我对主题相对有限的理解来看,似乎大多数字符串类型的关联数组实际上是使用哈希函数创建的,该函数与引擎盖下某种类型的树一起操作。这可能是一个AVL树或红/黑树,指向键/值对中的值元素的位置。

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

我知道后缀树/数组和aho corasick可以将搜索降低到theta(m),以获得更大的内存开销,但是我特别要问的是,对于另一个so成员所声明的任意长度的字符串,是否存在常量时间哈希方法。

谢谢。

7 回复 | 直到 14 年前

Ron Warholic 15 年前

一般来说,我认为任何完整的字符串哈希都必须使用字符串中的每个字符,因此对于n个字符,需要增长为o(n)。不过,我认为对于实际的字符串散列,可以使用近似散列,它很容易是O(1)。

考虑一个总是使用最小(n,20)字符来计算标准哈希的字符串哈希。显然,随着字符串大小的增加,这个值会增加为O(1)。它能可靠地工作吗?这取决于你的领域…

Mark Byers 15 年前

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

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

也可以返回常量值1。严格地说,这仍然是一个哈希函数,尽管不是一个非常有用的函数。

Josef Grahn 15 年前

如果不冒着哈希冲突的严重风险,就无法轻松地为字符串实现一般的常量时间哈希算法。

如果时间不变,则无法访问字符串中的每个字符。作为一个简单的例子,假设我们采用前6个字符。然后有人来尝试散列一个URL数组。has函数将看到每个字符串的“http://”。

其他字符选择方案也可能出现类似的情况。您可以根据前一个字符的值随机选取伪字符,但如果由于某种原因字符串具有“错误”模式,并且许多字符串以相同的哈希值结尾,则仍然存在失败的风险。

Pascal Cuoq 15 年前

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

哈希函数的质量和计算量之间的折衷是可能的,而且长字符串上的哈希函数无论如何都必须发生冲突。

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

xtofl Adam Rosenfield 15 年前

虽然我无法想象无限长字符串的固定时间哈希函数,但实际上并不需要它。

使用散列函数的思想是生成散列值的分布,使其 许多弦不太可能发生碰撞 -考虑中的领域。此密钥将允许直接访问数据存储。这两个结合的结果是 持续时间查找-平均 .

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

Nick Johnson 15 年前

当然,这是可行的,只要在将所有字符串传递给需要散列的对象之前确保它们都是“实习生”。interning是将字符串插入到字符串表中的过程,这样具有相同值的所有interned字符串实际上都是相同的对象。然后,您可以简单地将(固定长度)指针散列到实习生字符串,而不是散列字符串本身。

Daniel Lemire 14 年前

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

考虑将无穷多的键(如任意长度的所有字符串)散列到1,2,__中的数字集的问题。随机散列首先随机选取H函数族中的散列函数H。

我将向您展示,在所有的h函数上,总是有无穷多的键会发生碰撞,也就是说,对于所有的哈希函数,它们总是有相同的哈希值。

选取任意散列函数h:至少有一个散列值y,使得集合a=s:h(s)=y是无限的,也就是说,有无限多个字符串发生碰撞。选择任何其他散列函数h_152;,散列集合A中的键。至少有一个散列值y_152;,这样,集合A__s位于:h_(s)=y__是无限的,也就是说,两个散列函数上有无穷多的字符串碰撞。你可以多次重复这个论点。重复h次。然后有一组无限多的字符串,其中所有字符串在所有H哈希函数上发生冲突。CQFD。

进一步阅读 : 可变长度字符串的合理散列是不可能的 http://lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/