Когда хеш-функции ортогональны друг другу?

Question

Когда хеш-функции ортогональны друг другу?

А можете ли вы привести в Java пример двух хеш-функций, которые ортогональны друг другу?

Answer 1

От (документ с результатами поиска Google)

(Ортогональные хеш-функции) Две хеш-функции h1 и h2 ортогональны, если для всех состояний s, s' ∈ S с h1 (s) = h1 (s') и h2 (s) = h2 (s'), мы имеем s = s'.

С. Эделькамп, Идеальное хеширование для государственного освоения космоса на 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.

Answer 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

Выше h1(s) = h1(s') для пар значений s которые либо 0 отдельно или 5 Кроме. Для h1 расстояние либо 0 или же 7,

Единственные пары, для которых выполняются оба условия, это те, где расстояние 0 - так только когда s1 == s2, Таким образом, это ортогональные (хотя и несовершенные) хеш-функции.

И это, я думаю, отвечает на обе части вашего вопроса.