# Can someone offer an intuitive understanding of linear/quadratic probing and double hashing?

I'm reading through Introduction to Algorithms, and I'm having trouble grasping intuitively how linear probing, quadratic probing, and double hashing exactly work. I suspect my confusion lies within my hazy understanding of hashing itself, so I'd appreciate if anyone could clear up these areas and help me grasp the concepts. Here's what the textbook has to say about linear probing and quadratic probing:

What does it mean to "first probe T[h'(k)]?" Also, what is "then we wrap around to slots T[0],...?" I'm also confused as to what primary clustering means; in particular, the part that talks about "long runs of occupied slots [building] up..."

Any help would be great. Thank you.

• For historical perspective, probing was introduced in Communion by Whitley Streiber. – Will Jagy Apr 11 '13 at 23:22
• @WillJagy. Yuck! (reluctantly, +1) – Rick Decker Apr 12 '13 at 1:19
• @RickDecker if you google wiki probing one of the first few responses is completely informative. And very funny. – Will Jagy Apr 12 '13 at 1:50

In both cases, as you probably know, you have a universe of objects, $U$, and you wish to insert a number $n\le m$ of these objects into an array $T = T[0], T[1], \dots, T[m-1]$ with no more than one object in each array slot (commonly known as a bucket) . One way to do this is to use a hash function $h(x)$ that maps $U$ into the set of array indices $\{0, 1, \dots, m-1\}$. The problem is that the size of $U$ is generally larger than $m$, the number of buckets in the array, so you have the potential that two different objects in your universe might be sent by $h$ to the same bucket, known as a collision. In other words, you might have different objects $x_1, x_2$ such that $h(x_1) = h(x_2)$. To handle situations like this, you need not only a hash function, but also a protocol to deal with collisions when they occur.
In linear probing, the protocol to insert an object $x$ into the array is to first look at the bucket at index $h(x)$, namely $T[h(x)]$, which is what your notes refer to as the "first probe". If that bucket, $T[h(x)]$ is already occupied by an object other than $x$, you then try to insert $x$ into $T[h(x)+1]$. If that doesn't work, you try to insert $x$ into $T[h(x)+2], T[h(x)+3]$, and so on, until you find a vacant bucket or reach the last slot, $T[m-1]$ in your array. What do you do if you come to the last slot and haven't found a place yet for $x$? A simple way is to do what your notes call "wrap around", namely continue searching, starting at the top bucket, $T[0]$ and continuing to search at $T[1], T[2], T[3]$ and so on, which explains the $\mod m$ in your notes. Unless the hash table is completely full, this strategy will always find an available slot for the object $x$.
A good way to see this in action is to try an example. Suppose, for instance, you have a hash table with 11 buckets and a very simple hash function from the integers into the indices $\{0, 1, 2, \dots, 10\}$ given by $h(x)=(11 \mod x)$, try inserting a collection of numbers like $2, 17, 21, 35, 47, 13, 3, 6, 46, 29,10$ in that order and count the number of probes required using linear probing. Then compare that with quadratic probing, using successive probes given by $i^2+2i$. In other words, from an initial probe to index $h(x)=t$, look at slots $$t+3, t+8, t+4, t+2, t+2, t+4, t+6, t+8, t+10, t+1$$ if necessary, wrapping $\mod 11$ to keep the indices in range. Count the number of probes this takes; it should be less than linear probing (though I haven't tried it).
• Let's say that the slots of your hash table are $T[0], \dots T[12]$ so you have 13 slots. Suppose you're using linear probing, trying to insert an element into $T[10]$ and suppose that slot and $T[11], T[12]$ are already occupied. Probing into $T[10], T[11]$ and $T[12]$ fails to find a vacant slot, so you continue with $T[0], T[1], T[2],\dots$ until you found a vacant slot. It's as if your array was arranged in a circle, rather than a linear segment.. – Rick Decker Apr 16 '13 at 12:10