Open Addressing: Concept
What You'll Learn
You'll discover an alternative collision-resolution strategy where all elements are stored directly in the hash table array itself, without using separate chains.
The Core Idea
When two keys hash to the same index (a collision), open addressing solves the problem by probing for another empty slot within the hash table array. Instead of creating linked lists at each bucket (like separate chaining), every element must find a home somewhere in the fixed-size table.
Think of it like musical chairs: if your assigned seat is taken, you follow a specific pattern to find the next available chair—but everyone must sit in a chair (no standing in lines beside chairs).
How It Works
When inserting a key:
- Hash the key to get an index
- If that bucket is empty, place the element there
- If occupied (collision!), use a probe sequence to check alternative buckets until an empty one is found
- Store the element in that empty bucket
When searching or deleting, you follow the same probe sequence to locate the element.
Key Differences from Separate Chaining
- No extra data structures: Everything lives in the hash table array
- Fixed capacity: The table has a maximum size
- Load factor matters more: As the table fills up, finding empty slots becomes harder
- Memory efficiency: No pointer overhead for linked list nodes
Analogy
Imagine a parking lot where each license plate "hashes" to a preferred spot. If your spot is taken, you drive forward checking successive spaces until you find an empty one. You don't create a waiting line at your preferred spot—you just park elsewhere in the lot.
Key Takeaway: Open addressing resolves collisions by probing for alternative empty slots within the hash table itself, keeping all elements stored directly in the array rather than in separate data structures.