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

Question

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

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

谢谢，柴坦尼亚

Answer 1

将条目复制到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());
}