Šta je kolizija heširanja i koja postoje rešenja za nju?

Колизија хеша се јавља када два различита улазна вредности дају исту вредност хеш функције. Ово је неизбежно, јер је скуп могућих улаза обично већи од скупа могућих хеш вредности.

Методе за решавање колизија:

1. Отворена адресација — у случају колизије, тражи се следећа слободна ћелија по одређеној секвенци (линеарно, квадратично, дупло хеширање).
2. Везивање (chaining) — у свакој ћелији хеш табеле се чува повезана листа свих елемената са истом хеш вредношћу.
3. Поновно хеширање — у случају колизије, примењује се друга хеш функција.

Пример са везивањем у Python-у:

хеш_табела = [[] for _ in range(10)]

def уметни(кључ, вредност):
    индекс = hash(кључ) % 10
    хеш_табела[индекс].append((кључ, вредност))

уметни('јабука', 1)
уметни('пам', 2)  # могућа колизија