Chaining (Open Addressing)

In the design of hash tables, when multiple distinct key-value pairs map to the same index position, collisions inevitably occur. Strategies for resolving this issue are primarily categorized into two groups: Open Addressing and Chained Hashing. Among these, Chained Hashing (also known as Closed Hashing or Linked List Hashing) is one of the most classic and efficient solutions for handling collisions in large-scale datasets. Its core idea is quite intuitive: instead of storing only a single element per slot in a hash table, each bucket maintains a linked list (or other linear structure) to store all key-value pairs mapping to that index. This design not only effectively avoids lookup failures caused by collisions but also significantly enhances the scalability and capacity expansion capabilities of the hash table.

Basic Structure of Data Structures

The implementation of chained hashing relies on constructing a composite data structure. While traditional arrays can only store single elements, a Chained Hash Table typically consists of a main array combined with a set of independent linked lists.

  • Index Region: This refers to the integer range $[0, m-1]$ calculated by the hash function, where $m$ is the number of buckets. Essentially, this region acts as an array of fixed length.
  • Node Structure: Each element requires a specific data structure to store key-value pairs. Typically, it comprises three parts: a Data Field, a Pointer Field, and a Hash Code Field.

In practical development scenarios, to simplify memory management, dynamic linked lists or std::list in C++ / ArrayList in Java are often used directly as node containers. When collisions occur, new elements simply need to be appended to the tail of the corresponding index's list; complex displacement operations are not required. Theoretically, this approach allows a hash table to expand to any size (provided sufficient memory exists), because even if all keys map to the same position, the linked lists can fully accommodate them.

Insertion and Search Algorithm Flow

Understanding the workflow of chained hashing is key to mastering its application. Whether inserting new data or retrieving specific information, the entire process strictly follows the logic steps of "Calculate Index -> Traverse Linked List".

1. Hash Function Calculation
First, use a preset hash function $H(k)$ to map the input key-value pair $k$ to an index $i$ in the main array. This step determines the approximate location of elements within the table. Since chained hashing allows for collisions, no matter how many times collisions occur, they will not affect the execution of subsequent steps.

2. Insertion Operation (Insert)
When inserting a new node into the hash table:

  1. Calculate the hash value of the key to obtain index $i$.
  2. Check if the linked list at index $i$ in the main array is empty or if an identical key already exists at the tail (depending on specific business requirements).
  3. If it does not exist, create a new node and fill in the data, then insert it into either the head or tail of the corresponding linked list. To accelerate lookups, many implementations prefer "Head Insertion" over "Tail Insertion", as the former has a time complexity of $O(1)$.

Code Logic Example (Pseudocode):

def insert(key, value):
    index = hash_function(key) % table_size
    
    # Get reference to linked list at corresponding index
    linked_list = buckets[index]
    
    if key not in linked_list:
        new_node = Node(key, value)
        
        # Head insertion: add directly to the front for highest efficiency
        new_node.next = linked_list.head
        linked_list.head = new_node
        
        return True
    
    return False

3. Search Operation (Search)
During a search operation, we first locate the target index via the hash function. If the corresponding linked list at that position is empty, it indicates that the key-value pair does not exist in the table; otherwise, iteration must begin from the head of the linked list to compare keys one by one:

  1. Calculate $H(k)$ to obtain initial index $i$.
  2. Iterate starting from the head of the linked list pointed to by buckets[i].
  3. Compare the Key of the current node with the target key sequentially. If they match, return that node (or its corresponding Value); if no match is found after traversing ends, it indicates a miss.

The time complexity for this process is $O(1)$ on average, but degrades to $O(n)$ in the worst-case scenario where all elements have identical hash values ($n$ being the length of the linked list). In practical engineering projects, ensuring uniform data distribution through well-designed hash functions can keep the average length of chains at a low level.

Performance Analysis and Pros/Cons Comparison

Compared to Open Addressing methods (Open Addressing), Chained Hashing possesses significant performance advantages and distinct application scenarios.

Advantage Analysis:

  • No Collision Limitation: This is the greatest advantage of chained hashing. Regardless of how many elements map to the same index, they can be stored and accessed normally; there are no situations where a "full table" prevents insertion.
  • Easy Expansion Implementation: When the hash table's load factor becomes too high, it suffices to double the length of the main array (e.g., from 16 to 32) and re-hang all linked lists onto their new positions. Since nodes themselves are independent objects, this migration operation is relatively simple and efficient.
  • Flexible Memory Utilization: For sparse data or dynamically changing datasets, chained hashing adapts better to storage requirements with varying densities.

Potential Challenges:

  • Additional Space Overhead: Each node requires an additional pointer field to maintain linked list connections, consuming approximately 4~8 bytes more memory than Open Addressing (depending on the architecture). Furthermore, due to the existence of numerous free nodes used as buffers for collision elements, overall cohesion is slightly lower.
  • Traversal Cost: Although average lookup speed is extremely fast, if a poorly designed hash function leads to severe collisions causing very long chains, single operation time complexity will be pushed up to linear level $O(n)$, severely impacting performance.

In summary, thanks to its simple collision resolution mechanism and powerful expansion capabilities, Chained Hashing has become the preferred solution for modern programming language standard libraries (such as Java's HashMap or partial implementations in C++ STL). Mastering its underlying logic and code implementation details is of great significance for deeply understanding data structure principles and optimizing system-level storage structures.