Koje metode postoje za smanjenje verovatnoće kolizija pri korišćenju hash tabela?

Za smanjenje verovatnoće kolizija u hash tabelama koriste se sledeće metode:

• Izbor dobre hash funkcije — funkcija treba ravnomerno da raspoređuje ključeve po tabeli.
• Korišćenje metoda za rešavanje kolizija:
  • Otvorena adresacija (linearno sondiranje, kvadratno sondiranje, dvostruko hashiranje) — traženje sledeće slobodne ćelije.
  • Lančano povezivanje — čuvanje svih elemenata sa istim hash-om u povezanoj listi ili drugom kontejneru.
• Povećanje veličine tabele — pri dostizanju određenog nivoa opterećenja, vrši se rehash sa većom veličinom.

Primer lančanog povezivanja u C++:

std::unordered_map<int, std::string> map;
map[1] = "one";
map[2] = "two";
// Interno se koristi lančano povezivanje za kolizije