dka*_*ins 17 javascript hash integer
有什么简单的方法可以将32位整数(例如IP地址,例如Unix time_t等)散列为16位整数？
例如,hash_32b_to_16b(0x12345678)可能会返回0xABCD.
让我们从这开始,作为一个可怕但功能性的示例解决方案:
function hash_32b_to_16b(val32b) {
return val32b % 0xffff;
}
问题是关于JavaScript的,但可以随意添加任何与语言无关的解决方案,最好不使用库函数.
此问题的上下文是生成唯一ID(例如,64位ID可能由多个32位值的多个16位哈希组成).避免碰撞很重要.
简单=好.古怪+混淆=有趣.
最大限度地保留某些原始 32 位“信号”的熵的关键是确保 32 位输入位中的每一个都具有独立且相等的能力来改变 16 位输出字的值。
由于 OP 要求的位大小恰好是原始大小的一半，因此满足此标准的最简单方法是对上半部分和下半部分进行XOR，正如其他人所提到的。使用XOR是最佳的，因为，由于是显而易见由定义XOR -independently翻转32个输入位中的任一个是保证改变16位输出的值。
当您需要进一步减少超过一半大小时，问题变得更加有趣，例如从32 位输入到2 位输出。请记住，目标是尽可能多地保留来自源的熵，因此涉及天真地屏蔽两个最低位的解决方案 (i & 3)通常会朝着错误的方向前进；这样做可以保证除了未屏蔽的位之外的任何位都无法影响结果，这通常意味着运行时信号中存在任意的、可能有价值的部分，该部分被毫无原则地立即丢弃。
从前面的段落开始，您当然可以使用XOR再迭代三次，以产生具有所需属性的 2 位输出，即受每个/任何输入位的同等影响。当然，该解决方案仍然是最佳正确的，但涉及循环或多个展开操作，事实证明，这不是必需的！
幸运的是，有一种很好的技术，只有两个操作，可以为这种情况提供可证明的最佳结果。与XOR 一样，它不仅确保，对于任何给定的 32 位值，处理任何单个输入位都会导致（例如）2 位输出值发生变化，而且在给定均匀分布的情况下，还可以确保输入值，2 位输出值的分布也将完全均匀。例如，在4,294,967,296可能的输入值上，该方法精确地给出1,073,741,824四种可能的 2 位散列结果中的每一个{ 0, 1, 2, 3 }。
我在这里提到的方法使用了我通过详尽搜索发现的特定魔法值，并且似乎在互联网上的其他地方没有太多讨论，至少对于这里讨论的特定用途（即，确保统一的哈希分布是最大熵保持）。奇怪的是，根据同样的详尽搜索，魔法值实际上是唯一的，这意味着对于每个目标位宽{ 16, 8, 4, 2 }，我在下面显示的魔法值是唯一的值，当我在这里显示时，满足完美散列上面列出的标准。
不用多说，将 32 位散列到的唯一且数学上最佳的过程n = { 16, 8, 4, 2 }是乘以对应于n（无符号，丢弃溢出）的魔术值，然后取结果的n 最高位。要将这些结果位隔离为范围内的哈希值[0 ... (2? - 1)]，只需将乘法结果右移（无符号！）32 - n位。
“魔法”值和类似 C 的表达式语法如下：
最大限度地保留熵的散列，用于从 32 位减少到...
目标位乘数右移表达式 —————————————————————————————— ------- 16 0x80008001 16 (i * 0x80008001) >> 16 8 0x80808081 24 (i * 0x80808081) >> 24 4 0x88888889 28 (i * 0x88888889) >> 28 2 0xAAAAAAAB 30 (i * 0xAAAAAAAB) >> 30
笔记：
- 使用无符号 32 位乘法并丢弃任何溢出（不需要 64 位乘法）。
- 如果使用右移（如图所示）隔离结果，请务必使用无符号移位操作。
[编辑：添加了 64 位输入值的表]
最大熵保留散列，用于将 64 位值减少到...
目标位乘数右移表达式 ----------- ------------------ ----------- ---------- --------------------- 32 0x8000000080000001 32 (i * 0x8000000080000001) >> 32 16 0x8000800080008001 48 (i * 0x8000800080008001) >> 48 8 0x8080808080808081 56 (i * 0x8080808080808081) >> 56 4 0x8888888888888889 60 (i * 0x8888888888888889) >> 60 2 0xAAAAAAAAAAAAAAAB 62 (i * 0xAAAAAAAAAAAAAAAB) >> 62
我发现这一切都很酷。实际上，关键信息理论要求是保证，对于任何m-bit输入值及其对应的n-bit哈希值结果，翻转任何一个m源位总是会导致n-bit结果值发生一些变化。现在虽然2?总共有可能的结果值，但其中一个已经“使用”（由结果本身），因为从任何其他结果“切换”到那个值根本没有变化。这使得2? - 1可以m由单个位翻转的整个输入值集使用的结果值。
让我们考虑一个例子；事实上，为了展示这种技术看起来如何接近怪异或彻头彻尾的神奇，我们将考虑更极端的情况 wherem = 64和n = 2。对于 2 个输出位，有四个可能的结果值，{ 0, 1, 2, 3 }。假设一个任意的 64 位输入值0x7521d9318fbdf523，我们得到它的 2 位哈希值1：
(0x7521d9318fbdf523 * 0xAAAAAAAAAAAAAAAB) >> 62 // result --> '1'
所以结果是1和权利要求是没有价值的集合64个值，其中的一个单比特0x7521d9318fbdf523被触发可以具有相同的结果值。也就是说，无那些64个的其它结果可以使用值1和所有必须改用任一0，2或3。所以在这个例子中，似乎每一个都是 2?? 输入值——不包括其他 64 个输入值——将自私地占有四分之一的输出空间。当您考虑到这些相互作用约束的绝对规模时，是否可以同时存在总体上令人满意的解决方案？
果然，为了表明（确切地？）确实如此，这里是按顺序列出的哈希结果值，用于翻转一位0x7521d9318fbdf523（一次一个）的输入，从 MSB（位置 63）向下到 LSB（ 0）。
3 2 0 3 3 3 3 3 3 0 0 0 3 0 3 3 0 3 3 3 0 0 3 3 3 0 0 3 3 0 3 3 // continued…
0 0 3 0 0 3 0 3 0 0 0 3 0 3 3 3 0 3 0 3 3 3 3 3 3 0 0 0 3 0 0 3 // notice: no '1' values
如您所见，没有1值，这意味着源“原样”中的每一位都必须有助于影响结果（或者，如果您愿意，每一个位的事实上的状态0x7521d9318fbdf523是对于保持整个整体结果不“非- 1”至关重要）。因为无论您对 64 位输入进行何种单位更改，2 位结果值都将不再是1.
请记住，上面显示的“缺失值”表是从对随机选择的示例值的分析中转储的0x7521d9318fbdf523；每个其他可能的输入值都有一个类似的表，每个值都奇怪地缺少其所有者的实际结果值，但不知何故在其集合成员中保持全局一致。此属性本质上对应于在（固有有损）位宽缩减任务期间最大程度地保留可用熵。
所以我们看到，每一个2??可能的源值都独立地对 64 个其他源值施加了排除可能结果值之一的约束。与我的直觉相反的是，这 64 个成员的集合有数以亿计的数以亿计，每个成员还属于其他63个看似无关的比特处理集合。然而不知何故，尽管存在这种交织约束的最令人困惑的难题，但利用一个（我推测）同时完全满足它们的解决方案是微不足道的。
所有这些似乎都与您在上表中可能已经注意到的事情有关：即，我没有看到任何明显的方法可以将该技术扩展到压缩到1 位结果的情况。在这种情况下，只有两个可能的结果值{ 0, 1 }，因此如果任何/每个给定的（例如）64 位输入值仍然概括地从其所有 64 个单位翻转邻居的结果中排除其自己的结果，那么现在基本上将另一个，仅剩下的值强加给那些 64。我们在表中看到的数学分解似乎表明，在这种情况下的同时结果是一个过分的桥梁。
换句话说，特殊“保护信息”特征的XOR（即，其豪华的可靠保证，而不是AND，OR，等等，其C吗？一？N +和W'我？l？l？总是稍微改变一点）并不奇怪，它需要一定的成本，即对一定数量的肘部空间（至少 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位数.它也会以不同方式对IMO散列顺序32位数字.除非我遗漏了什么,否则我相信这个解决方案可以做到这两点.
我认为安全性不能成为这个问题的考虑因素,因为散列值太少了.我相信我提供的解决方案可以将32位数字均匀分配到16位哈希
这取决于整数的性质。如果它们可以包含一些位掩码，或者可以相差 2 的幂，那么简单的 XOR 将具有很高的冲突概率。您可以尝试(i>>16) ^ ((i&0xffff) * p)将 p 设为素数。
像 MD5 这样的安全哈希值都很好，但它们在这里显然是大材小用了。任何比 CRC16 更复杂的东西都太过分了。