Пользователь
0,0
рейтинг
26 декабря 2012 в 14:38

Разработка → Java собеседование. Коллекции vs null

Java*
Всем привет!

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

  1. Может ли null использоваться в качестве ключа в Map?
  2. Может ли 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"); // ошибки нет! 

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

Смотрим, что внутри
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
Михаил Денисов @monzdrpower
карма
35,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (47)

  • +1
    Бага. А ведь даже в javadoc сказано что должно бросаться NPE.
    • +1
      Там есть оговорка, что NPE только если в Map есть порядок.
      • 0
        Ну так TreeMap и есть упорядоченная коллекция.
        • 0
          Я просто подумал, что под багом вы имели в виду то, что null принимается в HashMap. Да, с TreeMap — бага.
      • +1
        Вы неправильно поняли оговорку. Только если используется natural ordering (то есть не используется компаратор), либо компаратор не обрабатывает null.
    • +1
      Технически там написано верно. Если put бросил NPE, значит вы задали ключом null и либо используется natural ordering, либо компаратор не допускает null keys. Но там не сказано, что если эти условия верны, то обязательно будет брошен NPE. Логическая импликация несимметрична :-)
      • +1
        Т.е. вы считаете что зря это исправили в 7ой джаве? :-)
        • +3
          Ни в коей мере :-) Да и, пожалуй, я перемудрил. Всё же документация читается как «если данные условия выполнены, то будет исключение», так что действительно документация не соответствовала реализации.
    • 0
      зафайлили?
  • +3
    Описанное поведение TreeMap поправлено в 7ой джаве. Возможно даже что фикс перенесен с одним из апдейтов в 6-ую.
    А из 1ой части про HashMap вы не сделали (по моему мнению) важный вывод. Что для java hashMap возможен результат 'get(key)' который вернул null и 'containsKey(key)' который вернул true. Иногда это может привести к логической ошибке, если кто-то поленится написать оба условния :)
    • 0
      Каким именно образом оно исправлено? Сразу кидает NPE или всегда корректно с null работает?
      • +1
        Вроде сразу кидает, сейчас не могу проверить.
        bugs.sun.com/view_bug.do?bug_id=5045147
        Кстати тоже смешно:
        Affected Versions: 1.3.1_06,6
        Fixed Versions: 7
        • +1
          Вот тут я объяснил, зачем так сделали. Написанное про Java 6 касается в равной степени и всех предыдущих — 1.3, 1.4 и 5.
      • +3
        Проверил — в 7-ке сразу падает с NPE, но там все хитро — ошибка будет если указанный в Map'e Comparator не поддерживает сравенения null. Компаратора по-умолчанию нет, поэтому мы пытаемся позвать null.compareTo(null) и тут уже падаем.
    • 0
      спасибо, добавил
    • +1
      Именно поэтому guava создала свои имплементации мэп и коллекций, которые не допускают null (как очереди в джаве, между прочим). Очень многие считают null в джаве ошибкой. «I call it my billion-dollar mistake.» — Sir C. A. R. Hoare, on his invention of the null reference
      • +1
        С null сейчас сражаются все, кому ни лень. И Scala, и Kotlin, и Ceylon — все так или иначе имеют какие-то способы указать типизированно и объектно отсутствие элемента без прибегания к null.
        • 0
          Java(-сообщество) вырастает из коротких штанишек наследства С++ типа null и Exception ( habrahabr.ru/post/146042/ и habrahabr.ru/post/155477/ см. про класс Either<Resut, Error> и Option<Resut>).

          С null самое плохое — на концептуальном уровне: возвращать null или кидать NPE — непонятно.
    • +1
      В шестёрке фиксить не стали:

      This is way too risky to fix in a jdk6 update release.


      Грубо говоря, представьте, что есть продакшен код, который эту фичу (случайно?) юзает. И вот люди обновляются с Java 1.6.0_50 на 1.6.0_51 и у н их всё грохается…

      А в Java 7 такие мелки штуки фиксать можно и нужно. Тем паче, что это реально баг.
      • 0
        А ещё у
        Map a = new HashMap();
        a.put("a", a);
        System.out.println(a);
        
        в разных версиях Java разные по фатальности последствия…
    • +1
      > если кто-то поленится написать оба условния

      Второе условие гарантирует первое, поэтому оба писать никогда не требуется. Скорее распространенной ошибкой можно назвать, когда «очищают ключ» через put(..., null) а не через remove().
  • +5
    > 1. Может ли null использоваться в качестве ключа в Map?
    > 2. Может ли Set содержать null?

    Ну так в документации на интерфейс Map прямо написано:

    Some map implementations have restrictions on the keys and values they may contain. For example, some implementations prohibit null keys and values, and some have restrictions on the types of their keys. Attempting to insert an ineligible key or value throws an unchecked exception, typically NullPointerException or ClassCastException. Attempting to query the presence of an ineligible key or value may throw an exception, or it may simply return false; some implementations will exhibit the former behavior and some will exhibit the latter. More generally, attempting an operation on an ineligible key or value whose completion would not result in the insertion of an ineligible element into the map may throw an exception or it may succeed, at the option of the implementation. Such exceptions are marked as «optional» in the specification for this interface.


    Про Set написано аналогично. Т.е. тут корректнее говорить не про Map/Set, а про конкретные реализации.
    • 0
      изначально это обощенный вопрос для собеседований на «поговорить». слово за слово, от интерфейсов к реализациям и их особенностям.
    • +2
      тут корректнее говорить не про Map/Set, а про конкретные реализации.

      Ну вообще говоря, странно будет если поведение конкретных реализаций будет отличаться от поведения определенного контрактом коллекции.
      • 0
        Ещё раз, цитата из документации к Map:
        Some map implementations have restrictions on the keys and values they may contain. For example, some implementations prohibit null keys and values, and some have restrictions on the types of their keys. Attempting to insert an ineligible key or value throws an unchecked exception, typically NullPointerException or ClassCastException.
      • 0
        Контракт-то как раз и не определяет.
  • +1
    Вообще, про это уже писали тут. На set расширяется тем, что HashSet основан на HashMap.
    • 0
      спасибо, добавил ссылку
  • 0
    А что мешает не строить предположения, а скачать JDK и посмотреть что в том же HashMap случай с null отдельно обрабатывается?
  • +6
    Ответ №2: В пустой TreeMap можно положить единственный ключ-null, все остальные операции (кроме size() и clear(), кстати) после этого не работают. В непустой TreeMap положить null-ключ нельзя из-за обязательного вызова compareTo().
    Я с таким ответом не согласен. Правильный ответ будет следующим:

    В TreeMap можно помещать null в качестве ключа, только если используется компаратор (а не естественный порядок) и компаратор умеет обрабатывать null в качестве аргумента.

    Вы ничего не сказали про компараторы, а ваш детальный разбор, что будет, если положить null в пустой или непустой TreeMap, бесполезен и даже вреден для разработчиков. Очевидно, такое поведение недокументировано, а значит, может измениться. Поэтому нужно считать, что складывать null при natural order просто нельзя. Неважно, единственный он или нет.

    К примеру, в WinAPI есть функции, где в ранних версиях в документации какой-то параметр был описан как «reserved, must be 0». Это именно означает, что надо передать 0, а не «я пробовал передавать разные числа, ничего страшного не случилось, так что передавайте, что хотите». Сегодня не случилось, а завтра выйдет апдейт к винде, и случится.
    • –1
      К примеру, в WinAPI есть функции, где в ранних версиях в документации какой-то параметр был описан как «reserved, must be 0».
      И эти люди запрещают мне ковыряться в носу! Сегодня, на Java, такая практика признана плохой. Но 1) во времена создания WinAPI ещё не было Java, 2) WinAPI, как говорит нам КО, вещь не объектно-ориентированная, даже без перегрузки функций 3) во времена создания WinAPI ООП ещё было несколько мутной вещью (вспомним язык Clipper).
      • –1
        WinAPI, как говорит нам КО, вещь… без перегрузки функций
        В общем, всё остальное можно было не писать читать.
    • 0
      Очевидно, такое поведение недокументировано, а значит, может измениться.
      Как-то раз я чуть не начал проходить собеседование в Oracle, в подразделение, занимающееся тестированием их родной Java-машины. Спасибо, вы меня натолкнули на понимание фразы интервьюера о «тестах, которые должны падать». Это как раз про такое поведение. Если его исправить, то с большой вероятностью у кучи народа всё повалится в production-е. Поэтому лучше отложить до следующей версии. А тесты на него уже есть.
  • +5
    Совершенно некорректные вопросы.
    Вопрос: «Может ли null использоваться в качестве ключа в Map?»
    Правильный ответ: Так как Map это интерфейс — то зависит от реализации.
    Подсказка: курим реализации (а также спецификации) HashMap, ConcurrentHashMap & Hashtable (который тоже Map).

    Вопрос: «Может ли Set содержать null?»
    Ответ: ну вы поняли. ;)
    • +3
      документ на интерфейс является документом на любую имплементацию, если в имплеменации нету своей документации. Разве нет?

      Правда в том, что во всех упомянутых коллекциях спека действительно переопределена :)
      • +4
        Правильный ответ: Так как Map это интерфейс — и спека у Map явно отдает принятие/запрет null'а в реализацию — то зависит от реализации.

        Ну не должен же я все подряд писать. Некоторые очевидные вещи можно опускать. ;)
        • 0
          Заодно и будет повод для следующих вопросов про конкретные реализации.
  • +3
    Если бы меня на собеседовании спросили, можно ли класть null в Map, я бы честно ответил, что не знаю. А если они продолжили допытываться, послал бы их куда подальше. Не об этом надо говорить на собеседованиях.
    • +1
      Одно время я поражался тому, что на собеседованиях спрашивают такую фигню, которая потом не пригождается. Потом понял, что компетенция нужна с запасом: учиться потом на ходу фундаментальным вещам — некогда.
    • 0
      Вы считаете, что такие знания не нужны? Ну допустим взяли Вас на работу, Вы сами никогда класть null в map не стали бы, но есть такая вещь как code review… и Вам попадается на рвью код, где кто-то воспользовался такой фитчей. Что Вы будете делать? Правильно — тратить полчаса оплачиваемого времени на изучение этого вопроса.
      • 0
        Да не нужно мне тратить полчаса. В ходе code review я прежде всего смотрю, покрыт ли этот код тестами. Если чувак воспользовался этой фичей, и у него есть тесты, доказывающие, что код в результате работает как надо — зачем мне тратить полчаса?
        • 0
          А «чувак» то ещё поспорит — стоит ли такие фундаментальные вещи, которые описаны в javadocs стандартной библиотеки (причём в самых первых строчках) проверять в unit test-ах?
          • 0
            Нет, я имел в виду, что юнит-тесты должны проверять не функциональность HashMap, описанную в javadoc, а функциональность моей программы, которая этот HashMap использует. Если моя программа делает то, что от не требуется, и это доказано тестами, то абсолютно неважно, использует ли она Map и что там она в Map складывает.
            • 0
              Дык unit test-ы не могут охватить весь диапазон ключей, которые складываются в hash map… Т.о. тесты не могут служить абсолютным доказательством правильной работы. Потому в code review следует смотреть не только на тесты.
              • 0
                Точно так же и code review не может служить абсолютным доказательством правильной работы.

                Я и не говорю, что надо смотреть только тесты. Я говорю, что не нужно знать, как реагирует Map на null — всего не запомнишь, всего не заметишь, всю документацию не прочитаешь. Если хочешь быть достаточно уверенным, что твоё приложние правильно работает, то зубрить javadoc'и всех стандартных Java классов — это неправильный путь.
                • 0
                  Большинство работодателей (в т.ч. Google, Oracle, Facebook) думает иначе — если человек не знает как работают даже базовые классы стандартной библиотеки и не читал даже первых строчек их javadocs… то в общем такой человек в пролёте. И может быть в этом даже есть рациональное зерно — это косвенно говорит о недостаточности опыта.

                  В данном случае я говорил об уверенности, что чужое приложение работает правильно — без понимания того, как работают базовые классы стандартной библиотеки (включая тонкости), невозможно сделать быстро и качественно code review. И даже знания одних javadocs обычно мало (т.к. там часто вода и общие слова) — чтоб хорошо понимать как работает тот или иной класс лучше изучать исходники.
  • 0
    Map map = new TreeMap();
    map.put(null,  "null"); // ошибки нет! 
    

    Только что проверил, у меня бросает NullPointer (Java 1.7 и 1.8)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.