java - 如何在 Java 中存储仅需要 'contains' 操作的巨大静态/不可变字符串集

Question

我有一个巨大的字符串列表(8 到 1000 万)。它们是维基百科页面标题。在这些字符串上创建类似 Set 的数据结构后，我唯一需要的操作是 boolean contains(String str)。

最直接的方法是使用HashSet、TreeSet 或类似的东西(例如，在 Java 中)。

是否有更适合此用例的数据结构？

PS:我们不能使用布隆过滤器，我们不想处理误报。

Answer 1

如果您比恒定时间 contains() 更关心节省空间，并且存储的字符串中有很多重叠，trie可能有帮助。在这种情况下，contains(str) 将是 O(n)，其中 n 是 str 的长度。