Open Addressing Hashing: How It Works and When to Use

Open addressing hashing is a method to handle collisions in a hash table by finding another empty slot within the table itself. Instead of storing multiple items in one slot, it searches for the next available position using a sequence until an empty slot is found.

How It Works

Imagine you have a row of mailboxes, each with a unique number. When you want to put a letter in a mailbox, you use a formula (hash function) to find the mailbox number. Sometimes, two letters want to go into the same mailbox, causing a collision.

Open addressing solves this by checking the next mailbox in line until it finds an empty one. This means all letters stay in the mailboxes themselves, and no extra boxes are needed. The process of checking the next mailbox can follow different patterns like moving one step at a time (linear probing), jumping in steps (quadratic probing), or using a second formula (double hashing).

This way, the hash table stays compact, and collisions are handled by searching for the next free spot inside the table.

Example

This example shows a simple hash table using linear probing to handle collisions with open addressing.

python

class OpenAddressingHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash(self, key):
        return key % self.size

    def insert(self, key):
        index = self.hash(key)
        start_index = index
        while self.table[index] is not None:
            index = (index + 1) % self.size
            if index == start_index:
                raise Exception('Hash table is full')
        self.table[index] = key

    def search(self, key):
        index = self.hash(key)
        start_index = index
        while self.table[index] is not None:
            if self.table[index] == key:
                return index
            index = (index + 1) % self.size
            if index == start_index:
                break
        return -1

# Usage example
hash_table = OpenAddressingHashTable(5)
hash_table.insert(10)  # Goes to index 0
hash_table.insert(15)  # Collision at 0, goes to index 1
hash_table.insert(20)  # Collision at 0 and 1, goes to index 2

search_15 = hash_table.search(15)
search_99 = hash_table.search(99)

print('Index of 15:', search_15)
print('Index of 99:', search_99)

Output

Index of 15: 1
Index of 99: -1

When to Use

Open addressing hashing is useful when you want to keep all data inside a fixed-size array without extra memory for linked lists. It works well when the hash table is not too full, typically below 70-80% capacity, to keep searches fast.

Use it in systems where memory is limited or predictable access time is important, such as caches, databases, or real-time systems. However, if the table gets too full, performance drops, so resizing or other collision methods might be better.

Key Points

• Open addressing stores all elements inside the hash table array itself.
• Collisions are resolved by probing for the next free slot.
• Common probing methods include linear, quadratic, and double hashing.
• Performance depends on keeping the table less than full.
• It avoids extra memory but can slow down when the table is crowded.

Key Takeaways

Open addressing handles collisions by searching for empty slots within the hash table array.

It keeps all data in one array, avoiding extra memory for linked structures.

Linear probing is a simple way to find the next free slot after a collision.

Performance is best when the table is not too full, usually under 70-80% capacity.

Use open addressing when memory is limited and predictable access times are needed.