Here's an explanation, to the best of my ability in a reddit post, and worked example that should help people wrap their heads around it.

The basic idea of this algorithm is to improve the long-term insertion performance of the hash tables by making the early insertions more expensive in exchange for making the later ones cheaper. This is specifically for making insertion into a hash table you know will get very full cheaper overall.

It's easiest to understand what this paper is doing by looking at an example. For this example, I'll use 0 to represent an open space, and X to represent a full space. I have spaces between each 4 slots in order to make it a little easier to keep track of position.

In each of these cases, we will be inserting 15 elements into a 16 element hash table, with each successive element denoted by 0-9, a-f. We know this ahead of time, that this table will be 93.75% full. The paper uses δ frequently to talk about fullness, where δ is defined as the proportion of the table that will be empty once all elements are inserted. In this case, δ is equal to 1-0.9375 = 0.0625.

Traditional Greedy Uniform Probing

The traditional (and previously believed to be optimal) approach is to randomly pick a sequence of slots to check for each element, and as soon as one is available, insert it in that location.

Let's walk through what that might look like:

OOOO OOOO OOOO OOOO

We insert our first element, 0, and get a random sequence of indices to check. For instance, it might look like [0, 6, 10, 4, ...]. We check index 0, see it is free, and insert 0 in that location. Now our hash table looks like

0OOO OOOO OOOO OOOO

Let's insert 3 more elements: 1, 2, 3. Element 1 gets a sequence starting with 4, and gets inserted there. Element 2 gets a sequence starting with 2, and gets inserted there. Element 3 has a sequence that looks like [2, 9, ...]. We check index 2, see it is occupied, and so then check index 9, which is free.

0O2O 1OOO O3OO OOOO

If we continue this process all the way up to e, we might get a table that looks like the below. Now, we need to insert e. The only available indices are 1 and 8. We generate a sequence for e, and it is [13, 12, 9, 7, 0, 4, 6, 8, 15, 14, 1, 5, 2, 3, 11, 10]. We needed to do 8 searches just to put a single element in!

0O24 15c8 O3b7 aO96

In this case, we had 2 out of 16 elements free. Each time we checked a new index, we had a 1/8[^1] chance to find a free space. On average, this will take 8 attempts.[^2] It turns out that when we have slightly larger examples that don't get quite so close to the last few elements of the hash table, the expected cost to insert the last few elements of the hash table is 1/δ. That is because each time you search for a place to insert an element, δ of the table will be empty.

For a long time, it was believed that was the best that you could do when you are inserting the last elements into the hash table without rearranging them.

The New Method

In this comment, I'm just going to go over the method that they call elastic probing in the paper. The basic idea of this approach is to split the array into sub-arrays of descending size, and only care about two of the sub-arrays at a time. We keep working on the first two sub-arrays until the first is twice as full as the eventual fullness, and then move our window. By doing extra work in early insertions, later insertions are much easier.

Unfortunately, it's difficult to fully demonstrate this with a toy example of size 16, but I will do my best to get the idea across. The paper works with 3/4 as their default fullness, but I will talk about 1/2 so that it works better. We have our first subarray of size 8, then 4, then 2 and 2. I've inserted | between each subarray. Label the arrays A1, A2, A3, A4.

OOOO OOOO|OOOO|OO|OO

First, we follow the normal rules to fill A1 1/2 of the way full:

OO03 21OO|OOOO|OO|OO

At any time, we are dealing with 2 successive subarrays. We say that A_i is e_1 free, and A_(i+1) is e_2 free.

At each insertion, we keep track of the current arrays we are inserting into, and follow these simple rules: 1. If A_i is less than half full, insert into A_i. 2. If A_i is more than twice as full as the eventual hash table, then move on to the next pair of subarrays, A_{i+1} and A_{i+2}. 3. If A_{i+1} is more than half full, insert into A_i. 4. Otherwise, try inserting into A_i a couple times, and if nothing is found, insert into A_{i+1}.

The first and second cases are relatively quick. The third case is actually very rare, which is specified in the paper. The fourth case is the common one, and the specific number of times to attempt insertion is dependent on both the eventual fullness of the table and how full A_i is at that point. Remember that all times I mention half full, the actual approach is 3/4 full.

Let's go through some insertions with this approach, and see how the array evolves:

OO03 21OO|OOOO|OO|OO

Insert 4: [3, 6] in A1, [9, ..] in A2

OO03 214O|OOOO|OO|OO

Insert 5: [2, 4] in A1, [8, ..] in A2

OO03 214O|5OOO|OO|OO

Insert 6: [1, 3] in A1, [10, ..] in A2

O603 214O|5OOO|OO|OO

Here we started to check more times in A1, because it is more full.

Insert 7: [4, 7, 6] in A1, [11, ..] in A2

O603 2147|5OOO|OO|OO

Insert 8: [4, 7, 6] in A1, [11, ..] in A2

O603 2147|5OOO|OO|OO

Insert 8: [5, 6, 1, 4] in A1, [8, 11, ..] in A2

O603 2147|5OO8|OO|OO

Insert 9: [3, 6, 0, 4] in A1, [9, ..] in A2

9603 2147|5OO8|OO|OO

We just finished filling up A1. In a real example, this wouldn't be all the way full, but with small numbers it works out this way.

Insert a: [8, 10] in A2, [13, ..] in A3

9603 2147|5Oa8|OO|OO

Summary

The real advantage of this approach is that not only does it reduce the worst case insertions at the end of filling up the array, it also reduces the average amount of work done to fill up the array. I recommend reading the section in the paper on "Bypassing the coupon-collecting bottleneck" to see the author's interpretation of why it works.

[1]: This is not quite true in this case, because we do not check indices more than once. However, for large hash tables, the contribution from previously checked values ends up being fairly negligible.

[2]: Inserting an element in a large hash table like this follows a geometric distribution, which is where we get the 1/p expected number of attempts.