我正在使用大量（5-2000万）字符串键（平均长度为10个字符），我需要将其存储在内存数据结构中，该结构支持在恒定时间或接近恒定时间内执行以下操作：
// Returns true if the input is present in the container, false otherwise
public boolean contains(String input)
就吞吐量而言，Java的Hashmap被证明是非常令人满意的，但占用了大量内存。我正在寻找一种内存效率高的解决方案，并且仍然支持体面的吞吐量（与散列相当或几乎一样好）。
我不在乎插入/删除时间。在我的应用程序中，我将仅执行插入（仅在启动时），随后将仅使用应用程序生存期的方法查询数据结构。contains
我读到HAT-Trie数据结构最接近我的需求。我想知道是否有一个具有实现的库。
欢迎提出其他建议，并指明实现。
谢谢。
对于您的约束，trie似乎是一个非常好的主意。
“跳出框框思考”替代方案：
如果你能负担得起对不存在的字符串回答“present”的概率
编辑：如果你能负担得起误报，按照WizardOfOdds在评论中的建议使用Bloom过滤器。
对于 k=1，Bloom 过滤器就像一个没有键的哈希表：每个“bucket”只是一个布尔值，它告诉是否存在至少一个具有相同哈希的输入。如果 1% 的误报是可以接受的，则您的哈希表可以小到大约 100 * 2000 万位或大约 200 MiB。对于 1/1000 的误报，为 2GiB。
使用多个哈希函数而不是一个哈希函数可以提高相同位数的误报率。
Google在Java中提出了一篇关于HAT尝试的博客文章。但是我不明白这将如何直接解决您的问题：结构是对键前缀的浅三元组，叶子是哈希表，其中包含具有给定前缀的所有键的后缀。因此，总的来说，您有很多哈希表存储当前一个大哈希表中的所有密钥（由于通用前缀，每个密钥可能总共节省了几个字节）。无论哪种方式，您都需要一个比默认Java更节省空间的哈希表，否则每个对象的开销也会给您带来同样严重的打击。那么，如果您采用此路线，为什么不从仅用于字符串键的专用哈希表类开始，并且仅在看起来仍然值得时才担心trie部分呢？
