Hash 32bit int до 16 бит int?
Каковы некоторые простые способы хэшировать 32-разрядное целое число (например, IP-адрес, например Unix time_t и т.д.), до 16-разрядного целого?
например. hash_32b_to_16b(0x12345678)
может вернуться 0xABCD
.
Начнем с этого как ужасное, но функциональное примерное решение:
function hash_32b_to_16b(val32b) {
return val32b % 0xffff;
}
Вопрос конкретно о JavaScript, но не стесняйтесь добавлять любые нейтрально-нейтральные решения, желательно без использования библиотечных функций.
Контекст для этого вопроса заключается в создании уникальных идентификаторов (например, 64-разрядный идентификатор может состоять из нескольких 16-разрядных хэшей различных 32-битных значений). Рекомендуется избегать столкновений.
Простой = хороший. Wacky + obfuscated = забавный.
Ответы
Ответ 1
Это зависит от характера целых чисел.
Если они могут содержать некоторые бит-маски или могут различаться степенями двух, то простые XOR будут иметь высокую вероятность столкновений.
Вы можете попробовать что-то вроде (i>>16) ^ ((i&0xffff) * p)
, где p - простое число.
Безопасность-хэши, такие как MD5, хороши, но они, очевидно, переполнены здесь. Все, что более сложно, чем CRC16, является излишним.
Ответ 2
Я думаю, что это лучшее, что вы получите. Вы можете сжать код в одну строку, но var теперь существует как документация:
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-битных хэшей
Ответ 3
Я бы сказал, просто применил стандартный хеш, например sha1 или md5, а затем захватил последние 16 бит этого.
Ответ 4
Предполагая, что вы ожидаете, что наименее значимые биты будут "меняться" больше всего, я думаю, что вы, вероятно, получите достаточно хороший дистрибутив, просто используя более низкие 16 бит значения как хэш.
Если числа, которые вы собираетесь использовать в хеше, не будут иметь такого распределения, тогда может оказаться полезным дополнительный шаг xor-ing в верхних 16 битах.
Конечно, это предложение состоит в том, что вы намереваетесь использовать хеш только для какой-то схемы поиска/хранения и не ищете криптосвязанные свойства неопределенности и необратимости (которые xor- предложения на самом деле не покупают вас).
Ответ 5
Что-то вроде этого....
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;
}