Nechápeš, pročež píšeš nesmysly. Představ si pole čísel v náhodném pořadí. Nalezení i-tého největšího prvku je lineární. A stejně lineární je to i v hashmapě, když jsou hodnotami čísla (na klíči nesejde). Nalezení mediánu je jen speciální případ nalezení i-tého největšího prvku.
Nesmysly tu píše spousta lidí, ale já ani MarSik to nejsme. i-tý největší prvek pole je úplně něco jiného, než i-tý prvek pole. i-tý největší prvek se vztahuje k hodnotám těch prvků, a mimo jiné předpokládá, že ty prvky umím porovnat a tedy seřadit. i-tý prvek se vztahuje k pořadí těch prvků v poli, v programátorském zápisu je to prostě
pole.
V hashmapě to „stejně lineární“ není – a bylo by dobré, kdybyste si konečně zjistil, jak hashmapa funguje. Začněme tím, že v hashmapě jsou dvě struktury, ve kterých se prvek hledá. První struktura je hashtabulka, klíčová struktura pro hashmapu – je to pole, ve kterém index pole přímo odpovídá hashi klíče. Mám klíč, z něj vypočítám hash, ten hash převedu do rozsahu velikosti pole (např. hash modulo velikost pole), a tahle hodnota se použije přímo jako index té hashtabulky. Vyhledávání v té tabulce tedy není v lineárním čase, ale v konstantním – je to prostě přístup do pole podle indexu. No a protože může dojít ke kolizi hashů, tj. víc klíčů má stejný hash a mělo by být umístěných ve jedné položce té hashtabulky, musím mít možnost uložit na tu pozici ne jeden klíč, ale jejich množinu. Nejjednodušší je udělat tam spojový seznam, v něm se pak konkrétní hodnota opravdu hledá v lineárním čase, ale pokud klíče umím setřídit, můžu tam použít i jinou strukturu, ve které půjde rychleji hledat – třeba seřazený seznam nebo binární vyhledávací strom.
Představte si to třeba pro hashtabulku o velikosti čtyř prvků. Prázdná vypadá takhle:
hashtable[0] = ();
hashtable[1] = ();
hashtable[2] = ();
hashtable[3] = ();
Budete tam chtít vložit klíč 'a', vypočítáte jeho hash, třeba 32745, a ten převedete do rozsahu hashtabulky, třeba modulo 4, takže vám vyjde index do hashovací tabulky 1. Takže klíč uložíte:
hashtable[0] = ();
hashtable[1] = ('a');
hashtable[2] = ();
hashtable[3] = ();
Pak budete chtít vložit klíč 'b', hash 126, index do hashovací tabulky 2:
hashtable[0] = ();
hashtable[1] = ('a');
hashtable[2] = ('b');
hashtable[3] = ();
Klíč 'c', hash 8293121, index do hashovací tabulky 1:
hashtable[0] = ();
hashtable[1] = ('a', 'c');
hashtable[2] = ('b');
hashtable[3] = ();
Vidíte, že tam došlo ke kolizi hashů (respektive až těch indexů v hashtabulce), takže pro hash 1 mám uložené dva různé klíče.
Když teď budu chtít v mapě najít klíč 'd', určím jeho hash 172340, index je 0, takže si v konstantním čase v hashtabulce najdu řádek s indexem 0:
hashtable[0] = (); //nalezený řádek v tabulce
hashtable[1] = ('a', 'c');
hashtable[2] = ('b');
hashtable[3] = ();
Vidím, že seznam klíčů je prázdný, tedy klíč 'd' v mapě není. Kdyby mi vyšel index 1, musím klíč hledat v té množině
('a', 'c'), a teprve pokud by tohle byl nesetříděný seznam, bude mít toto hledání lineární složitost. Tohle už je ale implementační detail, který může být v různých implementacích řešený různě. Podstatný pro hashovací tabulku je ten „trik“ že hash je přímo indexem pole a tudíž jeho vyhledání má konstantní časovou složitost.
66 Odpovědí
10755 Zhlédnutí