Как избежать хэш-столкновений, когда элементы известны

Question

Есть ли вообще избежать хэш-столкновений в хеш-функции, если мы знаем размер ввода перед построением хеш-таблицы? Другими словами, как мы можем сделать вставку наихудшего случая в O (1) раз?

Answer 1

То, о чем вы просите, называется perfect hash function. Для этого существует множество известных алгоритмов (см. this article in Dr. Dobbs' по одному из таких алгоритмов). Большинство из них полагаются на некоторую рандомизированную параметризованную схему, которая имеет нетривиальную вероятность не обнаруживать столкновений. Как только такой параметр найден, у вас есть идеальный хеш. См. this lecture для чтения.