Я сразу попробую ответить на главный вопрос.
написать хэш-таблицу без коллизий
Написать такую таблицу можно если мы заранее знаем весь набор данных (в случае автора это
множество ключей (K). Здесь для простоты предполагаем что
ключи - это целые числа int32 (DWORD).
Алгоритм примерно такой:
1) Берем размер хеш-таблицы в n = size(K). Метод открытой адресации.
2) Берем любую хеш-функцию (по области определения больше чем n
SHA1, MD5, xxhash, mur-mur-hash)
3) Начинаем наполнять таблицу.
4) Как только детектирована коллизия - удаляем старую таблицу и создаем новую
с размером например 120% от исходного n.
5) Повторяем алгортм до тех пор пока не будут расставлены все ключи.
Profit.
Если мы
не знаем наши данные изначально (у нас их нет и мы не знаем количество и тип данных)
то мы
не можем гарантировать отсустствие коллизий хотя-бы потому что у нас
нету такой хеш функции которая бы
гарантировала отсутствие коллизий на вариативном
типе данных.
Изучать хеширование на
базе целых чисел - вобщем-то не интересно. Более общий случай - это
строки (String) и я-бы делал эксперименты со строками и с реальными данными (мобильные
телефоны емейлы налоговые номера и прочее). Целые числа - это .... слишком синтетические
тесты и их результаты потом никуда натянуть нельзя.
UPD: Алгоритм в таком виде не работает. По крайней мере от коллизий мы не избавились.
Не голосуйте здесь пока.
