java - 内存高效的多值映射

Question

您好，我有以下问题: 我将字符串和相应的整数值列表存储在 MultiValueMap<String, Integer> 中。 我存储了大约 130 亿个字符串，一个字符串最多可以有 500 个或更多值。 对于每一个值，我将在 map 上随机访问。所以最坏的情况是 13 000 000 * 500 个看跌期权。现在 map 的速度很好，但内存开销变得相当高。一个 MultiValueMap<String, Integer>就是一个HashMap/TreeMap<String, <ArrayList<Integer>> . HashMap 和 TreeMap 都有相当多的内存开销。完成后我不会修改 map ，但我需要它快速且尽可能小，以便在程序中进行随机访问。 (我将它存储在磁盘上并在启动时加载它，序列化的 map 文件占用大约 600mb 但在内存中大约 3gb？)

最节省内存的方法是将字符串存储在已排序的字符串数组中，并为值提供相应的二维 int 数组。所以访问将是对字符串数组进行二分搜索并获取相应的值。

现在我有三种方法可以到达那里:

1. 我在创建阶段使用排序的 MultivalueMap (TreeMap) 来存储所有内容。获取所有值后，我通过调用 map.keyset().toArray(new String[0]); 获取字符串数组创建一个二维 int 数组并从多值映射中获取所有值。 优点:很容易实现，在创建过程中仍然很快。 缺点:在从 Map 复制到 Arrays 的过程中，它占用了更多的内存。

2. 我从一开始就使用 Arrays 或 ArrayLists 并将所有内容存储在其中 优点:最少的内存开销。 缺点:这将非常慢，因为每次添加新键时我都必须对数组进行排序/复制，而且我需要实现自己的(可能更慢)排序以保持相应的 int 数组的顺序相同，例如字符串。难以实现

3. 我使用数组和 MultivalueMap 作为缓冲区。在程序完成 10% 或 20% 的创建阶段后，我会将值添加到数组中并保持它们的顺序，然后启动一个新的 Map。 优点:可能仍然足够快且内存足够高效。 缺点:难以实现。

这些解决方案都不适合我。你知道这个问题的任何其他解决方案，也许是内存高效的 (MultiValue)Map 实现？

我知道我可能正在使用数据库，所以不要费心将其发布为答案。我想知道如何在不使用数据库的情况下做到这一点。

Answer 1

如果您切换到 Guava 的 Multimap -- 我不知道这是否适用于您的应用程序 -- 您也许可以使用 Trove 并获得

ListMultimap<String, Integer> multimap = Multimaps.newListMultimap(
  new HashMap<String, Collection<Integer>>(),
  new Supplier<List<Integer>>() {
    public List<Integer> get() {
      return new TIntListDecorator();
    }
  });

这将创建一个 ListMultimap，它使用 HashMap 映射到 int[] 支持的 List 值数组，这应该是内存效率的，尽管你会因为装箱而付出一点速度的代价。您也许可以为 MultiValueMap 做类似的事情，但我不知道它来自哪个库。