将大量键映射到少量值 [英] Mapping large set of Keys to a small set of Values

问题描述

如果您有1,000,000个键（整数）映射到10,000个值（整数）。

If you had 1,000,000 keys (ints) that mapped to 10,000 values (ints). What would be the most efficient way (lookup performance and memory usage) to implement.

假设值是随机的，那是实现的最有效方式（查找性能和内存使用）。也就是说，没有映射到单个值的键范围。

Assume the values are random. i.e there is not a range of keys that map to a single value.

我能想到的最简单的方法是HashMap，但想知道是否可以通过将

The easiest approach I can think of is a HashMap but wonder if you can do better by grouping the keys that match a single value.

Map<Integer,Integer> largeMap = Maps.newHashMap();
largeMap.put(1,4);
largeMap.put(2,232);
...
largeMap.put(1000000, 4);

推荐答案

如果已知键集位于给定范围（如示例中所示的1-1000000），那么最简单的方法是使用数组。问题是您需要按键查找值，并且将您限制为映射或数组。

If the set of keys is known to be in a given range (as 1-1000000 shown in your example), then the simplest is to use an array. The problem is that you need to look up values by key, and that limits you to either a map or an array.

以下内容仅使用值到值的映射避免重复使用等值对象（可能有更好的方法，但是我想不到）。数组只是用来按索引查找值：

The following uses a map of values to values simply to avoid duplicate instances of equal value objects (there may be a better way to do this, but I can't think of any). The array simply serves to look up values by index:

private static void addToArray(Integer[] array, int key, 
        Integer value, Map<Integer, Integer> map) {

    array[key] = map.putIfAbsent(value, value);
}

然后可以使用以下值添加值：

And then values can be added using:

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 相关的实际键。

If new Integer[1000001] seems like a hack, you can still maintain a sort of "index offset" to indicate the actual key associated with index 0 in the array.

我将其放在一个类中：

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);
}

这篇关于将大量键映射到少量值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！