Glossary

6.3 Open addressing and chaining

4 min read•july 30, 2024

Hash tables are a powerful data structure for efficient key-value storage and retrieval. and are two main collision resolution techniques, each with unique advantages. Understanding their implementation and performance characteristics is crucial for optimizing design.

This section explores open addressing techniques like and , as well as chaining with linked lists. We'll compare their space and time complexities, discussing factors that influence performance and guide the choice between these approaches in different scenarios.

Open Addressing vs Chaining

Collision Resolution Techniques

Top images from around the web for Collision Resolution Techniques

  • Hash Tables : Handling Collision View original

    Is this image relevant?

  • Fundamentals of data structures: Hashing - Wikibooks, open books for an open world View original

    Is this image relevant?

  • Hash Tables : Handling Collision View original

    Is this image relevant?

1 of 3

Top images from around the web for Collision Resolution Techniques

  • Hash Tables : Handling Collision View original

    Is this image relevant?

  • Fundamentals of data structures: Hashing - Wikibooks, open books for an open world View original

    Is this image relevant?

  • Hash Tables : Handling Collision View original

    Is this image relevant?

1 of 3
  • Open addressing resolves collisions by probing for the next available slot within the hash table array itself
  • Chaining handles collisions by storing multiple key-value pairs that hash to the same index in a separate data structure ( or array)
  • Open addressing requires less memory overhead led to more efficient space utilization
  • Chaining allows for a higher before performance degradation occurs enabled better handling of high collision rates
  • Choice between open addressing and chaining depends on factors such as expected load factor, memory constraints, and nature of data being stored

Performance Characteristics

  • Open addressing more susceptible to clustering resulted in decreased performance with increasing load
  • Chaining maintains better performance at higher load factors compared to open addressing
  • Open addressing typically keeps load factor below 0.7 to maintain good performance and avoid excessive probing
  • Chaining allows for load factor greater than 1 enabled storage of multiple key-value pairs at each slot
  • Open addressing performs better with smaller, fixed-size data sets (integers or pointers)
  • Chaining handles variable-sized elements and dynamic data sets more efficiently

Open Addressing Techniques

Linear Probing

  • Resolves collisions by sequentially searching for the next available slot
  • Probe sequence determined by formula h(k,i)=(h′(k)+i)mod  mh(k, i) = (h'(k) + i) \mod m
    • h′(k)h'(k) initial hash function
    • ii probe number
    • mm table size
  • Simple to implement and has good cache performance
  • Suffers from primary clustering led to longer probe sequences
  • Example: For key 42 and initial hash h′(42)=7h'(42) = 7, probe sequence: 7, 8, 9, 10, ...

Double Hashing

  • Uses two hash functions to compute the probe sequence reduced clustering compared to linear probing
  • Probe sequence given by h(k,i)=(h1(k)+i∗h2(k))mod  mh(k, i) = (h1(k) + i * h2(k)) \mod m
    • h1(k)h1(k) and h2(k)h2(k) two different hash functions
  • Provides more uniform probing distribution
  • Requires careful selection of hash functions to ensure full table coverage
  • Example: For key 42, h1(42)=7h1(42) = 7, h2(42)=3h2(42) = 3, probe sequence: 7, 10, 13, 16, ...

Additional Techniques and Considerations

  • uses a quadratic function to determine probe sequence offered compromise between linear probing and double hashing
  • in open addressing requires special handling often implemented using "tombstone" marker
  • Load factor in open addressing should typically be kept below 0.7 maintained good performance
  • Example of quadratic probing sequence: h(k,i)=(h′(k)+c1∗i+c2∗i2)mod  mh(k, i) = (h'(k) + c1*i + c2*i^2) \mod m, where c1c1 and c2c2 are constants

Chaining with Linked Lists

Implementation Details

  • Each slot in hash table array points to separate data structure (commonly linked list or dynamic array)
  • Linked list implementation involves nodes containing key-value pair and pointer to next node
  • Array-based chaining uses dynamic array at each slot resized as needed to accommodate more elements
  • hashes key, accesses corresponding slot, adds new key-value pair to linked list or array
  • Deletion straightforward removes target key-value pair from linked list or array at hashed index
  • Searching hashes key and searches through linked list or array at corresponding slot

Performance Considerations

  • Chaining allows for load factor greater than 1 enabled storage of multiple key-value pairs per slot
  • Performance degrades as number of elements per chain increases led to longer times
  • Balanced distribution of elements across chains crucial for maintaining good performance
  • Rehashing entire table when load factor exceeds threshold improved overall performance
  • Example: Hash table with 10 slots, 25 elements stored load factor of 2.5

Complexity Analysis of Hash Table Methods

Space Complexity

  • Open addressing space complexity O(n) where n number of slots in hash table array
  • Chaining space complexity O(n + m) where n number of slots and m total number of key-value pairs stored
  • Open addressing more space-efficient for smaller load factors
  • Chaining requires additional memory for linked lists or arrays at each slot
  • Example: Open addressing table with 1000 slots uses exactly 1000 memory units, while chaining might use more depending on number of stored elements

Time Complexity

  • Average-case time complexity for successful searches in open addressing O(1/(1-α)) where α load factor
  • Chaining average-case time complexity for operations O(1 + α) where α load factor (average number of elements per slot)
  • Worst-case time complexity for open addressing operations O(n) when table nearly full or poorly distributed
  • Chaining worst-case time complexity O(n) if all elements hash to same slot forming single long chain
  • Performance of both techniques degrades as load factor increases
  • Example: Open addressing with load factor 0.5 expected to perform search in ~2 probes, while chaining with same load factor requires ~1.5 comparisons on average

Key Terms to Review (20)

Average-case complexity: Average-case complexity measures the expected time or space an algorithm will take to complete under typical conditions. It takes into account the likelihood of different inputs and their respective processing times, making it crucial for understanding how algorithms perform in realistic scenarios. This concept is particularly relevant when evaluating data structures and algorithms that handle varying amounts of data or have probabilistic behavior.
Bucket: In the context of hashing, a bucket is a storage unit that holds one or more entries in a hash table. Buckets help manage collisions by grouping together entries that hash to the same index, allowing for efficient retrieval and organization of data. Each bucket can use different strategies to handle multiple entries, which ensures that the hash table operates effectively under various load conditions.
Cache lookup: Cache lookup is the process of retrieving data from a cache, which is a smaller, faster storage location that temporarily holds frequently accessed data to improve retrieval speed. This mechanism is particularly important in computer science for optimizing performance when accessing data structures like hash tables, especially when using techniques like open addressing and chaining to resolve collisions.
Chaining: Chaining is a collision resolution technique used in hash tables where each slot in the hash table can hold a linked list of entries that hash to the same index. This method allows multiple elements to be stored in a single position of the hash table, effectively managing collisions that occur when two or more keys are hashed to the same location. The use of linked lists helps to maintain efficient retrieval and storage operations, enhancing the overall performance of hash tables.
Database indexing: Database indexing is a data structure technique that improves the speed of data retrieval operations on a database table at the cost of additional space and maintenance overhead. It allows databases to quickly locate and access the data without scanning every row in a table, significantly enhancing query performance. Efficient indexing is crucial for optimizing database operations, especially as the size of the dataset grows.
Deletion: Deletion refers to the process of removing an element from a data structure, which can significantly impact the efficiency and integrity of the structure. Depending on the type of data structure, deletion may require different strategies to maintain order, balance, or performance. Proper handling of deletion is crucial for ensuring that subsequent operations on the data structure remain efficient and do not lead to errors or inefficient states.
Double hashing: Double hashing is a collision resolution technique used in hash tables, where two hash functions are applied to compute the index of an element. When a collision occurs, the second hash function generates a step size that determines how far to jump to find the next available slot. This method minimizes clustering and helps to distribute entries more uniformly across the hash table, improving performance.
Expected time complexity: Expected time complexity refers to the average time an algorithm takes to complete based on its input size, factoring in the randomness or probabilistic behavior of certain processes. This concept is particularly significant in algorithms where performance can vary widely depending on the specific characteristics of the input, such as in hash table operations or randomized sorting algorithms. Understanding expected time complexity helps in predicting algorithm efficiency and optimizing performance in practical scenarios.
Hash table: A hash table is a data structure that implements an associative array, allowing for efficient data retrieval through a unique key that maps to a specific value. It utilizes a hash function to compute an index in an array where the corresponding value is stored, enabling average-case constant time complexity for lookups, insertions, and deletions. This structure is crucial for optimizing data management and is commonly used in various programming applications.
Hashing with chaining: Hashing with chaining is a method used to resolve collisions in hash tables by storing multiple elements that hash to the same index in a linked list. This approach allows for efficient data retrieval as each list can grow to accommodate more items without losing direct access to the hashed index. As a result, it effectively manages overflow and maintains the average time complexity for search operations, making it a popular choice for implementing hash tables.
Insertion: Insertion is the process of adding a new element into a data structure while maintaining its specific properties and order. This operation is fundamental in various data structures, as it influences how data is organized, accessed, and modified efficiently.
Linear probing: Linear probing is a collision resolution technique used in hash tables to handle situations where two keys hash to the same index. When a collision occurs, linear probing looks for the next available slot by checking each subsequent index in a sequential manner until an empty slot is found. This method is straightforward and easy to implement, but it can lead to clustering, which affects performance as the load factor increases.
Linked List: A linked list is a data structure that consists of a sequence of elements, where each element (or node) contains a value and a reference (or pointer) to the next element in the sequence. This structure allows for efficient insertion and deletion of elements since these operations do not require shifting elements as in arrays. Linked lists are particularly useful in scenarios where dynamic memory allocation and flexibility in size are needed, making them relevant in various algorithms and data storage methods.
Load Factor: The load factor is a measure of how full a hash table is, calculated as the ratio of the number of entries to the number of buckets or slots in the table. It helps in assessing the efficiency of hash tables and influences the performance of basic operations, such as search, insertion, and deletion. A low load factor indicates that the hash table has plenty of empty slots, leading to fewer collisions and faster operations, while a high load factor suggests that the table is nearly full, which can lead to increased collision rates and decreased performance.
Open Addressing: Open addressing is a collision resolution technique used in hash tables where, upon a collision, the algorithm searches for the next available slot within the array to store the value. This method keeps all entries within the hash table itself, allowing for direct access while avoiding the need for linked lists or other external structures. Open addressing utilizes probing sequences, which can vary in their patterns, to efficiently find open slots in case of collisions.
Quadratic probing: Quadratic probing is a collision resolution technique used in open addressing for hash tables, where a sequence of indices is generated to resolve collisions based on the square of the probe number. Instead of using a linear function to find the next index when a collision occurs, quadratic probing adds the square of the probe number to the original hash index. This approach helps in spreading out the entries more evenly across the hash table and reduces clustering problems that can arise with linear probing.
Search: Search refers to the process of locating a specific data item within a collection of data. It is fundamental to various data structures and algorithms, allowing for efficient retrieval of information based on specific criteria. The effectiveness of a search operation is heavily influenced by the underlying data structure, which can determine how quickly and efficiently a desired item can be found.
Separate Chaining: Separate chaining is a technique used in hash tables to resolve collisions by storing multiple values in a single hash table index through linked lists or other data structures. When two or more keys hash to the same index, they are stored in a list at that index, allowing for efficient retrieval despite the collision. This method maintains a manageable load factor and ensures that operations like insertion, deletion, and lookup remain efficient under varying conditions.
Uniform distribution: Uniform distribution refers to a probability distribution where all outcomes are equally likely. In the context of hash tables, this means that when keys are hashed, they are distributed evenly across the table's buckets or slots, minimizing collisions. A uniform distribution is crucial for ensuring that data retrieval is efficient, as it impacts both open addressing and chaining methods by influencing how well these techniques can manage the storage of hashed entries.
Worst-case scenario: A worst-case scenario refers to the most unfavorable possible outcome in a given situation, especially when evaluating the efficiency and performance of algorithms. It’s important to analyze this scenario to understand the upper limits of an algorithm's time or space complexity, ensuring that even in the most extreme conditions, the algorithm will perform within acceptable bounds.
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.
Back
Practice QuizGlossary
Practice QuizGlossary
Next guide