Что такое лучшая функция хэширования для хранения больших случайных чисел?

Question

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

И вообще, я хочу знать, как решить, что хеш-функция хороша для любой конкретной проблемы?

EDIT: Я думаю, что люди, смущенные, используют термин «случайный». Здесь со случайным, я имею в виду, что у меня нет определенного диапазона чисел, из которого мне нужно выбрать [любое 32-битное целое число], но у меня есть общее число, которое будет указано для хранения в структуре данных, например, около 5000 номеров , Итак, предложите мне наилучшую хэш-функцию для этого сценария и почему вы делаете это лучше?

Answer 1

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

unsigned hash_number(long long x) 
{ 
    return (unsigned) x; 
} 

Answer 2

Ваш вопрос для меня не имеет смысла. Использование алгоритма хэширования для хранения некоторых случайных чисел является излишним. Если в этом есть что-то большее, выбор структуры данных будет зависеть от того, что это больше (что вы не говорите).

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

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

Итак, если вам нужно было удерживать 100 таких чисел, вы можете использовать хеш-функцию, которая смотрелась только на последние 12 бит. Это дает 2^12 = 4096 возможных хешей, поэтому столкновения будут происходить только 100/2048 времени, менее 5%. С другой стороны, вы используете в 20 раз больше памяти, чем должны. (Эта функция совпадает с тем, что принимает модуль числа до основания 2^12 и аналогична предложению Эппа.)

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

С другой стороны, реализация стека или кругового буфера чрезвычайно проста, очень эффективна и имеет вполне предсказуемое поведение.

Уверены ли вы, что вы не делаете это более сложным, чем это должно быть?

Answer 3

Даже если ваши номера ввода абсолютно случайны, использование h (x) = x может по-прежнему создавать проблемы с производительностью. Образуйте, что ваши номера случайным образом выбираются из 0, 2, 4, ..., 2k, хотя и случайны, ни один из них не будет сопоставлен с первым ведром хеш-таблицы (ведро 0), предполагая мощность двух размеров ковша. Таким образом, действительно имеет значение информационная энтропия входных чисел.

Отличный выбор в вашем случае - целая хеш-функция Томаса Ванга, которая обратима и поддерживает хороший лавинный эффект (http://en.wikipedia.org/wiki/Avalanche_effect). Существует статья, описывающая хэш-функцию Томаса Ванга и ее обратную: http://naml.us/blog/2012/03.