Java中最节省内存的映射表

Question

我正在使用`Map`接口来实现类似树形结构的数据结构，声明如下：

Map<String, Map<String, Map<Integer, Double>>>

目前我正在使用 HashMap 实现。 加载大量数据后，程序消耗了 4GB 的内存。 使用 Serializable 接口将整个实体持久化后，结果文件的大小仅为 1GB。

在此情况下，最节省内存的 Map 实现是什么？

- Vineeth Mohan

---

使用地图是正确的解决方案吗？难道你不应该使用List<FirstLevelNode>，其中FirstLevelNode持有List<SecondLevelNode>，而SecondLevelNode持有List<ThirdLevelNode>吗？ - JB Nizet

使用列表会影响检索的性能吗？我可以接受更长的加载时间，但我想要节省的是检索时间。 - Vineeth Mohan

可能吧。我们不知道你对树做了什么。 - JB Nizet

将这个结构称为树是很奇怪的。假设映射中没有任何值与多个键相关联，那么它确实呈树形状。否则，你会得到一个图。为了给出最好的答案，您需要描述此结构的访问模式。您通常手头有两个字符串和一个整数，想要找到相应的双精度值吗？还是您需要获取子树（例如，仅给定第一个字符串）并将其传递给其他地方？重新表述：这真的是从复合键（由两个字符串和一个整数组成的元组）到双精度浮点数的映射吗？ - seh

我只想映射一个 (String,String,Integer) -> Float。由于有大量这样的数据，实现最有效的方法非常重要。 - Vineeth Mohan

Answer 1

如果您想将（String，String，Integer）映射到Float，则最好使用Map，其中MyKey应按以下方式定义：

public final class MyKey {
    private final String a;
    private final String b;
    private final Integer c;

    public MyKey(String a, String b, Integer c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    // getters, if needed

    @Override
    public int hashCode() {
        return Objects.hash(a, b, c);
    }

    @Override
    public boolean equals(Object o) {
        if (o == this) {
            return true;
        }
        if (!(o instanceof MyKey)) {
            return false;
        }
        MyKey other = (MyKey) o;
        return Objects.equal(a, o.a)
               && Objects.equal(b, o.b)
               && Objects.equal(c, o.c);
    }
}

- JB Nizet

---

这是一种正确的方法，但它并没有回答原帖中关于哪种方法在内存占用方面最高效的问题。在这里，我们为每个键添加了四个对象头的开销。还有另一种设计，每个键只使用两个对象头：一个包裹在字节数组周围的虚拟类型。 - seh

与@seh的解决方案相比，此解决方案为+1。真正的问题是避免三个嵌套映射所产生的开销；更高级的方法需要付出更多的工作却只有微不足道的好处。 - Louis Wasserman

同意。但它已经比地图上的地图更有效率了很多。我会首先选择一个明确而简单的解决方案，只有在需要额外优化时才考虑它。 - JB Nizet

当然，但是OP并没有问他是否应该关心这些事情。他说他关心，我相信他的话，他希望通过我们的回答（以及在这种情况下，我们的深入提问）了解更多关于存储开销的知识。 - seh

@seh - 我无法看出这是一种解决方案。在这里，您正在将（String，String，Integer）映射到整数类型的唯一哈希码。在我的情况下可能不可能，因为有大量此类数据，2^32个整数无法表示它们全部。我的数据量将比那高得多。 - Vineeth Mohan

我并没有建议这样直接映射。相反，您可以将两个字符串和整数连接成一个字节数组，并依靠Arrays＃hashCode（byte []）计算连接键的哈希码。任何冲突都通过Arrays＃equals（byte []，byte []）正常解决。在这里不能直接使用字节数组，因为缺乏适当的hashCode（）和equals（）语义; 因此我提到了包装字节数组的“虚拟类型”。至于连接编码，SQLite有一个很好的设计，我已经在其他地方使用过：http://www.sqlite.org/src4/doc/trunk/www/key_encoding.wiki - seh

Answer 2

你这里有两种地图。一种是具有字符串键和映射值的地图。对于这种情况，如果你可以使用不可变性，我可能会使用Google Guava's ImmutableMap。它可能不能为你节省很多内存，但它可能比普通HashMap表现更好一些。

对于另一个具有整数键和双精度值的地图，你应该使用专门存储基本类型而不是对象的地图实现。例如，看看Trove4j's TIntDoubleHashMap。这将为你节省大量内存，因为基本类型被存储为基本类型而不是对象。

- Aleksander Blomskøld