How are elements inserted and how is collision managed when adding new data to the hash table?

Elements in a hash table are inserted according to the following principle:

1. The hash value of the key is computed using a hash function.
2. Based on this value, the index in the array (bucket) where the element should be placed is determined.
3. If there are no elements in this bucket, the new element is simply placed there.

If a collision occurs (i.e., two different keys produce the same index), collision resolution methods are applied:

• Chaining method: a linked list (or another container) of elements is stored in each cell of the array. All elements with the same index are added to this list.

• Open addressing: in case of a collision, the next free cell is searched for according to a certain strategy (linear probing, quadratic probing, double hashing).

Example of chaining method:

struct Node {
    KeyType key;
    ValueType value;
    Node* next;
};

// When inserting:
int index = hash(key) % table_size;
Node* head = table[index];
// Add a new node at the beginning of the list
Node* newNode = new Node{key, value, head};
table[index] = newNode;

Thus, collisions are managed either by storing multiple elements in one cell (chaining), or by searching for an alternative position (open addressing).