如何将 64 位哈希值缩短为 48 位值? [英] How to shorten a 64-bit hash value down to a 48-bit value?
问题描述
我在库中已经有一个 64 位的哈希函数(C 编码)，但我只需要 48 位.我需要将 64 位哈希值缩减为 48 位值，但它必须以安全的方式才能最大程度地减少冲突.
I already have a 64 bit hash function in a library (C coding), but I only need 48 bits. I need to trim down the 64 bit hash value to a 48 bit value, yet it has to be in a safe manner in order to minimize collision.
哈希函数是一个非常好的64位哈希函数.它已经用 SMHasher(DieHarder"哈希测试)进行了测试，并且证明比 Murmur2 更好.据我的同事说，在 lib 中实现的用于 64 位散列的算法是 xxHash，用 SMHasher 测试并获得了 10 的 Q.Score！对于那些想要查看它的人，可以在 github.com 上找到 xxHash 的源代码:github.com/Cyan4973/xxHash/releases/latest.
The hash function is a very good 64 bit hash function. It has been tested with SMHasher (the "DieHarder" hash testing) and proved better than Murmur2. According to my colleagues, the algorithm implemented in the lib for 64-bit hashing is xxHash, tested with SMHasher and got a Q.Score of 10! For those who want to see it, the source code for xxHash is available on github.com : github.com/Cyan4973/xxHash/releases/latest.
基本思想是让 64 位哈希值(或其中的一部分)中的所有位对生成的 48 位哈希值产生影响.有没有办法做到这一点?
The basic idea is to have all bits in the 64-bit hash value (or part of them) have an effect on the resulting 48-bit hash value. Is there any way to do that?
[后期编辑]:
所以我实现了自己的 48 位(准)-UUID 生成器.
请在此处查看完整的工作解决方案(包括源代码):https://stackoverflow.com/a/47895889/4731718.
推荐答案
如果 64 位散列是好的，那么选择任何 48 位也是一个好的散列.@李丹尼尔.当然，信息会丢失且不可逆转.
If the 64-bit hash is good, then selecting any 48 bits will also be a good hash. @Lee Daniel. Of course, information is lost and not reversible.
unsigned long long Mask48 = 0xFFFFFFFFFFFFu;
unsigned long long hash48 = hash64 & Mask48;
如果 64 位哈希函数较弱，则通过 pow(2,48) 下的最大素数进行 mod.一些桶会丢失.这不会损害好的散列，但肯定会使弱散列更好.
If 64-bit hash function is weak, then mod by the largest prime just under pow(2,48). Some buckets will be lost. This will not harm a good hash, yet certainly make weak hashes better.
unsigned long long LargestPrime48 = 281474976710597u; // FFFFFFFFFFC5
unsigned long long hash48 = hash64 % LargestPrime48;
这篇关于如何将 64 位哈希值缩短为 48 位值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
