How to calculate maximum/minimum number of probes required to build a hash-table

Question

I'm currently working with Algorithms Fourth Edition by Robert Sedgewick and Kevin Wayne and I'm stuck on one of the exercises. I know that there's someone who's posted the solutions to many of the exercises from this book on GitHub, but I want to do them on my own so that I can understand and learn from them.

I've been scanning the book for how to calculate the maximum/minimum number of probes required to build a hash-table (exercise 3.4.12), but I can't find any methods/functions/formulas which shows how to move forward when dealing with such a problem.

The exercise:

Suppose that the keys A through G, with the hash values given below, are inserted in some order into an initially empty table of size 7 (= m) using a linear-probing (when there's a collision ew just check the next entry in the table by incrementing index) table (with no resizing for this problem)

key = "A B C D E F G"

hash = "2 0 0 4 4 4 2"

Which of the following could not possibly result from inserting these keys?

a) E F G A C B D

b) C E B G F D A

c) B D F A C E G

d) C G B A D E F

e) F G B D A C E

f) G E C A D B F

I found this website http://orion.lcg.ufrj.br/Dr.Dobbs/books/book2/algo02e5.htm , but I couldn't understand much of it. I got stumped on what to do when I tried to solve this, first I thought I had misunderstood the question, or that I simply couldn't find the formula on how to solve the exercise.

How do I calculate the maximum and minimum number of probes that could be required to build a table of size m?

Answer 1

I don't think there's a specific formula for this question. You need to look at each order, and decide whether that order is possible to achieve.

Let's look at (a) together: E F G A C B D.

If we replace the keys with their hash values, we'll get 4 4 2 2 0 0 4. Now the important part - note that only G is located in "right" bucket, all other values have been shifted due to the linear probing. Is that possible?

Say we've inserted G first and it was written to index 2. What now? If we insert a key with hash 0 or 4, it will be placed in cell 0 or 4 without probing, which is not what we want. The only option is to insert A now, which also has a hash value of 2. Where will it go? Index 3 of course due to the linear probing. So far, so good, our array looks like this: X X G A X X X

What now? We're left only with keys whose hash is 0 or 4, and once we insert one such key, it will be placed in cell 0 or 4. But in the pattern we're being aseked about, all values with hashes 0 and 4 aren't in the "right" cell. Therefore, this pattern is not possible.

Now let's look at (b). The order is C E B G F D A which translates to 0 4 0 2 4 4 2. How can we create this pattern?

Let's insert C: C X X X X X X What now? Let's insert F: C X X X F X X. Now let's insert D. Due to linear probing, we'll end up with C X X X F D X. What now? We're stuck. It doesn't matter what we insert now, we won't be able to reach C E B G F D A. Is there anything we can change about our previous inserts to achieve a different result? No. Therefore, (b) is also impossible.