Hash Table Principles and Applications in Databases

Problem Description
A Hash Table is a data structure that maps keys to storage locations via a hash function, supporting efficient insertion, deletion, and lookup operations with an ideal time complexity of O(1). In databases, hash tables are commonly used to implement hash indexes, join operations (such as hash joins), and in-memory temporary data structures. Understanding their principles and optimization scenarios is crucial for database performance tuning.

Step-by-Step Analysis of Core Principles

1. Role of the Hash Function

   • The hash function converts a key of arbitrary length (e.g., a string or number) into a fixed-length hash value (typically an integer).
   • Requirements: Fast computation and uniform output distribution (to minimize collisions). For example, calculating the hash for the string "abc": hash("abc") = (a×31² + b×31 + c) mod bucket_size.
   • Example: The key "user_id:100" is mapped via the hash function to the value 5, corresponding to the 5th bucket in the hash table.

2. Resolving Hash Collisions

   • Different keys may map to the same location (e.g., both "id:100" and "id:200" map to bucket 5), known as a hash collision.
   • Common resolution methods:
     • Separate Chaining: Maintain a linked list or red-black tree within the bucket; colliding key-value pairs are appended to the list. Example: Bucket 5 stores the list [("id:100", data1), ("id:200", data2)].
     • Open Addressing: Upon collision, follow a rule (e.g., linear probing) to find the next empty bucket. Example: If bucket 5 is occupied, try buckets 6, 7, etc., until an empty slot is found.

3. Load Factor and Resizing Mechanism

   • Load Factor = number of elements / total number of buckets, measuring the crowding level of the hash table.
   • When the load factor exceeds a threshold (typically 0.75), performance degrades, requiring resizing (Rehashing):
     • Create a larger bucket array (e.g., double the original size).
     • Recalculate the hash values for all keys and redistribute them into the new buckets.
   • Example: Initial bucket count is 4; after inserting 3 keys, the load factor reaches 0.75, triggering resizing to 8 buckets and redistributing the keys.

Specific Applications in Databases

1. Hash Index

   • Suitable for equality queries (e.g., WHERE id = 100), but cannot support range queries (e.g., id > 100).
   • Implementation: The hash value of the index key points to the data row location.
   • Limitations: Hash collisions may reduce query efficiency; data is unordered, requiring extra operations for sorted queries.

2. Hash Join

   • Used for joining two tables (e.g., SELECT * FROM A JOIN B ON A.id = B.id).
   • Steps:
     • Build Phase: Hash the join keys of the smaller table (e.g., B) into an in-memory hash table.
     • Probe Phase: Iterate through the larger table (e.g., A), compute the hash value of the join key, and quickly match records in the hash table.
   • Advantage: High efficiency for joining large tables, avoiding the O(n²) complexity of nested loops.

3. In-Memory Temporary Tables

   • When executing complex queries (e.g., GROUP BY or DISTINCT), databases often use hash tables to store intermediate results.
   • Example: For SELECT department, COUNT(*) FROM employees GROUP BY department, a hash table uses department as the key and the cumulative count as the value, enabling efficient deduplication and aggregation.

Optimization and Considerations

• Choose high-quality hash functions (e.g., MurmurHash) to minimize collisions.
• Adjust the initial bucket size and load factor threshold to balance space and time efficiency.
• For disk storage, hash indexes must handle page splits and caching strategies to avoid frequent I/O.

Through the above steps, the core value of hash tables in databases lies in fast key-based positioning. However, the appropriate index type (hash index vs. B+ tree index) must be selected based on the query type (equality vs. range).