Hashing Integers
What You'll Learn
You'll learn practical techniques for converting integer keys into hash table indices, including identity hashing, modulo operations, and bit manipulation.
The Core Idea
When your hash table uses integers as keys (like student IDs, ages, or product codes), you need a strategy to convert those integers into valid array indices. The simplest techniques are:
Identity Hashing
If your integers are already small and densely packed (like 0-99), you can use the integer itself as the index. This is perfect when keys naturally fit your table size.
hash(42) = 42 // Use the key directly
Think of it like apartment numbers 1-100 in a building—each number directly corresponds to a door.
Modulo Method (Division Method)
For larger integers, use modulo to wrap them into your table size:
hash(key) = key % table_size
If your table has 10 slots, hash(12345) = 12345 % 10 = 5. This squeezes any integer into your available range.
Bit Manipulation
For performance, you can use bitwise AND when table size is a power of 2:
hash(key) = key & (table_size - 1)
With a table size of 8 (binary 1000), table_size - 1 = 7 (binary 0111). The AND operation keeps only the last 3 bits, giving values 0-7. This is faster than modulo on many processors.
When to Use Which
- Identity: Keys are already 0 to N-1
- Modulo: General-purpose, works with any table size
- Bit masking: Maximum speed, requires power-of-2 table sizes
Key Takeaway: Integer hashing transforms any integer key into a valid table index using identity mapping, modulo arithmetic, or bit manipulation—choose based on your key distribution and performance needs.