От какво се състои хеш таблицата?

Таблица за хеширане се състои от масив с фиксиран размер (кофа или слот) и хеш функция.

• Масив (Кофи/Слотове): Представлява последователност от клетки, в които се съхраняват двойки "ключ-стойност". Размерът на масива определя броя на възможните места за съхранение на елементи.

• Хеш функция: Преобразува ключа в цяло число (хеш код), което се използва за определяне на индекса на клетката в масива (кофа), където ще се съхранява или от където ще се извлича съответната стойност.

Освен това, може да присъства:

• Стратегия за разрешаване на колизии: Механизъм за обработка на ситуации, когато различни ключове генерират един и същ хеш код и сочат към една и съща клетка на масива. Често срещани стратегии:
  • Веригиране (Separate Chaining): Всяка клетка на масива съхранява указател към свързан списък (или друга структура от данни), който съдържа всички двойки "ключ-стойност", чиито хеш кодове сочат към тази клетка.
  • Отворено адресиране: При колизия се търси свободна клетка в масива според определено правило (например линейно или квадратично пробиране).