java – 内存有效的多值映射

嗨,我有以下问题：
我在MultiValueMap< String,Integer>中存储字符串和相应的整数值列表.
我存储了大约1300亿个字符串,一个字符串可以包含多达500个或更多的值.
对于每个值,我将在地图上随机访问.所以最糟糕的情况是13 000 000 * 500看涨期权.现在地图的速度很好但内存开销却很高. MultiValueMap< String,Integer>除了HashMap / TreeMap< String,< ArrayList< Integer>>之外别无其他. HashMap和TreeMap都有很多内存开销.一旦完成,我就不会修改地图,但我需要它在程序中随机访问的速度要快且尽可能小. (我将它存储在磁盘上并在启动时加载它,序列化的映射文件占用大约600mb但在内存中大约需要3gb？)

最有效的内存是将String存储在已排序的字符串数组中,并为值提供相应的二维int数组.因此访问将是字符串数组上的二进制搜索并获取相应的值.

现在我有三种方法可以实现目标：

>我使用一个排序的MultivalueMap(TreeMap)来创建所有的东西.在我完成获取所有值之后,我通过调用map.keyset()来获取字符串数组.toArray(new String [0]);创建一个二维int数组并从多值映射中获取所有值.
Pro：它易于实现,在创建过程中仍然很快.
Con：从Map到Arrays的复制过程中占用的内存更多.
>我从一开始就使用Arrays或ArrayLists,并将所有内容存储在那里
专业：最小的内存开销.
Con：这将非常慢,因为每次添加一个新Key时我都必须对Array进行排序/复制.另外,我需要实现自己的(可能更慢)排序,以保持相应的int数组的顺序相同字符串.难以实施
>我使用Arrays和MultivalueMap作为缓冲区.程序完成创建阶段的10％或20％后,我会将值添加到数组并保持顺序,然后启动一个新的Map.
Pro：足够的速度和足够的内存效率.
骗局：难以实施.

这些解决方案都不适合我.您是否知道此问题的任何其他解决方案,可能是内存高效(MultiValue)Map实现？

我知道我可以使用数据库,所以不要把它作为答案发布.我想知道如何在不使用数据库的情况下做到这一点.

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