Как устранить коллизии?
Как правило, хэши такого типа используются для сокращения пространства прямого поиска, то есть взяв, скажем, восьмибитный хэш (256 значений) можно уже искать не по всему списку значений, а по одному из 256 подсписков, содержащих только значения с одинаковым хэшем.
То есть каждая ячейка таблицы HashTable должна содержать вектор значений с одинаковым хэшем. Сначала вычисляется хэш от искомой строки, затем идёт перебор соответствующего вектора и прямое сравнение каждого его элемента с искомой строкой.
Первое. Заводи массив, в простейшем случае (таблица ограниченного размера) — как минимум вдвое больше, чем желаемая ёмкость. В каждом гнезде или пара (ключ, значение), или «ничего». То ли какое-то спец.значение ключа отведи на «ничего», то ли храни указатели на элементы (не забудь наладить управление памятью), то ли сделай два параллельных массива, один Entry[], второй bool[] (можно добавить bool в Entry, так лучше с прогерской точки зрения, но перерасход памяти).
Второе. Вычисляем хэш, берём остаток от деления на n, заглядываем в таблицу. Если там что-то есть, но у этого «чего-то» другой ключ, перескакиваем на 1 вперёд. Если снова неправильный ключ — то ещё на два, если снова — то ещё на три… Надеюсь, поймёшь, как делать цикл…
Третье. Зачем тебе map, если задача — сделать свою хэш-таблицу, а не пользоваться чужим самобалансирующимся деревом.
Такая таблица может только расширяться, удаление если и можно наладить, то тяжело. Википедия рекомендует второе спец.значение (кроме «ничего») — «тут когда-то что-то было». При поиске «тут когда-то что-то было» считаются занятыми, а при добавлении — свободными. Дурость в общем — удаление не упрощает поиск.