将部分MD5散列代码转换为长整型

Question

我正在使用MD5算法来散列磁盘上哈希表的键(我知道这是否是最好的算法还值得怀疑，但我现在还是使用它。这个问题可以推广到产生字节数组的任何算法)。我的问题是：

哈希码的大小决定了哈希表中组合(桶)的数量。由于MD5是128位的，所以有大量的组合(~ 3.4e38)，这对我的目的来说太大了。所以我想做的是提取MD5产生的字节数组的前n位，并将它们转换成一个长(或ulong)值。由于MD5生成一个字节数组，如果我想要一个整数字节数组，这将很容易做到，但这会导致组合数量的跳跃太大。我发现单比特版本要复杂得多。

目标：

n = 10  // I.e. I want 2^10 combinations
long pos = someFcn(byte[] key, n)

其中key是散列值，n是我想要使用的MD5结果的位数。那么，Pos将是一个从0到1023的整数(在n=10的情况下)。如果n= 11，代码将是从0到2^11-1 = 2027，等等。必须有点快/高效。

看起来没那么难，但我就是想不通。任何帮助都将不胜感激。谢谢。

Answer 1

首先，使用BitConverter.ToInt32将前四个字节转换为整数。不管怎样，它会得到4个字节，但这可能不会使它明显变慢，因为您无论如何都要使用32位寄存器来处理其余的计算，而像“如果它< 16，那么用前两个字节做这件事”这样的复杂东西只会使它变得更加复杂

然后，给定该整数，取最低的N位。如果您确实想要一个特定位数和编译时未知的存储桶数的2的幂，那么~((-1)<<N)是一个获得2^N-1的好技巧。

或者你可以简单地使用ToUInt32，取模一个素数，转换成UInt64可能会稍微好一点，这样你就有了足够的一半的比特开始，在本例中

Answer 2

要获取前10位，例如：

int result = ((int)key[0] << 2) | (((int)key[1] >> 6) & 0x03)

Answer 3

如果你有一个这样的数组，

unsigned char data[2000];

然后，您只需将前n位刮成一个整数，如下所示：

typedef unsigned long long int MyInt;

MyInt scrape(size_t n, unsigned char * data)
{
    MyInt result = 0;
    size_t b;

    for (b = 0; b < n / 8; ++b)
    {
       result <<= 8;
       result += data[b];
    }

    const size_t remaining_bits = n % 8;
    result <<= remaining_bits;
    result += (data[b] >> (8 - remaining_bits));

    return result;
 }

我假设CHAR_BITS == 8，如果你愿意，你可以随意泛化代码。此外，数组的大小乘以8必须至少为n。