{"id":538,"date":"2024-04-02T13:56:01","date_gmt":"2024-04-02T13:56:01","guid":{"rendered":"https:\/\/iseebugs.pl\/?p=538"},"modified":"2024-04-17T15:43:25","modified_gmt":"2024-04-17T15:43:25","slug":"java-hashmap-i-hashowanie-z-lotu-ptaka","status":"publish","type":"post","link":"https:\/\/iseebugs.pl\/index.php\/2024\/04\/02\/java-hashmap-i-hashowanie-z-lotu-ptaka\/","title":{"rendered":"Java HashMap i hashowanie z lotu ptaka"},"content":{"rendered":"\n
HashMapa jest jedn\u0105 z najpopularniejszych struktur danych z Java Collections Framework. HashMapa przechowuje dane w parach Kluch – Warto\u015b\u0107, a wyszukiwanie element\u00f3w dzia\u0142a na zasadzie hashowania. Ten artyku\u0142 jest wst\u0119pem do zrozumienia HashMapy z pewnymi uproszczeniami do prostego zrozumienia podstaw mapy.<\/p>\n\n\n\n
Budowa HashMapy<\/h2>\n\n\n\n
HashMapa jest to dynamicznie rozszerzalna struktura kt\u00f3ra przechowuje obiekty z przypisanym do niego kluczem. Kluczami oraz Warto\u015bciami mog\u0105 by\u0107 tylko obiekty referencyjne. Z tego powodu nie mo\u017cemy u\u017cy\u0107 typu prymitywnego np. „int” tylko klasy opakowuj\u0105cej „Integer”.<\/p>\n\n\n\n
Map<Key, String> testMap = new HashMap<>();<\/code><\/pre>\n\n\n\n
Identyfikacja obiekt\u00f3w dzia\u0142a na zasadzie hashowania, a sama struktura z punktu widzenia u\u017cytkownika jest nieuporz\u0105dkowana i zmienna. Po dodaniu kilku obiekt\u00f3w mapa mo\u017ce zmieni\u0107 ca\u0142\u0105 swoj\u0105 struktur\u0119.<\/p>\n\n\n\n
Do poprawnego dzia\u0142ania HashMapy wymagane s\u0105:<\/p>\n\n\n\n
\n
implementacja metody hashcode();<\/li>\n\n\n\n
implementacja metody equals();<\/li>\n\n\n\n
zadeklarowanie jako klucza obiektu nie mutowalnego<\/li>\n<\/ul>\n\n\n\n
Poprawne to nie oznacza konieczne\ud83d\ude09. Bez spe\u0142nienia tych warunk\u00f3w r\u00f3wnie\u017c stworzymy HashMap\u0119, tylko jej zachowanie mo\u017ce by\u0107 odmienne od oczekiwanego przez nas:)<\/p>\n\n\n\n
Najcz\u0119\u015bciej u\u017cywane metody HashMapy<\/h2>\n\n\n\n
Do najcz\u0119\u015bciej u\u017cywanych metod kt\u00f3re u\u0142atwiaj\u0105 prac\u0119 programista nale\u017c\u0105:<\/p>\n\n\n\n
\n
V put(Key, Value) – wstawia par\u0119 klucz – warto\u015b\u0107 do mapy. Je\u017celi podany klucz ju\u017c istnieje to przypisana do niego warto\u015b\u0107 zostaje nadpisana przez now\u0105 podan\u0105 przez u\u017cytkownika. <\/li>\n\n\n\n
V remove(Key) – usuwa pr\u0119 klucz-warto\u015b\u0107 z mapy<\/li>\n\n\n\n
V get(Key) – zwraca warto\u015b\u0107 przypisan\u0105 do klucza, w przypadku b\u0142\u0119dnego klucza zwraca null<\/li>\n\n\n\n
boolean isPresent() – zwraca true je\u017celi w mapie nie ma \u017cadnych par <\/li>\n\n\n\n
int size() – zwraca liczb\u0119 par znajduj\u0105cych si\u0119 w mapie<\/li>\n\n\n\n
void clear() – usuwa wszystkie pary z mapy<\/li>\n\n\n\n
Set<K> setKey() – zwraca zbi\u00f3r wszystkich kluczy z mapy (bez warto\u015bci)<\/li>\n\n\n\n
Collection<V> values() – zwraca wszystkie warto\u015bci z mapy (bez kluczy)<\/li>\n<\/ul>\n\n\n\n
Zapis odczyt obiekt\u00f3w<\/h2>\n\n\n\n
Algorytm hash’uj\u0105cy mapy- wersja uproszczona<\/h3>\n\n\n\n
Poni\u017cszy algorytm ma kilka uproszcze\u0144 ale do\u015b\u0107 dobrze obrazuje na podstawowym poziomie jak dzia\u0142a hashowanie w Javie.<\/p>\n\n\n
\n<\/figure><\/div>\n\n\n\n
Podczas pr\u00f3by zapisu nowego obiektu do mapy sprawdzane jest czy istnieje ju\u017c klucz lub klucze o takim Hash Codzie. Wiele kluczy mo\u017ce mie\u0107 taki sam hash code. <\/li>\n\n\n\n
Je\u017celi istniej\u0105 klucze o takim samym hash kodzie wtedy mapa por\u00f3wnuje nowy klucz z nimi. Por\u00f3wnanie nast\u0119puje tylko z tymi obiektami dzi\u0119ki czemu eliminujemy por\u00f3wnanie ze wszystkimi kluczami i wszystkimi polami co znacznie przyspiesza dzia\u0142anie programu.<\/li>\n\n\n\n
Je\u017celi znajdziemy identyczny klucz (metoda equals zwr\u00f3ci true) to nowy obiekt kt\u00f3ry jest przypisany do klucza nadpisuje ju\u017c istniej\u0105cy. Je\u017celi nie znajdzie identycznego klucza to tworzy now\u0105 par\u0119 klucz-obiekty o takim samym Hash Codzie.<\/li>\n<\/ol>\n\n\n\n
W przypadku pr\u00f3by odczytu obiektu za pomoc\u0105 podanego klucza mapa wykonuje takie same kroki jak przy zapisie. Jedyna r\u00f3\u017cnica polega na tym, \u017ce w przypadku braku w mapie podanego klucza metoda zwr\u00f3ci warto\u015b\u0107 null.<\/p>\n\n\n\n
Nie nadpisanie lub b\u0142\u0119dne nadpisanie metod equals() oraz hashCode()<\/h2>\n\n\n\n
Nie nadpisanie metody HashCode()<\/h3>\n\n\n\n
Za\u0142\u00f3\u017cmy, \u017ce mamy klas\u0119 „KeyObject” kt\u00f3ra jest kluczem w naszej mapie. Posiada tylko jedno pole typu String, ale nie nadpisuje \u017cadnej metody.<\/p>\n\n\n\n
public class KeyObject {\n String password;\n}<\/code><\/pre>\n\n\n\n
Nie nadpisanie metody HashCode() spowoduje u\u017cycie przez map\u0119 domy\u015blnej implementacji. Domy\u015blna implementacja tworzy hash code na podstawie adresu obiektu w pami\u0119ci a nie jego p\u00f3l.<\/em><\/strong> Taka sytuacja spowoduje, \u017ce obiekty kt\u00f3re s\u0105 identyczne b\u0119d\u0105 posiada\u0142y r\u00f3\u017cne hash cody. Nasze hash cody b\u0119d\u0105 takie same jedynie kiedy b\u0119d\u0105 mia\u0142y tak\u0105 sam\u0105 referencje.<\/p>\n\n\n\n
Jest to bardzo niepo\u017c\u0105dane poniewa\u017c praktycznie nigdy nie mogliby\u015bmy dosta\u0107 si\u0119 do danych znajduj\u0105cych si\u0119 w Mapie. Za\u0142\u00f3\u017cmy, \u017ce mamy map\u0119 kt\u00f3rej kluczem jest obiekt „KeyObject” przechowuj\u0105cy nazw\u0119 u\u017cytkownika i has\u0142o a danymi kt\u00f3re posiada u\u017cytkownik obiekt typu String. Poni\u017cszy przyk\u0142ad reprezentuje jak to mo\u017ce wygl\u0105da\u0107.<\/p>\n\n\n\n
Posiadamy domen\u0119 np. www.brakMetodHaszuj\u0105cych.pl gdzie:<\/p>\n\n\n\n
\n
Posiadamy baz\u0119 u\u017cytkownik\u00f3w wraz z danymi (linia 1).<\/li>\n\n\n\n
Stworzyli\u015bmy u\u017cytkownika o nazwie „User” wraz z has\u0142em oraz zapisali\u015bmy go do bazy danych.<\/li>\n<\/ol>\n\n\n\n
1 Map<KeyObject, String> userData = new HashMap<>();\n\n2 KeyObject keyA = new KeyObject();\n3 keyA.user = \"User\";\n4 keyA.password =\"Password\";\n5 System.out.println(keyA.hashCode());\n\n6 userData.put(keyA, \"user data\");\n\n7 KeyObject keyFromUser = new KeyObject();\n8 keyFromUser.user = \"User\";\n9 keyFromUser.password =\"Password\";\n10 System.out.println(keyFromUser.hashCode());\n\n11 String dataFromBackend = userData.get(keyFromUser);\n\n12 System.out.println(\"User data from map: \" + dataFromBackend);<\/code><\/pre>\n\n\n\n
U\u017cytkownik si\u0119 wylogowa\u0142 i chcia\u0142 si\u0119 ponownie zalogowa\u0107<\/p>\n\n\n\n
\n
Podaje dane – has\u0142o i login<\/li>\n\n\n\n
Frontend wysy\u0142a dane do Backendu <\/li>\n\n\n\n
Backend tworzy nowy obiekt na podstawie danych i nazywa go keyFromUser (linie 7-9)<\/li>\n<\/ul>\n\n\n\n
Po wykonaniu tego kodu chcieliby\u015bmy wy\u015bwietli\u0107 dane u\u017cytkownika (w ko\u0144cu obiekty „keyA” oraz „keyFromUser” s\u0105 identyczne) w postaci:<\/p>\n\n\n\n
User data from map: user data<\/code><\/pre>\n\n\n\n
Niestety przez brak metody hashCode() zamiast uzyska\u0107 powy\u017cszy komunikat otrzymujemy nast\u0119puj\u0105cy:<\/p>\n\n\n\n
250421012\n1915318863\nUser data from map: null<\/code><\/pre>\n\n\n\n
Nie jest to satysfakcjonuj\u0105cy wynik. Dzieje si\u0119 tak dlatego, poniewa\u017c jest tworzony nowy obiekt w pami\u0119ci. Brak nadpisanej metody hashCode powoduje, \u017ce domy\u015blna tworzy hashCode na podstawie innego miejsca kt\u00f3ry jest r\u00f3\u017cny od oczekiwanego.<\/p>\n\n\n\n
B\u0142\u0119dne nadpisanie metody HashCode()<\/h3>\n\n\n\n
B\u0142\u0119dne nadpisanie metody hashCode jest bardziej zgodne z oczekiwaniami. Je\u017celi mamy b\u0142\u0119dnie nadpisan\u0105 metod\u0119 hashCode w taki spos\u00f3b, \u017ce np.<\/p>\n\n\n\n
\n
Zawsze zwraca sta\u0142\u0105 liczb\u0119<\/li>\n\n\n\n
Zwraca liczb\u0119 ale nie na podstawie wszystkich p\u00f3l tylko kilku<\/li>\n<\/ul>\n\n\n\n
Spowoduje to znaczne spowolnienie przeszukiwania mapy w celu znalezienia odpowiedniego klucza oraz przypisanej do niego obiektu. W pierwszym przypadku b\u0119dziemy por\u00f3wnywa\u0107 wszystkie klucze ze sob\u0105 element po elemencie co prowadzi do zmniejszenia wydajno\u015bci z oczekiwanej O(1) do <\/p>\n\n\n\n
\n
O(log n) w wi\u0119kszo\u015bci przypadk\u00f3w<\/li>\n\n\n\n
O(n) je\u017celi pojemno\u015b\u0107 mapy jest mniejsza od 64 (to nie to samo co ilo\u015b\u0107 element\u00f3w w mapie)<\/li>\n<\/ul>\n\n\n\n
W drugim przypadku mo\u017cemy spowodowa\u0107, \u017ce metoda haszuj\u0105ca b\u0119dzie mniej wydajna od zamierzonej.<\/p>\n\n\n\n
Nie nadpisanie metody equals()<\/h3>\n\n\n\n
Zak\u0142adamy, \u017ce poprawili\u015bmy nasz kod i nadpisali\u015bmy metod\u0119 hashuj\u0105c\u0105. Teraz nasza klasa wygl\u0105da w nast\u0119puj\u0105cy spos\u00f3b:<\/p>\n\n\n\n
public class KeyObject {\n String user;\n String password;\n\n @Override\n public int hashCode() {\n final int prime = 31;\n int result = 1;\n result = prime * result + ((user == null) ? 0 : user.hashCode());\n result = prime * result + ((password == null) ? 0 : password.hashCode());\n return result;\n }\n}<\/code><\/pre>\n\n\n\n
Niestety wyniki nadal nie b\u0119d\u0105 si\u0119 nam podoba\u0107. W rezultacie wykonania naszego kodu otrzymamy:<\/p>\n\n\n\n
1363656689\n1363656689\nUser data from map: null<\/code><\/pre>\n\n\n\n
W tym momencie pozytywnie przeszli\u015bmy por\u00f3wnanie hashy. Niestety nienadpisanie metody equals powoduje, \u017ce por\u00f3wnywane s\u0105… miejsca w pami\u0119ci przechowywania danych, tak jak w pierwszym przyk\u0142adzie.<\/p>\n\n\n\n
B\u0142\u0119dne nadpisanie metody equals()<\/h3>\n\n\n\n
B\u0142\u0119dnie nadpisana metoda equals() spowoduje, \u017ce nie wszystkie pola b\u0119d\u0105 por\u00f3wnywane ze sob\u0105 lub mog\u0105 by\u0107 b\u0142\u0119dnie por\u00f3wnywane. Powy\u017csze mo\u017ce prowadzi\u0107 do niezgodno\u015bci kontraktu hashcode-equals a co za tym idzie poprawnym wyszukiwaniem element\u00f3w.<\/p>\n\n\n\n
Podsumowanie<\/h2>\n\n\n\n
Jestem pewien, \u017ce po przeczytaniu artyku\u0142u wiesz jak mniej wi\u0119cej wygl\u0105da przeszukiwanie przez HashMap\u0119 jej element\u00f3w i jak wa\u017cne s\u0105 implementacje metod hashCode() oraz equals(). Jest to dobry wst\u0119p hashMapy. Aby j\u0105 w pe\u0142ni zrozumie\u0107 nale\u017cy dodatkowo zg\u0142\u0119bi\u0107 takie poj\u0119cia jak:<\/p>\n\n\n\n
\n
kontrakt hashCode i equals<\/li>\n\n\n\n
dlaczego klucze nie powinny by\u0107 mutowalne<\/li>\n\n\n\n
jak dzia\u0142a hashowanie under the hood <\/li>\n<\/ul>\n\n\n
![\"\"](\"https:\/\/iseebugs.pl\/wp-content\/uploads\/2024\/04\/hash.uproszczony.png\")
<\/figure><\/div>\n\n\n