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

Question

我知道这个问题已经被问过很多次了。但是几乎所有的解决方案都具有 O(n^2) 的计算复杂度。

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

非常感谢，柴坦亚

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());
}