Хешировать интервал на 32 бита к интервалу на 16 битов?
Что некоторые простые пути состоят в том, чтобы хешировать 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 = забавный.
5 ответов
Это зависит от природы целых чисел.
Если они могут содержать несколько битовых масок или могут различаться степенью двойки, тогда простые операции XOR будут иметь высокую вероятность коллизий.
Вы можете попробовать что-то вроде (i >> 16) ^ ((i & 0xffff) * p) , где p - простое число.
Хеши безопасности, такие как MD5, хороши, но здесь явно излишек. Что-либо более сложное, чем CRC16, является излишним.
Предполагая, что вы ожидаете, что наименее значимые биты будут "изменяться" больше всего, я думаю, вы, вероятно, получите достаточно хорошее распределение, просто используя младшие 16 бит значения как хеш.
Если числа, которые вы собираетесь хэшировать, не будут иметь такого распределения, может оказаться полезным дополнительный шаг xor-ing в старших 16 битах.
Конечно, это предложение относится к тем случаям, когда вы намереваетесь использовать хеш просто для какой-то схемы поиска / хранения и не ищете связанные с криптографией свойства невозможности угадывания и необратимости (которые xor- предложения тоже вас не купят).
Думаю, это лучшее, что вы собираетесь получить. Вы можете сжать код до одной строки, но переменные пока существуют в качестве документации:
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-битным хешам
Я бы сказал, просто примените стандартный хеш, такой как sha1 или md5, а затем возьмите последние 16 его бит.
Что-то вроде этого ....
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;
}