java - 在地图中存储大量字符串的最节省内存的方法是什么？

Question

我想在 a 中存储大量字符串Map<String, MagicObject>，以便MagicObjects可以快速访问。此 Map 的条目太多，以至于内存正在成为瓶颈。假设MagicObjects无法优化，我可以在这种情况下使用的最有效的地图类型是什么？我目前正在使用以下内容：

gnu.trove.map.hash.TCustomHashMap<byte[], MagicObject>

Answer 1

如果您的键足够长并且有很多足够长的公共前缀，那么您可以使用trie（前缀树）数据结构来节省内存。这个问题的答案指向 trie 的几个 Java 实现。

Answer 2

开放思想，考虑霍夫曼编码先压缩你的字符串，然后再放入地图，只要你的字符串是固定的（字符串的数量和内容不改变）。

Answer 3

我参加这个聚会有点晚了，但这个问题出现在相关搜索中并引起了我的兴趣。我通常不回答 Java 问题。

此 Map 的条目太多，以至于内存正在成为瓶颈。

我对此表示怀疑。

为了使字符串在内存中的存储成为瓶颈，您需要大量的唯一字符串[1]。从长远来看，我最近使用了一个 180 万字的词典（180 万个独特的英文单词），它们在运行时占用了大约 1.6MB 的 RAM。

如果您使用字典中的每个单词作为键，您仍然只使用 1.6MB 的 RAM[2] 来存储键，因此内存不会成为您的瓶颈。

我怀疑您遇到的是字符串匹配的 O(n^2) 性能。我的意思是，随着更多键的添加，性能会成倍下降[3]。如果您使用字符串是键，这是不可避免的。

如果您想加快速度，请将每个键存储到不存储重复项的哈希表中，并将哈希键用作映射的键​​。

笔记：

[1] 我假设字符串都是唯一的，否则您不会尝试将它们用作地图的键。

[2] 即使 Java 使用每个字符 2 个字节，它仍然只有 3.2MB 的内存，总计。

[3] 如果您选择错误的数据结构（例如不平衡的二叉树）来存储您的值，它会更加缓慢。我不知道 map 如何在内部存储值，但是不平衡的二叉树将具有 O(2^n) 性能——几乎是你能找到的最差的性能。