Идеальная хеш-функция?
При чтении принципа "вихря" в Википедии я сталкиваюсь - "коллизии неизбежны в хеш-таблице, потому что число возможных ключей превышает число индексов в массиве. Ни один алгоритм хеширования, каким бы умным он ни был, не сможет избежать этих коллизий". Но не делает ли Gperf это точно?
Пожалуйста, просветите.
2 ответа
gperf создает хеш-функцию и хеш-таблицу на основе предварительно определенного списка строк.
Поэтому мне кажется, что gperf создает хеши достаточно долго, чтобы было достаточно возможностей.
Это то, что вы можете сделать, только если вы знаете каждый возможный ключ заранее - это предположение, которое не соответствовало описанию в записи википедии, которое, очевидно, было связано с "непостоянной" хэш-таблицей.
С веб-сайта gperf: "Для заданного списка строк он создает хеш-функцию и хеш-таблицу,..." - что означает, что он должен знать все строки ранее, чтобы подготовить функцию, которая работает без коллизий.
Обычные хеш-функции, которые вы используете в общих языках программирования, способны обрабатывать любые строки как входные данные друг за другом (список не приводится сразу) и, следовательно, могут вызывать коллизии.