使用O(n log n)复杂度按值对Java HashMap进行排序

Question

我知道这个问题已被多次询问和回答.但是几乎所有解决方案都具有O(n ^ 2)的计算复杂度.

我正在寻找O(n log n)复杂度的解决方案.有人可以建议吗？

谢谢堆,Chaitanya

Answer 1

将条目复制到a List,List按值排序; 复制回来LinkedHashMap.我认为甚至不可能有更好的解决方案.

List<Entry<K, V>> entries = new ArrayList<Entry<K, V>>(map.entrySet());
Collections.sort(entries, new Comparator<Entry<K, V>>() {
  public int compare(Entry<K, V> left, Entry<K, V> right) {
    return left.getValue().compareTo(right.getValue());
  }
}
Map<K, V> sortedMap = new LinkedHashMap<K, V>(entries.size());
for (Entry<K, V> entry : entries) {
  sortedMap.put(entry.getKey(), entry.getValue());
}