W jaki sposób HashMap Java obsługuje różne obiekty z tym samym kodem haszującym?

Twoje trzecie twierdzenie jest niepoprawne.

Jest całkowicie legalne, aby dwa nierówne obiekty miały ten sam kod skrótu. Jest używany przez HashMap jako "filtr pierwszego przejścia", dzięki czemu mapa może szybko znaleźć możliwe wpisy z podanym kluczem. Klucze z tym samym kodem skrótu są następnie testowane pod kątem równości z podanym kluczem.

Nie chcesz wymogu, że dwa nierówne obiekty nie mogą mieć tego samego kodu hashowego, ponieważ w przeciwnym razie ograniczyłoby cię to do 2³² możliwe Obiekty. (Oznaczałoby to również, że różne typy nie mogłyby nawet używać pól obiektu do generowania kodów skrótu, ponieważ inne klasy mogłyby generować ten sam hash.)

HashMap jest tablicą Entry obiektów.

Rozważ HashMap jako tablicę obiektów.

Zobacz co to jest Object:

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

Każdy obiekt Entry reprezentuje parę klucz-wartość. Pole next odnosi się do innego obiektu Entry, Jeśli kubełek ma więcej niż jeden Entry.

Czasami może się zdarzyć, że kody skrótu dla dwóch różnych obiektów są takie same. W tym przypadku dwa obiekty zostaną zapisane w jednym wiadrze i zostaną przedstawione jako linked list. Punktem wejścia jest Ostatnio dodany obiekt. Ten obiekt odnosi się do innego obiektu z polem next i tak dalej. Ostatni wpis odnosi się do null.

Kiedy tworzysz HashMap z domyślnym konstruktorem

HashMap hashMap = new HashMap();

Tablica jest tworzona z rozmiarem 16 i domyślnym balansem obciążenia 0.75.

Dodawanie nowej pary klucz-wartość

1. Oblicz hashcode dla klucza
2. Oblicz pozycję hash % (arrayLength-1) gdzie należy umieścić element (wiadro liczba)
3. jeśli spróbujesz dodać wartość za pomocą klucza, który został już zapisany w HashMap, wartość zostanie nadpisana.
4. w przeciwnym razie element jest dodawany do wiadra.

Jeśli wiadro ma już co najmniej jeden element, nowy jest dodawany i umieszczany w pierwszej pozycji wiadra. Jego pole next odnosi się do starego elementu.

Usunięcie

1. Oblicz hashcode dla podanego klucza
2. oblicz liczbę wiadra hash % (arrayLength-1)
3. Get a odniesienie do pierwszego obiektu wpisowego w zasobniku i przy pomocy metody equals iteracja wszystkich wpisów w podanym zasobniku. Ostatecznie znajdziemy poprawną Entry. Jeśli żądany element nie zostanie znaleziony, zwróć null

Doskonałe informacje znajdziesz na stronie http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html

Do Podsumowania:

HashMap działa na zasadzie hashowania

Put( key, value): HashMap przechowuje zarówno obiekt key, jak i value jako mapę.Wejście. Hashmap stosuje hashcode (klucz), aby uzyskać wiadro. w przypadku kolizji HashMap używa LinkedList do przechowywania obiektu.

Get (key): HashMap używa hashcode obiektu Key, aby znaleźć out bucket location, a następnie call keys.metoda equals () do identyfikacji poprawnego węzła w LinkedList i zwrócenia powiązanego obiektu wartości dla tego klucza w Java HashMap.

Oto przybliżony opis mechanizmu HashMap dla wersji Java 8, (może nieco różnić się od Java 6) .

Struktury danych

• tabela Hash
  Wartość Hash jest obliczana za pomocą hash() na kluczu i decyduje, które wiadro z hashtable użyć dla danego klucza.
• Linked list (pojedynczo)
  Gdy liczba elementów w zasobniku jest mała, lista pojedynczo połączona jest używany.
• czerwono-czarne drzewo
  Gdy liczba elementów w wiadrze jest duża, używane jest czerwono-czarne drzewo.

Klasy (wewnętrzne)

• Map.Entry
  Reprezentuj pojedynczą jednostkę na mapie, jednostkę klucza/wartości.

• HashMap.Node
  Linked list version of node.

  Może reprezentować:

  • wiadro z Haszem.
    Ponieważ ma właściwość haszującą.
  • węzeł w liście pojedynczo połączonej, (stąd też head of linkedlist) .
• HashMap.TreeNode
  Wersja drzewa węzła.

Pola (wewnętrzne)

• Node[] table
  Tabela kubełkowa, (Głowa połączonych list).
  Jeśli wiadro nie zawiera elementów, to jest null, więc zajmuje tylko spację referencji.
• Set<Map.Entry> entrySet Zestaw Bytów.
• int size
  Liczba podmiotów.
• float loadFactor
  Wskazać, jak pełna jest tabela hash, przed zmiana rozmiaru.
• int threshold
  Następny Rozmiar, przy którym należy zmienić rozmiar.
  Wzór: threshold = capacity * loadFactor

Metody (wewnętrzne)

• int hash(key)
  Oblicz hash według klucza.

• Jak mapować hash do bucket?
  Użyj następującej logiki:

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

O pojemności

W tabeli hash pojemność oznacza liczbę łyżek, można ją uzyskać z table.length.
Można również obliczyć za pomocą threshold i loadFactor, nie ma więc potrzeby definiowania pola klasy.

Może uzyskać efektywną pojemność poprzez: capacity()

Operacje

• Znajdź obiekt według klucza.
  Najpierw znajdź wiadro według wartości skrótu, a następnie zapętl listę połączoną lub posortowane drzewo wyszukiwania.
• Dodaj encję z kluczem.
  Najpierw znajdź wiadro według wartości hash klucza.
  Następnie spróbuj znaleźć wartość:
  • jeśli znaleziono, zastąp wartość.
  • W Przeciwnym Razie Dodaj nowy węzeł na początku listy połączonej, lub wstawić do posortowanego drzewa.
• Resize
  Po osiągnięciu threshold, podwaja pojemność hashtable (table.length), a następnie wykonuje ponowne hash na wszystkich elementach, aby odbudować tabelę.
  To może być kosztowna operacja.

Wydajność

• get & put
  Złożoność czasowa jest O(1), ponieważ:
  • Bucket jest dostępny poprzez indeks tablicy, więc O(1).
  • lista powiązana w każdym wiadrze ma niewielką długość, więc może być wyświetlana jako O(1).
  • rozmiar drzewa jest również ograniczony, ponieważ rozszerzy pojemność i zmieni hash, gdy liczba elementów zwiększy się, więc może wyświetlać go jako O(1), a nie O(log N).

Hashcode określa, które wiadro dla hashmapy ma sprawdzić. Jeśli w zasobniku znajduje się więcej niż jeden obiekt, wykonywane jest wyszukiwanie liniowe, aby znaleźć, który element w zasobniku jest równy żądanemu elementowi (przy użyciu metody equals()).

Innymi słowy, jeśli masz doskonały hashcode, dostęp do hashmap jest stały, nigdy nie będziesz musiał iteracji przez bucket (technicznie rzecz biorąc, musisz mieć również bucket MAX_INT, implementacja Java może współdzielić kilka kodów hash w tym samym bucket aby ograniczyć wymagania przestrzenne). Jeśli masz najgorszy hashcode (zawsze zwraca ten sam numer), dostęp do hashmapy staje się liniowy, ponieważ musisz przeszukać każdy element na mapie (wszystkie są w tym samym koszyku), aby uzyskać to, czego chcesz.

Przez większość czasu dobrze napisany hashcode nie jest doskonały, ale jest wystarczająco unikalny, aby dać ci mniej lub bardziej stały dostęp.

Mylisz się co do punktu trzeciego. Dwa wpisy mogą mieć ten sam kod hashowy, ale nie są sobie równe. Spójrz na implementację HashMap.Pobierz z OpenJDK . Widać, że sprawdza, czy hasze są równe i klucze są równe. Gdyby punkt trzeci był prawdziwy, nie byłoby konieczne sprawdzanie, czy klucze są równe. Kod skrótu jest porównywany przed kluczem, ponieważ pierwszy z nich jest bardziej efektywnym porównaniem.

Jeśli jesteś zainteresowany nauką trochę więcej w związku z tym, proszę spojrzeć na Artykuł Wikipedii na temat Open Addressing collision resolution, który moim zdaniem jest mechanizmem używanym przez implementację OpenJdk. Mechanizm ten jest subtelnie inny niż podejście "wiaderkowe", o którym wspomina jedna z innych odpowiedzi.

To jest najbardziej mylące pytanie dla wielu z nas w wywiadach.Ale to nie takie skomplikowane.

wiemy

• HashMap przechowuje para klucz-wartość W mapie.Entry (we all know)

• HashMap działa na algorytmie haszującym i używa metody hashCode () i equals () w metodach put () I get (). (nawet my to wiemy)

• When we call put method by passing key-value pair, HashMap uses Key **hashCode()** with hashing to **find out the index** to store the key-value pair. (this is important)

• The Entry is **stored in the LinkedList**, so if there are already existing entry, it uses **equals() method to check if the passed key already exists** (even this is important)

• Jeśli tak to nadpisuje wartość tworzy nowy wpis i przechowuje ten wpis klucz-wartość.

• Kiedy wywołujemy metodę get przez przekazanie klucza, ponownie używa ona hashCode () , aby znaleźć indeks w tablicy, a następnie użyć metody equals (), aby znaleźć poprawny wpis i zwrócić jego wartość.

TEN OBRAZEK POMOŻE CI ZROZUMIEĆ:

Edycja Wrzesień 2017: tutaj widzimy jak wartość hash jeśli jest używana wraz z równymi po znalezieniu wiadro.

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

}

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

Widzimy więc, że jeśli oba obiekty S1 i S2 mają inną zawartość, to jesteśmy prawie pewni, że nasza nadpisana metoda Hashcode wygeneruje inny Hashcode(116232,11601) dla obu obiektów. Teraz, ponieważ istnieją różne kody hash, więc nie będzie nawet kłopotać się, aby wywołać metodę EQUALS. Ponieważ inny Hashcode gwarantuje inną zawartość w obiekcie.

    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. 

Mapa Hashowa działa na zasadzie hashowania

Metoda HashMap get (Key k) wywołuje metodę hashCode na obiekcie key i stosuje zwracaną wartość hashValue do własnej statycznej funkcji hash, aby znaleźć lokalizację zasobnika (tablicę pomocniczą), w której klucze i wartości są przechowywane w postaci zagnieżdżonej klasy o nazwie Entry (Map.Miejsce). Tak więc doszedłeś do wniosku, że z poprzedniego wiersza zarówno klucz, jak i wartość są przechowywane w zasobniku jako forma obiektu wejściowego . Więc myśląc, że tylko wartość jest przechowywana w wiadrze nie jest poprawny i nie zrobi dobrego wrażenia na rozmówcy .

• Gdy wywołamy metodę get (Key k) na obiekcie HashMap . Najpierw sprawdza, czy klucz jest null, czy nie . Zauważ, że w Hashmapie może być tylko jeden klucz null .

Jeśli klucz jest null, to klucze Null zawsze odwzorowują hash 0, a więc indeksują 0.

Jeżeli key nie jest null, to wywoła hashfunction na obiekcie key, patrz linia 4 w powyższej metodzie tj. key.hashCode (), czyli po kluczu.hashCode() zwraca hashValue, linia 4 wygląda jak

            int hash = hash(hashValue)

I teraz zastosuje zwróconą wartość hashValue do własnej funkcji hashującej .

Możemy się zastanawiać, dlaczego ponownie obliczamy hashvalue używając hash (hashValue). Odpowiedź jest to chroni przed słabą jakość funkcji hash.

Teraz końcowa wartość hashvalue jest używana do znalezienia miejsca bucket, w którym przechowywany jest obiekt Entry . Obiekt Entry przechowuje w zasobniku w ten sposób (hash, klucz, wartość, bucketindex)

Każdy obiekt wejściowy reprezentuje parę klucz-wartość. Pole następne odnosi się do innego obiektu wpisowego, jeśli wiadro ma więcej niż 1 wpis.

Czasami może się zdarzyć, że hashcody dla 2 różnych obiektów są takie same. W tym przypadku 2 obiekty zostaną zapisane w jednym koszyku i będą prezentowane jako LinkedList. Punkt wejścia jest ostatnio dodanym obiektem. Ten obiekt odnosi się do innego obiektu z następnym polem i tym samym jednym. Ostatni wpis odnosi się do null. Podczas tworzenia HashMap z domyślnym konstruktor

Tablica jest tworzona z rozmiarem 16 i domyślnym balansem obciążenia 0.75.

(źródło)

Nie będę wdawać się w szczegóły, jak działa HashMap, ale podam przykład, abyśmy mogli zapamiętać, jak działa HashMap, odnosząc go do rzeczywistości.

Mamy klucz, wartość, HashCode i bucket.

Przez jakiś czas będziemy odnosić się do każdego z nich następująco:

• Wiadro - > Społeczeństwo
• HashCode - > adres Towarzystwa (unikalny zawsze)
• wartość - > Dom w społeczeństwie
• Klucz - > adres Domu.

Korzystanie Z Mapy.get (klucz):

Stevie chce dostać się do domu swojego przyjaciela (Josse), który mieszka w willi w społeczeństwie VIP, niech to będzie społeczeństwo JavaLovers. Adres Josse ' a to jego SSN(co dla każdego jest inne). Prowadzony jest indeks, w którym poznajemy nazwę towarzystwa na podstawie SSN. Indeks ten można uznać za algorytm do wyszukiwania HashCode.

• nazwa Towarzystwa SSN
• 92313(Josse ' s) -- JavaLovers
• 13214 -- AngularJSLovers
• 98080 -- JavaLovers
• 53808 -- BiologyLovers

1. ten SSN (klucz) najpierw daje nam HashCode (z tabeli indeksów), który jest niczym innym jak nazwą społeczeństwa.
2. teraz wieloosobowe domy mogą być w tym samym społeczeństwie, więc HashCode może być wspólny.
3. przypuśćmy, że społeczeństwo jest wspólne dla dwóch domów, w jaki sposób możemy zidentyfikować dom, tak, używając klucza (SSN), który jest niczym innym jak adresem domu

Za pomocą Mapa.put (klucz,wartość)

To znajduje odpowiednie społeczeństwo dla tej wartości, znajdując HashCode, a następnie wartość jest przechowywana.

Mam nadzieję, że to pomoże i to jest otwarte na modyfikacje.

Jak działa hashMap w Javie?

HashMap działa na zasadzie hashowania, mamy metodę put () I get () do przechowywania i pobierania obiektu z HashMap. Kiedy przekazujemy zarówno klucz, jak i wartość do metody put() do przechowywania na Hashmapie, używa ona metody hashcode() obiektu klucza do obliczania hashcode i poprzez zastosowanie haszowania na tym hashcode identyfikuje lokalizację wiadra do przechowywania obiektu wartości. Podczas pobierania używa metody key object equals, aby dowiedzieć się poprawna para wartości klucza i obiekt return value skojarzony z tym kluczem. HashMap używa linked list w przypadku kolizji i obiekt będzie przechowywany w następnym węźle linked list. Również HashMap przechowuje zarówno krotkę klucza+wartości w każdym węźle połączonej listy.

Dwa obiekty są sobie równe, oznacza to, że mają ten sam hashcode, ale nie odwrotnie

Java 8 update in HashMap-

Wykonujesz tę operację w swoim kodzie-

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

Załóżmy więc, że Twój hashcode zwrócony dla obu kluczy "old" i "very-old" jest taki sam. Więc co się stanie.

myHashMap jest Hashmapą i załóżmy, że początkowo nie podałeś jej pojemności. Domyślna pojemność w Javie to 16. Więc teraz, gdy tylko zainicjowałeś hashmap używając nowego słowa kluczowego, stworzył 16 wiadrów. teraz, kiedy wykonałeś pierwsze oświadczenie -

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

Następnie obliczany jest hashcode dla "old", a ponieważ hashcode może być również bardzo dużą liczbą całkowitą, więc wewnętrznie java zrobiła to - (hash to hashcode tutaj i > > > to right shift)

hash XOR hash >>> 16

Więc dać jako większe zdjęcie zwróci jakiś indeks, który będzie między 0 do 15. Teraz twoja para wartości klucza "old" i "key-value-pair" zostanie przekonwertowana na instancję klucza i wartości obiektu Entry zmienna. i wtedy ten obiekt wpisowy zostanie zapisany w zasobniku, lub można powiedzieć, że w konkretnym indeksie ten obiekt wpisowy zostanie zapisany.

FYI-Entry jest klasą w map interface-Map.Wpis, z tym podpisem / definicją

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

Teraz, gdy wykonasz następne polecenie-

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

I "very-old" dają ten sam hashcode co "old", więc ta nowa para wartości klucza jest ponownie wysyłana do tego samego indeksu lub tego samego zasobnika. Ale ponieważ to wiadro nie jest puste, to next zmienna obiektu Entry służy do przechowywania tej nowej pary wartości klucza.

I będzie to przechowywane jako lista połączona dla każdego obiektu, który ma ten sam hashcode, ale triefy_threshold jest określony wartością 6. tak więc po tym osiągnięciu, linked list jest konwertowany na zrównoważone drzewo (czerwono-czarne drzewo) z pierwszym elementem jako korzeniem.

Jak się mówi, obraz jest wart 1000 słów. Mówię: jakiś kod jest lepszy niż 1000 słów. Oto kod źródłowy HashMap. Metoda 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;
    }

Więc staje się jasne, że hash jest używany do znalezienia "bucket" i pierwszy element jest zawsze sprawdzany w tym bucket. Jeśli nie, to equals klucza jest używany do znalezienia rzeczywistego elementu na liście połączonej.

Zobaczmy metodę 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;
    }

Jest nieco bardziej skomplikowane, ale staje się jasne, że nowy element jest umieścić w zakładce w pozycji obliczonej na podstawie hasha:

i = (n - 1) & hash tutaj {[5] } jest indeksem, w którym zostanie umieszczony nowy element (lub jest to "wiadro"). n jest wielkością tablicy tab (array of "buckets").

Po pierwsze, próbuje się umieścić go jako pierwszy element w tym "wiadrze". Jeśli istnieje już element, Dodaj nowy węzeł do listy.

To będzie długa odpowiedź, napij się i czytaj dalej ...

Hashowanie polega na przechowywaniu pary klucz-wartość w pamięci, która może być szybciej odczytywana i zapisywana. przechowuje klucze w tablicy i wartości w LinkedList .

Powiedzmy, że chcę zapisać 4 pary wartości klucza-

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

Więc do przechowywania kluczy potrzebujemy tablicy 4 elementów . Teraz jak mapować jeden z tych 4 kluczy do 4 indeksów tablicy (0,1,2,3)?

Więc java znajduje hashCode poszczególnych kluczy i mapować je do określonego indeksu tablicy. Hashcode formula is -

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

Hash i dziewczyna !! Wiem, co sobie myślisz. Twoja fascynacja tym dzikim duetem może sprawić, że przegapisz ważną rzecz .

dlaczego java mnoży to przez 31 ?

To dlatego, że 31 jest nieparzystą liczbą pierwszą w postaci 2^5 – 1 . I odd prime zmniejsza szansę na kolizję Hash

teraz jak ten kod hash jest mapowany do tablicy indeks?

Odpowiedź brzmi: Hash Code % (Array length -1) . Więc {[5] } jest odwzorowane na (3173020 % 3) = 1 w naszym przypadku . który jest drugim elementem tablicy .

A wartość "ahhan" jest przechowywana w LinkedList powiązanej z indeksem tablicy 1 .

HashCollision - jeśli spróbujesz znaleźć hasHCode z kluczy “misused” i “horsemints” używając opisanych powyżej wzorów zobaczysz, że obie dają nam to samo 1069518484. Whooaa !! lekcja -

2 równe obiekty muszą mieć ten sam hashCode, ale tam nie ma gwarancji, jeśli hashCode pasuje wtedy obiekty są równe . Więc powinien przechowywać obie wartości odpowiadające "misused" i "horsemints" do bucket 1 (1069518484 % 3) .

Teraz Mapa hash wygląda jak –

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

Teraz , jeśli jakiś body spróbuje znaleźć wartość klucza “horsemints”, java szybko znajdzie jego hashCode, moduł go i zacznie szukać jego wartości na LinkedList odpowiadającej index 1. Tak więc w ten sposób nie musimy przeszukiwać wszystkich 4 indeksów tablicy dzięki temu dostęp do danych jest szybszy.

właściwie skłamałem, kiedy powiedziałem, że HashMap przechowuje wartości w LinkedList .

Przechowuje obie pary wartości klucza jako wpis mapy. Więc właściwie Mapa wygląda tak .

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

Teraz możesz zobaczyć podczas przechodzenia przez linkedList odpowiadające do ArrayIndex1 w rzeczywistości porównuje klucz każdego wpisu do tej LinkedList do "horsemints" i kiedy go znajdzie, po prostu zwraca jego wartość .

Mam nadzieję, że dobrze się bawiłeś podczas czytania:)