如何将64位散列值缩短为48位值？ [英] How to shorten a 64-bit hash value down to a 48-bit value?

问题描述

我已经在一个库（C编码）中有一个64位散列函数，但我只需要48位。我需要将64位散列值修剪为48位值，但它必须以安全的方式来减少冲突。

哈希函数是一个很好的64位哈希函数。它已经通过SMHasher（DieHarder哈希测试）进行了测试，并且证明比Murmur2更好。据我的同事们说，在lib中执行64位哈希的算法是xxHash，使用SMHasher进行了测试，得到了10的Q.Score！对于那些想看到它的人，可以在github.com上找到xxHash的源代码： github。 COM / Cyan4973 / xxHash /版本/最新。

基本思想是让64位散列值（或其中的一部分）中的所有位对结果的48位散列值有影响。有没有办法做到这一点？

$ b

[Late EDIT]：

所以我实现了我自己的48位（准） UUID生成器。

请在此检查完整的工作解决方案（包括源代码）： https://stackoverflow.com / a / 47895889/4731718 。

解决方案

选择任何48位也将是一个很好的散列。 @李丹尼。当然，信息丢失并且不可逆。

  unsigned long long Mask48 = 0xFFFFFFFFFFFFu; 
 unsigned long long hash48 = hash64& Mask48; 
  

如果64位散列函数很弱，那么使用 POW（2,48）。有些水桶会丢失。这不会损害一个好的散列，但肯定会使散列效果更好。

  unsigned long long LargestPrime48 = 281474976710597u; // FFFFFFFFFFC5 
 unsigned long long hash48 = hash64％LargestPrime48; 
  

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.

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.

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?

[Late EDIT]:
So I have implemented my own 48-bit (quasi)-UUID generator.
Please check a complete working solution (including source code) here: https://stackoverflow.com/a/47895889/4731718.

解决方案

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;

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屋！