我正在使用大量（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 数据结构最适合我的需要。我想知道是否有一个有实现的库。
欢迎其他带有实现指针的建议。
谢谢你。
对于您的约束，特里树似乎是一个非常好的主意。
“跳出框框思考”的替代方案：
如果你能负担得起为不存在的字符串回答“存在”的概率
编辑：如果您能承受误报，请使用WizardOfOdds 在评论中建议的布隆过滤器。
对于 k=1，布隆过滤器就像一个没有键的哈希表：每个“桶”只是一个布尔值，用于判断是否存在至少一个具有相同哈希值的输入。如果 1% 的误报是可以接受的，那么您的哈希表可以小到大约 100 * 2000 万位或大约 200 MiB。1000 个误报中的 1 个，2GiB。
使用多个散列函数而不是一个可以提高相同位数的误报率。
Google 发布了一篇关于HAT 在 Java 中尝试的博客文章。但是我看不出这将如何直接解决您的问题：该结构是对键前缀的浅层尝试，叶子是哈希表，其中包含具有给定前缀的所有键的后缀。因此，总的来说，您有很多哈希表来存储当前一个大哈希表中的所有键（由于通用前缀，可能每个键总体上节省了几个字节）。无论哪种方式，您都需要一个比默认 Java 哈希表更节省空间的哈希表，否则每个对象的开销都会对您造成同样严重的影响。那么，为什么不从仅用于字符串键的专用哈希表类开始，如果您采用这条路线，并且只有在它看起来仍然值得时才担心 trie 部分？
为了节省空间、O(log(n)) 查找和简单代码，请尝试对字符数组进行二进制搜索。2000 万个平均长度为 10 的键产生 2 亿个字符：如果需要 2 个字节/字符，则为 400MB；200MB，如果你能逃脱 1。最重要的是，你需要以某种方式表示数组中键之间的边界。如果您可以保留分隔符，那是一种方法；否则您可能会使用 int 偏移量的并行数组。
最简单的变体将使用字符串数组，但每个对象开销的空间成本很高。它应该仍然在空间效率方面击败哈希表，尽管没有那么令人印象深刻。