Внутренняя реализация java.util. HashMap и HashSet

В чем важность хэш-кода @Override public int () в HashMap / HashSet ?

Это позволяет экземпляру карты создавать полезный хэш-код в зависимости от содержимого карты. Две карты с одинаковым содержимым будут создавать одинаковый хэш-код. Если содержимое отличается, хэш-код будет другим.

Где этот хеш-код используется внутри компании?

Никогда. Этот код существует только для того, чтобы вы могли использовать карту в качестве ключа на другой карте.

Могу ли я сопоставить значения с someObject (вместо String ), например myMap < someObject, Object> ?

Да, но someObject должен быть классом, а не объектом (ваше имя предполагает, что вы хотите передать объект; это должно быть SomeObject чтобы прояснить, что вы имеете в виду тип).

Какие все контракты мне нужно выполнить, чтобы это произошло успешно?

Класс должен реализовать hashCode () и равно () .

Где этот хэш-код используется внутри компании?

Никогда. Этот код существует только для того, чтобы вы могли использовать карту в качестве ключа на другой карте.

Могу ли я сопоставить значения с someObject (вместо String ), например myMap < someObject, Object> ?

Да, но someObject должен быть классом, а не объектом (ваше имя предполагает, что вы хотите передать объект; это должно быть SomeObject чтобы прояснить, что вы имеете в виду тип).

Какие все контракты мне нужно выполнить, чтобы это произошло успешно?

Класс должен реализовать hashCode () и равно () .

Где этот хеш-код используется внутри компании?

Никогда. Этот код существует только для того, чтобы вы могли использовать карту в качестве ключа на другой карте.

Могу ли я сопоставить значения с someObject (вместо String ), например myMap < someObject, Object> ?

Да, но someObject должен быть классом, а не объектом (ваше имя предполагает, что вы хотите передать объект; это должно быть SomeObject чтобы прояснить, что вы имеете в виду тип).

Какие все контракты мне нужно выполнить, чтобы это произошло успешно?

Класс должен реализовать hashCode () и равно () .

[РЕДАКТИРОВАТЬ]

Мы говорим, что хэш-код ключа (проверьте!) - это фактическая вещь, на которую отображается значение в хеш-таблице?

Да.

Контейнеры хеширования, такие как HashMap и HashSet , обеспечивают быстрый доступ к элементам, хранящимся в них, путем разделения их содержимого на «корзины».

Например, список чисел: 1, 2, 3, 4, 5, 6, 7, 8 , хранящийся в List , будет выглядеть (концептуально) в памяти примерно так: [ 1, 2, 3, 4, 5, 6, 7, 8] .

Сохранение того же набора чисел в Set будет выглядеть примерно так: [1, 2] [3, 4] [5, 6] [7, 8] . В этом примере список разделен на 4 сегмента.

Теперь представьте, что вы хотите найти значение 6 из списка и набора . Со списком вам нужно будет начать с начала списка и проверять каждое значение, пока не дойдете до 6, это займет 6 шагов. С помощью набора вы найдете правильную корзину, проверив каждый из элементов в этой корзине (только 2 в нашем примере), что делает этот процесс трехэтапным. Ценность этого подхода резко возрастает, чем больше у вас данных.

Но подождите, как мы узнали, в каком сегменте искать? Именно здесь на помощь приходит метод hashCode . Чтобы определить сегмент, в котором следует искать элемент, контейнеры хеширования Java вызывают hashCode , а затем применяют некоторую функцию к результату. Эта функция пытается сбалансировать количество сегментов и количество элементов для максимально быстрого поиска.

Во время поиска после того, как правильный сегмент был найден, каждый элемент в этом сегменте сравнивается по одному, как в списке. Вот почему, когда вы переопределяете hashCode , вы также должны переопределить равным . Таким образом, если объект любого типа имеет как метод equals , так и метод hashCode , его можно использовать в качестве ключа в Map или записи в ] Установите . Для правильной реализации этих методов необходимо соблюдать договор, канонический текст по этому поводу взят из замечательной книги Джоша Блоха «Эффективная Java»: Правило 8: Всегда переопределяйте hashCode, когда вы переопределяете равное

1. Любой объект в Java должен иметь метод hashCode () ; HashMap и HashSet не являются исключениями. Этот хэш-код используется, если вы вставляете хэш-карту / набор в другую хэш-карту / набор.
2. Любой тип класса может использоваться в качестве ключа в HashMap / HashSet . Для этого требуется, чтобы метод hashCode () возвращал равные значения для одинаковых объектов, а метод equals () реализовывался в соответствии с контрактом (рефлексивным, транзитивным, симметричным). Реализации по умолчанию из Object уже подчиняются этим контрактам, но вы можете переопределить их, если вы хотите равенство значений вместо ссылочного равенства.

Существует сложная взаимосвязь между equals (), hashcode () и хэш-таблицами в целом в Java (и .NET тоже, если на то пошло). Цитата из документации:

public int hashCode ()

Возвращает значение хэш-кода для объекта. Этот метод поддерживается для хэш-таблиц, таких как те, которые предоставляются java.util.Hashtable .

Общий контракт hashCode:

• Каждый раз, когда он вызывается для одного и того же объекта более одного раза во время выполнения приложения Java метод hashCode должен последовательно возвращать одно и то же целое число, при условии, что никакая информация, используемая в равных сравнениях для объекта, не изменяется. Это целое число не обязательно должно оставаться согласованным от одного выполнения приложения к другому выполнению того же самого приложения.
• Если два объекта равны согласно методу equals (Object), то вызов метода hashCode для каждого из двух объектов должен привести к одинаковому целочисленному результату.
• Не требуется, чтобы, если два объекта не равны согласно методу equals ( java.lang.Object ), тогда вызов метода hashCode для каждого из двух объектов должен дают отличные целочисленные результаты. Однако программист должен знать, что получение различных целочисленных результатов для неравных объектов может улучшить производительность хэш-таблиц.

Насколько это разумно практично, метод hashCode определяется классом Object ] действительно возвращает разные целые числа для разных объектов. (Обычно это реализуется путем преобразования внутреннего адреса объекта в целое число, но этот метод реализации не требуется для языка программирования Java ™.)

Строка

@Overrides public int hashCode()

просто сообщает, что метод hashCode () переопределяется. Это ia обычно знак того, что тип безопасно использовать в качестве ключа в HashMap .

И да, вы можете легко использовать любой объект, который подчиняется контракту для equals () и hashCode () в HashMap в качестве ключа.

В ответ на вопрос 2, хотя у вас может быть любой класс, который может использоваться в качестве ключа в Hashmap, лучше всего использовать неизменяемые классы в качестве ключей для HashMap. Или, по крайней мере, если ваши реализации hashCode и equals зависят от некоторых атрибутов вашего класса, вам следует позаботиться о том, чтобы не предоставлять методы для изменения этих атрибутов.

Да. Вы можете использовать любой объект в качестве ключа в HashMap. Для этого вам необходимо выполнить следующие шаги.

1. Переопределение равно.

2. Заменить хэш-код.

Контракты для обоих методов очень четко упомянуты в документации java.lang.Object. http://java.sun.com/javase/6/docs/api/java/lang/Object.html

И да, метод hashCode () используется внутри HashMap и, следовательно, возврат правильного значения важен для спектакль.

Вот метод hashCode () из HashMap

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

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

Контракты для обоих методов очень четко упомянуты в документации java.lang.Object. http://java.sun.com/javase/6/docs/api/java/lang/Object.html

И да, метод hashCode () используется внутри HashMap и, следовательно, возврат правильного значения важен для спектакль.

Вот метод hashCode () из HashMap

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

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

Контракты для обоих методов очень четко упомянуты в документации java.lang.Object. http://java.sun.com/javase/6/docs/api/java/lang/Object.html

И да, метод hashCode () используется внутри HashMap и, следовательно, возврат правильного значения важен для спектакль.

Вот метод hashCode () из HashMap

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

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

Вот метод hashCode () из HashMap

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

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

Вот метод hashCode () из HashMap

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

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

Аарон Дигулла абсолютно прав. Еще одно интересное замечание, которое люди, похоже, не осознают, заключается в том, что метод hashCode () ключевого объекта не используется дословно. Фактически, он повторно хешируется HashMap, то есть вызывает hash (someKey.hashCode)) , где hash () - это внутренний метод хеширования.

Чтобы увидеть это, взгляните на источник: http://kickjava.com/src/java/util/HashMap.java.htm

Причина в том, что некоторые люди плохо реализуют hashCode (), а hash () функция дает лучшее распределение хешей. В основном это сделано из соображений производительности.