Is there any pedagogically motivated reason to teach quadratic probing?

Question

I'm currently preparing a unit on the implementation of hash tables for a data structures and algorithms course (this is a university-level class if it matters).

Specifically, I'm focusing on preparing a lecture on different collision resolution strategies, focusing mainly on separate chaining, linear probing, quadratic probing, and double hashing.

My question is this: why do we teach quadratic probing at all?

I initially added quadratic probing to my todo list mainly because previous instructors of my course taught it and because it's listed in several textbooks I consulted (Data Structures and Algorithm Analysis in Java by Weiss, and Introduction to Algorithms by Cormen, et. al.)

However, I'm not really seeing the pedagogical value of doing so. While it's true that it does offer some minor theoretical speedups over linear probing which I suppose might be interesting to discuss, I don't think those speedups are actually "good enough" to be used in the wild (especially once you take into account things like cache locality, which can sometimes make linear probing surprisingly competitive).

Based on my (admitted informal and ad-hoc) survey of hash table implementations in popular programming languages, people seem to either use separate chaining (Java and C# (sort of)), double hashing (GCC's C++ stdlib implementation), or a linear congruential PRNG (Python).

In that case, is it worth bringing it up at all? I wouldn't mind covering it if I could use it as a vehicle to teach some more general CS concept in some way, or if it had interesting theoretical properties worth exploring, even if only briefly, but at the moment, it just doesn't seem worth the class time.

I suppose at best, I could use it as a stepping stone to bridge the gap between linear probing and some slightly more complicated technique, such as double hashing, but that's all I can think of.

Is there something I'm missing?

Answer 1

Yes, you should at least introduce the idea to your students.

That said, it is also a truism of education that you need not explain every concept at the same level of detail. In this particular case the first couple of paragraphs of the Wikipedia article on the subject is probably enough. A couple of minutes could be well-spent.

Students need to know that there are a range of solutions to any given problem and that those possible solutions have trade-offs. This is an excellent opportunity to stress that. Linear probing creates bottlenecks in some situations (poor hash functions for example). That can be a problem. Quadratic probing, while more complex, does a bit better. It might be easier to implement than trying to guarantee better hashes over which the programmer may have less control. Even if that particular solution is never used by your students they will encounter such choices in the future. Help them get ready for it.

By pure serendipity, Eugene Wallingford's blog post just yesterday discusses a related topic. Blog: Jan22-2018, "Same Footage, Different Film"

Answer 2

Although you did not specifically mention it, you might also discuss collision free hash functions. They are useful for situations where the "keys" are fixed or only change very slowly over time. A very common situation is the reserved keywords of a language. Other examples are the abbreviation of states for postal delivery, or the airport label on baggage tags.

For another example, we use a "help" program that simply displays a queue of students waiting for help. It lists their name and course and computer name. To join the queue, the student executes the command ~csXXX/bin/help. The machines in our labs are arranged alphabetically. so it help the TA find student. But, we need to map the machine name to a room number, so the TA only sees a list for the room they are in. The set of computers is static in that we rarely get new ones. One doesn't really need a hash table for the small number of machines (< 200), but it is interesting to play with tools like the gnu https://www.gnu.org/software/gperf to see how a hash function can be "designed" to map a known set of strings without collision.

Answer 3

In his Algorithms Jeff Erickson discusses and analyses a similar variant, which he calls binary search (a terrible name, if you ask me): For a table of size a power of 2 when searching for key $k$, the idea is to check positions $h(k) \oplus r$, where $\oplus$ is bit-by-bit exclusive or and $r$ is the number of the try. It shares the benefit of quadratic probing that the probe sequence depends on the start point $h(k)$ (not just the fact that the search landed there, thus avoiding primary clustering), it searches all the table (modulo a prime $m$ --table size-- just half the positions are squares, so quadratic search will only look at half the table), and it has much better locality (it looks at an expanding window into the table).