Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
I think there are a few variations of the definition in the literature, in which case we have no way to guess which one you are talking about. Please make the post self-contained by adding this. –  Srivatsan Jan 27 '12 at 14:28
    
thanks, for instance I was not aware, that the concept has various definitions that do not agree. I d be interested in that case for instance which is the most common or most useful one. –  Beltrame Jan 27 '12 at 14:37
1  
I think I must take back my claim about multiple definitions. (It is from a fuzzy memory. I don't know for sure that it is false either.) Sorry about this. Anyway, I checked Cormen et. al., Introduction to Algorithms, here's their definition: "We call a hashing technique perfect hashing if the worst-case number of memory accesses required to perform a search is $O(1)$." According to this, perfect hashing is more about the time complexity of accessing the element, not merely about hashing different elements into different bins. (I have not seen the definition in Wikipedia before.) –  Srivatsan Jan 27 '12 at 14:44
1  
Yeah, in the language of mathematics, you could call it an injection. –  Thomas Andrews Jan 27 '12 at 15:48
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
ok, this makes more sense now. Would it be correct to say that performance and injectivity of the hash function are very closely linked ? For instance if we implement the hash table with a linked list appended to collisions, then in order to guaranteed worst case 0(1) we need to ensure injectivity right ? –  Beltrame Jan 27 '12 at 16:22
1  
@PeeJay Traditionally, one talks about collisions, which is pretty much the opposite of injectivity. The study of collisions in hash functions is an extensive topic by itself: you could begin by looking up open hashing and chaining method in (e.g.) Cormen. You will notice that when people say the term "hash", they may not literally mean a single function; it could actually mean a more complicated hashing scheme, consisting of a hierarchy of hashes, or a collection of several hash functions. In these scenarios, it is not even clear to me what injectivity means. –  Srivatsan Jan 27 '12 at 16:29
1  
@PeeJay On the other hand, when we do think of a hash as a single function, if we do not have injectivity, that might lead to a potential loss of data due to collisions, which could be even more of a problem (depending on the application). Of course, one fix is to augment the hash function with a collision-resolution scheme; but then the resulting thing is what I've been calling a hash function scheme in this answer. Once again, the terms open hashing and closed hashing are relevant keywords. –  Srivatsan Jan 27 '12 at 16:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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