Jaké metody existují pro snížení pravděpodobnosti kolizí při používání hash tabulek?

Pro snížení pravděpodobnosti kolizí v hash tabulkách se používají následující metody:

• Výběr dobré hashovací funkce — funkce by měla rovnoměrně rozdělovat klíče v tabulce.
• Použití metod řešení kolizí:
  • Otevřená adresace (lineární sondování, kvadratické sondování, dvojité hashování) — hledání další volné buňky.
  • Řetězení — ukládání všech prvků se stejným hashem do spojového seznamu nebo jiného kontejneru.
• Zvětšení velikosti tabulky — při dosažení určitého zatížení se provádí rehash s větší velikostí.

Příklad řetězení v C++:

std::unordered_map<int, std::string> map;
map[1] = "one";
map[2] = "two";
// Interně se používá řetězení pro kolize