りふれろぐ

メモみたいな

Java9: Set.ofとCollections.unmodifiableSetの違い

しばらくJavaを書いてなかったのだが、最近必要な場面が出てきてしまった。
いつの間にかJava9どころかJava10が出ていて、色々と新しい機能が追加されているらしい。

変更不可能な Set が必要になったので、新しい知識のない私は次のコードを書いた。

Object[] objects;
/* 略 */
Set<Object> set = Collections.unmodifiableSet(new HashSet<>(Arrays.asList(objects)));

ところが、Java9において、引数に要素を与えると変更不可能な Set を返してくれるメソッド Set.of(E...) が追加されていたらしい。これを用いるとコードは以下のようになる。

Object[] objects;
/* 略 */
Set<Object> set = Set.of(objects);

めっちゃシンプル。わかりやすい。

パフォーマンスについてはどうなのだろうか。気になったので実装を調べたり、実験を行ったりしてみた。

実装

Collections.unmodifiableSet は、引数の Set をラップし、変更を加えるメソッドを使用できないようにしたものである*1。探索等の性能は引数に与えられた Set の実装に依存する。
今回のコードで引数に与えた HashSet は、内部的に HashMap を用いている。HashMap はいわゆるハッシュテーブルであり、ハッシュ値の衝突時処理は連鎖法である。

一方で、Set.of で返されるのは java.util.ImmutableCollections$AbstractImmutableSet の子クラスである。要素数によって異なるが、Java10では要素数が3以上であれば java.util.ImmutableCollections$SetN となるらしい。
このクラスもまたハッシュテーブルのような実装を行っているらしいが、HashSet と異なる点がいくつかある。

  • Map を使用していない。言い換えれば、キーのみを格納している。
  • 衝突処理は開番地法である。
  • 実装そのものの段階で変更不可能な Set となっている

パフォーマンスに関わる部分での違いは、衝突処理であろう。ハッシュ値が衝突するようなケースに対して、探索の性能はどのような違いを見せるだろうか。

実験

衝突が少ない場合

まず、衝突があまり起きない場合のパフォーマンスを調査する。

  • 要素の型となる適当なクラスを作成する。デフォルトではハッシュ値は Object クラスにおけるものを利用するため、おそらく衝突はあまり起きないだろう。
class MyObject extends Object {
	@Override
	public int hashCode() {
		return super.hashCode();
	}
}
  • 要素が N 個含まれる Set を、Set.of と Collections.unmodifiableSet の両方で作成する。作成の時間をそれぞれ計測する。なお、含まれる要素は同じにしてある。
  • 各 Set で、Set に含まれる要素に対し、M 回探索を行い、全体の時間を計測する。探索に用いる要素は各 Set で同じにしてある。
  • 各 Set で、Set に含まれない要素に対しても M 回探索を行い、時間を計測する。

N=100000, M=1000000 において、結果は以下のようになった。探索時間については探索1回あたりの時間としてある。

実装 作成 探索(含まれる場合) 探索(含まれない場合)
Set.of 11 ms 71 ns/回 77 ns/回
unmodifiableSet 14 ms 109 ns/回 54 ns/回

Set.of を用いたほうが探索のの効率が良さそうに見える。含まれない要素を探索した場合には、Collections.unmodifiableSet の方が時間が短くなった。

衝突が頻繁に起きる場合

MyObject クラスの hashCode の実装を、以下のように変更し、有効長を16ビットに落とす。

class MyObject extends Object {
	@Override
	public int hashCode() {
		return super.hashCode() & 0xffff;
	}
}

ほかの手順は同様であるが、M の値は変更してある。

N=100000, M=100000 において、結果は以下のようになった。

実装 作成 探索(含まれる場合) 探索(含まれない場合)
Set.of 5699 ms 44016 ns/回 173851 ns/回
unmodifiableSet 11 ms 122 ns/回 117 ns/回

Set.of の構築時間と得られた Set の探索時間が圧倒的に長くなってしまった。特に要素が含まれていない場合の探索時間が極端に悪化している。

衝突がほぼ常に起きる場合

ハッシュ値の有効長を8ビットまで落としてみた。

class MyObject extends Object {
	@Override
	public int hashCode() {
		return super.hashCode() & 0xff;
	}
}

N=100000, M=1000 において、結果は以下のようになった。

実装 作成 探索(含まれる場合) 探索(含まれない場合)
Set.of 16589 ms 141861 ns/回 279651 ns/回
unmodifiableSet 451 ms 7859 ns/回 9816 ns/回

ここまでくるとどちらの場合でも探索時間は非常に長くなってしまう。それでもなお Collections.unmodifiableSet の方が短い。

hashCode を定数とした場合

極端な例として、hashCode が定数を返す場合も実験する。

class MyObject extends Object {
	@Override
	public int hashCode() {
		return 0;
	}
}

N=100000, M=1000 において、結果は以下のようになった。

実装 作成 探索(含まれる場合) 探索(含まれない場合)
Set.of 16208 ms 133914 ns/回 264429 ns/回
unmodifiableSet 105433 ms 1072630 ns/回 2360586 ns/回

ここまでくると、HashSetをベースにした unmodifiableSet は線形探索のようになる(と思われる)ため、Set.of の場合よりも(10倍くらい)時間がかかるようになってしまった。

まとめ

  • Set.of を用いると簡単に変更不可能な Set を作ることができる
  • hashCode は衝突しづらくなるように実装しよう
  • ハッシュ値が衝突しづらければ Set.of で作ったほうが速いし楽


ところで、キーが順序付けできる場合には TreeSet などをベースにして、変更不可能な SortedSet や NavigableSet を作ることもできる。Collections.unmodifiableSortedSet や Collections.unmodifiableNavigableSet を参照。このあたりのパフォーマンスは調べるのが面倒になった。

*1:引数に与えた Set を直接変更してしまえば、ラップされた変更不可能なはずの Set も変更されてしまう。このようなことがないよう注意しなければならない。