Jak HashTable i HashMap key-value są przechowywane w pamięci?

Podstawowa idea HashMap jest taka:

1. A {[0] } jest tak naprawdę tablicą specjalnych obiektów, które przechowują zarówno Klucz, jak i wartość.
2. tablica ma pewną ilość wiader (slotów), powiedzmy 16.
3. algorytm haszujący jest dostarczany przez metodę hashCode(), którą posiada każdy obiekt. Dlatego pisząc nową Class, Należy zadbać o właściwą implementację metod hashCode() i equals(). Domyślna (z klasy Object) przyjmuje wskaźnik pamięci jako liczbę. Ale to nie jest dobre dla większości klas, z których chcielibyśmy korzystać. Na przykład klasa String używa algorytmu, który tworzy hash ze wszystkich znaków w łańcuchu-pomyśl o tym w następujący sposób: hashCode = 1.char + 2.char + 3.char... (uproszczone). Dlatego dwa równe ciągi, mimo że znajdują się w innym miejscu w pamięci, mają ten sam hashCode().
4. wynikiem hashCode(), powiedzmy "132", jest wtedy liczba wiadra, w którym obiekt powinien być przechowywany, jeśli mamy tak dużą tablicę. Ale my nie, nasz ma tylko 16 wiadrów. Więc my użyj oczywistych obliczeń 'hashcode % array.length = bucket' lub '132 mod 16 = 4' i zapisz parę klucz-wartość w wiadrze numer 4.
5. Jeśli nie ma jeszcze innej pary, jest ok.
6. jeśli istnieje jeden z kluczem równym kluczowi, który mamy, usuwamy Stary.
7. jeśli jest inna para klucz-wartość (kolizja), łączymy nową za starą do połączonej listy.
8. jeśli tablica zapasowa stanie się zbyt pełna, więc będziemy musieli zrobić zbyt wiele połączonych list, tworzymy nową tablicę z podwojoną długością, ponownie dodajemy wszystkie elementy do nowej tablicy, a następnie usuwamy starą. Jest to najprawdopodobniej najdroższa operacja na HashMap, więc chcesz powiedzieć swojemu Maps, ile łyżek użyjesz, jeśli znasz je wcześniej.
9. jeśli ktoś próbuje uzyskać wartość, podaje klucz, mieszamy go, modyfikujemy, a następnie przechodzimy przez potencjalną listę połączoną dla dokładnego dopasowania.

Zdjęcie dzięki uprzejmości Wikipedii:

W tym case,

• istnieje tablica z 256 wiadrami (numerowanymi, oczywiście, 0-255)
Jest pięć osób. Ich hashcody, po umieszczeniu przez mod 256, wskazują na cztery różne sloty w tablicy.
• widać, że Sandra Dee nie miała wolnego miejsca, więc została przykuta do Johna Smitha.