我有一个庞大的字符串列表（8 到 1000 万）。它们是维基百科页面标题。在这些字符串上创建一个类似 Set 的数据结构后，我需要的唯一操作是boolean contains(String str).
直接的方法是只使用 aHashSet或类似的TreeSet东西（例如在 Java 中）。
是否有更适合此用例的数据结构？
PS：我们不能使用布隆过滤器，我们不想处理误报。
问问题
134 次
1 回答
1
如果您比 constant-time 更关心节省空间contains()，并且存储的字符串中有很多重叠，那么trie可能会有所帮助。在这种情况下，的长度contains(str)在O(n)哪里。nstr
于 2012-11-16T03:33:21.487 回答