Aké sú spôsoby riešenia kolízií hash?

1. Metóda reťazcov (Separate Chaining):

   • Každý prvok hash tabuľky (kbel) je ukazovateľ na prepojený zoznam (alebo inú dátovú štruktúru, napríklad strom).
   • Všetky prvky hashované do jedného kbelu sa pridávajú do tohto zoznamu.

   // Príklad: uzol prepojeného zoznamu pre reťazce
   struct Node {
       int key;
       int value;
       Node* next;
   };
   
   // V kbelu sa uchováva ukazovateľ na hlavu zoznamu
   Node* buckets[TABLE_SIZE];
   

2. Metódy otvoreného adresovania (Open Addressing):

   • Všetky prvky sú priamo uložené v poli hash tabuľky.
   • Pri kolízii sa hľadá nasledujúce voľné miesto v poli.
   • Rozlišujú sa podľa spôsobu určenia nasledujúceho miesta:

     • Lineárne sondovanie (Linear Probing): Kontrolujú sa bunky v poradí s pevnou krokom i, i+1, i+2, ... mod TABLE_SIZE.

       // Príklad lineárneho sondovania
       int hash(int key) { return key % TABLE_SIZE; }
       
       int i = hash(key);
       while (table[i] != EMPTY && table[i].key != key) {
           i = (i + 1) % TABLE_SIZE;
       }
       // Teraz table[i] je buď prázdny, alebo obsahuje hľadaný prvok
       

     • Kvadratické sondovanie (Quadratic Probing): Kontrolujú sa bunky s krokom závislým od štvorca pokusu i, i+1², i+2², ... mod TABLE_SIZE.

       // Príklad kvadratického sondovania
       int hash(int key) { return key % TABLE_SIZE; }
       
       int i = hash(key);
       int attempt = 0;
       while (table[i] != EMPTY && table[i].key != key && attempt < TABLE_SIZE) {
           attempt++;
           i = (hash(key) + attempt * attempt) % TABLE_SIZE;
       }
       // Teraz table[i] je buď prázdny, alebo obsahuje hľadaný prvok (alebo je tabuľka plná)
       

     • Dvojité hashovanie (Double Hashing): Používa sa druhá hash funkcia na určenie kroku sondovania i, i + step, i + 2*step, ... mod TABLE_SIZE, kde step sa vypočíta z druhej hash funkcie z kľúča.

       // Príklad dvojitého hashovania
       int hash1(int key) { return key % TABLE_SIZE; }
       int hash2(int key) { return 1 + (key % (TABLE_SIZE - 1)); }
       
       int i = hash1(key);
       int step = hash2(key);
       while (table[i] != EMPTY && table[i].key != key) {
           i = (i + step) % TABLE_SIZE;
       }
       // Teraz table[i] je buď prázdny, alebo obsahuje hľadaný prvok
       

3. Dynamické zmeny veľkosti (Resizing):

   • Pri dosiahnutí určitého koeficientu zaplnenia (load factor) sa vytvorí nová, väčšia hash tabuľka.
   • Všetky prvky zo starej tabuľky sa prehashujú a vložia do novej.

   // Príklad logiky pri resize
   if (current_size / (double)table_size > max_load_factor) {
       // Vytvorenie novej tabuľky dvojnásobnej veľkosti
       // Prehashovanie a vloženie všetkých prvkov zo starej tabuľky
       // Vymazanie starej tabuľky
   }
   

Výber metódy závisí od požiadaviek na výkon, pamäť, zložitosť implementácie a očakávaný koeficient zaplnenia. Metóda reťazcov je zvyčajne jednoduchšia na implementáciu a dobre funguje pri vysokých koeficientoch zaplnenia, ale vyžaduje dodatočnú pamäť na ukazovatele. Metódy otvoreného adresovania môžu efektívnejšie využívať pamäť, ale sú citlivejšie na výber hash funkcie a majú problém s "kompresiou" prvkov. Resize je nevyhnutný na udržanie efektívnosti pri raste počtu prvkov.