🤔 В чем принцип работы HashTable?

Хеш-таблица – это структура данных, которая хранит пары "ключ → значение" и использует хеш-функцию для быстрого поиска, добавления и удаления данных.

🚩Основная идея

Ключ обрабатывается хеш-функцией → превращается в числовой индекс.
По индексу данные хранятся в массиве.
Быстрое обращение к данным по ключу: O(1) в среднем.

🚩Как это работает?

🟠Хеширование ключа
Представим, что у нас есть ключ "apple", и мы храним для него значение 100.
Применяем хеш-функцию к "apple"

$hash = hash('md5', 'apple'); 
echo $hash; // 1f3870be274f6c49b3e31a0c6728957f

Это хеш – длинное число, но нам нужно индексировать данные, поэтому мы берем его остаток от деления на размер массива (mod):

$index = hexdec(substr($hash, 0, 8)) % 10; 
echo $index; // Например, 3

🟠Поиск элемента
Когда мы ищем apple, алгоритм:
Применяет ту же хеш-функцию, получает индекс 3
Ищет значение в ячейке 3
Таким образом, поиск данных по ключу происходит мгновенно – O(1).
Коллизия – это когда разные ключи дают один и тот же индекс.
Пример: "apple" и "banana" могут попасть в одну ячейку!
Решения:
Метод цепочек – внутри каждой ячейки храним список значений (например, массив или связанный список).
Открытая адресация – если ячейка занята, ищем следующую свободную.

🚩Хеш-таблица в PHP

В PHP массивы (array) работают как хеш-таблицы!

$hashTable = [];
$hashTable['apple'] = 100;
$hashTable['banana'] = 200;

echo $hashTable['apple']; // 100

Ставь 👍 и забирай 📚 Базу знаний