What is a hash table?

A hash table is a data structure that implements an associative array (dictionary). It stores pairs of "key-value" where keys are unique.

Main principles:

• Hash function: Converts a key into a number (hash code or index). This index points to the storage location of the value in the array (bucket).
• Array (buckets): The actual storage for "key-value" pairs.
• Collisions: Situations where different keys generate the same hash code.

Collision resolution:

• Chaining method (Separate chaining): Each bucket contains a list (or another data structure) of elements with the same hash code.
• Open addressing method: When a collision occurs, searching for a free bucket is performed using various strategies (linear probing, quadratic probing, double hashing).

Characteristics:

• Fast access: Ideally O(1) for insert, search, and delete operations.
• Dependence on hash function: The quality of the hash function and collision resolution strategy greatly affect performance.
• Memory usage: Requires additional memory for the array of buckets.

Usage in QA:

• Storing test data (key - parameter name, value - expected or actual value).
• Checking the uniqueness of elements (e.g., user IDs).
• Implementing caches.