TreeSetにnullをaddする話

Java で TreeSet に null を add すると NullPointerException になります。*1

Airof:~ irof$ groovysh
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
Groovy Shell (1.8.2, JVM: 1.6.0_26)
Type 'help' or '\h' for help.
-----------------------------------------------------------------------------------------------------------
groovy:000> s = new TreeSet()
===> []
groovy:000> s.add(1)
===> true
groovy:000> s.add(null)
ERROR java.lang.NullPointerException:
null
        at java_util_Set$add.call (Unknown Source)
        at groovysh_evaluate.run (groovysh_evaluate:2)
        ...
groovy:000> 

groovysh ですけど Exception は Java で出てますから問題ありません。
ところで JavaSE6 では1件目に null が入るらしいです。試してみます。

Airof:~ irof$ groovysh
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
Groovy Shell (1.8.2, JVM: 1.6.0_26)
Type 'help' or '\h' for help.
-----------------------------------------------------------------------------------------------------------
groovy:000> s = new TreeSet()
===> []
groovy:000> s.add(null)
===> true

あら、本当に入った。

でも続けるとこうなる。

Airof:~ irof$ groovysh
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
Groovy Shell (1.8.2, JVM: 1.6.0_26)
Type 'help' or '\h' for help.
-----------------------------------------------------------------------------------------------------------
groovy:000> s = new TreeSet()
===> []
groovy:000> s.add(null)
===> true
groovy:000> s.add(null)
ERROR java.lang.NullPointerException:
null
        at java_util_Set$add.call (Unknown Source)
        at groovysh_evaluate.run (groovysh_evaluate:2)
        ...
groovy:000> s.add(1)   
ERROR java.lang.NullPointerException:
null
        at java_util_Set$add.call (Unknown Source)
        at groovysh_evaluate.run (groovysh_evaluate:2)
        ...

つまりその後一切追加出来ない状態です。これは嬉しくない。

これだとどこで出てるか解らないのでStackTraceを出してみます。上の方だけ。

groovy:000> try{s.add(1)}catch(Exception e){e.printStackTrace()}
java.lang.NullPointerException
	at java.lang.Integer.compareTo(Integer.java:978)
	at java.lang.Integer.compareTo(Integer.java:37)
	at java.util.TreeMap.put(TreeMap.java:545)
	at java.util.TreeSet.add(TreeSet.java:238)
	at java_util_Set$add.call(Unknown Source)
	at org.codehaus.groovy.runtime.callsite.CallSiteArray.defaultCall(CallSiteArray.java:42)

予想通り、 compareTo です。 TreeSet は自然順序付けなので要素同士を比較するわけです。
ちなみに add するのが null の場合はこうなります。

groovy:000> try{s.add(null)}catch(Exception e){e.printStackTrace()}                               
java.lang.NullPointerException
	at java.util.TreeMap.put(TreeMap.java:541)
	at java.util.TreeSet.add(TreeSet.java:238)
	at java_util_Set$add.call(Unknown Source)
	at org.codehaus.groovy.runtime.callsite.CallSiteArray.defaultCall(CallSiteArray.java:42)

ちょっと発生個所が違っているのは、 compareTo 呼ぶ前に Key の null チェックを行っているから。と言う事で、そもそも TreeMap の Key に null は使えない*2感じですね。それに引き摺られて TreeSet にも使えないという事です。詳しくは TreeMap を開いて該当行を見て下さい。

TreeMap を見てると、そもそもデフォルトコンストラクタの場合は Key を Comparable にキャストして比較している事に気づきます。と言うわけで、 Comparable でないものを TreeMap の Key にしたり、 TreeSet に入れれば「それと比較した時」に ClassCastException になるようです。つまり、当然ながらこれがアウト。*3

import java.util.TreeSet;

public class Hoge {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        set.add(new Object());
        set.add(new Object());
    }
}

実行するとこのように、２つ目の add で ClassCastException が発生します。

Airof:sandbox irof$ java -version
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
java version "1.6.0_26"
Java(TM) SE Runtime Environment (build 1.6.0_26-b03-383-11A511)
Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02-383, mixed mode)
Airof:sandbox irof$ java Hoge
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
Exception in thread "main" java.lang.ClassCastException: java.lang.Object cannot be cast to java.lang.Comparable
	at java.util.TreeMap.put(TreeMap.java:542)
	at java.util.TreeSet.add(TreeSet.java:238)
	at Hoge.main(Hoge.java:7)

正確には「してました」になります。
JavaSE7 だと*4こうなります。Hoge.java:6、つまり1つ目の add で ClassCastException が発生してます。

Airof:sandbox irof$ java -version
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
openjdk version "1.7.0-ea"
OpenJDK Runtime Environment (build 1.7.0-ea-b215)
OpenJDK 64-Bit Server VM (build 21.0-b17, mixed mode)
Airof:sandbox irof$ java Hoge
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
Exception in thread "main" java.lang.ClassCastException: java.lang.Object cannot be cast to java.lang.Comparable
	at java.util.TreeMap.compare(TreeMap.java:1188)
	at java.util.TreeMap.put(TreeMap.java:531)
	at java.util.TreeSet.add(TreeSet.java:255)
	at Hoge.main(Hoge.java:6)

これが"正しい挙動"です。そもそも一つ目が add 出来たのがおかしくて、それが JavaSE7 で修正されたってことらしいです。

このエントリを書いてるのは「JavaOne 2011 報告会 at 大阪」の細かい話「TreeSet の1件目 null のバグが修正された」のデモ時に見えたのが NullPointerException ではあるものの、発生個所が add でも put でもなく compare だったのが気になったからです。

なんかまとまらなくなって来た感じがありますが、この辺で JavaSE7 で TreeSet に null をぶっ込みます。

Airof:~ irof$ groovy -version
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
Groovy Version: 1.8.2 JVM: 1.7.0-ea
Airof:sandbox irof$ groovy -e "new TreeSet().add(null)"
Picked up _JAVA_OPTIONS: -Dfile.encoding=UTF-8
Caught: java.lang.NullPointerException
java.lang.NullPointerException
	at java_util_Set$add.call(Unknown Source)
	at script_from_command_line.run(script_from_command_line:1)
Airof:~ irof$ 

はい、1件目でも無事 NullPointerException が発生してます。発生個所は先ほど new Object() を put してたとこと同じです。

TreeMap のputを見ると、531行目にこんな記述がありました。

 528     public V put(K key, V value) {
 529         Entry<K,V> t = root;
 530         if (t == null) {
 531             compare(key, key); // type (and possibly null) check
 532 
 533             root = new Entry<>(key, value, null);
 534             size = 1;
 535             modCount++;
 536             return null;
 537         }

compare に 同じ key を渡してます。なんでこんな事をしてるかと言うと、「比較出来るか」を実際比較する事で試してるみたいです。compare自体の実装は至ってシンプルですね。

1185      * Compares two keys using the correct comparison method for this TreeMap.
1186      */
1187     final int compare(Object k1, Object k2) {
1188         return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1189             : comparator.compare((K)k1, (K)k2);
1190     }

だいじなこと

最期に一つだけ誤解して欲しくないのが「TreeMap の Key に null が使えない」では無い事。デフォルトコンストラクタを使用する場合は使えないだけです。つまり、これは通ります。JavaSE6 だろうと JavaSE7 だろうと関係なく。

groovy:000> s = new TreeSet([compare:{o1,o2 -> 1}] as Comparator)
===> []
groovy:000> s.add(null)
===> true
groovy:000> s.add(1)
===> true
groovy:000> s.add(1)
===> true

ただしこの場合、常にcompareが1を返すので、二回目の add(1) が true になっているように、同じ値でもいくらでも追加されていきます。Compareが0だと1つしか追加出来ません。そして contains は常に false を返します。TreeSet の場合は順序付けのみが同じかの判断基準になるためです。

まぁJavadocに書いてるんだけどね

Javadocについても言及して欲しいかも。 / TreeSetにnullをaddする話 - 日々常々 URL

2011-10-31 23:35:45 via Hatena

ハイ！＞＜

add
public boolean add(E e)
（説明略）
例外
NullPointerException - 指定された要素が null であり、このセットが自然順序付けを使用しているかそのコンパレータが null 要素を許可しない場合

Oracle Technology Network for Java Developers | Oracle Technology Network | Oracle

そのまま。 Set の実装次第( Comparator が許容する場合)では null は add 出来る事になってます。
ちなみに HashSet (これも内部では HashMap )では null は特別扱いしつつ add 出来るようにごにょってます。hash値とか計算しようないしコケるんじゃねーの？とか思ってました。
なお Set インタフェースの add は実装が許さない場合のみ NullPointerException を投げると書かれてるだけです。

参考

• Javadoc
  • Oracle Technology Network for Java Developers | Oracle Technology Network | Oracle
  • Oracle Technology Network for Java Developers | Oracle Technology Network | Oracle
• Mapのキーと値にnullを格納できるか？

*1:正確には違いますが、後述してますのでツッコミは堪えてくださいませ。

*2:正確には「デフォルトコンストラクタの TreeMap の Key には使えない」です。

*3:唯一のJavaコード。

*4:Macなんで1.7.0-eaですけど、もちろんWindowsでも同じです。