Hashing Composite Keys
What you'll learn: How to create a single hash value when your key is made up of multiple pieces of information.
Why Composite Keys?
Sometimes you need to store data using more than one piece of information as the key. Imagine a student database where you need both a student's name and their ID number to uniquely identify them. Or think of a chess game where a position is identified by both row and column coordinates (row, col). These are composite keys—keys built from multiple components.
The Challenge
Hash functions we've learned so far (like the division method or polynomial rolling hash) work on single values. But how do you hash a pair, triple, or even larger tuple of values?
Two Main Techniques
1. Weighted Sum Combine the components using addition with different weights (multipliers) to avoid collisions:
hash = (weight1 * component1 + weight2 * component2) mod table_size
For coordinates (3, 5) with weights 31 and 37:
hash = (31 * 3 + 37 * 5) mod 100 = 278 mod 100 = 78
The weights should be prime numbers to reduce patterns and collisions.
2. Nested Hashing Hash each component individually, then combine those hash values:
hash1 = hash_function(component1)
hash2 = hash_function(component2)
final_hash = (hash1 * prime + hash2) mod table_size
This reuses the good hash functions you already have for single values.
Choosing Weights
Use different prime numbers for each component. This ensures that (3, 5) and (5, 3) produce different hashes—order matters!
Key Takeaway: Composite keys are hashed by combining their components using weighted sums or nested hashing, treating multiple values as a single hashable unit.