TreeMap Strange

[Jean John]

Why is that if your treemap is empty and you try to remove some invalid key,there is no exception, whereas if the treemap has atleast one element and you try to remove an invalid key,it is a runtime exception? someone please explain.. Thanks.

This is the scenario i am talking about

import java.util.*;
public class Test{
	public static void main(String args[]){
		Map<Integer,String> m=new TreeMap<Integer,String>();
		m.clear();
		m.remove("hi");     //Possible Exception Statement?
		
		System.out.println(m.get(10));
		
	}
}

output:null
(No error)

import java.util.*;
public class Test{
	public static void main(String args[]){
		Map<Integer,String> m=new TreeMap<Integer,String>();
		m.clear();
		m.put(1, "java");
		m.remove("hi");    //Now this gives a runtime exception
		
		System.out.println(m.get(100));
		System.out.println(m.size());
	}
}

output: Run time Exception (Only for TreeMap
LinkedHashMap and HashMap dont care about what you are trying to remove)

[Jesper de Jong]

Welcome to JavaRanch!

The error that you get does not have anything to do with whether the map is empty or not. You're using it the wrong way.

You have a Map<Integer, String>. When you call the remove() method, you must call it with an Integer as the argument, but you are calling it with a string. Instead of this:

m.remove("hi");

you should be doing something like this:

m.remove(2);

[Rob Spoor]

Please UseCodeTags next time; I've added them for you this time.

Jesper, I (partly) disagree with your answer. Map.remove explicitly uses Object as its argument type; you are allowed to try to remove anything from the map. There's a but there though; the method is allowed to throw a ClassCastException.

Jean, the reason for this exception is this: TreeMap uses the compareTo method of its elements to find elements*. This means that when you try to remove the String, it will compare the String to the Integer. That's not allowed though; as String.compareTo requires a String and Integer.compareTo requires an Integer. I don't know which is being compared to which, but in the end the comparison is causing the ClassCastException. And unfortunately, that's allowed under the contract of Map. I get the feeling this exception was added because of TreeMap though.

As for why HashMap and LinkedHashMap don't throw an exception: these use hashCode() and equals. Unlike compareTo, equals is not allowed to throw a ClassCastException when the passed argument is of a wrong class; it's required to return false instead. So "hi".compareTo(1) throws an exception, "hi".equals(1) returns false.


* unless a Comparator is given in the constructor; in that case, the Comparator's compare method is used.

[Prasanna Soundarapandiyan]

Well, its really a nice question..

The reason for this behaviour is the implementation of TreeMap. while trying to remove an object out of Treemap, you are calling map.remove(key) method. Please see the implementation of remove method for Treemap,

   @SuppressWarnings("unchecked")
    @Override
    public V remove(Object key) {
        Comparable<K> object = comparator == null ? toComparable((K) key) : null;
        if (size == 0) {
            return null;
        }
        K keyK = (K) key;
        Node<K, V> node = root;
        while (node != null) {
            K[] keys = node.keys;
            int left_idx = node.left_idx;
            int result = cmp(object, keyK, keys[left_idx]);
            if (result < 0) {
                node = node.left;
            } else if (result == 0) {
                V value = node.values[left_idx];
                removeLeftmost(node);
                return value;
            } else {
                int right_idx = node.right_idx;
                if (left_idx != right_idx) {
                    result = cmp(object, keyK, keys[right_idx]);
                }
                if (result > 0) {
                    node = node.right;
                } else if (result == 0) {
                    V value = node.values[right_idx];
                    removeRightmost(node);
                    return value;
                } else { /*search in node*/
                    int low = left_idx + 1, mid = 0, high = right_idx - 1;
                    while (low <= high) {
                        mid = (low + high) >> 1;
                        result = cmp(object, keyK, keys[mid]);
                        if (result > 0) {
                            low = mid + 1;
                        } else if (result == 0) {
                            V value = node.values[mid];
                            removeMiddleElement(node, mid);
                            return value;
                        } else {
                            high = mid - 1;
                        }
                    }
                    return null;
                }
            }
        }
        return null;
    }

So, if you dont have any object in your map, then its size will be 0, and obviously it will return null only with out allowing further processing.

[Jean John]

Prasanna Soundarapandiyan wrote:Well, its really a nice question..

The reason for this behaviour is the implementation of TreeMap. while trying to remove an object out of Treemap, you are calling map.remove(key) method. Please see the implementation of remove method for Treemap,

   @SuppressWarnings("unchecked")
    @Override
    public V remove(Object key) {
        Comparable<K> object = comparator == null ? toComparable((K) key) : null;
        if (size == 0) {
            return null;
        }
        K keyK = (K) key;
        Node<K, V> node = root;
        while (node != null) {
            K[] keys = node.keys;
            int left_idx = node.left_idx;
            int result = cmp(object, keyK, keys[left_idx]);
            if (result < 0) {
                node = node.left;
            } else if (result == 0) {
                V value = node.values[left_idx];
                removeLeftmost(node);
                return value;
            } else {
                int right_idx = node.right_idx;
                if (left_idx != right_idx) {
                    result = cmp(object, keyK, keys[right_idx]);
                }
                if (result > 0) {
                    node = node.right;
                } else if (result == 0) {
                    V value = node.values[right_idx];
                    removeRightmost(node);
                    return value;
                } else { /*search in node*/
                    int low = left_idx + 1, mid = 0, high = right_idx - 1;
                    while (low <= high) {
                        mid = (low + high) >> 1;
                        result = cmp(object, keyK, keys[mid]);
                        if (result > 0) {
                            low = mid + 1;
                        } else if (result == 0) {
                            V value = node.values[mid];
                            removeMiddleElement(node, mid);
                            return value;
                        } else {
                            high = mid - 1;
                        }
                    }
                    return null;
                }
            }
        }
        return null;
    }

So, if you dont have any object in your map, then its size will be 0, and obviously it will return null only with out allowing further processing.

Seeing the implementation was really helpful..Thank you... Can you please tell me where you get the implementation details of the various java methods. Thanks in advance

[Henry Wong]

Jean John wrote:
Seeing the implementation was really helpful..Thank you... Can you please tell me where you get the implementation details of the various java methods. Thanks in advance

The source code for most of the core library is provided with the JDK -- as a src zip file on the top level directory of the installation.

Henry