Question

Consider a hash table T with m=10 slots that uses open addressing with linear probing and the hash function h(k,i) = ((k mod m) + i) mod m, where i = 0,1,..., m-1 is the probe number.

Show T after inserting keys <867,755,535,296,866,135,669,445,524>.

Answer 1

Solution:

Given,

=>Hash table size(m) = 10

=>Linear probing is used for collision resolution

=>Hash function: h(k) = (kmodm + i) mod m where i = 0, 1 ....m-1

=>Keys = 867, 755, 535, 296, 866, 135, 669, 445, 524

Explanation:

Inerting keys:

Insert 487:

=>487 mod 10 = 7

Insert 755:

=>755 mod 10 = 5

Insert 535:

=>535 mod 10 = 5(collision)

=>(5 + 1) mod 10 = 6

Insert 296:

=>296 mod 10 = 6(collision)

=>(6 + 1) mod 10 = 7(collision)

=>(6 + 2) mod 10 = 8

Insert 866:

=>866 mod 10 = 6(collision)

=>(6 + 1) mod 10 = 7(collision)

=>(6 + 2) mod 10 = 8(collision)

=>(6 + 3) mod 10 = 9

Insert 135:

=>135 mod 10 = 5(collision)

=>(5 + 1) mod 10 = 6(collision)

=>(6 + 1) mod 10 = 7(collision)

=>(6 + 2) mod 10 = 8(collision)

=>(6 + 3) mod 10 = 9(collision)

=>(6 + 4) mod 10 = 0

Insert 669:

=>669 mod 10 = 9(collision)

=>(9 + 1) mod 10 = 0(collision)

=>(9 + 2) mod 10 = 1

Insert 445:

=>445 mod 10 = 5(collision)

=>(5 + 1) mod 10 = 6(collision)

=>(6 + 1) mod 10 = 7(collision)

=>(6 + 2) mod 10 = 8(collision)

=>(6 + 3) mod 10 = 9(collision)

=>(6 + 4) mod 10 = 0(collision)

=>(6 + 5) mod 10 = 1(collision)

=>(6 + 6) mod 10 = 2

Insert 524:

=>524 mod 10 = 4

Final hash table:

135

669

445

524

755

535

487

296

866

    0           1           2        3     4          5             6         7           8              9

I have explained each and every part with the help of statements attached to the answer above.