在地图中寻找最高的n值

我认为这种方法是可以接受的单线程,但如果我有多个线程都触发转置和排序频繁它似乎不是很有效。另一种选择似乎是保持最高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;
}

理想情况下,如果您有多个线程访问的某个状态(如此映射),则将该状态封装在另一个类后面,这样每个线程就不会直接更新映射。

好吧,要在地图上找到最高的5个值,你可以在 O(n)

最简单的方法是通过映射的条目集执行for循环。

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

// Map name to value
Map<String, Integer> byName

// Maps value to names
NavigableMap<Integer, Collection<String>> byValue

byValue.navigableKeySet().descendingIterator()

我将创建如下方法:

private static int[] getMaxFromMap(Map<String, Integer> map, int qty) {
    int[] max = new int[qty];
    for (int a=0; a<qty; a++) {
        max[a] = Collections.max(map.values());
        map.values().removeAll(Collections.singleton(max[a]));
        if (map.size() == 0)
            break;
    }
    return max;
}

利用 Collections.max() Collections.singleton()

有两种方法可以轻松做到这一点:

1. 把地图放进一个盒子里 heap structure n 你想要的元素。
2. 遍历映射并更新 n 使用每个条目的最大值。

就我个人而言,我更喜欢第一种方法。

compareTo(无论在何处)方法的定义如下: 比较(参数){ return value2-value1;//降序 }

剩下的很简单。使用列表和调用集合.排序(参数)方法将完成排序部分。

online .

如果修改很少,我会实现一些 SortedByValHashMap<K,V> extends HashMap <K,V> ,类似于 LinkedHashMap )使条目按值排序。