Perfect hashing function and benefits

Question

Consider this class :

    public final class MyDate {
        private int year, month, day;

        public MyDate(int year, int month, int day) {
             this.year = year;
             this.month = month;
             this.day = day;
        }

        //Some stuff

        @Override
        public int hashCode() {
             return ((year << 4) | month) << 5 | day;
        }
}

This is a perfect hashing function because in the memory we have :

enter image description here

So in red, 5 bits store the day (1 to 31), in yellow 4 bits store the month (1 to 12) and the others store the year (1 to 16777215).

What's the benefit of a perfect hashFunction ? AFAIK, it can guaranted the add/remove/contains in O(1) in an HashSet but could I get other benefits of having one ?

I saw that many hash functions use prime numbers, what's the best manner to construct one (I imagine that create a perfect hashfunction is uncommun/rare) ?

EDIT :

About prime numbers -> answered here

your perfect hash function is only useful if the underlying hash array is sized to fit all possible values (which is unlikely with a jdk HashSet/HashMap). — jtahlborn, May 07 '13 at 20:08
I don't get it: why put a date in a hashset when I can easily create a new instance when I need one? — Andy, May 07 '13 at 20:50

score 8 · Accepted Answer · answered May 07 '13 at 20:11

A perfect hash function guarantees that you'll have no collisions. However, in order to be able to use one, you have to know exactly the set of key values that will need to be hashed, which is often not the case.

Others not so perfect, but still good hash functions (along with a collision resolution mechanism) don't have that requirement and are very fast to compute anyway, so they are often more appropriate.

score 1 · Answer 2 · answered May 07 '13 at 21:09

As per Juampi it's fast. How fast? Approximately O(1). Redis is a great example of constant time lookups in memory through hash table.

If you do not have a bucket of exactly one element on the results of the hash you then need to use equals to compare each item so you get lookup of O(1 plus z) where z is the bucket size.

But yes very slow hash functions certainly aren't a great idea after.

Perfect hashing function and benefits

2 Answers2