tombstone
A marker left in place of deleted data to record that something was deleted, so later lookups, reads or copies treat it correctly.
In more detail
Deleting data outright can confuse whatever reads it later: an open-addressed hash table would stop probing too early, and a replicated store might copy the old value back. A tombstone keeps the slot or record but marks it deleted, and it is cleaned up later, for example when a table is rehashed or a log is compacted.
Example
EMPTY, TOMB = None, object() # the course's two open-addressing slot markersRelated terms
- open addressing — A way of resolving hash collisions in which all entries live in one array and a colliding key probes forward to another free slot.
- empty slot — An open-addressed hash table slot that has never held an entry, which tells a lookup it can stop probing.
- linear probing — An open-addressing rule: if a key's slot is taken, try the next slot, then the next, wrapping around, until a free one is found.
- right to erasure — A person’s legal right, under laws such as the GDPR, to have their personal data deleted in many circumstances.
- data retention — Rules for how long each kind of data is kept and what happens to it when its purpose ends.
Taught in
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Handling PII And Data Privacy — Modern API Architecture: REST, GraphQL & gRPC