✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-072

Open Addressing

Open addressing is a collision-resolution technique in which all entries are stored directly inside the hash-table array. When a collision occurs, a probing sequence searches for another available position.

Explanation

Overview

Open addressing is a hash-table strategy that resolves collisions by examining alternative positions within the same table according to a defined probing rule.

Core idea

Every stored entry occupies a position in the table array. If the initial index is already occupied, the algorithm checks additional positions until it finds the requested key or an available slot.

Key concepts

name: Core idea; description: The central focus of open addressing is the capability described here: Open addressing is a collision-resolution technique in which all entries are stored directly inside the hash-table array. When a collision occurs, a probing sequence searches for another available position.; name: Problem context; description: Open Addressing is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using open addressing, check its assumptions, input requirements, expected output, and resource constraints.

Example

scenario: A software feature needs to use open addressing.; task: Design a small, testable solution that demonstrates open addressing while satisfying the requirements described in this entry.; approach: Identify the input and expected output, apply the central idea of open addressing, and trace the result with a small representative dataset.; learningPoint: This open addressing example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.

Advantages

Stores entries directly in the table array.; Avoids separate linked-list nodes and bucket references.; Can provide good cache locality.; May use memory efficiently when the load factor is controlled.; Does not require separate bucket allocation.

Example or application

Scenario

A software feature needs to use open addressing.

Task

Design a small, testable solution that demonstrates open addressing while satisfying the requirements described in this entry.

Approach

Identify the input and expected output, apply the central idea of open addressing, and trace the result with a small representative dataset.

Learning Point

This open addressing example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.

Definition

Open addressing is a hash-table strategy that resolves collisions by examining alternative positions within the same table according to a defined probing rule.

Core Idea

Every stored entry occupies a position in the table array. If the initial index is already occupied, the algorithm checks additional positions until it finds the requested key or an available slot.

Probing

Probing is the process of generating and examining a sequence of table indices after the initial hash position is occupied.

General Probe Formula

A general probing sequence can be represented as index_i = (h(k) + probe(i)) mod m, where h(k) is the initial hash value, probe(i) determines the offset, and m is the table capacity.

Storage Requirement

All key-value entries are stored directly in the table array. Separate linked-list buckets are not used.

Insertion Process

  • Calculate the initial hash index.

  • Check whether the position is empty or available.

  • If the position is occupied, generate the next probe position.

  • Continue probing according to the selected strategy.

  • Insert the entry when a suitable position is found.

  • Resize the table if its occupancy becomes too high.

Lookup Process

  • Calculate the initial hash index.

  • Check the key stored at that position.

  • If it matches, return the associated value.

  • If it does not match, follow the same probing sequence used during insertion.

  • Stop when the key is found or a position proves that the key cannot be present.

Deletion Process

Deletion requires special care. Simply marking a previously occupied position as empty may break a probe sequence and cause later entries to become unreachable. Implementations commonly use a special deleted marker called a tombstone.

Tombstones

A tombstone marks a slot where an entry was deleted. Lookup treats it as a position through which probing must continue, while insertion may eventually reuse it according to the implementation's rules.

Common Strategies

NameDescription

Linear Probing

Checks positions at a constant step, commonly one slot at a time.

Quadratic Probing

Uses quadratic offsets to select later positions.

Double Hashing

Uses a second hash function to determine the probe step.

Load Factor

For open addressing, the load factor α = n/m represents the fraction of table positions currently occupied by entries. It must remain below 1 for an insertion to have an available position.

Performance

Open addressing can provide average O(1) operations when the load factor is controlled and the probing strategy distributes searches effectively. Performance can degrade as the table approaches full occupancy.

Worst Case Complexity

Lookup, insertion, and deletion can require O(n) time when a long probe sequence must be examined.

Advantages

  • Stores entries directly in the table array.

  • Avoids separate linked-list nodes and bucket references.

  • Can provide good cache locality.

  • May use memory efficiently when the load factor is controlled.

  • Does not require separate bucket allocation.

Disadvantages

  • Performance can deteriorate rapidly at high load factors.

  • Deletion requires tombstones or another careful strategy.

  • Clustering can increase probe lengths.

  • The table needs an available slot for ordinary insertion.

  • Resizing requires redistributing existing entries.

Clustering Types

  • Primary clustering: long consecutive groups of occupied slots form and attract additional insertions.

  • Secondary clustering: keys with the same initial hash position follow the same probe sequence in methods such as quadratic probing.

Comparison With Separate Chaining

Open addressing keeps every entry inside the table array and uses probing to resolve collisions. Separate chaining maintains an independent collection of entries for each table index.

Common Applications

  • Memory-efficient hash maps.

  • High-performance dictionaries.

  • Systems where cache locality is important.

  • Embedded systems with controlled memory allocation.

  • Hash sets and lookup tables.

Key Concepts

NameDescription

Core idea

The central focus of open addressing is the capability described here: Open addressing is a collision-resolution technique in which all entries are stored directly inside the hash-table array. When a collision occurs, a probing sequence searches for another available position.

Problem context

Open Addressing is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using open addressing, check its assumptions, input requirements, expected output, and resource constraints.

Practice Questions

QuestionAnswer

What is the main purpose of open addressing?

Open addressing is a collision-resolution technique in which all entries are stored directly inside the hash-table array. When a collision occurs, a probing sequence searches for another available position.

What should be checked before applying open addressing?

For open addressing, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of open addressing be validated?

Trace a representative open addressing case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of open addressing.

  • Identify the assumptions, inputs, and conditions relevant to open addressing.

  • Evaluate an application of open addressing for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures