monzdrpower 26 дек 2012 в 14:38

Java собеседование. Коллекции vs null

3 мин

129K

Всем привет!

В топике Java собеседование. Коллекции подробно изложен вопрос работы с Set & Map в Java. Но у меня ещё есть парочка любимых вопросов из этой области:

Может ли null использоваться в качестве ключа в Map?
Может ли Set содержать null?

подсказка (HashMap.java)

   public V get(Object key) {  
        if (key == null)  
            return getForNullKey();  
        int hash = hash(key.hashCode());  
        for (Entry<K,V> 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<K,V> e = table[0]; e != null; e = e.next) {  
            if (e.key == null)  
                return e.value;  
        }  
        return null;  
    }

Предполагается, что пытливый читатель самостоятельно поразмыслит над ответами и затем сравнит их с моими. Самые нетерпеливые могут сразу проследовать под кат.

1. Может ли null использоваться в качестве ключа в Map?

HashMap

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

Смотрим, что внутри

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

Что же происходит? Цитата из первоисточника:

При добавлении новой пары ключ-значение, вычисляет хеш-код ключа, на основании которого вычисляется номер корзины (номер ячейки массива), в которую попадет новый элемент.

То есть получается, что вычисляется hash-code от null… хммм. Но как же он вычисляется без объекта, без hashCode()? Мой ответ — не знаю, но дебаггер показывает, что для null hash=0. Видимо где-то есть отдельная проверка.

Дальше все без сюрпризов, другой объект с hash=0 попадает в ту же «корзину».

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

Ответ №1: HashMap оперирует с null-ключом без каких-либо проблем. Его hash всегда равен 0

для особо экзотического случая map.put(null, null)

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

спасибо Vanger13

TreeMap

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

Но должна быть!

javadoc требует NPE
спасибо vkolotov

Смотрим, что внутри

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

А ведь так все хорошо начиналось! Положить положили, оно там лежит (size=1), но достать обратно не можем. Ну ок, допустим нам вовсе и не надо ничего доставать. А мы хотим только класть, вот такие мы странные. Пробуем.

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

Одноместная мапа, какая-то. Или нет? Добавим драмы, поменяем порядок вставки

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

Это что же за ромашка получается, null то работает, то не работает?! А получается вот что. Когда мы добавляем ключ null в пустое дерево — он попадает в root. А root, товарищи, он и в Африке root, он равнее всех прочих, для него не происходит вызова compareTo() и null спокойно занимает своё место в корне дерева. А если дерево не пустое — начинаются попытки сравнения с имеющимся содержимым, и мы получаем «законный» NPE. Никаких особых условий для null здесь не предусмотрено.

Ответ №2: В пустой TreeMap можно положить единственный ключ-null, все остальные операции (кроме size() и clear(), кстати) после этого не работают. В непустой TreeMap положить null-ключ нельзя из-за обязательного вызова compareTo().

2. Может ли Set содержать null?

Ответ на этот вопрос повторяет предыдущие, с учетом того, что Set, собственно, реализован на основе Map. HashSet работает «на ура», TreeSet — только для первого элемента.

Спасибо за внимание.

Полезные ссылки:
Java собеседование. Коллекции by sphinks
Структуры данных: бинарные деревья. Часть 1 by winger
Структуры данных: бинарные деревья. Часть 2: обзор сбалансированных деревьев by winger
Структуры данных в картинках. HashMap by tarzan82

Теги:

Хабы:

Java

Java собеседование. Коллекции vs null

1. Может ли null использоваться в качестве ключа в Map?

HashMap

TreeMap

2. Может ли Set содержать null?

Публикации

Истории

Работа

Ближайшие события