Myslím, že bude užitečnější, když vysvětlím HashMaps v angličtině.

Co je to HashMap?

HashMap je datová struktura, která dokáže mapovat určité klíče na určité hodnoty. Klíče a hodnoty mohou být jakékoliv. Kdybych například vytvářel hru, mohl bych každé uživatelské jméno propojit se seznamem přátel, reprezentovaným seznamem řetězců.

Proč používat HashMap?

HashMapy jsou mnohem rychlejší pro načítání dat než pole a propojené seznamy. Uspořádané pole by mohlo najít konkrétní hodnotu za O(log n) pomocí binárního vyhledávání. HashMap však dokáže zjistit, zda obsahuje konkrétní klíč, za O(1). Všechny klíče musí být unikátní.

Jak fungují HashMapy?

HashMapy používají pole na pozadí. Každý prvek pole je jiná datová struktura (obvykle spojový seznam nebo binární vyhledávací strom). HashMap používá funkci na klíči, která určuje, kam má být hodnota klíče v poli umístěna. Například pokud moje mapa HashMap přijímá řetězce… možné funkce hash mohou být:

A. Return the ASCII value of the first letter.B. Return the sum of the ASCII values of every character in the String.C. Return the ASCII value of the last character in the String.

Vrácená hodnota určí index, ve kterém se hodnota dostane do pole.

Ale počkat! Je tu problém! Proto máme vrácenou hodnotu upravit o délku pole.

return Math.abs(number%hashMapArray.length);

Kolise:

Není možné, že více klíčů způsobí, že hashovací funkce vygeneruje stejný index? Ano. Například pokud bychom použili první hashovací funkci uvedenou výše v hashovací mapě řetězců… jakékoli dva řetězce začínající stejným písmenem dostanou stejný index pole.

Tomu se říká kolize.

Jak kolize řešíme?

Jedna z technik řešení kolizí se nazývá řetězení. Protože každý prvek pole je spojový seznam (nebo podobná datová struktura), bude více klíčů, které mají stejnou hodnotu hash, umístěno do stejného spojového seznamu nebo „kbelíku“. Poté je hashovací mapa schopna získat hodnoty tak, že vypočítá hashovací kód pomocí hashovací funkce a prohledá konkrétní propojený seznam, aby zjistila, zda obsahuje hodnotu se stejným klíčem.

Dobrá hashovací funkce musí být napsána tak, aby nedocházelo ke kolizím.

Výhody řetězení:

-Array nemůže přetéct

-Data lze snadno odstranit

Nevýhody řetězení:

-Může dojít ke snížení výkonu, pokud buckety obsahují velmi dlouhé propojené seznamy.

Celkový počet záznamů k počtu bucketů se nazývá load factor. Pokud je faktor zatížení příliš nízký, dochází k plýtvání velkým množstvím místa. Pokud je load factor příliš vysoký, ztrácí se výhoda hašování. Dobrý kompromis pro faktor zatížení je 0,75

.