TreeMap has a bug in headMap() as of Java 1.4.2

[maxmike]

If a TreeMap contains only a null key and you request
headMap(<non-null-key>) it returns an empty Map. The custom comparator
specifies null as the smallest value. Does anybody know if this has
been fixed in 1.5?

 

[hiwa]

I have written an
SSCCE(http://homepage1.nifty.com/algafield/sscce.html) for your
problem. Please attach your own SSCCE for simplifying the test. JDK
1.6(beta) does not have the problem you have mentioned:

import java.util.*;

public class NullKey{

public static void main(String[] args){
TreeMap<KeyObj, String> tm
= new TreeMap<KeyObj, String>(new KeyObjComparator());

tm.put(null, "Null");
tm.put(new KeyObj(10), "ten");

SortedMap sm = tm.headMap(new KeyObj(10));
System.out.println(sm.size());
System.out.println(sm.get(null));
}
}

class KeyObj{
Integer num;

public KeyObj(Integer n){
num = n;
}
}

class KeyObjComparator implements Comparator<KeyObj>{

public int compare(KeyObj o1, KeyObj o2){
int retval;

if (o1 == null){
if (o2 == null){
retval = 0;
}
else{
retval = -1;
}
}
else if (o2 == null){
retval = 1;
}
else{
retval = o1.num.compareTo(o2.num);
}
return retval;
}
}

 

[hiwa]

1.4.2 just works fine.
(1.4.2_08 on Linux)

 

[Oliver Wong]

I have written an
SSCCE(http://homepage1.nifty.com/algafield/sscce.html) for your
problem. Please attach your own SSCCE for simplifying the test. JDK
1.6(beta) does not have the problem you have mentioned:

[code snipped]

Your code puts TWO elements in the hashmap. The OP said this bug occurs when
there's only one element in the hashmap. Here's a slightly simplified SSCCE
which demonstrates the problem:

<code>
import java.util.*;

public class NullKey {

public static void main(String[] args) {
TreeMap<Integer, String> tm = new TreeMap<Integer, String>(
new KeyObjComparator());

tm.put(null, "Foo");
// tm.put(Integer.valueOf(10), "ten");
System.out.println(tm.size());
SortedMap sm = tm.headMap(Integer.valueOf(10));
System.out.println(sm.size());
System.out.println(sm.get(null));
}
}

class KeyObjComparator implements Comparator<Integer> {

public int compare(Integer o1, Integer o2) {
int retval;

if (o1 == null) {
if (o2 == null) {
retval = 0;
} else {
retval = -1;
}
} else if (o2 == null) {
retval = 1;
} else {
retval = o1.compareTo(o2);
}
return retval;
}
}
</code>

The output is "1\n0\nFoo\n" when it should be "1\n\1\nFoo\n". This bug
occurs on Java 1.5.0_06-b05

- Oliver

 

[Eric Sosman]

maxmike wrote On 04/09/06 17:18,:

If a TreeMap contains only a null key and you request
headMap(<non-null-key>) it returns an empty Map. The custom comparator
specifies null as the smallest value. Does anybody know if this has
been fixed in 1.5?

It seems to me (not a language lawyer) that such a
custom Comparator must be inconsistent with equals:

theComparator(null, non_null) returns a negative
number, but

null.equals(non_null) throws an exception.

Is inconsistency with equals enough to cast doubt
on the bugginess of a Map's strange behavior?

 

[Christian Kaufhold]

If a TreeMap contains only a null key and you request
headMap(<non-null-key>) it returns an empty Map. The custom comparator
specifies null as the smallest value. Does anybody know if this has
been fixed in 1.5?

It has not.

The bug is in SubMapEntryIterator (and DescendingSubMapEntryIterator)
which sometimes stop iterating incorrectly before null keys.


Christian

 

[Patricia Shanahan]

maxmike wrote On 04/09/06 17:18,:



It seems to me (not a language lawyer) that such a
custom Comparator must be inconsistent with equals:

theComparator(null, non_null) returns a negative
number, but

null.equals(non_null) throws an exception.

Is inconsistency with equals enough to cast doubt
on the bugginess of a Map's strange behavior?

I think it would have been better if all the Map classes had excluded
null keys, and thrown NullPointerException on any attempt to put one.

However, that is not how TreeMap is defined. It accepts null as a key.
It specifies NullPointerException conditions such as "key is null and
this map uses natural ordering, or its comparator does not tolerate null
keys" (containsKey).

Moreover, TreeMap is not even consistent with itself. It should make up
its mind whether the null key is there or not. It reports size() zero,
but returns a non-null value on get(null).

According to the Javadoc, "The behavior of a sorted map is well-defined
even if its ordering is inconsistent with equals; it just fails to obey
the general contract of the Map interface."

Patricia

 

[maxmike]

It has not.

The bug is in SubMapEntryIterator (and DescendingSubMapEntryIterator)
which sometimes stop iterating incorrectly before null keys.


Christian

Thanks, Christian - it is actually important in my case to have null in
the btree, but I have
managed to walk around this bug by testing if the entire tree is empty
when there is only a null in it.