Bob*_*Bob 5 string hash prefix-tree
我有一大堆字符串，顺序约为 10^12 左右，我需要选择一个适当的数据结构，以便提供一个字符串，我可以以 O(log(n)) 之类的形式检索和关联的整数值或 O(m) 时间，其中“n”是字符串列表的长度，“m”是每个字符串的长度。
\n\n我们可以预期，我们的字符串集（每个字符串的长度为“m”）并通过某个大小为“q”的字母表进行编码，几乎涵盖了该长度的所有可能的字符串。例如，假设我们有 10^12 个长度为 m = 39 的唯一二进制字符串。这意味着我们已经覆盖了该长度的所有可能二进制字符串集合的约 54%。
\n\n因此，我担心为字符串找到合适的哈希函数来避免冲突。有没有一个好的我可以用的？索引我的 n 个字符串集需要多长时间？
\n\n或者我应该使用后缀树？我们知道 Ukkonen\xe2\x80\x99s 算法允许线性时间构造，我的猜测是，考虑到大量相似的字符串，这会节省空间？
\n小智 1
...
嗨鲍勃，
长话短说：经典的 HASH+BTREE 方法非常强大且超快。
无论 1000 万个还是 100 亿个字符串要存储在上述结构中，都没有关系 - 您总是有一个非常低的 MAX 搜索阈值。
好吧，你需要 10^12 = 1,000,000,000,000 - 但这是 1 万亿，这让我感到惊讶 - 即使我的重字符串语料库也在 10 亿范围内。
只需检查我在 C 中的实现： http: //www.sanmayce.com/#Section13Level
因此，我担心为字符串找到合适的哈希函数来避免冲突。有没有一个好的我可以用的？
C 语言中最快的哈希表查找函数如下：
http://www.sanmayce.com/Fastest_Hash/index.html#KT_torture3
它比强大的 CRC32 8slice 变体（Castagnoli 和 Koopman 的）快 300-500%，同时具有类似的碰撞。