我应该如何以内存高效的方式将字符串键映射到Java中的值？

data-structures collections memory java

2022-09-01 03:27:06

我正在寻找一种存储字符串>int映射的方法。当然，HashMap是一个最明显的解决方案，但是由于我的内存受限，需要存储200万对，7个字符长的密钥，我需要一些内存效率高的东西，检索速度是一个次要参数。

目前，我正在沿着以下路线前进：

List<Tuple<String, int>> list = new ArrayList<Tuple<String, int>>();
list.add(...); // load from file
Collections.sort(list);

然后用于检索：

Collections.binarySearch(list, key); // log(n), acceptable

我是否应该选择自定义树（每个节点都是单个字符，每个叶子都有结果），还是有一个现有的集合可以很好地适应这一点？字符串实际上是连续的（英国邮政编码，它们没有太大区别），所以我期望在这里节省大量内存。

答案 1

编辑：我刚刚看到你提到String是英国的邮政编码，所以我相当有信心你不会通过使用Trove TLongIntHashMap来犯很大的错误（顺便说一句，Trove是一个小库，它非常易于使用）。

编辑2：很多人似乎觉得这个答案很有趣，所以我添加了一些信息。

这里的目标是以内存效率高的方式使用包含键/值的映射，因此我们将从查找内存效率高的集合开始。

以下SO问题是相关的（但与这个问题远非相同）。

什么是最有效的 Java 集合库？

Jon Skeet提到Trove“只是一个来自原始类型的集合库”[原文如此]，事实上，它并没有增加太多功能。我们还可以看到一些关于Trove的内存和速度的基准测试（由.duckman）与默认集合相比。下面是一个代码段：

                      100000 put operations      100000 contains operations 
java collections             1938 ms                        203 ms
trove                         234 ms                        125 ms
pcj                           516 ms                         94 ms

还有一个例子显示了使用Trove而不是常规Java HashMap可以节省多少内存：

java collections        oscillates between 6644536 and 7168840 bytes
trove                                      1853296 bytes
pcj                                        1866112 bytes

因此，尽管基准测试总是需要谨慎对待，但很明显，Trove不仅会节省内存，而且总是会更快。

因此，我们现在的目标变成了使用Trove（通过将数百万个条目放入常规HashMap中，您的应用程序开始感觉无响应）。

您提到了 200 万对、7 个字符长的键和字符串/整数映射。

200万真的不是那么多，但你仍然会感觉到“对象”开销和在常规HashMap{String，Integer中将基元的恒定（取消）装箱到整数，这就是为什么Trove在这里很有意义。

但是，我要指出的是，如果您能够控制“7个字符”，则可以走得更远：如果您仅使用ASCII或ISO-8859-1字符，则您的7个字符将适合长（*）。在这种情况下，您可以完全躲避对象的创建，并在长上表示您的7个字符。然后，您将使用Trove TLongIntHashMap并完全绕过“Java对象”开销。

您特别指出您的密钥长度为7个字符，然后评论它们是英国邮政编码：我将每个邮政编码映射到一个长邮政编码，并使用Trove将数百万个键/值对放入内存中，从而节省大量内存。

Trove的优点基本上是它不是对对象/基元进行不断的装箱/取消装箱：在许多情况下，Trove直接与基元和基元一起工作。

（*）假设您最多只使用256个码位/字符，那么它适合7 * 8 == 56位，这足够小，可以容纳很长。

将密钥编码为的示例方法（假设 ASCII 字符，每个字符一个字节用于简化 - 7 位就足够了）：Stringlong

long encode(final String key) {
    final int length = key.length();
    if (length > 8) {
        throw new IndexOutOfBoundsException(
                "key is longer than 8 characters");
    }
    long result = 0;
    for (int i = 0; i < length; i++) {
        result += ((long) ((byte) key.charAt(i))) << i * 8;
    }
    return result;
}

答案 2

使用 Trove 库。

Trove 库已针对基元进行了优化和类。在这种情况下，会将参数化对象（）映射到基元。HashMapHashSetTObjectIntHashMap<String>Stringint