Vysvetlite, čo je dátová štruktúra hash tabuľka a ako funguje

Hash tabuľa je dátová štruktúra, ktorá uchováva páry kľúč-hodnota a zabezpečuje veľmi rýchly prístup k údajom pomocou kľúča. Funguje pomocou hashovacej funkcie, ktorá premieňa kľúč na index poľa, kde je uložená hodnota.

Princíp fungovania:

1. Pri pridávaní páru kľúč-hodnota prechádza kľúč hashovacou funkciou, ktorá vráti index.
2. Hodnota je uložená na tomto indexe v poli.
3. Pri vyhľadávaní kľúča hashovacia funkcia opäť vypočíta index a hodnota je rýchlo nájdená.

Aby sa predišlo kolíziám (keď rôzne kľúče dávajú ten istý index), používajú sa metódy ako:

• reťazenie (uloženie viacerých prvkov v jednej bunke vo forme zoznamu)
• otvorené adresovanie (hľadanie ďalšej voľnej bunky)

V C# príklad použitia slovníka (Dictionary), ktorý je založený na hash tabuľke:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // value == 5

Hash tabuľky zabezpečujú priemernú zložitosť operácií vkladania, odstraňovania a vyhľadávania okolo O(1).