一致性哈希 SHA1 模运算
Consistent hashing SHA1 modulo operation
希望这里的高手能帮帮我
我正在编写一个 C/C++ 代码来使用 SHA1 作为哈希算法来实现一致性哈希。
我需要实现模块操作如下:
0100 0011....0110 100 mod 0010 1001 = ?
如果除数 (0000 1111
) 是 2 的幂 pow(2,n)
,那么很容易,因为结果是被除数的最后 n 位。
SHA1 长度为 160 位(或 40 位十六进制)。我的问题是如何实现一个长位串到另一个任意位串的模运算?
谢谢。
正如用户 stark 在评论中指出的(我认为比必要的更粗鲁),这只是以 2^32 为基数的长除法。或者以 2 为基数,有更多的数字。您可以使用在学校学到的以 10 为基数的长除法算法。
有更高级的算法可以对更大的数字进行除法,但对于您的应用程序,我怀疑您可以按照以下几行非常简单且低效地进行除法(这是 base-2 版本,仅相当于减去分母的左移版本,直到你不能再这样做):
// Treat x,y as 160-bit numbers, where [0] is least significant and
// [4] is most significant. Compute x mod y, and put the result in out.
void mod160(unsigned int out[5], const unsigned int x[5], const unsigned y[5]) {
unsigned int temp[5];
copy160(out, x);
copy160(temp, y);
int n=0;
// Find first 1-bit in quotient.
while (lessthanhalf160(temp, x)) { lshift160(temp); ++n; }
while (n>=0) {
if (!less160(out, temp)) sub160(out, temp); // quotient bit is 1
rshift160(temp); --n; // proceed to next bit of quotient
}
}
为免疑义,以上仅为粗略的示意图:
- 它可能充满了错误。
- 我还没有写过像
less160
这样的积木函数的实现。
- 实际上,您可能只是将那些内联的代码放在一起,而不是使用单独的函数。例如,
copy160
只是五个赋值,或者一个短循环,或者一个 memcpy
.
肯定可以提高效率;例如,第一步可能会更好地计算前导 0 位,然后进行一次移位,而不是一次移位一个位置。 (不过,右移可能不想这样做,因为有一半的时间你只会做一个班次。)
"base-2^32"版本可能会更快,但实现起来会稍微复杂一些。
希望这里的高手能帮帮我
我正在编写一个 C/C++ 代码来使用 SHA1 作为哈希算法来实现一致性哈希。
我需要实现模块操作如下:
0100 0011....0110 100 mod 0010 1001 = ?
如果除数 (0000 1111
) 是 2 的幂 pow(2,n)
,那么很容易,因为结果是被除数的最后 n 位。
SHA1 长度为 160 位(或 40 位十六进制)。我的问题是如何实现一个长位串到另一个任意位串的模运算?
谢谢。
正如用户 stark 在评论中指出的(我认为比必要的更粗鲁),这只是以 2^32 为基数的长除法。或者以 2 为基数,有更多的数字。您可以使用在学校学到的以 10 为基数的长除法算法。
有更高级的算法可以对更大的数字进行除法,但对于您的应用程序,我怀疑您可以按照以下几行非常简单且低效地进行除法(这是 base-2 版本,仅相当于减去分母的左移版本,直到你不能再这样做):
// Treat x,y as 160-bit numbers, where [0] is least significant and
// [4] is most significant. Compute x mod y, and put the result in out.
void mod160(unsigned int out[5], const unsigned int x[5], const unsigned y[5]) {
unsigned int temp[5];
copy160(out, x);
copy160(temp, y);
int n=0;
// Find first 1-bit in quotient.
while (lessthanhalf160(temp, x)) { lshift160(temp); ++n; }
while (n>=0) {
if (!less160(out, temp)) sub160(out, temp); // quotient bit is 1
rshift160(temp); --n; // proceed to next bit of quotient
}
}
为免疑义,以上仅为粗略的示意图:
- 它可能充满了错误。
- 我还没有写过像
less160
这样的积木函数的实现。 - 实际上,您可能只是将那些内联的代码放在一起,而不是使用单独的函数。例如,
copy160
只是五个赋值,或者一个短循环,或者一个memcpy
.
肯定可以提高效率;例如,第一步可能会更好地计算前导 0 位,然后进行一次移位,而不是一次移位一个位置。 (不过,右移可能不想这样做,因为有一半的时间你只会做一个班次。)
"base-2^32"版本可能会更快,但实现起来会稍微复杂一些。