JavaのSortedSet

java

JavaのSortedSetについての備忘録。
HashSetなどの通常のSetは要素比較にオブジェクトのequalsを使うが、TreeSetなどのSortedSetは要素比較にcompareTo(またはcompare)を使う。そのため、SortedSetにComparatorを設定している場合は、要素比較の結果がHashSetなどとは異なることがある。

OpenJDKのソースコード

Setのequalsはcontainsを呼ぶ。

HashSet

HashSetのcontainsは、内部で保持しているHashMapのcontainsKeyを呼び、==またはkey.equalsで比較する。

TreeSet

TreeSetのcontainsは、内部で保持しているTreeMapのcontainsKeyを呼び、compareTo(またはcompare)で比較する。
そのため、String.CASE_INSENSITIVE_ORDERなどを使っていると、オブジェクトのequalsと結果が変わってくる。

Demo

% java -version
openjdk version "17.0.2" 2022-01-18
OpenJDK Runtime Environment Temurin-17.0.2+8 (build 17.0.2+8)
OpenJDK 64-Bit Server VM Temurin-17.0.2+8 (build 17.0.2+8, mixed mode, sharing)

String.CASE_INSENSITIVE_ORDERを使ったTreeSetを作成して、初期データ（a, B, c）を追加する

jshell> Set<String> tree = new TreeSet<>(String.CASE_INSENSITIVE_ORDER)
tree ==> []

jshell> tree.add("a")
$2 ==> true

jshell> tree.add("c")
$3 ==> true

jshell> tree.add("B")
$4 ==> true

jshell> tree
tree ==> [a, B, c]

case insensitiveなので、大文字・小文字は区別されない

jshell> tree.contains("a")
$6 ==> true

jshell> tree.contains("A")
$7 ==> true

jshell> String.CASE_INSENSITIVE_ORDER.compare("a", "A")
$8 ==> 0

このTreeSetから作ったHashSetは、大文字・小文字が区別される

jshell> Set<String> hash = new HashSet<>(tree)
hash ==> [a, B, c]

jshell> hash.contains("a")
$12 ==> true

jshell>  hash.contains("A")
$13 ==> false

２つのSetは同じデータを持っているので、equalsはどちらもtrueになる

jshell> tree.equals(hash)
$14 ==> true

jshell> hash.equals(tree)
$15 ==> true

この状態から片方のSetの要素を大文字に変更する
（HashSetから小文字のcを削除して、大文字のCを追加する）

jshell> hash.remove("c")
$16 ==> true

jshell> hash.add("C")
$17 ==> true

jshell> hash
hash ==> [a, B, C]

jshell> tree
tree ==> [a, B, c]

大文字・小文字の違いがあるためHashSetのequalsはfalse になるが、TreeSetはcase insensitiveのためtrueになる

jshell>  hash.equals(tree)
$21 ==> false

jshell>  tree.equals(hash)
$22 ==> true

参考