3

I have seen several implementations of dynamic tables with open addressing using linear probing that does not use deleted slots before resizing. Here is one example: https://gist.github.com/EntilZha/5397c02dc6be389c85d8

Is there any logical reason not to reuse a deleted slot immediately?

I know why it makes sense not to set the slot's value as Empty Hash Table: Why deletion is difficult in open addressing scheme because it would create a bug with the read operation. However, what's holding from writing to this slot? Wouldn't it be better to have most slots used as much as possible for performance?

TSR
  • 17,242
  • 27
  • 93
  • 197
  • As long as a previously used slot is never empty, your code should work fine. So yes, you can fill a DELETED slot with a new entry. – Frank Yellin Mar 02 '23 at 06:40

2 Answers2

1

No, there’s no reason not to fill tombstone slots as soon as you find them. In fact, a recent paper by Bender et al shows that in the absence of tombstones, primary clustering (where long runs of elements arise because collisions start linking together smaller runs of elements) can largely be eliminated in linear probing tables by periodically inserting additional tombstone elements into the table.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
0

Deleted slots are usually identified by a special marker.

While looking for slots during a read operation, only NULL indicates that the slot is empty, and special marker denotes that an element has been deleted before, therefore continue searching to indicate that the slot is not empty.

While doing a write operation, both NULL & specific marker indicates that the slot is empty. We can use deleted slots before resizing because special marker indicates that the slot is not empty, and we can use that slot to insert an element that also indicates that the slot is not empty, so there won't be any problems during read operation.

Prabhand Reddy
  • 77
  • 4