Java On-Memory高效键值存储

我存储了1.11亿个键值对（一个键可以有多个值 – 最大值为2/3），其键为50位整数，值为32位（最大值）整数。 现在，我的要求是：

1. 快速插入（键，值）对[允许重复]
2. 基于密钥快速检索值/值。

这里给出了一个很好的解决方案，基于MultiMap。 但是，我想在主内存中存储更多的键值对，没有/小的性能损失。 我从网络文章中研究过B + Tree，R + Tree，B Tree，Compact Multimap等可以很好地解决这个问题。 有谁能够帮助我：

是否有任何Java库可以满足我所有这些需求（上面提到/其他ds也可以接受。没有问题）？ 实际上，我想要一个高效的java库数据结构来存储/检索键值/值对，这需要占用更少的内存，并且必须在内存中构建。

注意：我曾尝试使用路易斯·沃瑟曼，京都/东京内阁等提到的HashMultiMap（带有一些修改的番石榴）等。我的经验对于磁盘烘焙解决方案并不好。 所以请避免:)。 另一点是，为了选择库/ ds，一个重点是：密钥是50位（所以如果我们分配64位），14位将丢失，值为32位Int（最大） – 大多数是10-12-14位。 所以，我们也可以节省空间。

Answer 1

我认为JDK中没有任何东西可以做到这一点。

然而，实现这样的事情是一个简单的编程问题。 这是一个带有线性探测的开放式散列表，其中键和值存储在并行数组中：

public class LongIntParallelHashMultimap { private static final long NULL = 0L; private final long[] keys; private final int[] values; private int size; public LongIntParallelHashMultimap(int capacity) { keys = new long[capacity]; values = new int[capacity]; } public void put(long key, int value) { if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL); if (size == keys.length) throw new IllegalStateException("map is full"); int index = indexFor(key); while (keys[index] != NULL) { index = successor(index); } keys[index] = key; values[index] = value; ++size; } public int[] get(long key) { if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL); int index = indexFor(key); int count = countHits(key, index); int[] hits = new int[count]; int hitIndex = 0; while (keys[index] != NULL) { if (keys[index] == key) { hits[hitIndex] = values[index]; ++hitIndex; } index = successor(index); } return hits; } private int countHits(long key, int index) { int numHits = 0; while (keys[index] != NULL) { if (keys[index] == key) ++numHits; index = successor(index); } return numHits; } private int indexFor(long key) { // the hashing constant is (the golden ratio * Long.MAX_VALUE) + 1 // see The Art of Computer Programming, section 6.4 // the constant has two important properties: // (1) it is coprime with 2^64, so multiplication by it is a bijective function, and does not generate collisions in the hash // (2) it has a 1 in the bottom bit, so it does not add zeroes in the bottom bits of the hash, and does not generate (gratuitous) collisions in the index long hash = key * 5700357409661598721L; return Math.abs((int) (hash % keys.length)); } private int successor(int index) { return (index + 1) % keys.length; } public int size() { return size; } } 

请注意，这是一个固定大小的结构。 您需要创建足够大的数据来保存所有数据–1.1亿条记录占用1.32 GB。 您创建的数据越大，超出存储数据所需的数量，插入和查找的速度就越快。 我发现有1.1亿个条目，负载系数为0.5（2.64 GB，是所需空间的两倍），查找密钥平均需要403纳秒，但负载系数为0.75（1.76 GB，a比需要的空间多三个，花了575纳秒。 将负载系数降低到0.5以下通常没有太大区别，实际上，当负载系数为0.33（4.00 GB，比所需空间多三倍）时，平均时间为394纳秒。 因此，即使您有5 GB可用，也不要全部使用它。

另请注意，不允许将零作为键。 如果这是一个问题，请将null值更改为其他值，并在创建时使用该值预先填充keys数组。

Answer 2

是否有任何Java库可以满足我的所有需求。

AFAIK没有。 或者至少，不是最小化内存占用的一种。

但是，应该很容易编写专门针对这些要求的自定义地图类。

Answer 3

寻找数据库是个好主意，因为这些问题就是它们的设计目标。 近年来，Key-Value数据库变得非常流行，例如对于Web服务（关键字“NoSQL”），所以你应该找到一些东西。

自定义数据结构的选择还取决于您是否希望使用硬盘驱动器来存储数据（以及必须具备的安全性），或者是否在程序退出时完全丢失。

如果手动实现并且整个数据库很容易适应内存，我只需在C中实现一个散列映射。创建一个散列函数，从一个值中提供（扩展良好的）内存地址。 如果已经分配，​​请在其中或旁边插入。 然后分配和检索是O（1）。 如果用Java实现它，那么每个（原始）对象将有4字节的开销。

Answer 4

基于@Tom Andersons解决方案，我删除了分配对象的需要，并添加了性能测试。

 import java.util.Arrays; import java.util.Random; public class LongIntParallelHashMultimap { private static final long NULL = Long.MIN_VALUE; private final long[] keys; private final int[] values; private int size; public LongIntParallelHashMultimap(int capacity) { keys = new long[capacity]; values = new int[capacity]; Arrays.fill(keys, NULL); } public void put(long key, int value) { if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL); if (size == keys.length) throw new IllegalStateException("map is full"); int index = indexFor(key); while (keys[index] != NULL) { index = successor(index); } keys[index] = key; values[index] = value; ++size; } public int get(long key, int[] hits) { if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL); int index = indexFor(key); int hitIndex = 0; while (keys[index] != NULL) { if (keys[index] == key) { hits[hitIndex] = values[index]; ++hitIndex; if (hitIndex == hits.length) break; } index = successor(index); } return hitIndex; } private int indexFor(long key) { return Math.abs((int) (key % keys.length)); } private int successor(int index) { index++; return index >= keys.length ? index - keys.length : index; } public int size() { return size; } public static class PerfTest { public static void main(String... args) { int values = 110* 1000 * 1000; long start0 = System.nanoTime(); long[] keysValues = generateKeys(values); LongIntParallelHashMultimap map = new LongIntParallelHashMultimap(222222227); long start = System.nanoTime(); addKeyValues(values, keysValues, map); long mid = System.nanoTime(); int sum = lookUpKeyValues(values, keysValues, map); long time = System.nanoTime(); System.out.printf("Generated %.1f M keys/s, Added %.1f M/s and looked up %.1f M/s%n", values * 1e3 / (start - start0), values * 1e3 / (mid - start), values * 1e3 / (time - mid)); System.out.println("Expected " + values + " got " + sum); } private static long[] generateKeys(int values) { Random rand = new Random(); long[] keysValues = new long[values]; for (int i = 0; i < values; i++) keysValues[i] = rand.nextLong(); return keysValues; } private static void addKeyValues(int values, long[] keysValues, LongIntParallelHashMultimap map) { for (int i = 0; i < values; i++) { map.put(keysValues[i], i); } assert map.size() == values; } private static int lookUpKeyValues(int values, long[] keysValues, LongIntParallelHashMultimap map) { int[] found = new int[8]; int sum = 0; for (int i = 0; i < values; i++) { sum += map.get(keysValues[i], found); } return sum; } } } 

版画

 Generated 34.8 M keys/s, Added 11.1 M/s and looked up 7.6 M/s 

使用Java 7 update 3在3.8 GHz i7上运行。

这比前一个测试慢得多，因为您正在访问主内存，而不是随机访问缓存。 这实际上是对你记忆速度的考验。 写入速度更快，因为它们可以与主存储器异步执行。

---

使用这个集合

 final SetMultimap map = Multimaps.newSetMultimap( TDecorators.wrap(new TLongObjectHashMap>()), new Supplier>() { public Set get() { return TDecorators.wrap(new TIntHashSet()); } }); 

使用5000万个条目（使用大约16 GB）和-mx20g运行相同的测试，我得到以下结果。

  Generated 47.2 M keys/s, Added 0.5 M/s and looked up 0.7 M/s 

对于110 M条目，您将需要大约35 GB的内存和比我的速度快10倍（3.8 GHz）的机器每秒执行500万次增加。

Answer 5

如果必须使用Java，则实现自己的哈希表/哈希映射。 表的一个重要属性是使用链表来处理冲突。 因此，当您执行查找时，您可能会返回列表中的所有元素。

Answer 6

我可能会迟到回答这个问题，但弹性搜索可以解决你的问题。