Hashing Introduction
Imagine a library with thousands of books. To find a book quickly, you don't search every shelf – you use a catalog system that tells you exactly where the book is. Hashing is that catalog system for data. It maps keys to values using a hash function, allowing near O(1) time for insertion, deletion, and search.
A hash function takes a key and returns an index (hash code) where the value should be stored. The storage structure is called a hash table. Good hash functions distribute keys uniformly to avoid collisions.
Properties of a good hash function:
- Deterministic – same key always produces same hash.
- Fast to compute.
- Uniform distribution – minimizes collisions.
Simple hash function for strings (Java's hashCode):
public static int simpleHash(String key, int tableSize) {
int hash = 0;
for (int i = 0; i < key.length(); i++) {
hash = (hash * 31 + key.charAt(i)) % tableSize;
}
return Math.abs(hash);
}
Two Minute Drill
- Hashing maps keys to indices using a hash function.
- Enables O(1) average-case operations.
- Hash function must be deterministic and distribute uniformly.
- Collisions occur when different keys map to same index.
Need more clarification?
Drop us an email at career@quipoinfotech.com