7. Deletion with Open Addressing Hash Tables We claimed in class that a hash tab

Question

7. Deletion with Open Addressing Hash Tables We claimed in class that a hash table using open addressing must use “lazy deletion.”

a) Give a short-as-possible example that demonstrates that using “full deletion” can lead to the hash table returning the wrong result for an operation. Make your example complete:

? Explain your hash table features, including the table size, probing strategy, and hash function.

? Give the sequence of operations and the state of the hash table after each operation.

? Demonstrate how lazy deletion leads to the correct result.

? Argue that no shorter sequence of operations can lead to the wrong result.

b) When rehashing to a larger table, do lazily-deleted items need to be included? Briefly explain.

Explanation / Answer

Hi Dear,

Please find my answer.

Qa)

Consider the following features for hash table

size: 3

probing strategy: Linear

hash function: (h(x) + i) % size

where h(x) = k % size , here k is the key

Now consider the following sequence of operations

1) Insert (0,Amy)

2) Insert (1,Sheldon)

3) Insert (3,Raj)

4) Delete (0,Amy)

State of hash table after each operation

1) key=0

h(key)=0 % 3=0 and i =0, index=(h(key)+0) % 3=0

Table index

(key,value) pair

0

(0,Amy)

1

NULL

2

NULL

2)key=1

h(key)=1 % 3=1 and i =0, index=(h(key)+0) % 3=1

Table index

(key,value) pair

0

(0,Amy)

1

(1,Sheldon)

2

NULL

3)key=3

h(key)=3 % 3=0 and i =0, index=(h(key)+0) % 3=0

but 0 is occupied, so we rehash

i=1 , index=(h(key)+1) % 3 = (0+1)%3=1

but 1 is also occupied, we hash again

i=2, index=(h(key)+2) % 3 = (0+2)%3=2

Table index

(key,value) pair

0

(0,Amy)

1

(1,Sheldon)

2

(3,Raj)

4) Delete (0,Amy)

Now assume you delete (0,Amy) ans set it back to NULL.When later you will search for (3,Raj) , you will find that hash(3) = 0 and table[0] = NULL, and you will return a wrong answer:(3, Raj) is not in the table.

To overcome this, you need to set table[0] with a special marker (say FLAG in this case) indicating to the search function to keep looking at index i+1, because there might be element there which its hash is also i.

Table index

(key,value) pair

0

FLAG

1

(2,Sheldon)

2

(3,Raj)

Q b).

No, lazily deleted item do not need to be included while rehashing to larger table. This is becuase items inserted after the lazily deleted items will be higher up in the rehashed table since the lazily-deleted item was not inserted in the first place

the table would like

Table index

(key,value) pair

0

(3,Raj)

1

(2,Sheldon)

2

NULL

Raj is already higher up in the table,,,,

Table index

(key,value) pair

0

(0,Amy)

1

NULL

2

NULL

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

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