{"id":544,"date":"2024-04-17T15:38:06","date_gmt":"2024-04-17T15:38:06","guid":{"rendered":"https:\/\/iseebugs.pl\/?p=544"},"modified":"2024-04-17T15:44:13","modified_gmt":"2024-04-17T15:44:13","slug":"hashmap","status":"publish","type":"post","link":"https:\/\/iseebugs.pl\/index.php\/2024\/04\/17\/hashmap\/","title":{"rendered":"Java HashMap i hashowanie under the hood"},"content":{"rendered":"\n

HashMapa jest to dynamicznie rozszerzalna struktura danych przechowuj\u0105ca pary <Klucz, Warto\u015b\u0107> i dzia\u0142aj\u0105ca na zasadzie hashowania. Dane s\u0105 nieuporz\u0105dkowane a oczekiwana z\u0142o\u017cono\u015b\u0107 obliczeniowa dost\u0119pu do konkretnego obiektu poprzez klucz wynosi O(1). HashMapa jest klas\u0105 implementuj\u0105c\u0105 interface Map z Java Collections Framework.<\/p>\n\n\n\n

Hashowanie<\/h2>\n\n\n\n

Powy\u017cszy kr\u00f3tki opis pojawia si\u0119 prawie wsz\u0119dzie tam gdzie jest pytanie co to jest HashMapa. Lecz nie dowiemy si\u0119 z niego niczego istotnego na temat hashowania co jest kluczowe w \u015bwiadomym i poprawnym korzystaniu z tej struktury. Aby to zrobi\u0107 musimy wej\u015b\u0107 w sam \u015brodek klasy HashMap i dowiedzie\u0107 si\u0119 naprawd\u0119 jest zbudowana.<\/p>\n\n\n\n

Struktura HashMapy<\/h2>\n\n\n\n

HashMapa pod spodem jest tak naprawd\u0119 zwyk\u0142\u0105 tablic\u0105 przechowuj\u0105c\u0105 obiekty typu Node<K,V> i metody kt\u00f3re na niej operuj\u0105. <\/p>\n\n\n\n

Kiedy deklarujemy zwyk\u0142a tablic\u0119 w Javie zawsze musimy zna\u0107 jej pojemno\u015b\u0107. Tak samo dzieje si\u0119 przy HashMapie, je\u017celi tego nie zrobimy wtedy pole CAPACITY<\/code> b\u0119dzie wst\u0119pnie ustawione na 16. Mo\u017cemy ustawi\u0107 r\u0119cznie pojemno\u015b\u0107 naszej mapy ale tylko raz i tylko przy jej inicjalizacji. Kom\u00f3rki nasze tablicy s\u0105 r\u00f3wnie\u017c nazywane bucketami (kube\u0142kami) co zostanie dalej om\u00f3wione przy hashowaniu.<\/p>\n\n\n\n

    \/**\n     * The default initial capacity - MUST be a power of two.\n     *\/\n    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; \/\/ aka 16<\/code><\/pre>\n\n\n\n
Je\u017celi osi\u0105gniemy pewne zape\u0142nienie naszej tablicy elementami, wtedy tablica dynamicznie si\u0119 nadpisze na nowy rozmiar. Dynamiczne rozszerzanie HashMapy nast\u0119puje automatycznie w momencie dodawania nowego elementu do mapy. Po dodaniu elementu nast\u0119puje sprawdzenie warunku czy nale\u017cy zwi\u0119kszy\u0107 HashMap\u0119 czy te\u017c nie. <\/p>\n\n\n\n
if (++size > threshold)\n            resize();<\/code><\/pre>\n\n\n\n
Sprawdzenie powy\u017cszego warunku jest to por\u00f3wnanie aktualnego rozmiaru tablicy po dodaniu nowego elementu z progiem przej\u015bcia na nowy rozmiar. Pr\u00f3g (threshold) jest  to iloczyn aktualnego rozmiaru tablicy i wsp\u00f3\u0142czynnika przej\u015bcia DEFAULT_LOAD_FACTOR<\/code>. <\/p>\n\n\n\n
threshold = current capacity * DEFAULT_LOAD_FACTOR\nthreshold = 16 * 0.75 = 12 - przy pocz\u0105tkowych warto\u015bciach mapy<\/code><\/pre>\n\n\n\n
W powy\u017cszym przyk\u0142adzie pierwszy raz mapa zwi\u0119kszy swoj\u0105 pojemno\u015b\u0107 dopiero kiedy dodamy element numer 13 do mapy, poniewa\u017c akceptowalnym progiem zape\u0142nienia jest 12.<\/p>\n\n\n\n
Tak samo jak przy pojemno\u015bci, tak i przy wsp\u00f3\u0142czynniku zape\u0142nienia mo\u017cemy indywidualnie go modyfikowa\u0107 wed\u0142ug potrzeb byle by\u0142 wi\u0119kszy od 0 i z zakresu typu float.<\/p>\n\n\n\n
 * As a general rule, the default load factor (.75) offers a good\n * tradeoff between time and space costs.<\/code><\/pre>\n\n\n\n
Je\u017celi nie mamy wyra\u017anej potrzeby zmiany wsp\u00f3\u0142czynnika mo\u017cemy spokojnie o nim zapomnie\u0107. Sama dokumentacja m\u00f3wi o tym, \u017ce jest to dobry kompromis pomi\u0119dzy czasem wyszukiwania a zajmowan\u0105 przestrzeni\u0105.<\/p>\n\n\n\n
Obiekt typu Node<\/h2>\n\n\n\n
Obiekt Node jest wewn\u0119trzn\u0105 klas\u0105 tworzon\u0105 na potrzeby HashMapy. Ka\u017cdy z obiekt\u00f3w tej klasy posiada 4 elementy. <\/p>\n\n\n\n
static class Node<K,V> implements Map.Entry<K,V> {\n        final int hash;\n        final K key;\n        V value;\n        Node<K,V> next;\n        }<\/code><\/pre>\n\n\n\n
hash – jest to kopia hashcode <\/strong>klucza nowej pary <Klucz, Warto\u015b\u0107><\/p>\n\n\n\n
key – jest to referencja do klucza<\/p>\n\n\n\n
value – jest to referencja obiektu do kt\u00f3rego odwo\u0142uje si\u0119 klucz<\/p>\n\n\n\n
next – jest to referencja do kolejnego obiektu o tym samym hashcodzie<\/p>\n\n\n\n
Z powy\u017cszego mo\u017cemy wyci\u0105gn\u0105\u0107 wniosek dlaczego tak wa\u017cne jest aby kluczami by\u0142y obiekty immutable (niezmienne). <\/p>\n\n\n\n
Za\u0142\u00f3\u017cmy, \u017ce mamy now\u0105 par\u0119 <Klucz, Warto\u015b\u0107> przy czym klucz jest obiektem mutable. Gdy zapisujemy t\u0105 par\u0119 do mapy, wtedy na sztywno inicjujemy jego hashcode w obiekcie Node pod polem hash. <\/p>\n\n\n\n
Je\u017celi z innego miejsca zmienimy jakie\u015b pola klucza poprzez referencj\u0119 wtedy zmienimy jego hashcode. Jego nowy hashcode nie b\u0119dzie zgadza\u0142 si\u0119 z tym przypisanym do Node’a i zapisanego na sztywno.  HashMapa nie odwo\u0142uje si\u0119 do hashy kluczy tylko do pola hash kt\u00f3rego dzi\u0119ki s\u0142owu kluczowemu final nie mo\u017cemy nadpisa\u0107. <\/p>\n\n\n\n
Dostanie si\u0119 przy pomocy tak zmodyfikowanego klucza spowoduje, \u017ce przez niezgodno\u015b\u0107 hashy nie dostaniemy si\u0119 do obiektu. Je\u017celi jednak podaliby\u015bmy klucz kt\u00f3ry przez przypadek mia\u0142 by taki sam hash jak ten z pola hash obiektu Node to r\u00f3wnie\u017c nie dostaniemy si\u0119 do obiektu poniewa\u017c nasz klucz nie przejdzie por\u00f3wnywania p\u00f3l metod\u0105 equals(). Taka sytuacja powoduje ca\u0142kowit\u0105 destabilizacj\u0105 pracy z dan\u0105 Map\u0105. Dlatego tak wa\u017cne jest wykorzystywanie element\u00f3w immutable jako kluczy.<\/p>\n\n\n\n
Zapis nowego obiektu<\/h2>\n\n\n\n
Zapisuj\u0105c nowy obiekt do HashMapy zapisujemy go do tablicy Node’\u00f3w w miejscu o odpowiednim indeksie tzw. bucket’cie. Ilo\u015b\u0107 naszych bucket’\u00f3w jest to aktualna pojemno\u015b\u0107 mapy. Za\u0142\u00f3\u017cmy, \u017ce mamy pocz\u0105tkow\u0105 pojemno\u015b\u0107 r\u00f3wna 16 i chcemy zapisa\u0107 w nim nowy obiekt kt\u00f3rego klucz posiada hash r\u00f3wny 25. Aby znale\u017a\u0107 odpowiedni indeks dla naszego nowego klucza musimy wykona\u0107 operacj\u0119 binarn\u0105 AND kt\u00f3ra wygl\u0105da nast\u0119puj\u0105co.<\/p>\n\n\n\n
tab[i = (n - 1) & hash]<\/code><\/pre>\n\n\n\n
    \n
  • Najpierw obliczamy warto\u015b\u0107 'n-1′ czyli nasza pojemno\u015b\u0107 tablicy minus jeden. 16 – 1 = 15 <\/li>\n\n\n\n
  • Zamieniamy nasze liczby z systemu dziesi\u0119tnego na binarny<\/li>\n<\/ul>\n\n\n\n
    15 = 1111\n25 = 11001<\/code><\/pre>\n\n\n\n
      \n
    • Wykonujemy operacj\u0119 binarna AND<\/li>\n<\/ul>\n\n\n\n
         1111   (n - 1)   - 15\n& 11001   (hash)    - 25\n-------\n   1001   (wynik)   - 9<\/code><\/pre>\n\n\n\n
      Ka\u017cdy hash o wi\u0119kszej ilo\u015bci bit\u00f3w od pojemno\u015bci tablicy jest skracany. W naszym przyk\u0142adzie do 4 bit\u00f3w. Nast\u0119pnie por\u00f3wnywane s\u0105 te same bity. Je\u017celi obydwa bity s\u0105 ustawione na „1” wtedy w wyniku otrzymujemy „1”. Po por\u00f3wnaniu obydwu liczb otrzymujemy w systemie binarnym liczb\u0119 1001 kt\u00f3ra odpowiada 9. w systemie dziesi\u0119tnym.<\/p>\n\n\n\n
      W ten \u0142atwy spos\u00f3b tylko na podstawie hashcode i rozmiaru tabeli HashMapa zapisuje obiekt do bucket’a. Podobnie wygl\u0105da odnajdywanie bucket’a w kt\u00f3rym znajduje si\u0119 szukany obiekt. Dzi\u0119ki temu nie ma konieczno\u015bci przeszukiwania ca\u0142ej mapy.<\/p>\n\n\n\n
      Bucket’y<\/h2>\n\n\n\n
      Jak pisa\u0142em wcze\u015bniej pocz\u0105tkowa pojemno\u015b\u0107 standardowej tablicy w mapie jest to 16 element\u00f3w. Automatyczne zwi\u0119kszenie jej pojemno\u015bci nast\u0119puje po zape\u0142nieniu do 75%. W zwi\u0105zku z czym przy zbli\u017caniu si\u0119 do zape\u0142nienia mapy nadal mamy wolne 25 lub… wi\u0119cej procent element\u00f3w tablicy. Taka sytuacja ma miejsce wtedy gdy kilka kluczy ma takie same hashcody. <\/p>\n\n\n\n
      Je\u017celi w jakim\u015b elemencie tabeli znajduje si\u0119 ju\u017c jeden obiekt, kolejny jest zapisywany jako referencja w polu next. W ten spos\u00f3b w danym bucket’cie tworzona jest LinkedLista obiekt\u00f3w o tym samym hashcodzie. W poni\u017cszym przyk\u0142adzie w HashMapie znajduj\u0105 si\u0119 4 pary <Klucz, Warto\u015b\u0107>. Jeden w jednym bucket’cie, oraz 3 w drugim. <\/p>\n\n\n\n
      \"\"<\/figure>\n\n\n\n
      Standardowa oczekiwana z\u0142o\u017cono\u015b\u0107 obliczeniowa przy odczycie z HashMapy wynosi O(1). Przy zdegenerowanych danych gdzie wszystkie hashe s\u0105 takie same mog\u0142oby doj\u015b\u0107 do sytuacji, \u017ce w jednym bucket’cie mamy jedn\u0105 d\u0142ug\u0105 LinkedList\u0119 obiekt\u00f3w. W takim przypadku z\u0142o\u017cono\u015b\u0107 obliczeniowa d\u0105\u017cy\u0142a by do O(n). Java b\u0119dzie por\u00f3wnywa\u0142a klucz referencyjny po kolei z ka\u017cdym kluczem w LinkedLi\u015bcie za pomoc\u0105 metody equals() a\u017c znajdzie mu odpowiadaj\u0105cy obiekt. \u017beby zapobiec takim sytuacj\u0105 tw\u00f3rcy Javy wprowadzili mechanizm red-black tree (czerwono-czarnego drzewa binarnego poszukiwa\u0144). Zamiana na RBT wyst\u0119puje w tych bucket’ach kt\u00f3re przechowuj\u0105 co najmniej 8 element\u00f3w a ca\u0142a tabela ma co najmniej 64 elementy. Zamiana mechanizmu LinkedListy na RBT powoduje spadek z\u0142o\u017cono\u015bci obliczeniowej dost\u0119pu do danych z O(n) do O(log n). <\/p>\n\n\n\n
      \"\"<\/figure>\n\n\n\n
      Czasy dost\u0119pu przy odczycie danych:<\/p>\n\n\n\n
      O(1) – oczekiwany<\/p>\n\n\n\n
      O(log n) – dla zdegenerowanych danych<\/p>\n\n\n\n
      O(n) – dla zdegenerowanych danych przy braku mo\u017cliwo\u015bci zastosowania red-black tree.<\/p>\n\n\n\n
      Zwi\u0119kszenie obj\u0119to\u015bci mapy<\/h2>\n\n\n\n
      Po osi\u0105gni\u0119ciu przez map\u0119 maksymalnej zaj\u0119to\u015bci i pr\u00f3bie dodania kolejnego elementu mapa automatycznie zwi\u0119kszy swoj\u0105 pojemno\u015b\u0107. Przy nowej zmianie pojemno\u015bc nasz pierwotny obiekt kt\u00f3ry mia\u0142 hash r\u00f3wny 25, po operacji binarnej wpada\u0142 do bucket’a z indeksem r\u00f3wnym 9. Teraz b\u0119dzie si\u0119 znajdowa\u0142 w innym bucket’cie. <\/p>\n\n\n\n
      Po zwi\u0119kszeniu pojemno\u015bci tablicy do 32 nasz obiekt wpadnie do bucketa r\u00f3wnego 25. Tak samo wszystkie inne obiekty musz\u0105 by\u0107 ponownie przepisane (nast\u0119puje rehashing), a co za tym idzie ca\u0142a struktura jest budowana na nowo wraz ze wszystkimi LinkedListami i drzewami binarnymi. Dlatego mimo i\u017c oczekiwana z\u0142o\u017cono\u015b\u0107 obliczeniowa odczytu HashMapy wynosi O(1) to w przypadku kiedy akurat b\u0119dzie nast\u0119powa\u0142o dynamiczne zwi\u0119kszenie pojemno\u015bci i rehashing wtedy b\u0119dzie si\u0119 zbli\u017ca\u0142a do O(n).<\/p>\n\n\n\n
      Podsumowanie<\/h2>\n\n\n\n
      W powy\u017cszym artykule przedstawi\u0142em jak dzia\u0142a hashowanie i zapis kluczy do HashMapy i dlaczego jego zrozumienie jest wa\u017cne do pisania bardzie odpornego na b\u0142\u0119dy kodu.<\/p>\n\n\n