One implementation of a hash table uses the linear insert and search techniques.

Question

One implementation of a hash table uses the linear insert and search techniques. Assume valid entries are positive and the empty table is initialized with 0. Use the provided hash function. Show the state of the array after inserting values: 10 45 26 5 70 13 18 25 How many probes are required to determine that value 13 is in the hash table? _____ How many probes are required to determine that value 38 is not in the hash table? _____ The hash table below is implemented as an array of linked lists and uses the chaining method of collision resolution. a. Assume the hash function used is hash (target) = target % 5 Draw the state of the hash table after inserting the following items in order. How many probes are required to determine that value 13 is in the hash table? _____ How many probes are required to determine that value 38 is not in the hash table? _____

Explanation / Answer

hash(10) = 10

hash(45) = 6

hash(26) = 0

hash(5) = 5

hash(70) = 5, so collision, so it will try 6, again collision, try 7, sits there

hash(13) = 0, collsion so try 1, sits there

hash(18) = 5, collsion 6, 7, go to 8

hash(25) = 12

content of hash table

Now searching 13, hash(13) = 0, but value is not 13, so it will check next cell, found 13, so probes = 2

probes for searching 38: hash(38) = 12, value at 12 is not 38, check next probe 0, next probe 1, next probe 2 which is empty (0 indicate empty)

so 4 probes determine 38 is not in table.

2

hash(13) = 3

hash(20) = 0

hash(14) = 4

hash(30) = 0

hash(8) =3

hash(6) = 1

for 13, hash(13) = 3, found as first element in linked list

for 38, hash(38) = 3, search in list, now found so not in table, list size is 2

0 1 2 3 4 5 6 7 8 9 10 11 12 26 13 0 0 0 5 45 70 18 0 10 0 25

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.