需要高效的内存存储方式来存储大量字符串（是：Java中的HAT-Trie实现）

Question

我正在使用一大组 （5-20​​百万个） 字符串键 （平均长度为10个字符）
，这些键需要存储在内存中的数据结构中，该数据结构在恒定时间或接近恒定时间内支持以下操作：

// Returns true if the input is present in the container, false otherwise
public boolean contains(String input)

就吞吐量而言，Java的Hashmap被证明是令人满意的，但占用了大量内存。我正在寻找一种内存效率高的解决方案，并且仍支持不错的吞吐量（与散列相当或几乎一样）。

我不在乎插入/删除时间。在我的应用程序中，我将仅执行插入操作（仅在启动时执行），随后将仅contains在应用程序生存期内使用该方法查询数据结构。

我读到HAT-Trie数据结构最符合我的需求。我想知道是否有一个实现的库。

欢迎提供其他有关实现建议的建议。

谢谢。

Answer 1

对于您的约束而言，特里树似乎是个好主意。

一种“框外思考”的替代方案：

如果您有能力为缺少的字符串回答“现在”的可能性

编辑：如果您可以负担得起误报，请使用WizardOfOdds在评论中建议的Bloom过滤器。

对于k = 1，Bloom过滤器就像没有键的哈希表：每个“
bucket”只是一个布尔值，它指示是否存在至少一个具有相同哈希值的输入。如果可接受1％的误报，则您的哈希表可以小到大约100 * 2000万比特或大约200 MiB。对于千分之一的误报，为2GiB。

使用多个散列函数代替一个散列函数可以提高相同数量位的误报率。