我试图了解一种伪随机的类似哈希的算法。它在分布式存储系统中用于通过复制放置数据。该算法类似于吸管。稻草桶类型允许所有物品相互竞争,从而通过复制稻草的过程进行复制品放置。放置复制品,吸管 为存储桶中的每个项目绘制随机长度的。的 秸秆最长的物品将获胜。每个吸管的长度 最初是一个固定范围内的值,基于以下三个实体的哈希值:
- 输入号码x
- 副本数r
- 铲斗编号I
使用Jenkins整数哈希函数计算所有三个实体的哈希。之后,他们基于ln(自然对数)哈希值创建一个负数,然后除以权重(或依赖权重的函数)。
问题:
- 为什么需要记录哈希值?
- 给定代码中实际上是在计算什么函数rush_ln()?我对注释2 ^ 44 * log2(input + 1)感到困惑。
- 为什么需要基于哈希值的ln(自然对数)创建一个负数?
u = hash32_3(bucket-> h.hash, x, ids[i], r);
u &= 0xffff;
ln = crush_ln(u) - 0x1000000000000ll;
return div64_s64(ln, weight);
}
/* compute 2^44*log2(input+1) */
static __u64 crush_ln(unsigned int xin)
{
unsigned int x = xin;
int iexpon, index1, index2;
__u64 RH, LH, LL, xl64, result;
x++;
/* normalize input */
iexpon = 15;
// figure out number of bits we need to shift and
// do it in one step instead of iteratively
if (!(x & 0x18000)) {
int bits = __builtin_clz(x & 0x1FFFF) - 16;
x <<= bits;
iexpon = 15 - bits;
}
index1 = (x >> 8) << 1;
/* RH ~ 2^56/index1 */
RH = __RH_LH_tbl[index1 - 256];
/* LH ~ 2^48 * log2(index1/256) */
LH = __RH_LH_tbl[index1 + 1 - 256];
/* RH*x ~ 2^48 * (2^15 + xf), xf<2^8 */
xl64 = (__s64)x * RH;
xl64 >>= 48;
result = iexpon;
result <<= (12 + 32);
index2 = xl64 & 0xff;
/* LL ~ 2^48*log2(1.0+index2/2^15) */
LL = __LL_tbl[index2];
LH = LH + LL;
LH >>= (48 - 12 - 32);
result += LH;
return result;
} ```