Как Java HashMap обрабатывает различные объекты с одним и тем же хеш-кодом?

Question

Насколько я понимаю, я думаю:

1. Совершенно законно, что два объекта имеют одинаковый хэш-код.
2. Если два объекта равны (используя метод equals ()) тогда они имеют одинаковый хэш-код.
3. Если два объекта не равны, они не могут иметь одинаковый хеш-код

Правильно ли я?

Теперь, если я правУ меня есть следующий вопрос: HashMap внутренне использует хеш-код объекта.Итак, если два объекта могут иметь одинаковый хеш-код, то как HashMap может отслеживать, какой ключ он использует?

Может кто-нибудь объяснить, как HashMap внутренне использует хеш-код объекта?

Answer 1

Хэш-карта работает следующим образом (это немного упрощено, но иллюстрирует основной механизм):

У него есть несколько «сегментов», которые он использует для хранения пар ключ-значение. Каждый блок имеет уникальный номер - это то, что идентифицирует блок. Когда вы помещаете пару ключ-значение в карту, хеш-карта будет смотреть на хеш-код ключа и сохранять пару в том блоке, идентификатором которого является хеш-код ключа. Например: хэш-код ключа - 235 -> пара хранится в номере корзины 235. (Обратите внимание, что в одной корзине может храниться более одной пары ключ-значение).

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

.

Теперь вы можете видеть, как это очень эффективно для поиска пар ключ-значение на карте: по хеш-коду ключа хэш-карта сразу же знает, в каком сегменте искать, так что ему нужно только проверить, что находится в это ведро.

Рассматривая вышеописанный механизм, вы также можете увидеть, какие требования необходимы для методов ключей hashCode() и equals():

• Если два ключа одинаковы (equals() возвращает true при сравнении), их метод hashCode() должен возвращать одно и то же число. Если ключи нарушают это, то равные ключи могут храниться в разных сегментах, и хэш-карта не сможет найти пары ключ-значение (потому что она будет выглядеть в одном и том же сегменте).

• Если два ключа различны, то не имеет значения, одинаковы ли их хэш-коды или нет. Они будут храниться в одном и том же сегменте, если их хэш-коды одинаковы, и в этом случае хеш-карта будет использовать equals(), чтобы отличать их друг от друга.

Answer 2

Ваше третье утверждение неверно.

Совершенно законно, если два неравных объекта имеют одинаковый хэш-код. Он используется HashMap в качестве «фильтра первого прохода», так что карта может быстро найти возможных записей с указанным ключом. Затем ключи с одинаковым хеш-кодом проверяются на равенство с указанным ключом.

Вы не хотели бы требовать, чтобы два неравных объекта не могли иметь один и тот же хеш-код, в противном случае это ограничило бы вас 2 ³² возможных объектов. (Это также означало бы, что разные типы не могут даже использовать поля объекта для генерации хеш-кодов, так как другие классы могут генерировать тот же хеш.)

Answer 3

HashMap - это массив Entry объектов.

Рассматривайте HashMap как просто массив объектов.

Посмотритечто такое Object:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
… 
}

Каждый объект Entry представляет пару ключ-значение.Поле next относится к другому Entry объекту, если в корзине более одного Entry.

Иногда может случиться, что хеш-коды для 2 разных объектов совпадают.В этом случае два объекта будут сохранены в одном сегменте и будут представлены в виде связанного списка.Точка входа - это недавно добавленный объект.Этот объект ссылается на другой объект с полем next и так далее.Последняя запись относится к null.

При создании HashMap с конструктором по умолчанию

HashMap hashMap = new HashMap();

Массив создается с размером 16 и балансировкой нагрузки по умолчанию 0,75.

Добавление новой пары ключ-значение

1. Вычисление хеш-кода для ключа
2. Вычисление позиции hash % (arrayLength-1), где должен быть размещен элемент (номер корзины)
3. Если вы попытаетесь добавить значение с ключом, который уже был сохранен в HashMap, то значение будет перезаписано.
4. В противном случае элемент будет добавлен в корзину.

Еслив корзине уже есть хотя бы один элемент, новый добавляется и помещается в первую позицию корзины.Его поле next относится к старому элементу.

Удаление

1. Вычисление хеш-кода для данного ключа
2. Вычисление номера корзины hash % (arrayLength-1)
3. Получить ссылку на первый объект Entry в сегменте и с помощью метода equals выполнить итерацию по всем элементам в данном сегменте.В конце концов мы найдем правильный Entry.Если нужный элемент не найден, вернуть null

Answer 4

Вы можете найти отличную информацию на http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html

Подводя итог:

HashMap работает по принципу хеширования

put (ключ, значение): HashMap сохраняет объект ключа и значения как Map.Entry. Hashmap применяет хеш-код (ключ) для получения корзины. если есть столкновение, HashMap использует LinkedList для хранения объекта.

get (key): HashMap использует хеш-код Key Object для определения местоположения корзины, а затем вызывает метод keys.equals (), чтобы определить правильный узел в LinkedList и вернуть объект связанного значения для этого ключа в Java HashMap .

Answer 5

Вот примерное описание механизма HashMap, для Java 8 версии, (может немного отличаться от Java 6) .

---

Структуры данных

• Хеш-таблица
  Значение хеша вычисляется с помощью ключа hash() и определяет, какой сегмент хеш-таблицы использовать для данного ключа.
• Связанный список (по одному)
  Когда количество элементов в корзине мало, используется односвязный список.
• Красно-Черное дерево
  Когда количество элементов в корзине велико, используется красно-черное дерево.

---

Классы (внутренние)

• Map.Entry
  Представляет одну сущность на карте, сущность ключ / значение.

• HashMap.Node
  Версия связанного списка узла.

  Может представлять:

  • Ведро с хешем.
    Потому что у него есть свойство хеша.
  • Узел в односвязном списке, (таким образом, также глава связного списка) .
• HashMap.TreeNode
  Древовидная версия узла.

---

Поля (внутренние)

• Node[] table
  Таблица ведра (заголовок связанных списков).
  Если корзина не содержит элементов, она пуста, поэтому занимает только место для ссылки.
• Set<Map.Entry> entrySet Набор сущностей.
• int size
  Количество объектов.
• float loadFactor
  Укажите, насколько разрешена полная хеш-таблица перед изменением размера.
• int threshold
  Следующий размер для изменения размера.
  Формула: threshold = capacity * loadFactor

---

Методы (внутренний)

• int hash(key)
  Рассчитать хеш по ключу.

• Как отобразить хэш в корзину?
  Используйте следующую логику:

  static int hashToBucket(int tableSize, int hash) {
      return (tableSize - 1) & hash;
  }
  

---

О вместимости

В хеш-таблице под емкостью понимается количество сегментов, которое можно получить из table.length.
Также может быть вычислено с помощью threshold и loadFactor, поэтому нет необходимости определять его как поле класса.

Может получить эффективную мощность через: capacity()

---

Операция

• Найти сущность по ключу.
  Сначала найдите блок по значению хеша, затем зацикливайте связанный список или ищите отсортированное дерево.
• Добавить объект с ключом.
  Сначала найдите контейнер в соответствии с хеш-значением ключа.
  Затем попробуйте найти значение:
  • Если найдено, заменить значение.
  • В противном случае добавить новый узел в начале связанного списка или вставить в отсортированное дерево.
• Изменение размера
  При достижении threshold емкость хэш-таблицы удваивается (table.length), а затем выполняется повторное хеширование всех элементов для восстановления таблицы.
  Это может быть дорогой операцией.

---

Performance

• получить и положить
  Временная сложность составляет O(1), потому что:
  • Доступ к Bucket осуществляется через индекс массива, таким образом, O(1).
  • Связанный список в каждом сегменте имеет небольшую длину, поэтому может рассматриваться как O(1).
  • Размер дерева также ограничен, поскольку при увеличении количества элементов будет расширяться емкость и повторное хэширование, поэтому его можно рассматривать как O(1), а не O(log N).

Answer 6

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

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

В большинстве случаев хорошо написанный хэш-код не идеален, но достаточно уникален, чтобы предоставить вам более или менее постоянный доступ.

Answer 7

Вы ошибаетесь в третьем пункте. Две записи могут иметь одинаковый хеш-код, но не быть равными. Взгляните на реализацию HashMap.get из OpenJdk . Вы можете видеть, что он проверяет, что хэши равны, а ключи равны. Если бы пункт три был верным, то было бы ненужно проверять, чтобы ключи были равны. Хеш-код сравнивается перед ключом, потому что первый - более эффективное сравнение.

Если вам интересно узнать немного больше об этом, взгляните на статью в Википедии о разрешении конфликтов Open Addressing , которая, как я считаю, является механизмом, который использует реализация OpenJdk. Этот механизм несколько отличается от подхода «корзины», который упоминается в других ответах.

Answer 8

import java.util.HashMap;

public class Students  {
    String name;
    int age;

    Students(String name, int age ){
        this.name = name;
        this.age=age;
    }

    @Override
    public int hashCode() {
        System.out.println("__hash__");
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        System.out.println("__eq__");
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Students other = (Students) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    public static void main(String[] args) {

        Students S1 = new Students("taj",22);
        Students S2 = new Students("taj",21);

        System.out.println(S1.hashCode());
        System.out.println(S2.hashCode());

        HashMap<Students,String > HM = new HashMap<Students,String > (); 
        HM.put(S1, "tajinder");
        HM.put(S2, "tajinder");
        System.out.println(HM.size());
    }
}

Output:

__ hash __

116232

__ hash __

116201

__ hash __

__ hash __

2

Итак, мы видим, что если оба объекта S1 и S2 имеют разное содержимое, то мы почти уверены, что наш переопределенный метод Hashcode будет генерировать разные Hashcode (116232,11601) для обоих объектов.СЕЙЧАС, поскольку существуют разные хеш-коды, поэтому даже не стоит вызывать метод EQUALS.Потому что другой Hashcode ГАРАНТИРУЕТ РАЗНОЕ содержимое в объекте.

    public static void main(String[] args) {

        Students S1 = new Students("taj",21);
        Students S2 = new Students("taj",21);

        System.out.println(S1.hashCode());
        System.out.println(S2.hashCode());

        HashMap<Students,String > HM = new HashMap<Students,String > (); 
        HM.put(S1, "tajinder");
        HM.put(S2, "tajinder");
        System.out.println(HM.size());
    }
}

Now lets change out main method a little bit. Output after this change is 

__ hash __

116201

__ hash __

116201

__ hash __

__ hash __

__ eq __

1
We can clearly see that equal method is called. Here is print statement __eq__, since we have same hashcode, then content of objects MAY or MAY not be similar. So program internally  calls Equal method to verify this. 


Conclusion 
If hashcode is different , equal method will not get called. 
if hashcode is same, equal method will get called.

Thanks , hope it helps. 

Answer 9

Каждый объект Entry представляет пару ключ-значение. Поле next относится к другому объекту Entry, если в ячейке более 1 записи.

Иногда может случиться, что хеш-коды для 2 разных объектов одинаковы. В этом случае 2 объекта будут сохранены в одном сегменте и будут представлены как LinkedList. Точкой входа является недавно добавленный объект. Этот объект ссылается на другой объект со следующим полем и так один. Последняя запись относится к нулю. При создании HashMap с конструктором по умолчанию

Массив создается с размером 16 и балансировкой нагрузки 0,75 по умолчанию.

(Источник)

Answer 10

два объекта равны, это означает, что они имеют одинаковый хэш-код, но не наоборот

Обновление Java 8 в HashMap-

вы делаете эту операцию в своем коде -

myHashmap.put("old","key-value-pair");
myHashMap.put("very-old","old-key-value-pair");

Итак, предположим, что ваш хэш-код, возвращенный для обоих ключей "old" и "very-old", одинаков. Тогда что будет.

myHashMap - это HashMap, и предположим, что изначально вы не указали его емкость. Таким образом, емкость по умолчанию для java равна 16. Итак, теперь, когда вы инициализировали hashmap с помощью нового ключевого слова, он создал 16 блоков. теперь, когда вы выполнили первое заявление-

myHashmap.put("old","key-value-pair");

тогда вычисляется хеш-код для "old", и поскольку хеш-код тоже может быть очень большим целым числом, так, внутренне Java это сделал - (хеш-код здесь - хеш-код, а >>> - сдвиг вправо)

hash XOR hash >>> 16

, поэтому для увеличения изображения он вернет некоторый индекс, который будет находиться в диапазоне от 0 до 15. Теперь ваша пара значений ключа "old" и "key-value-pair" будет преобразована в переменную экземпляра ключа и значения объекта Entry. и тогда этот объект записи будет сохранен в корзине, или вы можете сказать, что при определенном индексе этот объект записи будет сохранен.

FYI- Entry - это класс в интерфейсе Map - Map.Entry, с этими сигнатурами / определениями

class Entry{
          final Key k;
          value v;
          final int hash;
          Entry next;
}

теперь при выполнении следующего оператора -

myHashmap.put("very-old","old-key-value-pair");

и "very-old" дают тот же хеш-код, что и "old", поэтому эта новая пара значений ключа снова отправляется в тот же индекс или в тот же сегмент. Но поскольку этот сегмент не пустой, переменная next объекта Entry используется для хранения этой новой пары ключ-значение.

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