Какая хеш-функция должна хешировать упорядоченный список чисел?

Question

Рассмотрим тип, который представляет собой карту ключей int со значениями int.Ключи упорядочены меньше чем, и карту можно рассматривать как плоский список {key1, val1, key2, val2 и т. Д.}

Я создаю список этих карт и хочу иметь возможность идентифицироватьидентичные карты менее чем за O (N ^ 2) времени.Я намерен хешировать каждую карту один раз, чтобы добиться этого.

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

Есть идеи?Спасибо.

Answer 1

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

Что касается хэш-функции, поскольку ваша проблема не связана с безопасностью, вы можете выбрать любую функцию, какую пожелаете.Криптографические хеш-функции обеспечивают чрезвычайно хорошее «смешивание», а некоторые очень быстры (конкурируют с хорошо известными некриптографическими хеш-функциями, такими как CRC32).Например, MD4 .Но есть вероятность, что ваш язык программирования (вы не говорите, какой вы используете) уже обеспечивает реализацию MD5 , которая все еще довольно прилично быстра.