hash - "evenly distributing"跨可能值空间的连续数字的函数

Question

我需要在 Google AppEngine(或者您可以想到任何其他哈希表)中将一堆实体存储在我需要根据顺序输入自行创建的键下。

举个例子，假设我只处理长度为一位十进制数字的键。然后我需要为键“0”存储一个实体，为键“1”存储一个实体，为键“2”存储一个实体，依此类推。

问题是，如果我直接使用这个递增序列作为键，将会导致所有实体在物理上存储得非常接近，这可能会导致严重的性能问题。 Details here 。对于一般的哈希表，您可以认为所有条目并不是均匀分布在所有存储桶中，而是聚集在几个存储桶中，这也会导致查找等性能下降。

因此，我正在寻找一些函数来在可用值的空间中更均匀地“重新分配”我的值。

为了继续使用单位数字键的示例，我可以创建一个包含所有可能值的随机排列的表，例如 [5,9,2,4,1,8,0,6,3 ,7] 并对其进行索引。然后，当我存储彼此相邻的条目 0、1 和 2 时，我会分配更分散在服务器或哈希桶中的键 5、9 和 2。

但我需要找到一种方法来对 156 位数字执行此操作，在这种情况下，使用所有值随机排列的表是不可行的。

我有两个要求:

• 每个可能的 156 位数字都必须映射到恰好一个值(最多 160 位即可)。不允许碰撞
• 这在计算上应该很便宜

我找到了一种方法:简单地用 SHACAL-1 “加密”我的值或其他一些 160 位密码。但这对于我想要实现的目标来说似乎需要太多的计算工作。是否有一些伪随机函数可以使用我的值作为种子？它们能保证无碰撞吗？

Answer 1

您可以使用离散对数，它可以为您的所有数组位置提供完美的确定性排列。但是，排列是单向的:如果不诉诸暴力(或在允许的方向上重新进行排列)，则无法检索新的第 i 个数组位置的原始位置

或者

如果您不关心额外的空间，您可以存储对 <value-originalindex>并完全随机放置它们(使用一些 PRNG 函数)，在发生碰撞时重申(或记下已使用的位置)。现在这些对均匀分布。检索第 i 个元素需要 O(N)，其中 N 是位置数。这就是该算法的代价。

或者

仅获取 156 位值中的几个随机位，并使用它们来形成一个 12 位无符号索引。使用此索引从您的最终空间中选择第 k 个存储桶(您的空间被划分为 2^12 个存储桶)。仅当值共享相同的 12 位随机位时，值才会倾向于聚合，如果您仔细挑选它们，则不太可能...使用剩余的 156-12=143 位来偏移桶内。

或者

创建 156 位的固定随机排列。