在Map中查找最高n值

Question

我有一个String-> Integer的大型地图,我想在地图中找到最高的5个值.我当前的方法是将映射转换为pair(key,value)对象的数组列表,然后在获取第一个5之前使用Collections.sort()进行排序.一个键可以在操作过程中更新其值.

我认为这种方法是可以接受的单线程,但如果我有多个线程都触发转置和频繁排序它似乎不是很有效.替代方案似乎是维护最高5个条目的单独列表,并在地图上的相关操作发生时保持更新.

请问有什么建议/替代方案可以优化吗？如果有好处,我很乐意考虑不同的数据结构.

谢谢!

Answer 1

好吧,要在Map中找到最高的5个值,您可以O(n)在任何排序比这慢的时候做到.

最简单的方法是简单地通过Map的入口集进行for循环.

for (Entry<String, Integer> entry: map.entrySet()) {
    if (entry.getValue() > smallestMaxSoFar) 
        updateListOfMaximums();
}

Answer 2

我认为这种方法在单线程中是可以接受的，但是如果我有多个线程都频繁触发转置和排序，那么它似乎效率不高。另一种选择似乎是维护一个最高 5 个条目的单独列表，并在地图上发生相关操作时保持更新。

您也可以采用一种介于两者之间的方法。当线程请求地图的“排序视图”时，创建地图的副本，然后对其进行排序。

public List<Integer> getMaxFive() {
    Map<String, Integer> copy = null;
    synchronized(lockObject) {
        copy = new HashMap<String, Integer>(originalMap);
    }

    //sort the copy as usual
    return list;
}

理想情况下，如果您有多个线程访问某些状态（例如此映射），则可以将该状态封装在其他类后面，以便每个线程不会直接更新映射。