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

Всем привет!

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

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

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

Сразу скажу, что все результаты получены опытным путем, теоретические обоснования и исправления (ну мало ли) приветствуются.

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

HashMap

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

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

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

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

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

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

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

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

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

TreeMap

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

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

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