W jaki sposób Java HashMap obsługuje różne obiekty z tym samym kodem skrótu?

Zgodnie z moim zrozumieniem myślę:

1. Jest całkowicie legalne, aby dwa obiekty miały ten sam kod skrótu.
2. Jeśli dwa obiekty są równe (przy użyciu metody equals ()), mają ten sam kod skrótu.
3. Jeśli dwa obiekty nie są równe, nie mogą mieć tego samego kodu skrótu

Mam rację?

Teraz, jeśli mam rację, mam następujące pytanie: HashMapWewnętrznie używa kodu skrótu obiektu. Więc jeśli dwa obiekty mogą mieć ten sam kod skrótu, to w jaki sposób można HashMapśledzić, którego klucza używa?

Czy ktoś może wyjaśnić, w jaki sposób HashMapwewnętrznie wykorzystuje kod skrótu obiektu?

Mapa skrótów działa w ten sposób (jest to nieco uproszczone, ale ilustruje podstawowy mechanizm):

Ma wiele „segmentów”, których używa do przechowywania par klucz-wartość. Każdy segment ma unikalny numer - to właśnie identyfikuje segment. Kiedy umieścisz parę klucz-wartość na mapie, mapa hash spojrzy na kod skrótu klucza i zapisze parę w wiadrze, którego identyfikatorem jest kod skrótu klucza. Na przykład: Kod skrótu klucza to 235 -> para jest przechowywana w segmencie numer 235. (Uwaga: w jednym segmencie można zapisać więcej niż jedną parę klucz-wartość).

Kiedy odszukasz wartość w haszapie, podając jej klucz, najpierw sprawdzi kod hashu podanego klucza. Haszapa następnie zajrzy do odpowiedniego segmentu, a następnie porówna klucz, który podałeś, z kluczami wszystkich par w segmencie, porównując je z equals().

Teraz możesz zobaczyć, jak to jest bardzo efektywne w wyszukiwaniu par klucz-wartość na mapie: dzięki kodowi skrótu klucza haszapa natychmiast wie, w którym segmencie ma szukać, więc musi tylko sprawdzić, co jest w tym segmencie.

Patrząc na powyższy mechanizm, możesz również zobaczyć, jakie wymagania są niezbędne w odniesieniu do hashCode()i equals()metod kluczy:

• Jeśli dwa klucze są takie same ( equals()zwraca trueprzy porównywaniu), ich hashCode()metoda musi zwracać ten sam numer. Jeśli klucze naruszą ten warunek, wówczas klucze, które są równe, mogą być przechowywane w różnych segmentach, a mapa hash nie będzie w stanie znaleźć par klucz-wartość (ponieważ będzie wyglądać w tym samym segmencie).

• Jeśli dwa klucze są różne, nie ma znaczenia, czy ich kody skrótu są takie same, czy nie. Będą one przechowywane w tym samym segmencie, jeśli ich kody skrótu są takie same, aw tym przypadku mapa będzie equals()ich rozróżniać.

Twoje trzecie twierdzenie jest nieprawidłowe.

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

Nie chciałbyś wymagania, aby dwa nierówne obiekty nie miały tego samego kodu skrótu, ponieważ w przeciwnym razie ograniczałoby cię to do 2 ³² możliwych obiektów. (Oznaczałoby to również, że różne typy nie mogłyby nawet użyć pól obiektu do wygenerowania kodów skrótu, ponieważ inne klasy mogłyby wygenerować ten sam skrót).

HashMapto tablica Entryobiektów.

Traktuj HashMapjako tablicę obiektów.

Zobacz, co to Objectjest:

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

Każdy Entryobiekt reprezentuje parę klucz-wartość. Pole nextodnosi się do innego Entryobiektu, jeśli wiadro ma więcej niż jeden Entry.

Czasami może się zdarzyć, że kody skrótu dla 2 różnych obiektów są takie same. W takim przypadku dwa obiekty zostaną zapisane w jednym segmencie i zostaną przedstawione jako lista połączona. Punktem wejścia jest ostatnio dodany obiekt. Ten obiekt odnosi się do innego obiektu z nextpolem i tak dalej. Ostatni wpis odnosi się do null.

Podczas tworzenia HashMapz domyślnym konstruktorem

HashMap hashMap = new HashMap();

Tablica jest tworzona z rozmiarem 16 i domyślnym równoważeniem obciążenia 0,75.

Dodanie nowej pary klucz-wartość

1. Oblicz kod skrótu dla klucza
2. Oblicz pozycję, w hash % (arrayLength-1)której element powinien zostać umieszczony (numer łyżki)
3. Jeśli spróbujesz dodać wartość za pomocą klucza, który został już zapisany HashMap, wartość zostanie zastąpiona.
4. W przeciwnym razie element zostanie dodany do wiadra.

Jeśli wiadro ma już co najmniej jeden element, nowy zostaje dodany i umieszczony w pierwszej pozycji wiadra. Jego nextpole odnosi się do starego elementu.

Usunięcie

1. Oblicz hashcode dla danego klucza
2. Oblicz numer wiadra hash % (arrayLength-1)
3. Uzyskaj odniesienie do pierwszego obiektu Entry w segmencie i za pomocą metody equals iteruj wszystkie wpisy w danym segmencie. W końcu znajdziemy właściwy Entry. Jeśli żądany element nie zostanie znaleziony, zwróćnull

Doskonałe informacje można znaleźć na stronie http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html

Podsumowując:

HashMap działa na zasadzie mieszania

put (klucz, wartość): HashMap przechowuje zarówno klucz, jak i wartość obiektu jako Map.Entry. Hashmap stosuje hashcode (klucz), aby uzyskać wiadro. w przypadku kolizji HashMap używa LinkedList do przechowywania obiektu.

get (key): HashMap używa kodu skrótu Key Object, aby znaleźć lokalizację segmentu, a następnie wywołać metodę keys.equals () w celu zidentyfikowania poprawnego węzła na LinkedList i zwrócenia obiektu wartości powiązanej dla tego klucza w Java HashMap.

Oto ogólny opis HashMapmechanizmu dla Java 8wersji (może się nieco różnić od Java 6) .

Struktury danych

• Tabela
  skrótu Wartość skrótu jest obliczana za hash()pomocą klawisza i decyduje, którego segmentu tabeli mieszającej użyć dla danego klucza.
• Lista połączona (pojedynczo)
  Gdy liczba elementów w wiadrze jest niewielka, używana jest lista połączona pojedynczo.
• Czerwono-czarne drzewo
  Gdy liczba elementów w wiadrze jest duża, stosuje się czerwono-czarne drzewo.

Klasy (wewnętrzne)

• Map.Entry
  Reprezentuje pojedynczy byt na mapie, klucz / wartość.

• HashMap.Node
  Wersja połączonej listy węzła.

  Może reprezentować:

  • Wiadro mieszania.
    Ponieważ ma właściwość skrótu.
  • Węzeł na pojedynczo połączonej liście (a więc także szef połączonej listy ) .
• HashMap.TreeNode
  Wersja drzewa węzła.

Pola (wewnętrzne)

• Node[] table
  Tabela kubełkowa (nagłówek połączonych list).
  Jeśli segment nie zawiera elementów, ma wartość null, dlatego zajmuje tylko miejsce odniesienia.
• Set<Map.Entry> entrySet Zestaw bytów.
• int size
  Liczba podmiotów.
• float loadFactor
  Wskaż, jak pełna jest tabela skrótów, przed zmianą rozmiaru.
• int threshold
  Następny rozmiar do zmiany rozmiaru.
  Formuła:threshold = capacity * loadFactor

Metody (wewnętrzne)

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

• Jak mapować skrót do wiadra?
  Użyj następującej logiki:

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

O pojemności

W tabeli skrótów pojemność oznacza liczbę łyżek, z której można ją uzyskać table.length.
Można go również obliczyć za pomocą, thresholda loadFactorzatem nie trzeba definiować go jako pola klasy.

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

Operacje

• Znajdź jednostkę według klucza.
  Najpierw znajdź segment według wartości skrótu, a następnie zapętloną listę lub wyszukaj posortowane drzewo.
• Dodaj encję za pomocą klucza.
  Najpierw znajdź segment zgodnie z wartością skrótu klucza.
  Następnie spróbuj znaleźć wartość:
  • Jeśli znaleziono, zastąp wartość.
  • W przeciwnym razie dodaj nowy węzeł na początku połączonej listy lub wstaw do posortowanego drzewa.
• Zmień rozmiar
  Po thresholdosiągnięciu podwoi pojemność hashtable ( table.length), a następnie przeprowadzi ponowne mieszanie wszystkich elementów w celu przebudowania tabeli.
  To może być kosztowna operacja.

Występ

• get & put
  Złożoność czasu jest O(1), ponieważ:
  • Dostęp do segmentu można uzyskać za pomocą indeksu tablicy O(1).
  • Połączona lista w każdym wiadrze ma małą długość, dlatego może wyglądać jak O(1).
  • Rozmiar drzewa jest również ograniczony, ponieważ zwiększy pojemność i ponownie haszuje, gdy liczba elementów wzrośnie, więc można go postrzegać jako O(1)nie O(log N).

Kod skrótu określa, które wiadro ma sprawdzić skrót. Jeśli w wiadrze znajduje się więcej niż jeden obiekt, przeprowadzane jest wyszukiwanie liniowe w celu znalezienia, który element w wiadrze jest równy pożądanemu przedmiotowi (przy użyciu equals()).

Innymi słowy, jeśli masz doskonały kod skrótu, to dostęp do planu skrótu jest stały, nigdy nie będziesz musiał iterować przez segment (technicznie musiałbyś również mieć segmenty MAX_INT, implementacja Java może współdzielić kilka kodów skrótu w tym samym segmencie, aby zmniejszone wymagania dotyczące miejsca). Jeśli masz najgorszy kod skrótu (zawsze zwraca ten sam numer), dostęp do mapy skrótów staje się liniowy, ponieważ musisz przeszukać każdy element na mapie (wszystkie są w tym samym segmencie), aby uzyskać to, czego chcesz.

Przez większość czasu dobrze napisany hashcode nie jest idealny, ale jest wystarczająco wyjątkowy, aby dać ci mniej więcej stały dostęp.

Mylisz się w punkcie trzecim. Dwa wpisy mogą mieć ten sam kod skrótu, ale nie mogą być równe. Spójrz na implementację HashMap.get z OpenJdk . Widać, że sprawdza, czy wartości skrótów są równe, a 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ż ten pierwszy jest bardziej wydajnym porównaniem.

Jeśli chcesz dowiedzieć się więcej na ten temat, zajrzyj do artykułu w Wikipedii na temat rozwiązywania kolizji w Open Addressing , który moim zdaniem jest mechanizmem używanym przez implementację OpenJdk. Mechanizm ten jest nieco inny niż podejście „kubełkowe”, o którym wspomina jedna z pozostałych odpowiedzi.

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 przesłonięta metoda Hashcode wygeneruje inny Hashcode (116232,11601) dla obu obiektów. TERAZ, ponieważ istnieją różne kody skrótu, więc nawet nie będzie kłopotać się z wywołaniem metody EQUALS. Ponieważ inny kod skrótu GWARANTUJE RÓŻNĄ 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. 

dwa obiekty są równe, co oznacza, że ​​mają taki sam kod skrótu, ale nie odwrotnie.

2 równe obiekty ------> mają ten sam kod skrótu

2 obiekty mają ten sam kod skrótu ---- xxxxx -> NIE są sobie równe

Aktualizacja Java 8 w HashMap-

wykonujesz tę operację w swoim kodzie -

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

Załóżmy więc, że kod skrótu został zwrócony dla obu kluczy "old"i "very-old"jest taki sam. Co się stanie.

myHashMapjest HashMap i załóżmy, że początkowo nie określiłeś jego pojemności. Tak więc domyślna pojemność jak na Javę wynosi 16. Więc jak tylko zainicjowałeś hashap za pomocą nowego słowa kluczowego, stworzyłem 16 segmentów. teraz, kiedy wykonałeś pierwszą instrukcję

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

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

hash XOR hash >>> 16

tak aby dać jako większy obraz, powróci jakiś indeks, który byłby od 0 do 15. Teraz twój parę klucz wartość "old"i "old-value"będą konwertowane na klucz i wartość zmiennej instancji obiektu wpisu za. a następnie ten obiekt wejściowy zostanie zapisany w segmencie, lub można powiedzieć, że pod określonym indeksem ten obiekt wejściowy zostanie zapisany.

FYI- Entry to klasa w interfejsie Map- Map.Entry, z tymi podpisami / definicjami

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

teraz, gdy wykonasz następną instrukcję -

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

i "very-old"podaje ten sam kod skrótu co "old", więc ta nowa para wartości klucza jest ponownie wysyłana do tego samego indeksu lub tego samego segmentu. Ponieważ jednak ten segment nie jest pusty, nextzmienna obiektu Entry służy do przechowywania tej nowej pary wartości klucza.

i to będzie przechowywane jako lista połączona dla każdego obiektu, który ma ten sam kod skrótu, ale wartość TRIEFY_THRESHOLD jest określona wartością 6. więc po osiągnięciu tego lista połączona jest przekształcana w drzewo zrównoważone (drzewo czerwono-czarne) z pierwszym elementem jako korzeń.

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

Czasami może się zdarzyć, że hashCodes dla 2 różnych obiektów są takie same. W takim przypadku 2 obiekty zostaną zapisane w jednym segmencie i będą prezentowane jako LinkedList. Punktem wejścia jest ostatnio dodany obiekt. Ten obiekt odnosi się do innego obiektu z następnym polem, a więc jednym. Ostatni wpis odnosi się do null. Podczas tworzenia HashMap z domyślnym konstruktorem

Tablica jest tworzona z rozmiarem 16 i domyślnym równoważeniem obciążenia 0,75.

(Źródło)

Mapa mieszania działa na zasadzie mieszania

Metoda HashMap get (Key k) wywołuje metodę hashCode na obiekcie klucza i stosuje zwrócony hashValue do własnej statycznej funkcji skrótu w celu znalezienia położenia segmentu (macierzy bazowej), w którym klucze i wartości są przechowywane w formie zagnieżdżonej klasy o nazwie Entry (Map). Wejście). Doszliście więc do wniosku, że z poprzedniego wiersza, że ​​zarówno klucz, jak i wartość są przechowywane w segmencie jako forma obiektu Entry. Myślenie, że w wiadrze przechowywana jest tylko wartość, jest nieprawidłowe i nie wywrze dobrego wrażenia na ankiecie.

• Ilekroć wywołujemy metodę get (Key k) na obiekcie HashMap. Najpierw sprawdza, czy klucz jest pusty, czy nie. Zauważ, że w HashMap może być tylko jeden klucz zerowy.

Jeśli klucz ma wartość NULL, to klucze Null zawsze są mapowane na wartość skrótu 0, a zatem indeks 0.

Jeśli klucz nie jest pusty, wówczas wywoła funkcję skrótu na obiekcie klucza, patrz wiersz 4 w powyższej metodzie, tj. Key.hashCode (), więc po key.hashCode () zwraca hashValue, wiersz 4 wygląda jak

            int hash = hash(hashValue)

a teraz stosuje zwrócony hashValue do własnej funkcji skrótu.

Możemy się zastanawiać, dlaczego ponownie obliczamy wartość skrótu za pomocą skrótu (hashValue). Odpowiedź brzmi: chroni przed funkcjami skrótu niskiej jakości.

Teraz końcowa wartość skrótu służy do znalezienia położenia segmentu, w którym przechowywany jest obiekt Entry. Przechowuj obiekty obiektów w wiadrze w ten sposób (skrót, klucz, wartość, bucketindex)

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

Mamy Key, Value, HashCode i wiadro.

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

• Wiadro -> Społeczeństwo
• HashCode -> Adres towarzystwa (zawsze unikalny)
• Wartość -> Dom w społeczeństwie
• Klucz -> Adres domu.

Za pomocą Map.get (klucz):

Stevie chce dostać się do domu swojego przyjaciela (Josse), który mieszka w willi w społeczności VIP, niech to będzie JavaLovers Society. Adres Jossego to jego SSN (który jest inny dla wszystkich). Prowadzony jest indeks, w którym dowiadujemy się nazwy Towarzystwa na podstawie SSN. Ten indeks można uznać za algorytm służący do wyszukiwania kodu HashCode.

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

1. Ten SSN (klucz) najpierw daje nam HashCode (z tabeli indeksu), który jest niczym innym jak nazwą Towarzystwa.
2. Teraz wiele domów może należeć do tego samego społeczeństwa, więc HashCode może być wspólny.
3. Załóżmy, że Towarzystwo jest wspólne dla dwóch domów, w jaki sposób zidentyfikujemy, do którego domu zamierzamy, tak, używając klucza (SSN), który jest niczym innym jak adresem Domu

Korzystanie z Map.put (klucz, wartość)

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

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

To będzie długa odpowiedź, weź drinka i czytaj dalej…

Hashowanie polega na przechowywaniu w pamięci pary klucz-wartość, którą można szybciej odczytywać i zapisywać. Przechowuje klucze w tablicy i wartości w LinkedList.

Powiedzmy, że chcę przechowywać 4 pary kluczowych wartości -

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

Aby przechowywać klucze, potrzebujemy tablicy 4 elementów. Jak teraz odwzorować jeden z tych 4 kluczy na 4 indeksy tablic (0,1,2,3)?

Więc java znajduje hashCode poszczególnych kluczy i mapuje je na określony indeks tablicy. Formuły Hashcode to -

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 o czym myślisz. Twoja fascynacja dzikim duetem może sprawić, że przegapisz ważną rzecz.

Dlaczego Java pomnoży to przez 31?

To dlatego, że 31 jest nieparzystą liczbą pierwszą w postaci 2 ^ 5 - 1. A nieparzysta liczba pierwsza zmniejsza prawdopodobieństwo kolizji Hash

Jak ten kod skrótu jest odwzorowany na indeks tablicy?

Odpowiedź brzmi Hash Code % (Array length -1) . Tak “girl”jest odwzorowane (3173020 % 3) = 1w 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źć hasHCodeklucze “misused”i “horsemints”użyć opisanych powyżej formuł, zobaczysz, że oba dają nam to samo 1069518484. Whooaa !! wyciągnięta lekcja -

2 równe obiekty muszą mieć ten sam hashCode, ale nie ma gwarancji, że jeśli hashCode się zgadza, to obiekty są równe. Powinien więc przechowywać zarówno wartości odpowiadające „niewłaściwie użytemu”, jak i „koniom” w segmencie 1 (1069518484% 3).

Teraz mapa skrótu wygląda następująco -

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

Teraz, jeśli jakieś ciało spróbuje znaleźć wartość klucza “horsemints”, java szybko znajdzie jej hashCode, moduł i zacznie szukać jego wartości w odnośniku LinkedList index 1. W ten sposób nie musimy przeszukiwać wszystkich 4 indeksów tablic, co przyspieszy dostęp do danych.

Ale poczekaj jedną sekundę. istnieją 3 wartości w tym odnośniku 1 odpowiadającym indeksowi tablicy, w jaki sposób dowiaduje się, która z nich była wartością kluczowych „konników”?

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

Przechowuje obie pary wartości klucza jako wpis mapy. Mapa faktycznie 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ącą ArrayIndex1 faktycznie porównuje on klucz każdego wpisu do tej LinkedList z „koniami”, a gdy go znajdzie, po prostu zwraca jego wartość.

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

Jak powiedziano, obraz jest wart 1000 słów. Mówię: jakiś kod jest lepszy niż 1000 słów. Oto kod źródłowy HashMap. Uzyskaj metodę:

/**
     * 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;
    }

Staje się więc jasne, że skrót znajduje się w celu znalezienia „segmentu”, a pierwszy element jest zawsze sprawdzany w tym segmencie. Jeśli nie, to equalsklucz służy do znalezienia rzeczywistego elementu na połączonej liście.

Zobaczmy put()metodę:

  /**
     * 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 to nieco bardziej skomplikowane, ale staje się jasne, że nowy element jest umieszczany na karcie w pozycji obliczonej na podstawie skrótu:

i = (n - 1) & hashoto iindeks, w którym zostanie umieszczony nowy element (lub jest to „wiadro”). nto rozmiar tabtablicy (tablica „segmentów”).

Najpierw próbuje się go umieścić jako pierwszy element w tym „wiadrze”. Jeśli istnieje już element, dodaj nowy węzeł do listy.