Hashing

Hey students! 👋 Welcome to one of the most fascinating topics in computer science - hashing! This lesson will teach you how hash tables work, why they're incredibly fast for data storage and retrieval, and how programmers solve the tricky problems that come with them. By the end of this lesson, you'll understand hash functions, collision resolution strategies, and why hash tables are used everywhere from databases to your favorite apps. Get ready to discover why hashing is often called the "magic" behind lightning-fast data access! ⚡

What Are Hash Tables and Why Do We Need Them?

Imagine you're organizing a massive library with millions of books 📚. If you stored them randomly, finding a specific book would take forever - you'd have to check every single book until you found the right one! This is exactly the problem hash tables solve in computer science.

A hash table (also called a hash map) is a data structure that stores key-value pairs and allows incredibly fast data retrieval. Instead of searching through every item like in a regular array or list, hash tables use a clever mathematical trick to jump directly to where your data is stored.

Here's how it works: when you want to store data, the hash table takes your key (like a book's ISBN number) and runs it through a hash function - a special mathematical formula that converts your key into an array index. This index tells the hash table exactly where to store or find your data.

Real-world example: When you log into Instagram, the app doesn't search through millions of usernames to find yours. Instead, it uses your username as a key, runs it through a hash function, and instantly knows where your account data is stored! This is why login happens in milliseconds, not minutes.

The average time complexity for hash table operations is O(1) - constant time. This means whether your hash table has 100 items or 100 million items, finding your data takes roughly the same amount of time. Compare this to searching through an unsorted array, which takes O(n) time and gets slower as your data grows!

Understanding Hash Functions

A hash function is the mathematical engine that powers hash tables. Think of it as a special calculator that takes any input (your key) and produces a number that fits within your hash table's size.

Good hash functions have several important properties:

Deterministic: The same input always produces the same output. If "apple" hashes to index 42 today, it must hash to index 42 tomorrow too.

Uniform Distribution: A quality hash function spreads keys evenly across all available indices. If all your keys hash to just a few indices, you'll have performance problems.

Fast Computation: Since hash functions run every time you access data, they need to be lightning-fast to calculate.

Here's a simple example of a hash function for strings:

$$\text{hash}(key) = \left(\sum_{i=0}^{n-1} key[i] \times 31^i\right) \bmod \text{table\_size}$$

This function takes each character in your string, multiplies it by increasing powers of 31 (a prime number that works well for hashing), adds them all up, and uses modulo to ensure the result fits in your table.

Let's say you have a hash table with 10 slots and want to hash the word "cat":

• 'c' = 99, 'a' = 97, 't' = 116 (ASCII values)
• hash("cat") = (99×31⁰ + 97×31¹ + 116×31²) mod 10
• hash("cat") = (99 + 3007 + 111316) mod 10 = 114422 mod 10 = 2

So "cat" would be stored at index 2 in your hash table!

The Collision Problem and Resolution Strategies

Here's where things get interesting! 🎯 Even with the best hash functions, sometimes different keys produce the same hash value. This is called a collision, and it's actually inevitable due to something called the "pigeonhole principle."

Think about it: if you have infinite possible keys (like all possible text strings) but only a finite number of hash table slots, some keys must share the same slot. It's like having 11 pigeons and only 10 pigeonholes - at least one hole must contain multiple pigeons!

The load factor measures how full your hash table is: $\alpha = \frac{n}{m}$ where n is the number of stored items and m is the table size. As the load factor increases, collisions become more frequent.

Separate Chaining

The first collision resolution strategy is separate chaining (also called chaining). Instead of storing just one item per slot, each slot contains a linked list that can hold multiple items.

When you want to store a new item:

1. Calculate the hash value
2. Go to that index in the hash table
3. Add the new item to the linked list at that position

When searching for an item:

1. Calculate the hash value
2. Go to that index
3. Search through the linked list until you find your item

Chaining is simple and works well when you have a good hash function. The average search time is O(1 + α), where α is the load factor. If your hash function distributes keys evenly and your load factor stays reasonable (typically under 0.75), performance remains excellent.

Open Addressing

The second major approach is open addressing, where all items are stored directly in the hash table array - no linked lists allowed! When a collision occurs, you use a systematic method to find another empty slot.

Linear Probing: If slot h(key) is occupied, try h(key)+1, then h(key)+2, and so on until you find an empty slot. It's like looking for parking - if your preferred spot is taken, you check the next space, then the next, until you find one.

Quadratic Probing: Instead of checking consecutive slots, you check slots at quadratic intervals: h(key)+1², h(key)+2², h(key)+3², etc. This helps avoid clustering problems that can occur with linear probing.

Double Hashing: Uses a second hash function to determine the step size. If the first hash gives you index i and there's a collision, you use a second hash function to calculate how many steps to jump for your next attempt.

Each method has trade-offs. Linear probing has good cache performance but can create clusters of occupied slots. Quadratic probing reduces clustering but might not find empty slots even when they exist. Double hashing provides the best distribution but requires computing two hash functions.

Performance Analysis and Practical Considerations

Understanding hash table performance is crucial for making good design decisions! 📊

Time Complexity:

• Average case: O(1) for insertion, deletion, and search
• Worst case: O(n) when all keys hash to the same slot

Space Complexity: O(n) where n is the number of key-value pairs

The load factor is critical for performance. Research shows that:

• For chaining: performance degrades gradually as load factor increases
• For open addressing: performance drops dramatically when load factor exceeds 0.7

This is why most hash table implementations automatically resize when the load factor gets too high. When resizing occurs, a new larger array is created, and all existing items are rehashed into the new table.

Real-world applications showcase hashing everywhere:

• Databases: Use hash indices for lightning-fast record lookup
• Compilers: Store variable names and their memory locations
• Caches: Web browsers use hash tables to quickly find cached web pages
• Password Storage: Websites hash passwords for security (though they use cryptographic hash functions, not the simple ones we discussed)

Python's dictionaries, Java's HashMap, and JavaScript's objects all use hash tables internally. When you write user_data["name"] in Python, you're using a hash table!

Conclusion

Hashing represents one of computer science's most elegant solutions to the fundamental problem of fast data access. By using hash functions to transform keys into array indices, hash tables achieve average O(1) performance for basic operations. While collisions are inevitable, strategies like separate chaining and open addressing ensure hash tables remain efficient even as they grow. Understanding load factors, collision resolution, and performance characteristics helps you make informed decisions about when and how to use hash tables in your programs. From databases to web applications, hashing powers the fast, responsive software we use every day.

Study Notes

• Hash Table: Data structure storing key-value pairs with average O(1) access time

• Hash Function: Mathematical function converting keys to array indices: hash(key) → index

• Collision: When different keys produce the same hash value (inevitable due to pigeonhole principle)

• Load Factor: α = n/m (number of items / table size), affects performance significantly

• Separate Chaining: Collision resolution using linked lists at each hash table slot

• Open Addressing: All items stored in main array, systematic probing finds alternative slots

• Linear Probing: Check consecutive slots: h(key), h(key)+1, h(key)+2, ...

• Quadratic Probing: Check quadratic intervals: h(key)+1², h(key)+2², h(key)+3², ...

• Double Hashing: Uses second hash function to determine step size for probing

• Time Complexity: Average O(1), worst case O(n) for all basic operations

• Optimal Load Factor: Keep under 0.75 for open addressing, can be higher for chaining

• Resizing: Automatically resize and rehash when load factor becomes too high