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

Хеш таблицата се състои от:

1. Масив (или списък): Основната структура от данни, в която се съхраняват елементите. Понякога се нарича "коши" (buckets) или "слотове".
2. Хеш функция: Функция, която приема ключ като вход и връща индекс (цяло число) в масива. Добрата хеш функция осигурява равномерно разпределение на ключовете по масива, минимизирайки колизиите.
3. Механизъм за обработка на колизии: Метод за решаване на ситуацията, когато хеш функцията генерира същия индекс за различни ключове. Два основни метода:
   • Разделяне на вериги (Separate Chaining): Всеки елемент от масива съхранява указател към списък (свързан списък, дърво B и др.) от елементи, които са хеширани в този индекс.
   • Отворена адресация (Open Addressing): При колизия се търси друго свободно място в масива за поставяне на елемента. Стратегии за търсене:
     • Линейно пробиране (Linear Probing)
     • Квадратично пробиране (Quadratic Probing)
     • Двоен хешинг (Double Hashing)
4. Операции: Реализация на основните операции: вмъкване (insert), търсене (search), изтриване (delete). Тези операции използват хеш функцията за определяне на местоположението на елементите в масива и механизма за обработка на колизиите при необходимост.