散列函数何时相互正交？ [英] When are hash functions orthogonal to each other?

问题描述

你能否提供一个Java中的两个相互正交的散列函数的例子？

解决方案

From（ Google搜索结果文件）

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

S。在英语中，如果传递给两个不同正交散列函数的任何两个给定值导致相同的输出，那么这些输入

示例：

 让h g是散列函数。 
设b是当前未知的值。 
h（0）= h（b）= 5 
g（0）= g（b）= 4 
如果h和g是正交的，b必须等于0. 
 
因此，对于赋予h的任何给出唯一结果的值，
如果为g赋予相同的值，则它们还必须产生唯一的结果，
如果它们是正交散列函数。 
  

伪代码：

  //假定由于溢出而不会发生环绕。 
 HashFunc h = x  - > x + 1; 
 HashFunc g = y  - > y + 2; 
 h（0）= 1 //没有其他输入值导致 - > 1 
 g（0）= 2 //没有其他输入值导致 - > 2 
 //这些必须是正交散列函数。 
 
 //现在对于一些非正交散列函数：
 //让域只有整数。 
 HashFunc j = x  - >细胞（abs（x / 2））; 
 HashFunc k = x  - >小区（SQRT（X））; 
j（0）= 0 //唯一结果
k（0）= 0 //唯一结果
j（1）= j（2）= 1 
k（1）= 1！ = k（2）= 2 
 // k（1）产生一个唯一的值，但它对于j不是唯一的。 
 //这些不能是正交散列函数。 
  

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?

解决方案

From (a Google search result paper)

(Orthogonal Hash Functions) Two hash functions h1 and h2 are orthogonal, if for all states s, s' ∈ S with h1 (s) = h1 (s') and h2 (s) = h2 (s') we have s = s'.

S. Edelkamp, Perfect Hashing for State Space Exploration on the GPU.

In English, if any two given values passed to two different orthogonal hash functions result in the same outputs, those inputs must have been the same value.

Example:

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.

Pseudocode:

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

这篇关于散列函数何时相互正交？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！