MapのソートをStream#sortedで行うと安定ソートにならない件

Posted on by つちえ

タイトルの通りですが、Mapのソートが安定ソートにならなかったので、その例と対応策(?)をまとめておきたいと思います。

例）Mapの値(昇順)で並び替える場合

Map<String, String> map = new HashMap<>();
map.put("Y", "a");
map.put("X", "a");

map.entrySet().stream()
   .sorted(Map.Entry.comparingByValue())
   .forEach(System.out::println);

// 出力結果
// X=a
// Y=a

Arrays#sortは安定ソートなので同じような結果になると思いまいたが、違うようです…

ドキュメントを見てみたり実装を覗いてみましたが、なんだかんだ解決に至らず数時間をムダにしてしまいました。
解決策は単純で`HashMap`を`LinkedHashMap`に替えるだけでした。(ソートアルゴリズムは関係なかったです…)
Map<String, String> map = new LinkedHashMap<>();
// 同じ処理なので省略

// 出力結果
// Y=a
// X=a

ドキュメントに記載されているぐらい超キホン的なことですが、地味にはまったので違いをまとめて終わりにしようかと思います。

API 特徴
HashMap 順序を保持しないMap。キーをハッシュ化して保持しているので、検索処理はMapの中で最速。
LinkedHashMap 順序が挿入順になるようデータを保持するMap。データ件数に比例して検索処理が遅くなる。

以上。