Что такое хеш-таблица?

Хеш-таблица — это структура данных, которая реализует ассоциативный массив (словарь). Она хранит пары "ключ-значение", где ключи уникальны.

Основные принципы:

• Хеш-функция: Преобразует ключ в число (хеш-код или индекс). Этот индекс указывает на место хранения значения в массиве (корзине).
• Массив (корзины): Фактическое хранилище пар "ключ-значение".
• Коллизии: Ситуация, когда разные ключи генерируют один и тот же хеш-код.

Решение коллизий:

• Метод цепочек (Separate chaining): В каждой корзине хранится список (или другая структура данных) элементов, имеющих одинаковый хеш-код.
• Метод открытой адресации (Open addressing): При коллизии поиск свободной корзины производится с использованием различных стратегий (линейное зондирование, квадратичное зондирование, двойное хеширование).

Характеристики:

• Быстрый доступ: В идеальном случае O(1) для операций вставки, поиска и удаления.
• Зависимость от хеш-функции: Качество хеш-функции и стратегия разрешения коллизий сильно влияют на производительность.
• Использование памяти: Требует дополнительной памяти для массива корзин.

Использование в QA:

• Хранение тестовых данных (ключ - имя параметра, значение - ожидаемое или фактическое значение).
• Проверка уникальности элементов (например, ID пользователей).
• Реализация кешей.