有没有一个函数取两个值,让f(x,y)==f(y,x),输出是唯一的?

一些功能 f(x, y)

• f(x, y) == f(y, x)
• f(x, y) != f(a, b) => (x == a 和 y == b )或者( x == b y == a )

会有很多这样的东西-我能想到的就是“排序连接”:

1. (x, y) 任何命令
2. 应用哈希函数 u(a) 到 x y 单独(其中 u(a) == u(b) 暗示 a == b ,以及 (为常数)
3. 连接 u(x) 和 u(y)

如果 x == y 那么这两个散列就非常相似了,所以不失一般性 x < y 因此:

• f(y, x) = u(x) + u(y) = f(x, y)

另外,如果 f(x, y) == f(a, b) ,这意味着:

• u(x) == u(a) u(y) == u(b) => x == a 和 y==b
• u(y) == u(a) 和 u(x) == u(b) => y==a 和 x==b

对x和y进行排序,然后应用任何哈希函数,其中得到的哈希长度是常量。

orderIndifferentHash 你可以先点 val1 和 val2 然后应用任何你喜欢的哈希函数来得到结果。

function orderIndifferentHash( val1, val2 ) {
  if( val1 < val2 ) {
    first = val1
    second = val2
  }
  else {
    first = val2
    second = val1
  }
  hashInput = concat( first, second )
  return someHash( hashInput )

  // or as an alternative:
  // return concat( someHash( first ), someHash( second ) )
}

对于数字,一种方法是两个数字 x 和 y 十 和 独立于论证顺序。当然,为了实现任何实际意义上的效率,您需要为所有可能的值保留一个素数表 十 和 是的 . 如果 十 从相对较小的范围内选择,这将起作用。但是如果范围很大,表本身就变得非常不切实际,你将别无选择,只能接受一些冲突概率(比如保持一个大小合理的N素数表,并为给定的值选择x%N个素数) 十 ).

其他答案中已经提到的另一种解决方案是构建一个完美的哈希函数,该函数可以在 和 十 和 . 通过预排序实现顺序无关性 十 和 是的 . 当然,构建一个完美的散列只有在一个合理的小范围内的一组参数才有可能。

有些事情告诉我,基于素数的方法将为您提供满足所需条件的尽可能短的哈希。 不,不是真的。

假设你有杂烩 h(x,y) . 然后定义 f(x,y) = h(x,y) + h(y,x) . 现在有一个对称散列。