我有一大堆字符串，顺序约为 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