Perfect Hash Function just an Injection?

Question

I just read up on the concept of perfect hash functions on a set $S$. I am quoting:

"A perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions."

It seems to me it's just lingo for an injection to $\mathbb{N}$. I am wondering whether this is correct, or whether there are subtleties that I am missing or whether there are more useful definitions that add subtleties that I am currently not aware of.

Answer 1

First a note on the concept of a hash function:

A hash function is more a cloud of ideas than a single definition. In its plainest form, a hash function is merely a function $h : S \to T$, possibly randomized. However, depending on the context and the reader, the term hash could imply any of the following (and this list is likely not exhaustive):

1. $h$ does not have any collisions (or, collisions occur with low probability). Sometimes we incorporate this property into the name, and call such a function a collision-resistant hash.

2. $h$ has some limited independence property. For instance, a pairwise-independent hash is a randomized function $h : S \to T$ such that for any distinct $s_1, s_2 \in S$, the $T$-valued random variables $h(s_1)$ and $h(s_2)$ are independent.

3. We can use $h$ to store and retrieve $S$ quickly. Here we could think of $S$ as some data, and $T$ as the bins to hold it.

For the items (1.) and (2.) above, it is usually sufficient to consider $h$ as a mathematical function with some additional properties; but this does not give the complete picture for (3.). For item (3.), we might also fast algorithms to compute $h$, to perform insertions and lookups, and so on. Such a collection of algorithms is sometimes called a hashing scheme/*technique*, or a hash function construction. (More details on this follow.)

---

Perfect hashing.

Definition 1: Let me quote from the introduction in the section on perfect hashing in Cormen et. al., Introduction to Algorithms (2nd ed., Chapter/Section 11.5, p. 245):

Although hashing is most often used for its excellent expected performance, hashing an be used to obtain excellent worst-case performance when the set of keys is static: once the keys are stored in the table, the set of keys never changes. Some applications naturally have static sets of keys: consider the set of reserved words in a programming language, or the set of file names on a CD-ROM. We call a hashing technique perfect hashing if the worst-case number of memory accesses required to perform a search is $O(1)$.

From this paragraph, it is clear that (at least from the point of view of this book), the difference between a regular hash function and perfect hash function is not that perfect hashing is injective, but that we get a guaranteed worst-case performance. (It is possible that worst-case guarantee would be considered attractive by these authors, simply because this is a textbook on the mathematical aspects of algorithms. Perhaps a systems engineer might care more about the fast search time than the fact that this is worst-case.)

Definition 2: Here's a slightly different definition. The following excerpt is from Djamal Belazzougui, Fabiano C. Botelho, and Martin Dietzfelbinger, Hash, Displace, and Compress, referenced in the Wikipedia article on Perfect hash function:

In this paper, we study the problem of providing perfect hash functions, minimal perfect hash functions, and $k$-perfect hash functions. In all situations, a “universe” $U$ of possible keys is given, and a set $S \subseteq U$ of size $n = |S|$ of relevant keys is given as input. The range is $[m] = \{0, 1, \ldots , m − 1\}$.

Definition. (a) A function $h: U \to [m]$ is called a perfect hash function (PHF) for $S \subseteq U$ if $h$ is one-to-one on $S$. (b) A function $h: U \to [m]$ is called a minimal perfect hash function (MPHF) for $S \subseteq U$ if $h$ is a PHF and $m = n = |S|$. (c) For integer $k \geq 1$, a function $h: U \to [m]$ is called a $k$-perfect hash function ($k$-PHF) for $S \subseteq U$ if for every $j \in [m]$ we have $|\{x \in S \mid h(x) = j\}| \leq k$.

“A hash function construction” consists in the following: We consider algorithms that for a given set $S$ construct a (static) data structure DS such that using DS on input $x \in U$ one can calculate a value $h(x) \in [m]$, with the property that $h$ is a PHF (MPHF, $k$-PHF) for $S$. The evaluation time should be constant.

Perfect hashing can be used in many applications in which we want to assign a unique identifier to each key without storing any information on the key. One of the most obvious applications of perfect hashing (or $k$-perfect hashing) is when we have a small fast memory in which we can store the perfect hash function while the keys and associated satellite data are stored in slower but larger memory. The size of a block or a transfer unit may be chosen so that $k$ data items can be retrieved in one read access. In this case we can ensure that data associated with a key can be retrieved in a single probe to slower memory. This has been used for example in hardware routers. Perfect hashing has also been found to be competitive with traditional hashing in internal memory on standard computers. Recently perfect hashing has been used to accelerate algorithms on graphs when the graph representation does not fit in main memory.

(I suppressed the references cited in the above paragraph.)

Notice that these authors segregate the mathematical aspect --for want of a better phrase-- of $h$ (i.e., it is one-to-one on a given subset $S$) from the computation aspect. This is usually done so that the author could focus on one or the other aspect; however, the computation aspect seldom just disappears completely.