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

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

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

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

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

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

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

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

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

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

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

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.

Иногда может случиться так, что хеш-коды для двух разных объектов совпадают. В этом случае два объекта будут сохранены в одной корзине и будут представлены в виде связанного списка. Точка входа - это недавно добавленный объект. Этот объект ссылается на другой объект с полем 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

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

Обобщить:

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

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

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

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

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

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

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

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

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

  Он может представлять:

  • A hash bucket.
    Because it has a hash property.
  • Узел в односвязном списке, (также глава связанного списка).
• HashMap.TreeNode
  Древовидная версия узла.

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

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

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

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

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

О емкости

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

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

Операции

• Поиск объекта по ключу.
  Сначала найдите сегмент по значению хеш-функции, затем зациклите связанный список или выполните поиск по отсортированному дереву.
• Add entity with key.
  First find the bucket according to hash value of key.
  Then try find the value:
  • If found, replace the value.
  • В противном случае добавьте новый узел в начало связанного списка или вставьте в отсортированное дерево.
• Изменить размер
  При достижении threshold будет удваиваться емкость хеш-таблицы (table.length), а затем выполнить повторное хеширование для всех элементов, чтобы перестроить таблицу.
  Это может быть дорогостоящей операцией.

Представление

• get & put
  Time complexity is O(1), because:
  • Bucket is accessed via array index, thus O(1).
  • Связанный список в каждом сегменте имеет небольшую длину, поэтому может отображаться как O(1).
  • Размер дерева также ограничен, так как при увеличении количества элементов будет увеличиваться емкость и повторное хеширование, поэтому его можно рассматривать как O(1), а не O(log N).

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

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

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

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

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

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. Потому что другой хэш-код ГАРАНТИРУЕТ РАЗНОЕ содержимое в объекте.

    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. 

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

2 одинаковых объекта ------ ›у них одинаковый хэш-код

2 объекта имеют одинаковый хэш-код ---- xxxxx - ›они НЕ равны

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

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

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

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

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

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

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

hash XOR hash >>> 16

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

FYI- Entry - это класс в интерфейсе Map - Map.Entry с этой подписью / определением

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

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

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

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

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

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

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

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

(Источник)

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

Метод HashMap get (Key k) вызывает метод hashCode для ключевого объекта и применяет возвращенный hashValue к своей собственной статической хеш-функции, чтобы найти местоположение сегмента (резервный массив), где ключи и значения хранятся в форме вложенного класса Entry (Map. Вход) . Итак, вы пришли к выводу, что из предыдущей строки ключ и значение хранятся в корзине как форма объекта Entry. Поэтому думать, что в корзине хранится только значение, неверно и не произведет хорошего впечатления на интервьюера.

• Всякий раз, когда мы вызываем метод get (Key k) для объекта HashMap. Сначала он проверяет, является ли ключ нулевым или нет. Обратите внимание, что в HashMap может быть только один нулевой ключ.

Если ключ равен нулю, то нулевые ключи всегда сопоставляются с хешем 0, таким образом, индекс 0.

Если ключ не равен нулю, тогда он вызовет хеш-функцию для ключевого объекта, см. Строку 4 в методе выше, то есть key.hashCode (), поэтому после того, как key.hashCode () вернет hashValue, строка 4 будет выглядеть как

            int hash = hash(hashValue)

и теперь он применяет возвращенное значение hashValue к своей собственной функции хеширования.

Мы могли бы задаться вопросом, почему мы снова вычисляем хэш-значение, используя hash (hashValue). Ответ: он защищает от некачественных хэш-функций.

Теперь окончательное хеш-значение используется для поиска места в корзине, в которой хранится объект Entry. Объект ввода хранится в такой корзине (хэш, ключ, значение, bucketindex)

Я не буду вдаваться в подробности того, как работает HashMap, но приведу пример, чтобы мы могли вспомнить, как работает HashMap, соотнося его с реальностью.

У нас есть Key, Value, HashCode и bucket.

На какое-то время мы будем связывать каждый из них со следующим:

• Ведро -> Общество
• HashCode -> Адрес общества (всегда уникальный)
• Ценность -> Дом в обществе
• Ключ -> Адрес дома.

Использование Map.get (ключ):

Стиви хочет попасть в дом своего друга (Хосе), который живет на вилле в VIP-сообществе, пусть это будет JavaLovers Society. Адрес Хосе - его SSN (который у всех разный). Существует индекс, в котором мы узнаем название Общества на основе SSN. Этот индекс можно рассматривать как алгоритм определения HashCode.

• Название общества SSN
• 92313 (Хосе) - JavaLovers
• 13214 - AngularJSLovers
• 98080 - JavaLovers
• 53808 - Любители биологии

1. Этот SSN (ключ) сначала дает нам HashCode (из индексной таблицы), который является не чем иным, как именем Общества.
2. Теперь несколько домов могут находиться в одном обществе, поэтому HashCode может быть общим.
3. Предположим, что Общество является общим для двух домов, как мы собираемся определить, в какой дом мы собираемся, да, используя ключ (SSN), который является не чем иным, как адресом дома.

Использование Map.put (ключ, значение)

Это находит подходящее общество для этого значения путем нахождения HashCode, а затем значение сохраняется.

Я надеюсь, что это поможет, и это открыто для модификаций.

Это будет длинный ответ, выпейте и читайте дальше ...

Хеширование - это все о хранении пары ключ-значение в памяти, которая может быть прочитана и записана быстрее. Он хранит ключи в массиве, а значения - в LinkedList.

Допустим, я хочу сохранить 4 пары значений ключа -

{
“girl” => “ahhan” , 
“misused” => “Manmohan Singh” , 
“horsemints” => “guess what”, 
“no” => “way”
}

Итак, для хранения ключей нам понадобится массив из 4 элементов. Как теперь сопоставить один из этих 4 ключей с 4 индексами массива (0,1,2,3)?

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

1) reverse the string.

2) keep on multiplying ascii of each character with increasing power of 31 . then add the components .

3) So hashCode() of girl would be –(ascii values of  l,r,i,g are 108, 114, 105 and 103) . 

e.g. girl =  108 * 31^0  + 114 * 31^1  + 105 * 31^2 + 103 * 31^3  = 3173020

Хэш и девочка !! Я знаю, что вы думаете. Ваше увлечение этим диким дуэтом могло заставить вас упустить важную вещь.

Почему Java умножает это на 31?

Это потому, что 31 - нечетное простое число в форме 2 ^ 5 - 1. А нечетное простое число снижает вероятность коллизии хэша.

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

ответ: Hash Code % (Array length -1). Итак, в нашем случае “girl” отображается на (3173020 % 3) = 1. который является вторым элементом массива.

а значение «ахан» сохраняется в LinkedList, связанном с индексом массива 1.

HashCollision. Если вы попытаетесь найти hasHCode ключей “misused” и “horsemints”, используя формулы, описанные выше, вы увидите, что оба дают нам одинаковые 1069518484. Ого !! урок выучен -

2 одинаковых объекта должны иметь одинаковый хэш-код, но нет гарантии, что если хэш-код совпадает, то объекты равны. Таким образом, в ведре 1 должны быть сохранены оба значения, соответствующие «неправильному использованию» и «конским монетам» (1069518484% 3).

Теперь хеш-карта выглядит так -

Array Index 0 –
Array Index 1 - LinkedIst (“ahhan” , “Manmohan Singh” , “guess what”)
Array Index 2 – LinkedList (“way”)
Array Index 3 – 

Теперь, если какое-то тело пытается найти значение для ключа “horsemints”, java быстро найдет его хэш-код, модулирует его и начнет поиск его значения в LinkedList, соответствующем index 1. Таким образом, нам не нужно искать по всем 4 индексам массива, что ускоряет доступ к данным.

Но подождите, одну секунду. в этом связанном списке есть 3 значения, соответствующие индексу массива 1, как определить, какое из них было значением для ключа «horsemints»?

На самом деле я соврал, когда сказал, что HashMap просто хранит значения в LinkedList.

Он хранит обе пары ключ-значение как запись карты. Итак, на самом деле карта выглядит так.

Array Index 0 –
Array Index 1 - LinkedIst (<”girl” => “ahhan”> , <” misused” => “Manmohan Singh”> , <”horsemints” => “guess what”>)
Array Index 2 – LinkedList (<”no” => “way”>)
Array Index 3 – 

Теперь вы можете видеть, что при просмотре связанного списка, соответствующего ArrayIndex1, он фактически сравнивает ключ каждой записи в этом LinkedList с «конскими мельницами», и когда он находит его, он просто возвращает его значение.

Надеюсь, вам понравилось читать это :)

Как говорится, картинка стоит 1000 слов. Я говорю: какой-то код лучше 1000 слов. Вот исходный код HashMap. Получить метод:

/**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

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

Посмотрим на метод put():

  /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

Это немного сложнее, но становится ясно, что новый элемент помещается во вкладку в позиции, рассчитанной на основе хэша:

i = (n - 1) & hash здесь i - это индекс, куда будет помещен новый элемент (или это «ведро»). n - это размер массива tab (массив «корзин»).

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