将一个整数集合从域中哈希到一个桶集合中。

Question

假设我有一组整数，范围在1到100之间。我只会从中抽出其中的5个整数。然后我想将这5个整数放入5个桶中，保证唯一性（无需使用类似quadratic probing之类的去重方法）。请问如何实现。

例如，我有以下数字（从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

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

H : D(X) -> B

下一次我可能会有6个数字，范围在1到1000之间，分成6个桶。那么我需要一个新的哈希函数来使用这些约束条件（6个数字，6个桶，范围为1-1000）。

目标是尽可能少的步骤。

注意：此示例的哈希函数不会接受大于10,000的整数域，以及整数集大小也限制在像1,000这样的小数字。

---

更新

我正在尝试实现以下目标：

// 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 ]

在大小为5的数组中，“1”以某种方式被“散列”，进入那个“slot2”（对于这个示例，该槽是任意的），等等。

- Lance

---

只是为了澄清，您是否只想将这六个值哈希到单独的桶中，还是正在寻找适用于任何数字集合的函数，但前提是前六个数字始终具有不同的哈希值？ - r3mainer

我正在寻找一种方法，将一个大小为n的整数集合中的“任何”整数散列成相等数量的桶（一个大小为n的集合），其中这些整数来自某个有限域。5和6的值只是为了演示它如何工作。 - Lance

Answer 1

可以尝试以下方法：

1. 创建一组桶ID并在哈希之前填充它（此处假设集合保证唯一性）。这意味着您必须事先知道要使用多少个桶。
2. 对于来自输入集的每个元素，计算hash(element) modulo bucketIds.size以查找下一个要使用的ID的索引。
3. 从桶ID的集合中删除生成的桶ID
4. 重复此过程（直到完成或桶ID集用完为止）

可以查看使用JS数组的简单实现（Node8）。

- diginoise

---

例如，（1）我只会从1开始递增桶ID。因此，如果我有5个数字，则桶为“1 2 3 4 5”。然后对于（2）不确定“哈希”是什么。然后（3）删除我们散列到的桶ID，现在假设我们有“1 2 3 4”。然后不确定如何使用一旦生成的哈希函数。不太确定我是否明白，也许如果您可以发布一个示例，那将有助于我更好地跟随。 - Lance

在JS中添加示例 - diginoise

Answer 2

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

创建一个包含从0到k-1的数字的n个值的数组，例如[a₀=0，a₁=1，...，a_k=0，...，a_n=n％k]，并且这些数字分布大致相等。

然后对于初始集合中的每个k个值（其中i = 0..k-1），将此数组的第k个元素更改为i，可以通过直接赋值或与其他值交换来实现（注意不要覆盖先前设置的先前元素的值集）。

然后要散列值y，只需从该数组中获取第y个值。

---

演示

Here's a Javascript demo that basically implements the above algorithm, except that instead of pre-filling the array with values from 0 to k-1, it first inserts the hash values for the selected items, then fills the remaining items with the repeating sequence of numbers from 0 to k-1. You will probably get better collision resistance by using a random sequence instead of incrementing values, but I hope you get the picture.

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>

- r3mainer

---

听起来很有趣！试着跟上。第一段我大部分都能理解。假设我们有array.length == 100，里面有值1 2 3 4 5（如果桶大小为5），就像[1, 4, 5, 5, 1, 2, 1, 1, 3, 3, 5, 3, 2, ...]，以某种方式生成并均匀分布。然后只需将数组的第k个元素更改为i。所以[...,i=20,value=5,...,i=50,value=4,...]。类似这样的东西。嗯。不确定为什么是随机间隔的数字。还不完全确定我是否理解了，但它似乎是我正在寻找的！谢谢。也许如果您能添加一个示例会更好 :) - Lance

不确定为什么要这样做：“创建一个包含从0到k-1的数字的n个值的数组，数量大致相等，例如[a0 = 0，a1 = 1，...，ak = 0，...，an = n％k]。” - Lance

Answer 3

如果您想要一个不是直接映射的函数，您也可以尝试 多项式回归。

这里是一个使用一些在 GNU 许可下的 免费代码 的 JavaScript 示例。

/***************************************************************************
 *   Copyright (C) 2018 by Paul Lutus                                      *
 *   [e-mail]                                                  *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

// classic Gauss-Jordan matrix manipulation functions

var gj = gj || {}

gj.divide = function(A,  i,  j,  m) {
  for (var q = j + 1; q < m; q++) {
    A[i][q] /= A[i][j];
  }
  A[i][j] = 1;
}

gj.eliminate = function(A, i, j, n, m) {
  for (var k = 0; k < n; k++) {
    if (k != i && A[k][j] != 0) {
      for (var q = j + 1; q < m; q++) {
        A[k][q] -= A[k][j] * A[i][q];
      }
      A[k][j] = 0;
    }
  }
}

gj.echelonize = function(A) {
  var n = A.length;
  var m = A[0].length;
  var i = 0;
  var j = 0;
  var k;
  var swap;
  while (i < n && j < m) {
    //look for non-zero entries in col j at or below row i
    k = i;
    while (k < n && A[k][j] == 0) {
      k++;
    }
    // if an entry is found at row k
    if (k < n) {
      //  if k is not i, then swap row i with row k
      if (k != i) {
        swap = A[i];
        A[i] = A[k];
        A[k] = swap;
      }
      // if A[i][j] is != 1, divide row i by A[i][j]
      if (A[i][j] != 1) {
        gj.divide(A, i, j, m);
      }
      // eliminate all other non-zero entries
      gj.eliminate(A, i, j, n, m);
      i++;
    }
    j++;
  }
}

// a simple data class

function Pair(x,y) {
  this.x = x;
  this.y = y;
};

Pair.prototype.toString = function() {return x + ',' + y};

// matrix functions

var matf = matf || {}

// a weak substitue for printf()

matf.number_format = function(n,p,w) {
  s = n.toExponential(p);
  while(s.length < w) {
    s = ' ' + s;
  }
  return s;
}

// produce a single y result for a given x

matf.regress = function(x, terms) {
  var y = 0;
  var m = 1;
  for (var i = 0; i < terms.length;i++) {
    y += terms[i] * m;
    m *= x;
  }
  return y;
}

// compute correlation coefficient

matf.corr_coeff = function(data, terms) {
  var r = 0;
  var n = data.length;
  var sx = 0;
  var sx2 = 0, sy = 0, sy2 = 0, sxy = 0;
  var x, y;
  for (var i = 0;i < data.length;i++) {
    pr = data[i];
    var x = matf.regress(pr.x, terms);
    var y = pr.y;
    sx += x;
    sy += y;
    sxy += x * y;
    sx2 += x * x;
    sy2 += y * y;
  }
  var div = Math.sqrt((sx2 - (sx * sx) / n) * (sy2 - (sy * sy) / n));
  if (div != 0) {
    r = Math.pow((sxy - (sx * sy) / n) / div, 2);
  }
  return r;
}

// compute standard error

matf.std_error = function(data, terms) {
  var  r = 0;
  var  n = data.length;
  if (n > 2) {
    var a = 0;
    for (var i = 0;i < data.length;i++) {
      pr = data[i];
      a += Math.pow((matf.regress(pr.x, terms) - pr.y), 2);
    }
    r = Math.sqrt(a / (n - 2));
  }
  return r;
}


// create regression coefficients
// for provided data set
// data = pair array
// p = polynomial degree

matf.compute_coefficients = function(data,  p) {
  p += 1;
  var n = data.length;
  var r, c;
  var rs = 2 * p - 1;
  //
  // by request: read each datum only once
  // not the most efficient processing method
  // but required if the data set is huge
  //
  // create square matrix with added RH column
  m = Array();
  for (var i = 0; i < p; i++) {
    mm = Array();
    for (var j = 0; j <= p; j++) {
      mm[j] = 0;
    }
    m[i] = mm;
  }
  //double[][] m = new double[p][p + 1];
  // create array of precalculated matrix data
  mpc = Array();
  for(var i = 0;i < rs;i++) {
    mpc[i] = 0;
  }
  mpc[0] = n;
  for (var i = 0;i < data.length;i++) {
    pr = data[i];
    // process precalculation array
    for (r = 1; r < rs; r++) {
      mpc[r] += Math.pow(pr.x, r);
    }
    // process RH column cells
    m[0][p] += pr.y;
    for (r = 1; r < p; r++) {
      m[r][p] += Math.pow(pr.x, r) * pr.y;
    }
  }
  // populate square matrix section
  for (r = 0; r < p; r++) {
    for (c = 0; c < p; c++) {
      m[r][c] = mpc[r + c];
    }
  }
  // reduce matrix
  gj.echelonize(m);
  // extract result column
  terms = Array();
  for (var i = 0;i < m.length;i++) {
    mc = m[i];
    terms[i] = mc[p];
  }
  return terms;
}

// test the system using known data

matf.test = function() {
  var xd = [-1,0,1,2,3,5,7,9];
  var yd = [-1,3,2.5,5,4,2,5,4];
  
  data = Array();
  
  for(var i = 0;i < xd.length;i++) {
    data[i] = new Pair(xd[i],yd[i]);
  }
  
  terms = compute_coefficients(data,6);
  
  var prec = 16;
  
  var width = 24;
  
  for(var i = 0;i < terms.length;i++) {
    print(number_format(terms[i],prec,width) + ' * x^' + i);
  }
  
  cc = corr_coeff(data,terms);
  
  print ('cc = ' + number_format(cc,prec,width));
  
  se = std_error(data,terms);
  
  print('se = ' + number_format(se,prec,width));
}

//test();

// "data" is an array of Pair(x,y) data
// p = polynomial degree

matf.process_data = function(data,p) {
  var terms = matf.compute_coefficients(data,p);
  var cc = matf.corr_coeff(data,terms);
  var se = matf.std_error(data,terms);
  return [terms,cc,se];
}

/**** END Paul Lutus' code ****/


function f(cs, x){
  let n = cs.length - 1;
  let result = 0;
  for (let i=0; i<cs.length; i++)
    result += cs[i] * Math.pow(x, i);
  return result;
}

var data = [[1,1], [5,2], [20,3], [50,4], [100,5]];
var xy_data = []

for (let i of data)
  xy_data.push(new Pair(i[0], i[1]));

var result = matf.process_data(xy_data, xy_data.length - 1);

for (let i=0; i<data.length; i++)
  console.log(data[i][0], f(result[0], data[i][0]));

- גלעד ברקן