如果您有 1,000,000 个键(整数)映射到 10,000 个值(整数)。什么是最有效的实现方式(查找性能和内存使用)。
假设值是随机的。即不存在映射到单个值的一系列键。
我能想到的最简单的方法是 HashMap,但想知道是否可以通过对匹配单个值的键进行分组来做得更好。
Map<Integer,Integer> largeMap = Maps.newHashMap();
largeMap.put(1,4);
largeMap.put(2,232);
...
largeMap.put(1000000, 4);
最佳答案
如果已知键集在给定范围内(如示例中所示的 1-1000000),那么最简单的方法是使用数组。问题是您需要按键查找值,这将您限制为映射或数组。
下面使用值到值的映射只是为了避免等值对象的重复实例(可能有更好的方法来做到这一点,但我想不出任何方法)。该数组仅用于按索引查找值:
private static void addToArray(Integer[] array, int key,
Integer value, Map<Integer, Integer> map) {
array[key] = map.putIfAbsent(value, value);
}
然后可以使用以下方式添加值:
Map<Integer, Integer> keys = new HashMap<>();
Integer[] largeArray = new Integer[1000001];
addToArray(largeArray, 1, 4, keys);
addToArray(largeArray, 2, 232, keys);
...
addToArray(largeArray, 1000000, 4, keys);
如果 new Integer[1000001]
看起来像是 hack,您仍然可以维护一种“索引偏移量”来指示与索引 0
相关联的实际 key 数组。
我会把它放在类里面:
class LargeMap {
private Map<Integer, Integer> keys = new HashMap<>();
private Integer[] keyArray;
public LargeMap(int size) {
this.keyArray = new Integer[size];
}
public void put(int key, Integer value) {
this.keyArray[key] = this.keys.putIfAbsent(value, value);
}
public Integer get(int key) {
return this.keyArray[key];
}
}
和:
public static void main(String[] args) {
LargeMap myMap = new LargeMap(1000_000);
myMap.put(1, 4);
myMap.put(2, 232);
myMap.put(1000_000, 4);
}
关于java - 将大量键映射到少量值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54506530/