Co je to hash a jak se používá ve slovnících v…

Hash (nebo hash-hodnota) je číselná hodnota pevnej dĺžky, ktorá je vypočítaná na základe obsahu objektu pomocou hashovacej funkcie. Dobrá hashovacia funkcia zabezpečuje deterministickosť (t.j. ten istý objekt vždy dá rovnaký hash) a snaží sa o rovnomerné rozloženie hashov pre rôzne objekty.

V Pythone používajú slovníky (typ dict) hashovanie na efektívne ukladanie a vyhľadávanie párov "kľúč-hodnota". Kľúče v slovníku musia byť hashovateľné, teda musia mať metódu __hash__() a byť nemenné alebo mať implementáciu __eq__() a __hash__(), ktorá zabezpečuje, že objekty rovnakej hodnoty majú rovnaký hash.

Proces práce slovníka s hashmi:

Vkladanie: Pri pridávaní páru (kľúč, hodnota) sa vypočíta hash kľúča. Na základe hash sa určí približné miesto (košík alebo "bucket") na uloženie tohto páru v pamäti. Ak má viacero kľúčov rovnaký hash (kolízia), páry sa ukladajú do tohto košíka, často vo forme prepojeného zoznamu alebo iného mechanizmu riešenia kolízií.
Vyhľadávanie: Pri hľadaní hodnoty podľa kľúča sa vypočíta hash odovzdaného kľúča. Pomocou hash sa rýchlo nájde príslušný košík. Potom v tomto košíku prebieha porovnanie kľúčov (pomocou metódy __eq__()) na nájdenie požadovaného kľúča a získanie s ním spojené hodnoty.

Výhody hashovania:

Efektivita: Priemerné operácie vkladania, odstraňovania a vyhľadávania v slovníku majú konštantnú časovú zložitosť O(1), nezávisle od veľkosti slovníka.
Rýchly prístup: Hash umožňuje rýchlo sa dostať na predpokladané miesto uloženia dát, čím sa obchádza prehľadávanie všetkých prvkov.

Obmedzenia a vlastnosti:

Hashovateľné kľúče: Ako bolo spomenuté, kľúče musia byť hashovateľné. Menné typy, ako zoznamy (list) a množiny (set), nie sú hashovateľné podľa predvoleného nastavenia a nemôžu byť použité ako kľúče v slovníku.
Kolízie: Hoci hashovacie funkcie sa snažia minimalizovať kolízie, môžu sa vyskytnúť, čo môže mierne spomaliť operácie v najhoršom prípade (ovplyvňuje konštantu v O(1)).
Poradie: Do Pythonu 3.7 závisel poradie prvkov v slovníku od poradia vloženia a hashov kľúčov. Od verzie 3.7 slovníky zachovávajú poradie vloženia kľúčov ako vedľajší efekt implementácie, ale nie je to súčasť mechanizmu hashovania.

Príklad hashovateľného a nehashovateľného objektu:

# Hashovateľný objekt (nemenný)
string_key = "hello"
int_key = 123
tuple_key = (1, 2)

print(hash(string_key))
print(hash(int_key))
print(hash(tuple_key))

# Nehashovateľný objekt (meniteľný)
list_key = [1, 2]
# print(hash(list_key)) # Vyvolá TypeError

# Príklad použitia v slovníku
my_dict = {
    string_key: "world",
    int_key: 456,
    tuple_key: "tuple"
}

print(my_dict[string_key])
print(my_dict[int_key])
print(my_dict[tuple_key])

Hash je teda základný mechanizmus, ktorý umožňuje slovníkom v Pythone dosahovať vysokú výkonnosť operácií na základe rýchleho výpočtu číselného zobrazenia kľúča.

Co je to hash a jak se používá ve slovnících v Pythonu?