Коллизияи хеш ва чӣ гуна усулҳо барои ҳалли он вуҷуд доранд?

Ҳаш муноқашаси, вақте ки икки турли кириш қиймати бир хил ҳаш функцияси қийматини беради. Бу қачон бўлса ҳам, мумкин, чунки мумкин бўлган киришлар тўплами одатда мумкин бўлган ҳаш қийматлар тўпламидан катта.

Муноқашаларни ҳал қилиш усуллари:

1. Очиқ манзиллаш — муноқаша бўлганда, белгиланган тартибда кейинги бўш ҳуҷра қидирилади (линейли, квадратик, иккилик ҳашлаш).
2. Занҷирлаш (chaining) — ҳар бир ҳаш таблицасининг ҳар бир ҳуҷрасида, бир хил ҳаш қийматга эга бўлган барча элементлар учун боғланган рўйхат сақланади.
3. Янги ҳашлаш — муноқаша бўлганда, бошқа ҳаш функцияси қўлланади.

Pythonда занҷирлаш мисоли:

ҳаш_жадвали = [[] for _ in range(10)]

def қўшиш(калит, қиймат):
    индекс = hash(калит) % 10
    ҳаш_жадвали[индекс].append((калит, қиймат))

қўшиш('олма', 1)
қўшиш('пам', 2)  # мумкин муноқаша