How does a hash table work?

A hash table is a data structure that implements an associative array.

Working principle:

Hashing. For each key, a hash code is computed using a hash function. The hash code is an integer.
Indexing. The hash code is used to determine an index in the array (or vector) of the internal hash table structure. Usually, the index is calculated as hash_code % array_size, where array_size is the size of the array.
Storing. The value associated with the key is stored at the found index in the array.

Problems and their solutions:

Collisions. Different keys can produce the same hash code, and consequently, the same index in the array. This is called a collision.
- Collision resolution methods:
  - Separate Chaining: Each cell of the array stores a list (list, vector, etc.) of key-value pairs. When a collision occurs, the new pair is added to this list. During search by index, the list is traversed to find the desired key.
  - Open Addressing: When a collision occurs, another free cell in the array is searched according to a certain rule (probing).
    - Linear Probing: Cells index + 1, index + 2, etc., are checked sequentially modulo the array size.
    - Quadratic Probing: Cells index + 1^2, index + 2^2, etc., are checked modulo the array size.
    - Double Hashing: A second hash function is used to determine the probing step.

Advantages:

On average, insertion, deletion, and search operations are performed with a complexity of O(1).

Disadvantages:

In the worst case (e.g., with many collisions or a poor hash function), the operation complexity can reach O(n), where n is the number of elements.
Requires additional memory (e.g., for lists in separate chaining or for probing in open addressing).

Example of usage in C++ (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Creating a hash table (unordered_map)
    std::unordered_map<std::string, int> ages;

    // Inserting elements
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;

    // Accessing a value by key
    std::cout << "Alice's age: " << ages["Alice"] << std::endl;

    // Searching for an element
    if (ages.count("Bob")) {
        std::cout << "Bob is in the map." << std::endl;
    }

    // Removing an element
    ages.erase("Charlie");

    return 0;
}