HashMap - jedna z nejčastěji používaných datových struktur v programovacím jazyce Java. Jedná se o implementaci asociativního pole založeného na principu hash tabulky. V podstatě jde o sbírku, která umožňuje ukládat páry klíč-hodnota, kde je každý klíč jedinečný.
Základní myšlenkou použití hashmap je mít rychlý přístup k prvkům na klíč. Místo toho, aby se hashmap procházel celou sbírkou a hledal správný prvek, používá hash funkci k nalezení bakety, ve které by měla být. Hash funkce přijímá klíč jako vstup a vrací index pole, kde by měl být tento klíč uložen.
Když vložíte prvky do hashmap, každý prvek dostane svůj jedinečný hash kód. Pokud mají dvě položky stejné klíče, pak budou hash kódy pro ně také stejné. Ale co když dva prvky s různými klíči mají stejný hash kód? Říká se tomu kolize. V takovém případě HashMap používá jinou datovou strukturu - propojený seznam, aby ukládal všechny položky se stejnými hash kódy do stejné nádrže. Právě díky propojeným seznamům může hashmap ukládat více položek se stejnými hash kódy a rychle najít požadovaný klíč.
Třída HashMap poskytuje metody pro přidávání, mazání a vyhledávání položek. Nabízí také sadu metod pro interakci s daty, jako je získání velikosti sbírky a kontrola přítomnosti položky. Kromě toho je HashMap určitou kombinací pole a přidruženého seznamu, což umožňuje operace přidávání, mazání a vyhledávání položek v neustálém čase.
HashMap v Javě
Když je prvek přidán do hashmap, vejde se do jedné z buněk vnitřního pole. Hashovací algoritmus vypočítá hash kód klíče a převede jej na index buňky. Pokud již tato buňka obsahuje prvek, pak hashmap používá metodu řetězu, při které je přidaná položka přidána do přidruženého seznamu s jinými položkami. Pokud buňka nemá žádné prvky, pak je prvek přidán přímo do buňky.
Při hledání položky v hashmap algoritmus hash vypočítá hash kód klíče a použije jej k určení indexu buňky. Poté se vyhledá v propojeném seznamu položek. Pokud prvek není nalezen, vrátí se hodnota null.
- Rychlé přidávání a vyhledávání položek.
- Flexibilita při používání různých typů klíčů.
- Možnost ukládat velké množství dat.
- Potenciální kolize při použití stejného hash kódu.
- Nežádoucí využití velkého množství paměti.
Velikost vnitřního pole hashmap se může dynamicky měnit v závislosti na počtu prvků a podílu výplně. To zajišťuje vysokou účinnost operací přidávání a vyhledávání položek.
Hashmap v Javě je výkonný nástroj, který se široce používá k řešení různých úkolů, které vyžadují rychlý a efektivní přístup k datům. Je důležité vzít v úvahu jeho vlastnosti a vybrat vhodnou implementaci pro konkrétní úkol.
Princip hashmap
Když dojde k přidání položky do Hashmapu, vypočítá hash kód klíče a identifikuje index hash tabulky, ve kterém bude hodnota uložena. Pokud je v tomto indexu již jiná hodnota, dochází ke kolizi a položky jsou umístěny v přidruženém seznamu. V případě kolizí jsou položky přidány na začátek seznamu, což umožňuje uložit do HashMap více hodnot se stejným hash kódem.
Když obdržíte hodnotu podle klíče, HashMap nejprve vypočítá hash kód klíče a najde příslušný index v hash tabulce. Poté zkontroluje hodnoty v seznamu souvisejícím s tímto indexem a vrátí hodnotu odpovídající klíči.
Aby bylo zajištěno rychlé získání hodnot, hash karty v Javě používají instance tříd klíčů, které musí správně implementovat metody hashCode() a equals(). To umožňuje HashMap efektivně vypočítat hash kódy a porovnávat klíče při hledání hodnot.
Hashování klíčů v hashmap
Když vložíte prvek do HashMap, nejprve vypočítá hash kód klíče pomocí metody hashCode() . Tento hash kód je poté převeden pomocí funkce hash, aby se získal skutečný index vnitřního pole, kde bude hodnota uložena.
Proces hašování výrazně urychluje dobu přístupu k prvkům, protože umožňuje rychlý výpočet pozice, kde by měly být uloženy. Může však nastat situace, kdy dva různé klíče mohou mít stejný hash kód, který se nazývá kolize. V tomto případě jsou kolizní prvky uloženy uvnitř jednoho bucketu (tužka, kbelík), který je součástí vnitřního masivu HashMap.
Když dojde k nalezení prvku v HashMap na jeho klíči, nejprve vypočítá hash kód klíče a najde index bucket, kde by položka měla být. Poté prochází tímto bucket a porovnává klíče prvků pomocí metody equals (), dokud nebude nalezena položka s odpovídajícím klíčem nebo nebude dosaženo konce bucket.
Dobrá hash funkce by měla distribuovat klíče rovnoměrně v celé řadě hash kódů, aby se snížil počet kolizí. Pokud hash funkce distribuuje klíče špatně, může to vést ke zhoršení výkonu HashMap a prodloužení doby provádění operací přidávání, vyhledávání nebo mazání položek.
Kolize a řešení problémů
Když dojde ke kolizi, Hashmap hledá další prázdnou buňku v poli pro uložení prvku. Tento přístup může způsobit problémy s výkonem, zejména při velkém počtu prvků a hustém plnění pole.
K řešení problémů s kolizemi se v Javě používá metoda řetězů (angl. chaining). Namísto ukládání prvků do pole každá buňka pole obsahuje propojený seznam položek se stejnými hash. To umožňuje efektivní ukládání mnoha položek se stejným hash kódem.
Když je přidána nová položka, Hashmap nejprve zkontroluje, zda již existuje prvek se stejným klíčem. Pokud existuje, je přidán na konec propojeného seznamu. Pokud ne, vytvoří se nová položka a přidá se do přidruženého seznamu příslušné buňky.
Při hledání položky s určitým klíčem, Hashmap nejprve vypočítá hash kód klíče a najde příslušnou buňku pole. Poté se vyhledá požadovaná položka v propojeném seznamu buňky.
Metoda řetízků řeší problém kolizí, ale při špatně navržených hashovacích funkcích nebo nevhodném výběru velikosti pole mohou kolize stále nastat a snížit výkon Hashmap. Proto je důležité správně zvolit hash funkce a velikosti polí a v případě potřeby zvážit možnost zvětšení velikosti pole.
- Umí rychle a efektivně najít položky podle klíče, pokud je kolize malá a seznam položek v buňce malý
- Umožňuje přidávat a odstraňovat prvky bez přestavby celé struktury
- Při kolizích může být nutné hledat položku v propojeném seznamu, což trvá déle
- Nesprávný výběr hash funkce nebo velikosti pole může negativně ovlivnit výkon