Блог

Я всегда был уверен, что «корзина» в Java hash map содержит либо связанный список, либо какое-то дерево, действительно, вы можете прочитать во многих местах в Интернете, как корзина содержит этот список, а затем перебирает записи, используя функцию equals, чтобы найти записи, которые хранятся в том же списке.корзина (т.Е. Имеет тот же ключ), имея это в виду, может ли кто-нибудь объяснить, почему следующий тривиальный код работает не так, как ожидалось :-

 private class MyString {
    String internalString;
        MyString(String string) {
            internalString = string;
        }
        @Override
        public int hashCode() {
            return internalString.length();  // rubbish hashcode but perfectly legal
        }
    }
...
Map<MyString, String> map = new HashMap<>();
        map.put(new MyString("key1"), "val1");
        map.put(new MyString("key2"), "val2"); 

        String retVal = map.get(new MyString("key1"));

        System.out.println("Val returned = " retVal);
 

В этом примере я ожидал, что две записи карты будут в списке в (том же) корзине, а для retVal будет равно «val1», однако оно равно нулю?
Быстрая отладка показывает, почему, корзина вообще не содержит списка, а только одну запись…..

Я думал, что схожу с ума, пока не прочитал это на веб-сайте baeldung (https://www.baeldung.com/java-map-duplicate-keys ) …Однако ни одна из существующих реализаций Java core Map не позволяет Map обрабатывать несколько значений для одного ключа.

Что происходит, содержит ли корзина в хэш-карте список или нет?

Действительно ли корзина java hashmap содержит список?

Это зависит.

Для более старых реализаций (Java 7 и более ранних версий), да, он действительно содержит список. (Это односвязный список внутреннего Node типа.)

Для более новых реализаций (Java 8 и более поздних версий) она может содержать либо список, либо двоичное дерево, в зависимости от того, сколько записей хэшируется в конкретной корзине. Если число мало, используется односвязный список. Если число больше жестко заданного порога (8 в Java 8), то список HashMap преобразуется в сбалансированное двоичное дерево… так что поиск в корзине выполняется O(logN) вместо O(N) . Это смягчает воздействие функции хэш-кода, которая генерирует много коллизий (или той, в которой это может произойти путем выбора ключей определенным образом).

Если вы хотите узнать больше о том, как HashMap это работает, ознакомьтесь с исходным кодом. (Это хорошо прокомментировано, и в комментариях объясняется обоснование, а также подробное описание того, как это работает. Это хуже времени… если вы заинтересованы в такого рода вещах.)

Однако ни одна из существующих реализаций Java core Map не позволяет Map обрабатывать несколько значений для одного ключа.

Это что-то совсем другое. Речь идет о нескольких значениях для ключа, а не о нескольких ключах в корзине.

Статья написана правильно. И это не противоречит моему заявлению «корзина содержит список или дерево».

Проще говоря, HashMap корзина может содержать несколько пар ключ / значение, где все ключи разные.

Единственный момент, по которому я бы придрался к цитируемому тексту, заключается в том, что он, по-видимому, подразумевает, что это реализации Map , которые имеют ограничение на одно значение для каждого ключа. На самом деле это сам Map API накладывает это ограничение … если только вы не используете (скажем) a List в качестве типа значения карты.