Quadratic Probing: Exercise III

  • Describe other probing strategies (quadratic, double hashing, ... for open address hash table.

Suppose we have a hash table with capacity M=7M=7, and we aim to insert integer keys. Further, assume the hashCode() is defined as the sum of the digits of key.

Exercise Complete the table after each of the following operations, assuming collision resolution using quadratic probing.

[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ]
insert(5005)
insert(6374)
insert(2637)
insert(7897)
insert(3453)
insert(2703)
insert(7151)
Solution
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ]
insert(5005)5005
insert(6374)50056374
insert(2637)500526376374
insert(7897)7897500526376374
insert(3453)78973453500526376374
insert(2703)789734535005263727036374
insert(7151)7897345371515005263727036374

Here are the calculations:

5+0+0+5=10  ⟹  10 % 7=3 5 + 0 + 0 + 5 = 10 \implies 10 \space \% \space 7 = 3

6+3+7+4=20  ⟹  20 % 7=6 6 + 3 + 7 + 4 = 20 \implies 20 \space \% \space 7 = 6

2+6+3+7=18  ⟹  18 % 7=4 2 + 6 + 3 + 7 = 18 \implies 18 \space \% \space 7 = 4

7+8+9+7=31  ⟹  31 % 7=3 7 + 8 + 9 + 7 = 31 \implies 31 \space \% \space 7 = 3

The position [3] is already occupied; the quadratic probe would explore the sequence:

  • (3+1)%7=4(3 + 1) \% 7 = 4 OCCUPIED
  • (3+4)%7=0(3 + 4) \% 7 = 0 Bingo!

3+4+5+3=15  ⟹  15 % 7=1 3 + 4 + 5 + 3 = 15 \implies 15 \space \% \space 7 = 1

2+7+0+3=12  ⟹  12 % 7=5 2 + 7 + 0 + 3 = 12 \implies 12 \space \% \space 7 = 5

7+1+5+1=14  ⟹  14 % 7=0 7 + 1 + 5 + 1 = 14 \implies 14 \space \% \space 7 = 0

The position [0] is already occupied; the quadratic probe would explore the sequence:

  • (0+1)%7=1(0 + 1) \% 7 = 1 OCCUPIED
  • (0+4)%7=4(0 + 4) \% 7 = 4 OCCUPIED
  • (0+9)%7=2(0 + 9) \% 7 = 2 Bingo!