#hash
Вопрос:
Я ищу одностороннее хеширование для объединения двух 32-битных целых чисел в одно 32-битное целое число. Не уверен, что это возможно сделать без столкновения.
Правка: Я думаю, что мои целые числа, как правило, невелики. Один из них редко занимает более 14 бит, а другой редко занимает более 20 бит.
Правка 2: Спасибо за помощь в комментариях. Я думаю, что в таких случаях, как если бы комбинация двух целых чисел занимала более 32 бит, я могу сделать что-то по-другому, чтобы не хэшировать ее. С учетом этого, как я должен хэшировать свои целые числа?
Спасибо!
Комментарии:
1. Математически невозможно избежать столкновений по принципу «ячейки «. Существует 2^32 32-разрядных целых числа и 2^64 пары.
2. Или подумайте об этом так: рассмотрим пары формы
(0,x), в которых первое число равно 0. Таких пар уже столько же, сколько доступных хэш-значений, поэтому они будут использовать все пространство хэш-значений. Затем хэш пары(1,0)должен столкнуться с одним из них.3. Можете ли вы рассказать нам больше о своей настройке? Если у вас есть фиксированная коллекция пар, которая не «слишком велика», вы можете найти идеальную хэш-функцию специально для этих пар. Но если вы пытаетесь хэшировать «общие пары», то, как говорит Нейт Элдридж, это невозможно сделать.
4. 14 20-это все еще больше, чем 32, если вы можете ограничить это еще немного и сделать это гарантией, тогда это то, с чем мы можем работать