Question 1

注意：将讨论中出现的答案放在评论中，以便感兴趣的人更容易阅读

（更新后的版本）

假设我们有一个生成独立事件的源，我们希望将这些事件均匀地分配到个桶中。 $B$

关键步骤是：

散列为大小为的整数 $e$ $i$ $2^N$
投影到 as $\mathcal{R} \times [0, 1[$ $p = \frac{i}{2^N}$
找到匹配的桶使得 $b_i$ $\frac{b_i}{B} \le p \lt \frac{b_{i+1}}{B}$

对于 1. 一个流行的解决方案是使用MurmurHash生成一个 64 位或 128 位整数。

对于 3. 一个简单的解决方案是迭代并检查是否在 $j = 1..B$ $p$ $[\frac{b_j}{B}, \frac{b_{j+1}}{B}[$

在（python）伪代码中，整个过程可能是：

def hash_to_bucket(e, B):
    i = murmurhash3.to_long128(str(e))
    p = i / float(2**128)
    for j in range(0, B):
        if j/float(B) <= p and (j+1)/float(B) > p:
            return j+1
    return B

（以前的版本，真的不是最优的）

第一个观察是哈希的第n个字母应该相对于字母表均匀分布（这里是 16 个字母长 - 感谢@leonbloy 指出）。

~~然后，要将其投影到 [0,100[ 范围，诀窍是从散列中获取 2 个字母（例如，第 1 和第 2 位置）并生成一个整数：~~

~~int_value = int(hash[0])+16*int(hash[1])~~

~~该值位于 [0,16+(16-1)*16[ 范围内，因此我们只需将其取模为 100 即可生成 [0, 100[ 范围内的存储桶：~~ 正如评论中指出的那样，做所以影响分布的均匀性，因为第一个字母比第二个字母更有影响力。

bucket = int_value % 100

理论上，您可以将整个哈希转换为（非常大的）整数，方法是将其解释为数字： i = h[0] + 16*h[1]+16*16*h[2] ... + 16^ 31*h[31]（每个字母代表一个十六进制数）。然后你可以对这个大数字取模以将其投影到存储桶空间。然后可以注意到，取 i 的模可以分解为分配和加法运算：

\begin{aligned} i \mod N = ( \\ (h_{0} \mod N) \\ + (16 \mod N \times h_{1} \mod N) \\ + . . . \\ + (16^{31} \mod N \times h_{31} \mod N) \\ ) \mod N \end{aligned}

$\begin{align} i \mod N = (&\\ &(h_0 \mod N) \\ &+ (16 \mod N \times h_1 \mod N) \\ &+ ... \\ &+ (16^{31} \mod N \times h_{31} \mod N)\\ &) \mod N \end{align}$

Question 2

我遇到了类似的问题，并想出了一个不同的解决方案，它可以更快、更容易地用任何语言实现。

我的第一个想法是在固定数量的桶中快速统一地调度项目，并且为了可扩展，我应该模仿随机性。

所以我编写了这个小函数，在 [0, 1[ 中返回一个浮点数，给定一个字符串（或实际上任何类型的数据）。

在 Python 中：

import math
def pseudo_random_checksum(s, precision=10000):
    x = sum([ord(c) * math.sin(i + 1) for i,c in enumerate(s)]) * precision
    return x - math.floor(x)

当然它不是随机的，事实上它甚至不是伪随机的，相同的数据总是会返回相同的校验和。但它的行为就像随机的，而且非常快。

您只需将每个项目分配给存储桶编号 math.floor(N * pseudo_random_checksum(item)) 即可轻松分派和稍后检索 N 个存储桶中的项目。

Question 3

在这里，您可以找到适用于按位运算的无分支统一存储桶分布。

Answer 1