Хеш-таблица — структура данных для ассоциативного массива (key→value) с ожидаемой амортизированной O(1) вставкой/поиском/удалением.

• Ключи проходят через хеш-функцию → индекс корзины.

• Коллизии: цепочки (linked list/дерево) или открытая адресация (linear/probing).

• Важны: равномерная хеш-функция, фактор загрузки (load factor) и стратегия ресайза.

• Память > массива, но быстрый доступ; не сохраняет порядок.

• Примеры: hash map/dict в большинстве языков.

Пример коллизий:

• Chaining: корзина хранит список/дерево; при высокой коллизии в Java HashMap — дерево O(log n).

• Open addressing: приём linear probing — поиск следующей свободной ячейки по шагу 1.