2010-06-17 2 views
15

Какие простые способы хэшировать 32-разрядное целое число (например, IP-адрес, например Unix time_t и т. Д.), До 16-битного целого?Hash 32bit int to 16bit int?

E.g. hash_32b_to_16b(0x12345678) возвращение товара не принимается 0xABCD.

Давайте начнем с этого, как ужасным, но функциональным примером решение:

function hash_32b_to_16b(val32b) { 
    return val32b % 0xffff; 
} 

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

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

Простой = хороший. Wacky + obfuscated = забавный.

+1

XOR высокие 2 байта с низкими 2 байтами? 0x1234 XOR 0x5678. Но вы не можете пометить вопрос «криптографией» и попросить что-то вроде этого ... –

+0

@Remus: Почему я не могу пометить его «криптографией»?Разве это не дистиллированный и чрезвычайно простой вопрос, связанный с криптованием? Постскриптум Почему бы не написать свой комментарий в качестве ответа? – dkamins

+0

К моменту Ремуса я согласен, что речь идет не о криптографии. Если я думаю об этом праве, ваш 16-битный хеш будет отображаться в одном из двух 32-битных целых чисел. Мне интересно узнать о конкретной проблеме, которую вы пытаетесь решить, и я надеюсь, что это не имеет никакого отношения к безопасности. –

ответ

2

Это зависит от характера целых чисел. Если они могут содержать некоторые бит-маски или могут различаться степенями двух, то простые XOR будут иметь высокую вероятность столкновений. Вы можете попробовать что-то вроде (i>>16)^((i&0xffff) * p), где p - простое число.

Безопасность-хеши, такие как MD5, все хорошо, но они, очевидно, являются излишним. Все более сложное, чем CRC16, является излишним.

+0

Это интересный момент и, по-видимому, актуальный для хэширования IP-адресов, да? – dkamins

+0

Да. Для значений времени i & 0xffff обычно должно быть достаточно. (надеясь, что нет сна (65536), где угодно :)) – Rotsor

+0

Будет ли фиксированное простое число? Почему это работает? – dkamins

4

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

function hash_32b_to_16b(val32b) { 
    var rightBits = val32b & 0xffff; // Left-most 16 bits 
    var leftBits = val32b & 0xffff0000; // Right-most 16 bits 

    leftBits = leftBits >>> 16; // Shift the left-most 16 bits to a 16-bit value 

    return rightBits^leftBits; // XOR the left-most and right-most bits 
} 

Учитывая параметры проблемы, лучшее решение будет иметь каждый 16-битный хэш соответствует ровно 2^16 32-битных номеров. Это также означало бы, что ИМО хэш последовательно 32-битные номера по-разному. Если я чего-то не упускаю, я считаю, что это решение делает эти две вещи.

Я бы сказал, что безопасность не может быть предметом рассмотрения в этой задаче, так как хеш-значение слишком мало. Я считаю, что решение, которое я дал обеспечивает равномерное распределение 32-битные числа на 16-битные хеши

+0

Почему вы считаете, что это самое лучшее? Я думаю, что он может получить очень много коллизий за полезные и частые номера. – Rotsor

+1

Это не лучшая идея. Причина в том, что IP-адреса часто назначаются как смежные подсети. Это означает, что если IP-адрес A.B.C.D существует в сети, то A. (B^1) .C.D и A.B.C. (D^1) будут несколько более вероятно существовать и получить тот же хеш. Очевидно, что любой хеш будет иметь множество столкновений. Но ваша схема будет иметь больше коллизий, чем вы ожидали бы от хэширования 32-битных целых чисел, выбранных одинаково. Вы получите лучшие результаты, взбивая бит немного больше. – sigfpe

+1

критерии, которые вы использовали для оценки качества хеш-функции, выполняйте даже для более простой: hash = val & 0xffff. Однако эти функции имеют разную вероятность столкновений по реальным данным. – Rotsor

0

что-то простое, как это ....

function hash_32b_to_16b(val32b) {  
    var h = hmac(secretKey, sha512); 
    var v = val32b; 
    for(var i = 0; i < 4096; ++i) 
     v = h(v); 
    return v % 0xffff; 
} 
+0

Почему 4096 раз? – dkamins

+2

Чтобы замедлить его. Это общепринятая техника для хеширования паролей, чтобы сделать порядок на порядок сложнее создать таблицы радуги или паролей грубой силы. – yfeldblum

2

Я бы сказал, просто применить стандартный хэш как sha1 или md5, а затем захватить последние 16 бит этого.

+0

Возможно, возникли проблемы с короткими входными потоками (например, 4 байта) для sha1 или md5? – dkamins

+0

sh1 и md5 обычно недоступны в средах JavaScript. Существуют ли несколько менее безопасные, но значительно упрощенные версии, выражаемые в нескольких строках JS? – dkamins

2

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

Если числа, которые вы собираетесь использовать в хеше, не будут иметь такого распределения, тогда может оказаться полезным дополнительный шаг xor-ing в верхних 16 битах.

Конечно, это предложение состоит в том, что вы намерены использовать хэш только для какой-либо схемы поиска/хранения и не ищете криптосвязанные свойства неопределенности и необратимости (которые xor предложения не действительно покупают вас).

Смежные вопросы