Какъв е принципът на работа на хеш таблицата?

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

Стъпки:

Изчисляване на хеша: За даден ключ се изчислява хеш.

<?php
$key = "example";
$hash = crc32($key); // Пример за проста хеш функция

Определяне на индекса: Хешът се преобразува в индекс на масива, обикновено чрез операция модул на размера на масива.
```
<?php
$arraySize = 10;
$index = $hash % $arraySize;
```
Достъп до кошницата: Достъп до съответната кошница в масива чрез изчисления индекс.
Решаване на колизии: Тъй като различни ключове могат да имат един и същ хеш (колизия), кошницата може да съдържа няколко двойки "ключ-стойност". За решаване на колизии се използват различни методи:
- Метод на веригата (Separate Chaining): Във всяка кошница се съхранява списък (например свързан списък) от двойки "ключ-стойност", чиито хешове съвпадат.
- Метод на отворена адресация (Open Addressing): При колизия се извършва повторно търсене на свободна клетка в масива по определено правило (линейно, квадратично, двойно хеширане).

Операции:

Вмъкване: Изчислява се хешът на ключа, определя се индексът, и двойката "ключ-стойност" се поставя в съответната кошница. При колизия се добавя към списъка (веригата) или се търси свободно място.
Търсене: Изчислява се хешът на ключа, определя се индексът. В съответната кошница се търси стойността по ключа. При метода на веригата се обхождат елементите на списъка; при отворена адресация се извършва последователно търсене.
Изтриване: Изчислява се хешът на ключа, определя се индекс. В съответната кошница се намира и изтрива двойката по ключ.

Предимства:

Бърз достъп до елементите (средно O(1)).
Ефективно използване на паметта.

Недостатъци:

Производителността може да се влоши при голям брой колизии.
Размерът на таблицата може да изисква настройка (rehashing) за поддържане на ефективността.