There are two techniques in collision handling in hash tables (chaining and open

Question

There are two techniques in collision handling in hash tables (chaining and open addressing).

a) Briefly explain the difference between the two technique b) Suppose that we have the hash function h(k) = k mod i l and perform following insert operations. Draw the hash table after following operations insert ki-13 Insert k2 = 22 Insert = 8 insert k4-14 c) Hashing with open addressing, Linear Probing Suppose that we have the following hash function: h(k, i) (h(k) + i) mod 5 1-0, 1,2, ,and h,(k) = k mod 5 Insert ki 7 Insert k2-6 Insert ks 11 Show the hash table after performing above inserts (clearly show your work)

Explanation / Answer

a) Difference between chaining and open addressing

b) Hash function => k mod 11

Insert k1 = 13

hash key = 13 mod 11 = 2

Insert k2 = 22

hash key = 22 mod 11 = 0

Insert k3 = 8

hash key = 8 mod 11 = 8

Insert k4 = 14

hash key = 14 mod 11 => 3

c)

In linear probing, we linearly probe for next slot. For example, typical gap between two probes is 1 as taken in below example also.
let hash(x) be the slot index computed using hash function and S be the table size

h'(k) = k mod 5

h(k) = (h'(k) + i) mod 5

Hence the size of hash table is 5

Insert k1 = 7

7 mod 5 = 2

Insert k2 = 6

6 mod 5 = 1

Insert k3 = 11

11 mod 5 = 1

1 is already fill get the next valid place in the hash table

=> (1+1) mod 5 = 2

2 is also in conflict, check for next available space

=> (2+1) mod 5 = 3 mod 5 = 3

Hence fill in location 3

Chaining Open addressing The idea is to make each cell of hash table point to a linked list of records that have same hash function value. Open Addressing is done using linear, double and quadratic probing Performance of hashing: O(1) Linear probing has the best cache performance Hash table will never fill Hash table can fill Simple in terms of computation More computation are required Chaining is mostly used when it is unknown how many and how frequently keys may be inserted or deleted. Open addressing is used when the frequency and number of keys is known.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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