CODEWITHSUNDEEP
algorithmhash
shiv shah
shiv shah

Reputation: 77

Perfect Hashing Time Complexity

Would a perfect hash have delete insert and search in 0(1) time? If so then why don't computer scientists use perfect hashing all the time if not what would be the time complexity?

Upvotes: 2

Views: 1226

Answers (1)

Adam Kotwasinski
Adam Kotwasinski

Reputation: 4574

Would a perfect hash have delete insert and search in 0(1) time?

Yes, as you'd get only one-element buckets. So you get as many buckets as there are elements.

If so then why don't computer scientists use perfect hashing all the time if not what would be the time complexity?

One of the reasons is theoretical. Perfect hash function is injective, and definition of such a function might be difficult if not impossible.

Consider following trivial structure:

{
  int x;
  int y;
}

Basically you want to have your hash() function to give unique results for every possible values of x and y, this might not be possible. Basically for trivial ones like x + y, x * y, x ^ y, you can always create another input that would give the same result.

On the other hand, it's possible (as |N^2| = |N| = aleph-null) - see Cantor pairing function.

The other of the reasons is practical - your return function has to have a return type. The return type would need to be capable of storing all possible injection results - so for hash of two 32-bit values it would need 64 bits, for three 3 * 32 etc. (compare that above mentioned pairing function effectively multiplies the arguments)

Upvotes: 1

Related Questions