Open Addressing in Hash Tables Tutorial

What Is Open Addressing?

Open addressing is a collision-resolution technique used in hash tables. When a key maps to an occupied position, the hash table searches for another available position according to a defined probing strategy.

Unlike separate chaining, where each bucket can contain a collection of entries, open addressing stores every entry directly inside the hash table's array.

Basic idea: Hash Key → Initial Index → Collision → Probe Another Index → Store Entry

Hash Table

Index   Value
  0       -
  1       -
  2       A
  3       B
  4       C
  5       -
  6       -

If a new key maps to index 2:

2 is occupied
↓
Probe another position
↓
3 is occupied
↓
Probe another position
↓
5 is empty
↓
Store the key at 5

Why Is Open Addressing Needed?

Hash functions map keys to table positions. Since many different keys can map to the same position, collisions are unavoidable.

Table size = 7

10 % 7 = 3
17 % 7 = 3
24 % 7 = 3

10 → index 3
17 → index 3
24 → index 3

Collision!

Open addressing resolves the collision by looking for another position in the same table. The exact position depends on the selected probing technique.

How Open Addressing Works

Every key has an initial position calculated from its hash value. If that position is occupied, the probing sequence determines where to look next.

Calculate the hash value for the key.
Convert the hash value into an initial table index.
Check whether the position is available.
If it is empty, store the entry there.
If it is occupied, follow the probing sequence.
Continue until a suitable position is found.

Key
 ↓
Hash Function
 ↓
Initial Index
 ↓
Is the slot empty?
 ├── Yes → Store
 └── No
      ↓
   Probe
      ↓
Another Index
      ↓
Is the slot empty?
 ├── Yes → Store
 └── No → Continue probing

Example of Open Addressing

Consider a table with seven positions and the simple hash function key % 7.

Insert 10:

10 % 7 = 3

Index 3 is empty.

Store 10 at index 3.


Insert 17:

17 % 7 = 3

Index 3 is occupied.

Probe index 4.

Store 17 at index 4.


Insert 24:

24 % 7 = 3

Index 3 is occupied.
Index 4 is occupied.

Probe index 5.

Store 24 at index 5.

The resulting table becomes:

Index   Key
  0      -
  1      -
  2      -
  3      10
  4      17
  5      24
  6      -

Probing in Open Addressing

Probing is the process of checking alternative table positions after the initial position is occupied. Different probing strategies produce different sequences.

The three commonly discussed strategies are:

Linear probing
Quadratic probing
Double hashing

Linear Probing

Linear probing checks the next table position whenever a collision occurs. The probe moves through consecutive indexes and wraps around when it reaches the end.

index = hash(key) % tableSize

probe:
index
(index + 1) % tableSize
(index + 2) % tableSize
(index + 3) % tableSize
...

For example, if the initial index is 4:

4 → 5 → 6 → 0 → 1 → 2 → ...

Linear Probing Example

Table size = 7

10 % 7 = 3
Store 10 at 3

17 % 7 = 3
3 occupied
Store 17 at 4

24 % 7 = 3
3 occupied
4 occupied
Store 24 at 5

Primary Clustering

Linear probing can create primary clustering. This occurs when consecutive occupied positions form a cluster. New entries that collide with any position inside the cluster may extend that same cluster.

Index:

0   1   2   3   4   5   6
        X   X   X   X
            ← cluster →

As clusters grow, searches and insertions may need to examine more positions.

Quadratic Probing

Quadratic probing uses a quadratic function to determine the distance between probe positions. Instead of checking consecutive indexes, the probe offset grows with the number of attempts.

probeIndex =
  (initialIndex + attempt²) % tableSize

A possible sequence might therefore look like:

Initial index = 3

Attempt 0:
3 + 0² = 3

Attempt 1:
3 + 1² = 4

Attempt 2:
3 + 2² = 7
7 % tableSize

Attempt 3:
3 + 3² = 12
12 % tableSize

The exact coverage of the table depends on the probing formula and table size, so implementations need appropriate parameters to ensure that available positions can be reached.

Secondary Clustering

Quadratic probing reduces the primary clustering associated with linear probing, but keys that have the same initial hash position can still follow the same probe sequence. This behavior is commonly described as secondary clustering.

This distinction is useful when comparing probing techniques:

Linear probing can form large consecutive clusters.
Quadratic probing changes the spacing between probes.
Keys with the same initial position can still share the same quadratic sequence.

Double Hashing

Double hashing uses two hash functions. The first determines the initial position, while the second determines the step size used during probing.

initialIndex = hash1(key) % tableSize

step = hash2(key)

probeIndex =
  (initialIndex + attempt * step) % tableSize

Because the step size depends on the key, different keys can follow different probe sequences even when they experience collisions.

Double Hashing Example

hash1(key) → 3
hash2(key) → 2

Probe sequence:

Attempt 0:
(3 + 0 × 2) % 7 = 3

Attempt 1:
(3 + 1 × 2) % 7 = 5

Attempt 2:
(3 + 2 × 2) % 7 = 0

Attempt 3:
(3 + 3 × 2) % 7 = 2

A suitable second hash function and table size are important because the probing sequence should be able to reach the required table positions.

Insertion with Open Addressing

Insertion starts at the key's initial hash position. If the position is occupied by the same key, the value can be updated. If it contains another key, probing continues.

function insert(key, value) {
  let index = hash(key);

  while (table[index] !== undefined) {
    if (table[index].key === key) {
      table[index].value = value;
      return;
    }

    index = nextProbe(index);
  }

  table[index] = { key, value };
}

Searching with Open Addressing

Searching follows the same probe sequence used by insertion. The table starts at the initial hash position and continues probing until it finds the requested key or reaches a condition indicating that the key is not present.

Search "C"

Initial position → 3

Index 3:
contains A

Probe index 4:
contains B

Probe index 5:
contains C

Found C.

Search cannot simply stop at the first occupied position because the requested key may have been placed farther along the probe sequence.

Deletion in Open Addressing

Deletion is one of the more subtle parts of open addressing. Simply making a deleted position empty can break the probe sequence used by future searches.

Table:

3 → A
4 → B
5 → C

Suppose B is deleted.

If index 4 becomes empty:

Search for C
↓
Check 3 → A
Check 4 → EMPTY
↓
Search incorrectly stops

But C is actually at index 5.

A common solution is to mark the position with a special deleted state, often called a tombstone. Searches continue through tombstones, while future insertions may reuse them.

Empty vs Deleted Slots

An open-addressed table may need to distinguish between a slot that has never been used and a slot from which an entry was deleted.

EMPTY
  ↓
No entry has occupied this slot
  ↓
A search may stop here


DELETED
  ↓
An entry used to occupy this slot
  ↓
A search must continue probing

This distinction is important for maintaining correct search behavior.

Load Factor in Open Addressing

The load factor is the number of stored entries divided by the number of table positions.

Load Factor =
Number of Entries / Table Capacity

Example:

7 entries / 10 positions
= 0.7

Open addressing cannot store more live entries than the number of available table slots. As the table becomes crowded, collisions and probe lengths generally increase.

Important: Unlike separate chaining, open addressing requires the table itself to provide a position for every stored entry.

Clustering in Open Addressing

Clustering occurs when occupied positions become concentrated in patterns that cause future operations to inspect many locations.

Two important forms are:

Primary clustering: strongly associated with linear probing.
Secondary clustering: can occur with quadratic probing when keys share the same initial hash position.

Double hashing can produce more varied probe sequences because the step size depends on the second hash function.

Rehashing in Open Addressing

When an open-addressed hash table becomes too full, it can be resized. Existing entries are then inserted into the new table again using the new capacity.

Old capacity = 7

17 % 7 = 3


New capacity = 13

17 % 13 = 4

Old position → 3
New position → 4

Because the table size affects the calculated position and probe sequence, entries cannot generally be copied directly to their old indexes.

Complete Linear Probing Implementation

The following implementation demonstrates insertion, lookup, deletion, and tombstones in a simple open-addressed hash table.

class LinearProbingHashTable {
  constructor(size = 10) {
    this.table = new Array(size);
    this.deleted = Symbol('deleted');
  }

  hash(key) {
    return key % this.table.length;
  }

  set(key, value) {
    let index = this.hash(key);
    let firstDeleted = -1;

    for (let attempts = 0;
         attempts < this.table.length;
         attempts++) {

      const entry = this.table[index];

      if (entry === undefined) {
        if (firstDeleted !== -1) {
          this.table[firstDeleted] = { key, value };
        } else {
          this.table[index] = { key, value };
        }

        return;
      }

      if (entry === this.deleted) {
        if (firstDeleted === -1) {
          firstDeleted = index;
        }
      } else if (entry.key === key) {
        entry.value = value;
        return;
      }

      index = (index + 1) % this.table.length;
    }

    throw new Error('Hash table is full');
  }

  get(key) {
    let index = this.hash(key);

    for (let attempts = 0;
         attempts < this.table.length;
         attempts++) {

      const entry = this.table[index];

      if (entry === undefined) {
        return undefined;
      }

      if (
        entry !== this.deleted &&
        entry.key === key
      ) {
        return entry.value;
      }

      index = (index + 1) % this.table.length;
    }

    return undefined;
  }

  delete(key) {
    let index = this.hash(key);

    for (let attempts = 0;
         attempts < this.table.length;
         attempts++) {

      const entry = this.table[index];

      if (entry === undefined) {
        return false;
      }

      if (
        entry !== this.deleted &&
        entry.key === key
      ) {
        this.table[index] = this.deleted;
        return true;
      }

      index = (index + 1) % this.table.length;
    }

    return false;
  }
}

const table = new LinearProbingHashTable(7);

table.set(10, 'Alice');
table.set(17, 'Bob');
table.set(24, 'Carol');

console.log(table.get(10));
// Alice

console.log(table.get(17));
// Bob

table.delete(17);

console.log(table.get(17));
// undefined

console.log(table.get(24));
// Carol

Linear Probing vs Quadratic Probing vs Double Hashing

Technique	Probe Pattern	Main Concern
Linear probing	Consecutive positions	Primary clustering
Quadratic probing	Quadratic offsets	Secondary clustering and probe coverage
Double hashing	Key-dependent step size	Requires a suitable second hash function

Open Addressing vs Separate Chaining

Both techniques resolve hash collisions, but they use different storage models.

Feature	Open Addressing	Separate Chaining
Collision handling	Probe another table position	Store another entry in the same bucket
Entry storage	Inside the table array	Inside bucket collections
Load factor	Must remain below capacity	Can exceed 1
Deletion	Requires careful handling	Generally simpler
Extra bucket structures	Not required	Required

Time Complexity of Open Addressing

With a well-distributed hash function and a suitably maintained load factor, search, insertion, and deletion are commonly expected to take O(1) average time.

However, as the table becomes crowded or the hash distribution becomes poor, probe sequences can become longer. In the worst case, an operation can require O(n) time.

Operation	Average Case	Worst Case
Search	O(1) expected	O(n)
Insertion	O(1) expected	O(n)
Deletion	O(1) expected	O(n)

Advantages of Open Addressing

All entries are stored directly inside the table.
No separate linked-list structure is required for buckets.
It can have efficient memory locality because entries are kept in the table array.
Several probing strategies can be used to control collision behavior.
It avoids the additional node or bucket-collection overhead associated with chaining.

Limitations of Open Addressing

Performance can degrade as the table becomes crowded.
Deletion requires special handling.
Probing can create clustering.
The table cannot hold more live entries than its capacity.
Resizing requires reinserting existing entries.
The probing strategy must be designed carefully to provide useful table coverage.

Open Addressing and Hash Function Quality

A good hash function is especially important in open addressing because collisions directly create additional probes. Poor distribution can cause many keys to begin at the same positions and generate long probe sequences.

Poor distribution:

Hash → 3
Hash → 3
Hash → 3
Hash → 3

Probe:

3 → 4 → 5 → 6 → ...


Better distribution:

Hash → 1
Hash → 3
Hash → 5
Hash → 7

The hash function and probing strategy should therefore be considered together when designing an open-addressed hash table.

Common Mistakes with Open Addressing

1. Stopping at the First Occupied Slot

An occupied slot does not necessarily contain the requested key. The implementation must continue following the appropriate probe sequence.

2. Treating Deleted Slots as Empty

In many open-addressing implementations, a deleted slot needs a distinct tombstone state so that future searches do not stop too early.

3. Ignoring Wraparound

Probing must normally wrap from the final table index back to index zero.

index = (index + 1) % tableSize

4. Allowing the Table to Become Completely Full

An open-addressed table needs available positions for new entries. Implementations commonly resize before the table becomes too crowded.

5. Using an Incompatible Probing Formula

A probing strategy must be able to reach appropriate table positions. Poor choices of table size or probe step can cause parts of the table to remain unreachable for certain keys.

Open Addressing in Interview Questions

Open addressing is a common hash-table interview topic. Questions often focus on what happens after a collision and how the implementation preserves correct lookup behavior.

Important concepts to understand include:

Open addressing and collision resolution.
Linear probing.
Quadratic probing.
Double hashing.
Primary and secondary clustering.
Load factor.
Tombstones and deletion.
Rehashing.
Average-case and worst-case complexity.
Open addressing versus separate chaining.

Key Takeaways

Open addressing resolves collisions by finding another position inside the hash table.
Every entry is stored directly in the table rather than in an external bucket chain.
Linear probing checks consecutive positions.
Quadratic probing uses quadratic probe offsets.
Double hashing uses a second hash function to determine the probe step.
Linear probing can suffer from primary clustering.
Quadratic probing can experience secondary clustering.
Deletion requires special handling, commonly through tombstones.
A high load factor generally increases probe lengths.
Resizing requires existing entries to be reinserted into the new table.
With suitable hashing and load management, hash-table operations are commonly O(1) expected.
In the worst case, excessive collisions can make operations O(n).

Topics

Open Addressing in Hash Tables