为什么采用哈希的mod的盐水哈希会导致非常不均匀的分布

Question

我有一百万个随机生成的唯一ID。

如果我这样做：

result = int(hash(id + 'some_salt')) % 1000

然后，这似乎导致ID均匀分布到0到999之间的某个整数，每个整数有大约1000个ID映射到它

如果我现在在上面添加一些盐，并再次获取哈希：

x = int(hash(id)) % 1000
result = int(hash(str(x) + 'some_salt') % 1000)

然后得到的分布是完全不均匀的。对于每个ID，结果当然在[00999]的范围内，但这个范围内的一些整数有零个映射到它们的ID，而其他整数有几千个。

为什么这会导致价值的分布非常不均匀？

我如何调整这一点，以使我的百万ID和任何给定的salt在[00999]范围内的整数均匀分布？我想保留将潜在的非常大的输入空间减少到一些小得多的空间（例如大小为1000）的中间步骤。

我使用的是SHA-256哈希。

以下是一些Python代码，它展示了非常不一致的结果：

import numpy as np
import hashlib
OUTPUT_RANGE_SIZE = 1000
unique_ids = xrange(1000000) # sequential here, but could be any kind of unique ids
frequencies = np.zeros(OUTPUT_RANGE_SIZE, dtype='int')
for idx in xrange(len(unique_ids)):
    id = unique_ids[idx]
    hash_mod = int(hashlib.sha256(str(id)).hexdigest(), 16) % 1000
    result = int(hashlib.sha256(str(hash_mod) + 'some_salt').hexdigest(), 16) % OUTPUT_RANGE_SIZE
    frequencies[result] = frequencies[result] + 1
print frequencies

Answer 1

通过在第一次哈希运算中应用模运算符，您确保了该阶段只有1000个唯一输出，无论您有多少个唯一数字作为输入。当你对它进行散列并再次对其进行模运算时，碰巧其中一些散列会映射到相同的桶；因此，bucket中的值的数量大约是散列到该bucket ID的值的1000倍。您可以通过将频率数组中的值除以1000:来看到这一点

[1, 0, 2, 1, 0, 0, 0, ...]

如果从第一步中删除模运算符，那么第二步中的输出值将按预期均匀分布。

附言：不要发明自己的密码系统。如果这对安全至关重要，请了解最佳做法并加以实施。