Open-bucket hash tables (1)
Open-bucket hash table (OBHT):
- Each bucket may be occupied by at most one entry.
- Whenever there is a collision, displace the new entry to another bucket.
Each bucket has three possible states:
- never-occupied (has never contained an entry)
- occupied (currently contains an entry)
- formerly-occupied (previously contained an entry, which has been deleted and not yet replaced).