How does a hash table work?

A hash table (or associative array) stores pairs of "key-value". The principle of operation is based on using a hash function, which transforms the key into a numerical index (hash), pointing to the storage location of the value in the array (bucket).

Steps:

Hash calculation: For a given key, the hash is calculated.

<?php
$key = "example";
$hash = crc32($key); // Example of a simple hash function

Index determination: The hash is converted into an array index, usually using the modulo operation with the array size.
```
<?php
$arraySize = 10;
$index = $hash % $arraySize;
```
Access to the bucket: Access is made to the corresponding bucket in the array using the calculated index.
Collision resolution: Since different keys can have the same hash (collision), the bucket may contain multiple "key-value" pairs. Different methods are used to resolve collisions:
- Chaining method: Each bucket stores a list (e.g., linked list) of "key-value" pairs with matching hashes.
- Open addressing method: In case of collision, a re-search for a free cell in the array is performed according to a certain rule (linear, quadratic probing, double hashing).

Operations:

Insertion: The hash of the key is calculated, the index is determined, and the "key-value" pair is placed in the corresponding bucket. In case of collision, it is added to the list (chains) or a free space is searched (open addressing).
Search: The hash of the key is calculated, the index is determined. The value is searched in the corresponding bucket by key. In chaining method, list elements are iterated; in open addressing, a sequential search is performed.
Deletion: The hash of the key is calculated, the index is determined. The pair is found and deleted in the corresponding bucket by key.

Advantages:

Fast access to elements (average O(1)).
Efficient use of memory.

Disadvantages:

Performance may degrade with a large number of collisions.
The size of the table may require adjustment (rehashing) to maintain efficiency.