如何将整数哈希细分为范围

今天golang学习网给大家带来了《如何将整数哈希细分为范围》，其中涉及到的知识点包括等等，无论你是小白还是老手，都适合看一看哦~有好的建议也欢迎大家在评论留言，若是看完有所收获，也希望大家能多多点赞支持呀！一起加油学习~

我有无符号的64位数字，代表尾数或分数（代表从[0..1)的范围，其中0.0映射到0和0xffffff..映射到“就在1.0之前”的数字）

现在我想将此范围拆分为相等的 buckets - 并回答 - 给定随机数 key，它将落在范围的哪一部分？

通过以下代码更容易获得：

func bucketindex(key, buckets uint64) uint64 {
    return uint64(float64(key) / ((math.pow(2, 64) / float64(buckets)))
}

我尝试“破解这个问题” - 是将 2^64 一分为二，就像我将范围缩小到 32 位，并在 64 位中操作以便进行数学运算：

// ~=key / ((1 << 64) / buckets)
return ((key >> 32) * buckets) >> 32

但范围不再相等.. 例如，三分之一 (buckets==3) 将位于 0x5555555600000000，而不是位于 0x5555555555555556 这是一个悲伤的故事，所以我问你知道找到 (1 << 64)/buckets 的更好方法吗？

正确答案

如果 buckets 是（编译时）常量，则可以使用 constant expression 来计算存储桶大小：常量具有任意大小。否则，您可以使用 big.int 在运行时计算它，并存储结果（这样您就不必一直使用 big.int 计算）。

在编译时使用常量表达式

要实现整数除法向上舍入，请将除数 - 1 添加到被除数中：

const (
    max        = math.maxuint64 + 1
    buckets    = 3
    bucketsize = uint64((max + buckets - 1) / buckets)
)

在运行时使用 big.Int

我们也可以对 big.int 使用上述相同的逻辑。另一种方法是使用 Int.DivMod()（而不是添加 buckets -1），如果 mod 大于零，则将结果增加 1。

func calcBucketSize(max, buckets *big.Int) uint64 {
    max = max.Add(max, buckets)
    max = max.Add(max, big.NewInt(-1))
    return max.Div(max, buckets).Uint64()
}

var bucketSize = calcBucketSize(new(big.Int).SetUint64(math.MaxUint64), big.NewInt(3))

到这里，我们也就讲完了《如何将整数哈希细分为范围》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！