0
$\begingroup$

Is a perfect hash function always bijective ? In Wiki "In mathematical terms, it is a total injective function" but it does not mean, that it is bijective.

$\endgroup$
  • $\begingroup$ If the input domain is larger than the output, how could it be bijective? $\endgroup$ – mikeazo Oct 4 '15 at 23:38
  • 2
    $\begingroup$ Please note, that what you refer as a perfect hash is not a perfect hash in a cryptographic sense. A perfect cryptographic hash is random oracle and that is almost never injective. The Wikipedia article refers to hashing for non cryptographic purposes, e.g. database lookup. And that is a complete different story. $\endgroup$ – user27950 Oct 5 '15 at 7:48
2
$\begingroup$

No, it is not always bijective.

A perfect hash guarantees that no two inputs (from the set of valid inputs) collides, so it is clearly a 1 to 1 mapping. However, in the case where the output range contains more possible values than there were valid inputs, there will be outputs which do not map back to inputs. hence it is not bijective.

If you restrain the problem dramatically, and define the range of the outputs to be "the set of outputs attained from valid inputs," then you could argue it is bijective because you have constrained the output sufficiently to make such a claim. However, it would be up to you to explain why this very particular output range is a valid one for whatever topic is being discussed at that time.

$\endgroup$
1
$\begingroup$

The injective hash function wikipedia referes to is not a secure hash function for cryptographic purposes. It is a hash function used for fast database access.
An ideal secure hash function is a random oracle and a random oracle is not injective with very high probability.

$\endgroup$
0
$\begingroup$

Depends on how you define the function. A perfect hash function is a bijection from an input set onto a set of integers. However, that set of integers is not necessarily a continuous range, unless you have a minimal perfect hash function.

So if you define the function as mapping a particular set to e.g. $\mathbb{N}$ or $[1, n]$ where $n$ is larger than the size of the set, it is not a bijection.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.