将部分MD5哈希码转换为long

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 then do this with the first two bytes" will just make it more complicated

”之类的复杂内容

然后，给定该整数，取最低 N 位。如果您确实想要在编译时未知的特定位数[两个桶数的幂]，

~((-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

。

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;
}