monzdrpower December 26, 2012 at 14:38

Java job interview. Collections vs null

Hello!

In the topic of Java interview. Collections detail the issue of working with Set & Map in Java. But I still have a couple of favorite questions from this area:

Can null be used as a key in Map?
Can Set contain null ?

tooltip (HashMap.java)

   public V get(Object key) {  
        if (key == null)  
            return getForNullKey();  
        int hash = hash(key.hashCode());  
        for (Entry e = table[indexFor(hash, table.length)];  
             e != null;  
             e = e.next) {  
            Object k;  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
                return e.value;  
        }  
        return null;  
    }  
    /** 
     * Offloaded version of get() to look up null keys.  Null keys map 
     * to index 0.  This null case is split out into separate methods 
     * for the sake of performance in the two most commonly used 
     * operations (get and put), but incorporated with conditionals in 
     * others. 
     */  
    private V getForNullKey() {  
        for (Entry e = table[0]; e != null; e = e.next) {  
            if (e.key == null)  
                return e.value;  
        }  
        return null;  
    }

It is assumed that an inquisitive reader will independently reflect on the answers and then compare them with mine. The most impatient can immediately proceed to cat.

1. Can null be used as a key in Map?

Hashmap

Map map = new HashMap();
map.put(null,  "test"); // момент истины ... ошибки нет!

We look inside

System.out.println(map.size()); // вывод: 1
System.out.println(map.get(null)); // вывод: test

What is going on? Quote from the source:

When adding a new key-value pair, it calculates the hash code of the key, based on which the number of the basket (cell number of the array) into which the new element falls is calculated.

That is, it turns out that hash-code is calculated from null ... hmmm. But how is it calculated without an object, without hashCode ()? My answer is I don’t know, but the debugger shows that for null hash = 0. Apparently somewhere there is a separate check.

Then all without surprises, another object with hash = 0 falls into the same "basket".

map.put(0,  "0");
System.out.println(map.size()); // вывод: 2

Answer No. 1: HashMap operates with a null key without any problems. Its hash is always 0

for a particularly exotic case map.put (null, null)

Map map = new HashMap();
map.put(null,  null); 
map.get(null);  // результат null говорит нам, что значения по этому ключу нет, значит и самого ключа тоже нет
map.containsKey(null); // результат true: а ключ на самом деле есть, и значение тоже есть

thanks Vanger13

Treemap

Map map = new TreeMap();
map.put(null,  "null"); // ошибки нет!

But it must be!

javadoc requires NPE
thanks vkolotov

We look inside

System.out.println(map.size()); // вывод: 1
System.out.println(map.get(null)); // БАБАХ!! Exception in thread "main" java.lang.NullPointerException

But it all started so well! Put put, it lies there (size = 1), but we can’t get it back. Well ok, let's say we don’t have to get anything. And we only want to put, these are we strange. We try.

Map map = new TreeMap();
map.put(null,  "null"); // ошибки нет
System.out.println(map.size()); // вывод: 1
map.put(0,  "0"); // БАБАХ!! Exception in thread "main" java.lang.NullPointerException

Single Mapa, some kind. Or not? Add dramas, change insertion order

Map map = new TreeMap();
map.put(0,  "0"); // ошибки нет 
map.put(1,  1); // ошибки нет 
System.out.println(map.size()); // вывод: 2
map.put(null,  "null"); // БАБАХ!! Exception in thread "main" java.lang.NullPointerException

What kind of daisy is it? Does null work, then it doesn’t work ?! But it turns out this. When we add the null key to an empty tree - it falls into root. And root, comrades, he is also root in Africa, he is more equal than all the others, compareTo () is not called for him and null calmly takes its place in the root of the tree. And if the tree is not empty, attempts to compare with the existing content begin, and we get a “legitimate” NPE. No special conditions for null are provided here.

Answer # 2: You can put a single key-null in an empty TreeMap, all other operations (except size () and clear (), by the way) do not work after that. You cannot put a null key in a non-empty TreeMap due to the mandatory call to compareTo ().

2. Can Set contain null?

The answer to this question repeats the previous ones, given the fact that Set, in fact, is implemented on the basis of Map. HashSet works with a bang, TreeSet - only for the first element.

Thanks for attention.

Useful links:
Java interview. Collections by sphinks
Data Structures: Binary Trees. Part 1 by winger
Data Structures: Binary Trees. Part 2: a review of balanced trees by winger
Data structures in pictures. HashMap by tarzan82

Tags:

Java job interview. Collections vs null

1. Can null be used as a key in Map?

Hashmap

Treemap

2. Can Set contain null?

Also popular now: