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.