6

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

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

3 回答 3

4

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

于 2016-06-15T15:19:05.453 回答
1

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

于 2016-06-15T15:34:47.847 回答
-1

我参加这个聚会有点晚了,但这个问题出现在相关搜索中并引起了我的兴趣。我通常不回答 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) 性能——几乎是你能找到的最差的性能。

于 2018-04-04T20:54:45.583 回答