哈希函数 returns 即使不同的项导致相同的总和，相同的哈希值也是如此

Question

假设我有：

n = 14

n 是以下整数和的结果：

[5, 2, 7] -> 5 + 2 + 7 = 14 = n
[3, 4, 5, 2] -> 3 + 4 + 5 + 2 = 14 = n
[1, 13] -> 1 + 13 = 14 = n
[13, 1] -> 13 + 1 = 14 = n
[4, 3, 5, 2] -> 4 + 3 + 5 + 2 = 14 = n
...

我需要一个哈希函数 h 以便：

h([5, 2, 7]) = h([3, 4, 5, 2]) = h([1, 13]) = h([13, 1]) = h([4, 3, 5, 2]) = h(...)

即整数项的顺序无关紧要，只要它们的整数和相同，它们的散列也应该相同。

我需要在不计算总和 n 的情况下执行此操作，因为项以及 n 可能非常高并且很容易溢出（它们不适合 int), 这就是我问这个问题的原因。

您知道或者您是否了解我如何实现这样的哈希函数？给定 list/sequence 个整数，如果整数的总和相同但不计算总和，则此散列函数必须 return 相同的散列。

感谢您的关注。

编辑：我详细阐述了@derpirscher 的回答并进一步修改了他的函数，因为我在 BIG_PRIME 的倍数上发生了碰撞（这个例子在 JavaScript 中）：

function hash(seq) {
  const BIG_PRIME = 999999999989;
  const MAX_SAFE_INTEGER_DIV_2_FLOOR = Math.floor(Number.MAX_SAFE_INTEGER / 2);
  let h = 0;
  for (i = 0; i < seq.length; i++) {
    let value = seq[i];
    if (h > MAX_SAFE_INTEGER_DIV_2_FLOOR) {
      h = h % BIG_PRIME;
    }
    if (value > MAX_SAFE_INTEGER_DIV_2_FLOOR) {
      value = value % BIG_PRIME;
    }
    h += value;
  }
  return h;
}

我现在的问题是：你觉得这个功能怎么样？是否有一些我没有考虑到的边缘情况？

谢谢。

编辑 2：

使用上面的函数 hash([1,2]); 和 hash([4504 * BIG_PRIME +1, 4504 * BIG_PRIME + 2]) 会像@derpirscher 提到的那样发生碰撞。

这是上述函数的另一个修改版本，如果两项中的任何一项大于 MAX_SAFE_INTEGER_DIV_2_FLOOR：[=27=，则仅对两项中的一项计算模 % BIG_PRIME ]

function hash(seq) {
  const BIG_PRIME = 999999999989;
  const MAX_SAFE_INTEGER_DIV_2_FLOOR = Math.floor(Number.MAX_SAFE_INTEGER / 2);
  let h = 0;
  for (let i = 0; i < seq.length; i++) {
    let value = seq[i];
    if (
      h > MAX_SAFE_INTEGER_DIV_2_FLOOR &&
      value > MAX_SAFE_INTEGER_DIV_2_FLOOR
    ) {
      if (h > MAX_SAFE_INTEGER_DIV_2_FLOOR) {
        h = h % BIG_PRIME;
      } else if (value > MAX_SAFE_INTEGER_DIV_2_FLOOR) {
        value = value % BIG_PRIME;
      }
    }
    h += value;
  }
  return h;
}

我认为这个版本进一步降低了碰撞次数。

你怎么看？谢谢。

编辑 3：

尽管我试图详细说明@derpirscher 的回答，但他对 hash 的实施是正确的，也是可以使用的。

如果您需要这样的哈希函数，请使用他的版本。

Answer 1

您可以对某个大质数求模求和。如果你想保持在 int 的范围内，你需要知道最大整数是多少，在你使用的语言中。然后 select BIG_PRIME 就在 maxint / 2

下面

假设 int 为 4 个字节，maxint = 2147483647 因此最大素数 < maxint/2 将是 1073741789;

int hash(int[] seq) {
  BIG_PRIME = 1073741789;
  int h = 0;
  for (int i = 0; i < seq.Length; i++) {
    h = h % BIG_PRIME + seq[i] % BIG_PRIME;
  }
  return h;
}

因为在每一步中，两个被加数都将始终低于 maxint/2 你不会得到任何溢出。

编辑

从数学的角度来看，以下属性可能对您的用例很重要：

(a + b + c + ...) % N  == (a % N + b % N + c % N + ...) % N

但是，是的，当然，在每个散列函数中都会有冲突。你不可能有没有冲突的散列函数，因为散列函数域的大小（即可能的输入值的数量）通常比共域的大小（即可能的输出值的数量）大得多.

对于您的示例，域的大小（原则上）是无限的，因为您的序列中可以包含 1 到 2000000000 之间的任意数字。但是你的codomain只是~2000000000个元素（即int的范围）

哈希函数 returns 即使不同的项导致相同的总和，相同的哈希值也是如此

Hash function that returns the same hash for a sum even if different terms lead to the same sum

hash

sum

hashcode

hash-function