我想在 a 中存储大量字符串Map<String, MagicObject>
,以便MagicObjects
可以快速访问。此 Map 的条目太多,以至于内存正在成为瓶颈。假设MagicObjects
无法优化,我可以在这种情况下使用的最有效的地图类型是什么?我目前正在使用以下内容:
gnu.trove.map.hash.TCustomHashMap<byte[], MagicObject>
我想在 a 中存储大量字符串Map<String, MagicObject>
,以便MagicObjects
可以快速访问。此 Map 的条目太多,以至于内存正在成为瓶颈。假设MagicObjects
无法优化,我可以在这种情况下使用的最有效的地图类型是什么?我目前正在使用以下内容:
gnu.trove.map.hash.TCustomHashMap<byte[], MagicObject>
开放思想,考虑霍夫曼编码先压缩你的字符串,然后再放入地图,只要你的字符串是固定的(字符串的数量和内容不改变)。
我参加这个聚会有点晚了,但这个问题出现在相关搜索中并引起了我的兴趣。我通常不回答 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) 性能——几乎是你能找到的最差的性能。