San*_*nto 5 string associative-array string-algorithm
关于SO的另一个问题是将一些语言中的工具用于散列字符串,以便在表格中快速查找.两个例子是.NET中的dictionary <>和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(m)会被theta(log(n))黯然失色,但如果我们处于这样一个域中,我们搜索的文本将非常大,我们就不能忽略它.
我知道后缀树/数组和Aho-Corasick可以将搜索降低到theta(m)以获得更大的内存费用,但是我要问的是,如果存在任意长度的字符串的常量时间哈希方法,那么其他SO成员声称.
谢谢.
散列函数不必(也不能)为每个字符串返回唯一值.
您可以使用前10个字符初始化随机数生成器,然后使用它从字符串中提取100个随机字符,并将其哈希.这将是恒定的时间.
你也可以只返回常量值1.严格来说,这仍然是一个哈希函数,虽然不是一个非常有用的函数.
一般来说,我认为任何完整的字符串哈希必须使用字符串的每个字符,因此需要增长为n个字符的O(n).但是我认为对于实际的字符串哈希,你可以使用很容易为O(1)的近似哈希值.
考虑一个始终使用Min(n,20)个字符来计算标准哈希的字符串哈希.显然,这会随着字符串大小增长为O(1).它会可靠地运作吗？这取决于你的域名......