Hashing

think about how lazy deletion is handled in open addressing hash tables.

Recall that in lazy deletion, we mark the cell that contained a deleted item with a flag to indicatean element used to be here but is not here anymore. Probing (forfind) then continues past any flagged cells, but aninsert can reuse any such cell.

You should NOT assume that any changes other than those specifically stated are made to the hashtable (e.g. operations still work exactly the same way as we discussed in lecture).

For both part a) and part b) we are asking you to compare the proposed modification to how an open addressing hash table with lazy deletion would normally work.

We have an open addressing hash table that uses lazy deletion. The cellX is marked asdeleted. Consider the following two proposed modifications to how thefind operation works.

Use the diagram below to explain your answer for both modifications:

CellX	CellY	CellZ

1. Proposed modification A:
   1. While probing, a successfulfind operation hits and moves past cellX and finds the key it is looking for in cellY.
   2. Thefind operation then moves the found key to cellX, marks cellX asno longer deleted, andmarks cellY asdeleted (it contains no value, but we treat it as a collision).This is a recursive operation.
   3. Thefind operation then returns the found value.

If this proposed modification is used, would the resulting hash table workbetter orworse onaverage than a normal open addressing hash table using lazy deletion? Just say it's "Better" or "Worse".

Solution:

Explain your answer. Focus on how the modification would impact thefind operation.

Limit your answer to4 - 5short sentences.

Solution:

1. Proposed modification B:
   1. While probing, a successfulfind operation hits and moves past cellX and finds the key it is looking for in cellY.
   2. Thefind operation then moves the found key to cellX, marks cellX asno longer deleted, andmarks cellY asopen (as if it had never had a value in it).
   3. Thefind operation then returns the found value.

If this proposed modification is used, would the resulting hash table workbetter orworse onaverage than a normal open addressing hash table using lazy deletion? Just say it's "Better" or "Worse".

Solution:

Explain your answer. Focus on how the modification would impact thefind operation.

Limit your answer to4 - 5short sentences.

Solution: