Z čoho sa skladá hash tabuľka?

Hash tabuľka pozostáva z poľa pevnej veľkosti (vedro alebo slot) a hash funkcie.

• Pole (Vedrá/Sloty): Predstavuje sled buniek, v ktorých sú uložené páry "kľúč-hodnota". Veľkosť poľa určuje počet možných miest na uloženie prvkov.

• Hash funkcia: Premení kľúč na celé číslo (hash kód), ktoré sa používa na určenie indexu bunky v poli (vedro), kde bude hodnota uložená alebo odkiaľ bude extrahovaná.

Okrem toho môže byť prítomná:

• Stratégia riešenia kolízií: Mechanizmus na spracovanie situácií, keď rôzne kľúče generujú rovnaký hash kód a ukazujú na rovnakú bunku poľa. Časté stratégie:
  • Reťazenie (Separate Chaining): Každá bunka poľa uchováva ukazovateľ na spojený zoznam (alebo inú dátovú štruktúru), ktorý obsahuje všetky páry "kľúč-hodnota", ktorých hash kódy ukazujú na túto bunku.
  • Otvárané adresovanie: Pri kolízii sa hľadá voľná bunka v poli podľa určitého pravidla (napríklad lineárne alebo kvadratické sondovanie).