Какво е хеш таблица?

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

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

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

Решения на колизиите:

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

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

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

Използване в QA:

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