Hash Function

When we have m < |U|, we need some way of shoe-horning the universe into the table.

A hash function $h:U\rightarrow [0,m-1]$ does this for us.

The hash value of an object $k\in U$ is h(k).

A perfect hash function has the property that all the inserted objects K have a unique hash value.

For a perfect hash function h:

• Insert(k): $T[h(k)] \leftarrow k$
• Delete(k): $T[h(k)] \leftarrow \mbox{empty}$
• Find(k): h(k)
• Member(k): $T[\mbox{Find}(k)] = 1$?

Acts just like the direct-address table: everything O(1) worst case.