2

我有一百万个随机生成的唯一 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，结果当然在 [0,999] 范围内，但在此范围内的一些整数映射到它们的 ID 为零，而其他整数则有几千个。

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

如何调整它以使我的百万个 ID 和任何给定的盐在 [0,999] 范围内均匀分布整数？我想保留将可能非常大的输入空间减少到一些更小的空间（例如大小为 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
4

1 回答 1

3

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

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

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

强制性后记：不要发明自己的密码系统。如果这对安全至关重要，请了解最佳实践并实施它们。

于 2015-03-30T11:35:03.907 回答