When are hash functions orthogonal to each other?
And can you provide an example in Java of two hash functions that are orthogonal to each other?
问问题
670 次
2 回答
2
来自http://www.aaai.org/ocs/index.php/ICAPS/ICAPS10/paper/download/1439/1529
通过 Google 获得：（define "orthogonal hash"第二次点击）。
翻译：
如果你有一个“完美的散列函数”，那么h(s) == h(s') iff s == s'.
如果您有“任何两个散列函数”，其中有值s，s'则两者都有
h1(s) == h1(s') and h2(s) == h2(s')
如果以上对 s == s' 成立，则这些函数称为正交函数
这实际上是一个相当棘手的概念。如果 h1 和 h2 都是完美的散列函数，那么根据上述定义，它们将自动必须是正交的（如果我理解正确的话）。但是你可以有不完美的符合上述定义的函数。
示例：在状态空间[0, 9]中，两个函数
h1(int x) return x % 5;
h2(int x) return x % 7;
将是正交的：
x h1 h2
0 0 0
1 1 1
2 2 2
3 3 3
4 4 4
5 0 5
6 1 6
7 2 0
8 3 1
9 4 2
s在上面，对于0分开或分开的值对，h1(s) = h1(s') 5。对于 h1，距离是0或7。
两个条件都为真的唯一对是距离为的那些0- 所以只有当s1==时s2。因此，这些是正交（尽管不完美）的散列函数。
我认为，这回答了你问题的两个部分。
于 2014-02-11T18:27:14.700 回答
2
来自（谷歌搜索结果论文）
（正交散列函数）两个散列函数 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.
于 2014-02-11T18:03:48.887 回答