Consider the hash table that results after the letters A L G O R I T H M I C hav
ID: 3869395 • Letter: C
Question
Consider the hash table that results after the letters
A L G O R I T H M I C
have been inserted, in that order, into an initially empty table with 13 slots
using quadratic probing. (Assume we're implementing a multi-set, so duplicate
entries are permitted.) For your hash function, use h(k) = k % 13 where k is assigned as follows:
A:1 B:2 C:3 D:4 E:5 F:6 G:7 H:8 I:9 J:10
K:11 L:12 M:13 N:14 O:15 P:16 Q:17 R:18 S:19 T:20
U:21 V:22 W:23 X:24 Y:25 Z:26
What letter will be in position 4 of the array used to store the table?
A
L
G
O
R
I
T
H
M
C
That slot is empty
Please show the work in detail. Thanks.
Explanation / Answer
hash of A is 1. So it will go to index 1.
hash of L is 12. So it will go to index 12.
hash of G is 7. So it will go to index 7.
hash of O is 2. So it will go to index 2.
hash of R is 5. So it will go to index 5.
hash of I is 9. So it will go to index 9.
hash of T is 7. So it will go to index 7.
hash of H is 8. So it will go to index 8.
hash of M is 0. So it will go to index 0.
hash of C is 3. So it will go to index 3.
As there are no collisions encountered, we did not use the concept of linear probing.
The position 4 is in index 3. So C is located in position 4.
If position 4 is taken as index 4. Then that slot is empty.