java - 哈希函数什么时候相互正交？

Question

哈希函数什么时候相互正交？

您能否提供一个 Java 中两个相互正交的哈希函数的示例？

Answer 1

来自 ( a Google search result paper )

(Orthogonal Hash Functions) 两个哈希函数h1和h2是正交的， 如果对于所有状态 s，s' ∈ S 且 h1 (s) = h1 (s') 和 h2 (s) = h2 (s') 我们有 s = s'。

S。 Edelkamp，用于 GPU 上状态空间探索的完美哈希。

在英语中，如果传递给两个不同的正交哈希函数的任何两个给定值产生相同的输出，则这些输入必须具有相同的值。

例子:

Let h and g be hash functions.
Let b be a currently unknown value.
h(0) = h(b) = 5
g(0) = g(b) = 4
if h and g are orthogonal, b MUST equal 0.

Thus for any values given to h that result in a unique result,
If those same values are given to g, they must also result in a unique result,
  IF they are orthogonal hash functions.

伪代码:

// Assume no wraparound will ever occur due to overflow.
HashFunc h = x -> x + 1;
HashFunc g = y -> y + 2;
h(0) = 1 // No other input value results in --> 1
g(0) = 2 // No other input value results in --> 2
// These must have been orthogonal hash functions.

// Now for some non-orthogonal hash functions:
// Let the domain be integers only.
HashFunc j = x -> ceil(abs(x / 2));
HashFunc k = x -> ceil(sqrt(x));
j(0) = 0 // Unique result
k(0) = 0 // Unique result
j(1) = j(2) = 1
k(1) = 1 != k(2) = 2 
// k(1) results in a unique value, but it isn't unique for j.
// These cannot be orthogonal hash functions.