До сих пор я знал только два принципиально различных способа разрешения коллизий, оба описаны в кормене. Разумеется это разрешающие цепочки и двойное хеширование.

Читал немного про perfect hashing, но то что следует ниже придумал час назад.

Итак, мы хотим положить в хеш таблицу n заранее известных объектов. А потом спрашивать её, содержит ли она такой объект. Предлагается завести массив размера n значениями которого могут быть объекты или null. И второй массив, где i-тый элемент равен true, если в этой ячейке есть коллизия, либо false в противном случае. Без особого матана, я численно прикинул, что порядка 1 / exp(1.0) (1/2.71828…) объектов должны с кем-то образовать коллизию. Для этой части объектов заведем подобную хеш-таблицу рекурсивно. Когда у нас осталось n < K объектов, для построения хеш-таблицы, мы просто применяем линейный поиск по списку. Ну или бинарный поиск, значение K фиксированное, и может быть выбрано оптимально исходя из практики тестирования.

Понятно, что если в первом массиве мы нашли null по хешу, то такого объекта нет, если там какой-то объект есть, то смотрим совпали ли мы с ним, если нет, продолжаем искать в хеш-таблице следующего уровня, которая в 1 / exp(1.0) раз меньше исходной.

Хеш-функции на разных уровнях могут отличаться.

Худшая оценка сложности Ln(n), где Ln – это натуральный логарифм, логарифм по основанию числа e = exp(1.0) ~ 2.71828…, число эйлера. Средняя оценка сложности 1 / (1 – 1 / e) = 1.5819
Прерасход памяти, составит те же 1.5819 (указателей), если мы считаем что в первом массиве хранятся указатели, плюс битовый массив для второго массива, но это проценты. В обычной хеш-таблице с разрешающими цепочками мы используем по одному указателю для самой таблицы, плюс по одному указателю для каждого находящегося в ней объекта (для поля next) т.е в общей сложности примерно 2 указателя на объект.

Вопрос: известен ли вам этот велосипед или ему подобный?

Знаете ли вы принципиально иные способы разрешения коллизий, чем два предложенные в кормене?