将部分 MD5 哈希码转换为长哈希码

Question

我正在使用 MD5 算法对磁盘哈希表的密钥进行哈希处理（我知道这是否是用于此目的的最佳算法是值得怀疑的，但我现在就使用它。这个问题可以推广到任何生成字节数组的算法）。我的问题是这样的：

哈希码的大小决定了哈希表中组合（桶）的数量。由于 MD5 是 128 位，因此存在大量组合（~ 3.4e38），这对于我的目的来说太大了。所以我想要做的是取出 MD5 生成的字节数组的前 n 位，并将它们转换为 long （或 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 位。如果您确实想要在编译时未知的特定位数[桶数的两个幂]，~((-1)< 是一个获得 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。

Answer 4

string input;

using (System.Security.Cryptography.MD5 md5 = System.Security.Cryptography.MD5.Create())
{
    byte[] inputBytes = System.Text.Encoding.ASCII.GetBytes(input);
    byte[] hashBytes = md5.ComputeHash(inputBytes).TakeLast(7).ToArray();
    var hashStr = BitConverter.ToString(hashBytes).Replace("-", "");
    var res = long.Parse(hashStr, System.Globalization.NumberStyles.HexNumber);
    return res;
}