基于@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<Long, Integer> map = Multimaps.newSetMultimap(
TDecorators.wrap(new TLongObjectHashMap<Collection<Integer>>()),
new Supplier<Set<Integer>>() {
public Set<Integer> 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
对于 1.1 亿个条目，您将需要大约 35 GB 的内存和一台比我的 (3.8 GHz) 快 10 倍的机器来每秒执行 500 万次添加。