java - 需要内存有效的方式来存储大量字符串(是 : HAT-Trie implementation in java)

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

trie 对于您的约束来说似乎是一个非常好的主意。

“跳出框框思考”的替代方案:

如果你有能力为不存在的字符串回答“存在”的概率

编辑:如果您能承受误报，请使用 Bloom filter正如 WizardOfOdds 在评论中所建议的那样。

对于 k=1，布隆过滤器就像一个没有键的哈希表:每个“桶”只是一个 boolean 值，用于判断是否存在至少一个具有相同哈希的输入。如果 1% 的误报是可以接受的，那么您的哈希表可以小到大约 100 * 2000 万位或大约 200 MiB。每 1000 个误报中就有 1 个是 2GiB。

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