哈希从32bit int到16bit int? [英] Hash 32bit int to 16bit int?

问题描述

将32位整数(例如IP地址，例如Unix time_t等)散列为16位整数的简单方法是什么?

What are some simple ways to hash a 32-bit integer (e.g. IP address, e.g. Unix time_t, etc.) down to a 16-bit integer?

例如hash_32b_to_16b(0x12345678)可能返回0xABCD.

让我们以一个可怕但实用的示例解决方案开始:

Let's start with this as a horrible but functional example solution:

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

问题专门针对JavaScript，但可以随意添加任何与语言无关的解决方案，最好不要使用库函数.

Question is specifically about JavaScript, but feel free to add any language-neutral solutions, preferably without using library functions.

此问题的上下文正在生成唯一的ID(例如，一个64位ID可能由多个具有各种32位值的16位哈希组成).避免碰撞很重要.

The context for this question is generating unique IDs (e.g. a 64-bit ID might be composed of several 16-bit hashes of various 32-bit values). Avoiding collisions is important.

简单=好.古怪+模糊=可笑.

Simple = good. Wacky+obfuscated = amusing.

推荐答案

这取决于整数的性质. 如果它们可以包含一些位掩码，或者可以相差2的幂，则简单的XOR发生冲突的可能性很高. 您可以尝试使用(i>>16) ^ ((i&0xffff) * p)之类的东西，其中p是质数.

This depends on the nature of the integers. If they can contain some bit-masks, or can differ by powers of two, then simple XORs will have high probability of collisions. You can try something like (i>>16) ^ ((i&0xffff) * p) with p being a prime number.

像MD5这样的安全性杂凑都很好，但是在这里显然它们是一个过大的杀伤力.比CRC16更复杂的是过大的杀伤力.

Security-hashes like MD5 are all good, but they are obviously an overkill here. Anything more complex than CRC16 is overkill.

这篇关于哈希从32bit int到16bit int?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！