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

Question

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

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

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

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

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

Answer 1

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

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

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

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

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

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

• Имя общества SSN
• 92313 (Josse's) - JavaLovers
• 13214 - AngularJSLovers
• 98080 - JavaLovers
• 53808 - BiologyLovers

---

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

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

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

Надеюсь, это поможет, и это открыто для изменений.

Answer 2

Хеш-карта работает по принципу хеширования

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

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

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

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

            int hash = hash(hashValue)

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

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

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

Answer 3

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

/**
     * 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 (массива "сегментов").

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

Answer 4

Ответ будет длинным, выпей и читай ...

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

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

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

2 одинаковых объекта должны иметь одинаковый hashCode, но нет гарантии, что hashCode соответствует, тогда объекты равны. Так должно храниться оба значения соответствуют «неправильно использованным» и «мятам» в ведро 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 значения в этом LinkList, соответствующем индексу массива 1, как он узнает, какое из них было значением для ключевых «скачек»?

На самом деле я солгал, когда сказал, что 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 с «horsemints» и, когда находит его, просто возвращает его значение.

Надеюсь, вам было весело читать это:)