查找哈希映射中值最低的键

Question

我正试图找到一种有效的方法来返回HashMap中数据结构中值最低的键。除了循环整个HashMap之外，还有什么快速有效的方法可以做到这一点吗？

例如，如果我有一个哈希图，它看起来像这样：

1: 200
3: 400
5: 1

我想把钥匙还给你。

Answer 1

否，必须循环遍历HashMap中的所有键才能找到最小的键。如果这是一个重要的操作，那么最好使用SortedMap，例如TreeMap，它将元素按排序顺序排列，然后您可以简单地调用firstKey()来查找最低键。

Answer 2

正如其他人所提到的，HashMap本身并不提供此功能。

因此，您可以选择按需计算或预先计算。

要按需计算，您需要迭代HashMap.entrySet()

根据映射的大小、其变化的频率和需要key-with-lowest-value的频率，预计算（缓存）可能更有效。如下所示：

class HashMapWithLowestValueCached<K, V extends Comparable> extends HashMap<K, V> {    
    V lowestValue;
    K lowestValueKey;    
    void put(K k, V v) {
      if (v.compareTo(lowestValue) < 0) {
        lowestValue = v; 
        lowestValueKey = k;
      }
      super.put(k, v);
    }
    K lowestValueKey () { return lowestValueKey; }
}

Answer 3

不，没有办法做到这一点。您需要对HashMap中的所有元素进行迭代，以找到值最低的元素。

我们之所以有不同种类的存储，是因为它们以不同的效率支持不同种类的操作。HashMap并不是为了根据元素的值高效地检索元素而设计的。您需要的存储类类型将取决于您需要能够快速执行的其他操作。假设您可能还希望能够根据密钥快速检索项目，那么以下方法可能会起作用：

1. 围绕HashMap编写一个包装器，跟踪添加到其中的所有元素，并记住哪一个元素最小。只有当检索smalls是您需要按值访问的唯一方式时，这才真正有用
2. 将所有数据存储两次——一次在HashMap中，一次在按值排序的数据结构中——例如，键和值反转的SortedMap
3. 如果您发现不需要按关键字检索，只需反转关键字和值即可

Answer 4

不，没有快速有效的方法可以做到这一点——您需要循环整个哈希图。原因是散列映射中的键和值不遵循任何特定的顺序。

Answer 5

否，因为否则O（n log n）中会存在排序算法（不过是概率性的）：将所有元素添加到哈希图中，而不是逐个提取最低的元素。

Answer 6

//create hashmap  
HashMap<Integer, String> yourHashmap = new HashMap<>();
//add your values here
yourHashmap.put(1,"200");
yourHashmap.put(3,"400");
yourHashmap.put(5,"1");
        
//then create empty arraylist
ArrayList<Integer> listDuplicates = new ArrayList<Integer>(); 
        
//filing the empty arraylist with all id's from duplicateHashmap
for (Map.Entry<Integer, String> entry : yourHashmap.entrySet()) {
    listDuplicates.add(entry.getKey());
}
        
//Ordering the numbers
Collections.sort(listDuplicates);
        
for (Integer num : listDuplicates) {
    int id = num; //entry
    String number2 = duplicateHashmap.get(num);//value
    System.out.println("lowest value = "+id+" : "+number2);
    //breaking here because we've found the lowest value...
    break;          
}