将一组整数从一个域散列到一组桶中

Question

假设我有一组介于1-100之间的整数.我只会从帽子中抽出5个这样的整数.我想然后将这5个整数放入5个保证唯一的桶中(无需重复数据删除或任何使用二次探测之类的东西).想知道如何做到这一点.

例如,假设我有这些数字(随机从1-100):

1 5 20 50 100

然后我想把这些数字放到这5个桶中:

a b c d e

使用一些哈希函数来完成它.例如,也许是这样的:

hash(1)   -> b
hash(5)   -> a
hash(20)  -> e
hash(50)  -> d
hash(100) -> c

想知道如何编写哈希函数,以便x从数字域D和该域中的一组数字中D(X)获取一个数字,并b从该组桶中输出1个桶B.

H : D(X) -> B

下次我可能有1到1,000之间的6个数字,进入6个桶.那么我需要一个使用这些约束的新哈希函数(6个数字,6个桶,范围1-1,000).

目标是尽可能少的步骤.

注意:此示例的哈希函数不会占用大于10,000的域中的整数,以及限制为一些小数的整数集的大小,如1000.

---

更新

基本上我试图让这件事发生:

// var domain = [1, 2, ..., 100]
// var set = [1, 5, 20, 50, 100]
// var buckets = [1, 2, 3, 4, 5]

hash(1) // 2
hash(5) // 1
hash(20) // 5
hash(50) // 4
hash(100) // 3

function hash(integer) {
  if (integer == 1) return 2
  if (integer == 5) return 1
  if (integer == 20) return 5
  if (integer == 50) return 4
  if (integer == 100) return 3
}

但我不知道如何动态构造该哈希函数.

一个解决方案(在JavaScript中)就是创建一个这样的地图:

var map = {
  1: 2,
  5: 1,
  20: 5,
  50: 4,
  100: 3
}

但这有点作弊,因为JavaScript中的对象被实现为下面的哈希表(或类似的东西).所以我正在寻找如何在低级别执行此操作,只是基本上使用程序集给你的.

差不多,我想这样做:

           1                     
    5      |                     
    |      |                    20
    |      |             50     |
    |      |      100    |      |
[ slot1, slot2, slot3, slot4, slot5 ]

其中1以某种方式"散列"进入其slot2在大小为5的阵列(该时隙是任意的在这个例子中)等.

Answer 1

假设整数值的域是从 0 到 n-1 的范围，并且您希望将值集 [x ₀ , x ₁ , ..., x _k-1 ] 映射到从 0 到 k-1 的值。

创建一个包含 n 个值的数组，其中包含大致相等数量的从 0 到 k-1 的数字，例如 [a ₀ = 0, a ₁ = 1, ..., a _k = 0, ..., a _n = n %k]。

然后，对于初始集合中的每个 k 值（x _i，其中 i = 0 .. k-1），通过直接赋值或与其他地方的值交换，将此数组的第 k 个元素更改为 i （注意不要破坏初始集合的前一个元素的值集）。

然后，要对值 y 进行哈希处理，只需从该数组中获取第 y 个值即可。

演示版

这是一个 Javascript 演示，基本上实现了上述算法，不同之处在于它不是用 0 到 k-1 的值预先填充数组，而是首先插入所选项目的哈希值，然后用重复序列填充剩余的项目从 0 到 k-1 的数字。通过使用随机序列而不是递增值，您可能会获得更好的抗碰撞性，但我希望您能明白。

var hash_array;

function generate_hash() {
  var i, j, k;
  var v = document.getElementById;
  var n = document.getElementById("n").value;
  // Create a new hash lookup table
  hash_array = Array(n);
  // Initialize every value to -1
  for (i=0; i<n; i++) hash_array[i] = -1;
  // Map the given values to the first k hash buckets
  var initial_values = document.getElementById("init").value.split(/ +/);
  k = initial_values.length;
  for (i=0; i<k; i++) {
    hash_array[initial_values[i]] = i;
  }
  // Fill the remaining buckets with values from 0 to k-1
  // This could be done by selecting values randomly, but
  // here we're just cycling through the values from 0 to k-1
  for (i=j=0; i<hash_array.length; i++) {
    if (hash_array[i] == -1) {
      hash_array[i] = j;
      j = (j + 1) % k;
    }
  }
  document.getElementById("gen").innerHTML = "Hash lookup table:<br>" + hash_array.join(", ");
}

<h2>Demo</h2>
<p>Creating a hash function that works on integer values  less than <i>n</i>. What is the value of <i>n</i>?<br>
<input type="number" id="n" min="6" max="100" value="20"/></p>
<p>Enter a few different values separated by spaces. These will hash to the first buckets<br/>
<input type="text" size="40" id="init" value="2 3 5 6 9"/></p>
<p id="gen"><button onclick="generate_hash(); return false">Generate hash table</button></p>