Идеальная хеш-функция?

Question

Читая принцип pigeonhole в Википедии, я сталкиваюсь - «коллизии неизбежны в хеш-таблице, поскольку число возможных ключей превышает число индексов в массиве. Алгоритм хеширования не имеет значения, неважно как умно, можно избежать этих столкновений ». Но разве gperf не делает это точно?

Пожалуйста, просветите.

Answer 1

gperf создает хеш-функцию и хеш-таблицу на основе предопределенного списка строк.

Поэтому мне кажется, что gperf создает хеши достаточно долго, чтобывозможностей достаточно.
Это то, что вы можете сделать, только если вы знаете каждый возможный ключ заранее - это предположение, которое не соответствовало описанию в записи википедии, которое, очевидно, было связано с «непостоянным»хэш-таблицы.

Answer 2

С веб-сайта gperf: «Для заданного списка строк он создает хеш-функцию и хеш-таблицу ...» - это означает, что он должен знать все строки ранее, чтобы подготовить функцию, которая работает без столкновения.

Обычные хеш-функции, которые вы используете в общих языках программирования, способны обрабатывать любые строки как входные данные одну за другой (список не приводится сразу) и, следовательно, могут вызывать коллизии.