Čo je hash a ako sa používa v slovníkoch v Pythone…

Hash (alebo 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ť imuttabilné alebo mať implementáciu __eq__() a __hash__(), ktorá zabezpečuje, že rovnaké objekty 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ízie), páry sa ukladajú do tohto košíka, často vo forme prepojenej listy alebo iného mechanizmu na riešenie kolízií.
Vyhľadávanie: Pri hľadaní hodnoty podľa kľúča sa vypočíta hash daného kľúča. Pomocou hash sa rýchlo nájde príslušná košík. Potom vnútri tejto košíka 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 sa vykonávajú s konštantnou časovou zložitosťou 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é. Meniace sa 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 poradie prvkov v slovníku záviselo 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 to nie je 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))

# Nhashovateľný objekt (meniteľný)
list_key = [1, 2]
# print(hash(list_key)) # Toto spôsobí TypeError

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

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

Takže hash je základný mechanizmus, ktorý umožňuje slovníkom v Pythone dosahovať vysokú výkonnosť operácií, založenú na rýchlom výpočte číselného zobrazenia kľúča.

Čo je hash a ako sa používa v slovníkoch v Pythone?