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

на собесе у меня спросили именно про коллизии, я поплыл если честно, теория одно а объяснить с ходу совсем другое

1. Берёшь ключ, например строку "user123".
2. Прогоняешь её через хэш-функцию, на выходе получается число, обычно большое.
3. Это число сжимают по размеру массива через остаток от деления, получается индекс ячейки.
4. В эту ячейку кладёшь пару ключ-значение.
5. При поиске повторяешь те же шаги: хэшируешь ключ, находишь индекс, сразу попадаешь в нужную ячейку, без перебора всего массива.
6. Если в одну ячейку попали два разных ключа, это коллизия, обычная история при плохом хэше или маленькой таблице.
7. Спасают либо связный список внутри ячейки, либо поиск следующей свободной ячейки рядом.
8. Отсюда и скорость: в среднем добавление и поиск это почти мгновенная операция, независимо от размера таблицы, пока коллизий немного.

Идея Ключ превращается в число (хэш), число указывает на ячейку массива, где хранится значение. Коллизии Если два ключа попали в одну ячейку, используют список или другую ячейку рядом.