java - 如何在 HashMap 中找到与最大值关联的键？

Question

我想找到与 a 中的最大值关联的键HashMap<Integer,Integer>。

我在 Java Map 中看到了 Finding Key associated with max Value的问题，但使用时有一定的限制HashMap。

任何帮助，将不胜感激。

Answer 1

您可以在这里做的只是对您的 HashMap 进行排序并选择第一个或最后一个键以获得最大值或最小值。

public LinkedHashMap<Integer,Integer> sortHashMapByValues(HashMap<Integer,Integer> passedMap) {
   List<Integer> mapKeys = new ArrayList<Integer>(passedMap.keySet());
   List<Integer> mapValues = new ArrayList<Integer>(passedMap.values());
   Collections.sort(mapValues);
   Collections.sort(mapKeys);

   LinkedHashMap<Integer,Integer> sortedMap = 
       new LinkedHashMap<Integer,Integer>();

   Iterator valueIt = mapValues.iterator();
   while (valueIt.hasNext()) {
       Object val = valueIt.next();
    Iterator keyIt = mapKeys.iterator();

    while (keyIt.hasNext()) {
        int key = (Integer)keyIt.next();
        int comp1 = (Integer)passedMap.get(key);
        int comp2 = (Integer)val;

        if (comp1 == comp2){
            passedMap.remove(key);
            mapKeys.remove(key);
            sortedMap.put(key,(Integer) val);
            break;
        }

    }

}
return sortedMap;
}

请记住 - 它们可能是多个具有相同值的键。

Answer 2

只要你承诺 map 是 type HashMap，你不会比遍历 map 中的所有键/值对，寻找最大值更好。这样的哈希表是在内部组织的，以便通过哈希码找到键的最大速度；组织对与这些键关联的值漠不关心。

为了最好地解决您的问题，您需要对值进行倒排索引。由于原始映射中的多个键可以具有相同的值（假设它不是双射），因此倒排索引实际上是一个multimap，其中任何给定的整数键（取自原始映射值的集合）都可以是与任意数量的整数值（这是您的原始地图键）相关联。

如果你的倒排索引是 type NavigableMap，值类型是整数的集合，那么你可以使用该NavigableMap#lastEntry()方法找到最大整数键及其对应值的配对。或者，如果你手头只有一个SortedMap，你仍然可以使用它的SortedMap#lastKey()方法来找到有问题的密钥。这假设地图是按整数的自然顺序排列的，从最低到最高。

Guava 库提供了一组多映射类型，其中TreeMultimap类型SortedMap通过其TreeMultimap#asMap()方法公开类型视图。我建议你先尝试使用那个。

---

如果您只需要为给定的输入映射找到此答案一次，并且不想费心构建整个倒排索引，请尝试以下O(n)解决方案：

public static <T extends Number & Comparable<? super T>>
Collection<? extends T> keysForMaxValueIn(Map<? extends T, ? extends T> map) {
  final int size = map.size();
  switch (size) {
    case 0:
      return Collections.emptySet();
    case 1:
      return Collections.singleton(map.keySet().iterator().next());
    default:
      final T max = Collections.max(map.values());
      // We know that there will be no duplicates in the original key set.        
      final Collection<T> keys = new ArrayList<T>(size);
      for (Map.Entry<? extends T, ? extends T> entry : map.entrySet())
        if (max.equals(entry.getValue()))
          keys.add(entry.getKey());
      return keys;
  }
}

Answer 3

由于HashMap没有排序，最简单的解决方案可能是最好的。如果你只想要一个键，那么它只是

Comparator<Map.Entry<Integer, Integer>> comparator =
  new Comparator<Map.Entry<Integer, Integer>>() {
    public int compare(
        Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2) {
      return e1.getValue().compareTo(e2.getValue());
    }
};
return Collections.max(map.entrySet(), comparator).getKey();

如果您想要与最大值关联的所有键，那就有点棘手了；你可能会做类似的事情

Integer bestSeenValue = null;
List<Integer> bestKeys = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
  if (bestSeenValue == null || entry.getValue() > bestSeenValue) {
    bestSeenValue = entry.getValue();
    bestKeys.clear();
  }
  if (entry.getValue().equals(bestSeenValue)) {
    bestKeys.add(entry.getKey());
  }
}

Answer 4

此代码将打印所有具有最大值的键

public class NewClass4 {
    public static void main(String[] args)
    {
        HashMap<Integer,Integer>map=new HashMap<Integer, Integer>();
        map.put(1, 50);
        map.put(2, 60);
        map.put(3, 30);
        map.put(4, 60);
        map.put(5, 60);
        int maxValueInMap=(Collections.max(map.values()));  // This will return max value in the Hashmap
        for (Entry<Integer, Integer> entry : map.entrySet()) {  // Itrate through hashmap
            if (entry.getValue()==maxValueInMap) {
                System.out.println(entry.getKey());     // Print the key with max value
            }
        }

    }
}