求问原始哈希表实现方案：现有实现均基于separate chaining或open addressing

Hey there! Great question—let's break down what counts as "original" hash table implementations, since the two methods you've found are actually the foundational building blocks of almost all hash tables we use today.

While separate chaining and open addressing are the most widely recognized core approaches, there are some primitive, early variants and precursors worth exploring:

1. Early Separate Chaining #

The earliest form of separate chaining was incredibly straightforward:

• Use an array to hold the head of linked lists. When a hash collision happens, just append the new element to the end of the corresponding list.
• In early programming environments with limited pointer support, developers often used arrays to simulate linked lists (e.g., a separate index array to track the next element's position) instead of actual linked list structures.
• Here's a simplified pseudocode example of this primitive implementation:

# Initialize hash table components
hash_table = [None] * table_size
next_ptr = [0] * max_element_count
storage = []
current_idx = 0

def insert(key, value):
    hash_val = hash(key) % table_size
    if hash_table[hash_val] is None:
        hash_table[hash_val] = current_idx
    else:
        # Traverse to the end of the "linked list"
        current = hash_table[hash_val]
        while next_ptr[current] != 0:
            current = next_ptr[current]
        next_ptr[current] = current_idx
    storage.append((key, value))
    current_idx += 1

2. Primitive Open Addressing #

The original open addressing technique was linear probing—the simplest way to resolve collisions:

• When a slot is taken, just check the next position in the array (wrapping around if needed) until you find an empty slot. This was popular in early systems because it didn't require extra memory for linked lists.
• Quadratic probing came later as a refinement, but linear probing is the true "original" open addressing method.
• Pseudocode for linear probing:

hash_table = [None] * table_size

def insert(key, value):
    hash_val = hash(key) % table_size
    # Keep looking for an empty slot
    while hash_table[hash_val] is not None:
        hash_val = (hash_val + 1) % table_size
    hash_table[hash_val] = (key, value)

3. Precursors to Modern Hash Tables #

Before hash tables were formally defined, there were even more primitive fast-lookup structures:

• Direct Addressing Tables: If your keys are a small, contiguous range (like 0-99), you can use the key directly as the array index to store values. This isn't a true hash table (no hash function involved), but it's the earliest concept of O(1) lookup storage.
• Simple Folding Hash Functions: For long keys (like strings), early developers would split the key into chunks, sum them, and take the modulus to get a hash value. This primitive hashing was paired with either chaining or linear probing to build basic hash tables.

It's no surprise you're mostly finding separate chaining and open addressing—these two approaches have stood the test of time as the most efficient and easy-to-implement foundations. Almost all modern hash table optimizations (like replacing linked lists with red-black trees, double hashing, or cuckoo hashing) are just refinements of these original designs.

内容的提问来源于stack exchange，提问作者Demps