Understanding Hashing: Functions, Collisions, and Concepts

Welcome to the next lesson in our journey through data structures! In the previous session, we explored tree traversal algorithms—in-order, pre-order, and post-order—which are powerful ways to visit and process every node in a tree. These methods are fundamental but often involve visiting multiple nodes to find a specific one, with a search time of $O(\log n)$ in a balanced tree or $O(n)$ in the worst case.

But what if we need to access data almost instantaneously? Imagine a dictionary where you don't have to flip through pages but can magically open to the exact right page just by knowing the word. This is the promise of hash tables, a data structure optimized for incredibly fast lookups, insertions, and deletions.

Today, we will lay the conceptual groundwork for this powerful tool. You will learn to explain the concept of hashing, hash functions, and collisions. This lesson will focus on the "what" and "why" behind hash tables, preparing us to build one in C in our next session.

1. The Need for Speed: From Arrays to Hash Tables

At its core, a hash table is a clever use of an array. We know that accessing an element in an array by its index is an $O(1)$ operation—it's immediate. The challenge, however, is that we usually want to look up data using a meaningful key, like a username string, not an arbitrary integer index. Searching for that key in an array would require a linear scan, which is an inefficient $O(n)$ operation.

Hash tables solve this by creating a direct link between the key and an array index.

As the video explains, the central idea is to use a special function—a hash function—to compute an array index directly from the key.

2. The Hash Function: The Engine of the Hash Table

A hash function is a procedure that takes a key and maps it to an integer index. This index is then used to store or retrieve the corresponding value in the hash table array.

A simple hash function for a string, as mentioned in the video, could be to sum the ASCII values of its characters. Let's make this more robust. Usually, the array we use for the hash table is much smaller than the range of possible hash values. To ensure the index is always within the array's bounds, we use the modulo operator (%).

The most common hashing scheme is:
$\text{index}=\text{hash}(\text{key})(\mathrm{mod}\text{table\_size})$

Let's watch a clear, practical example of this.

For a deeper dive into the properties and types of hash functions, the following reading is excellent.

A good hash function should have two main properties:

1. It should be fast to compute. If the hash function is slow, it defeats the purpose of having a fast data structure.
2. It should distribute keys uniformly. It should spread keys evenly across all the available slots in the array, minimizing clumps and gaps.

3. Collisions: An Unavoidable Problem

What happens if our hash function generates the same index for two different keys? For example, using the (sum of ASCII) % 11 function, what if "Sue" and "Mia" both result in an index of 4? This is called a collision.

Collisions are not just a possibility; they are a mathematical certainty in any practical hash table. This is due to the pigeonhole principle: if you have more items (keys) than you have containers (array slots), at least one container must hold more than one item.

The next video segment explains this inevitability perfectly.

Since collisions are unavoidable, every hash table implementation must have a collision resolution strategy. While we won't implement these today, it's crucial to know the two main approaches.

1. Open Addressing (e.g., Linear Probing): If the target slot is occupied, we probe for the next available empty slot in the array and place the item there.
2. Separate Chaining: Each slot in the array acts as a "bucket" that can hold multiple items. This is typically implemented using a linked list, where each slot in the array stores the head of a list containing all items that hashed to that index.

The following video segments will give you a clear visual introduction to these two strategies.

4. Practice and Review

Let's do a quick pencil-and-paper exercise to solidify these concepts.

Imagine you have a hash table of size m = 7. Your hash function for strings is sum of ASCII values of the first three letters % 7.

Calculate the hash index for the following keys. Do any of them collide?

• "apple" (ASCII: a=97, p=112, p=112)
• "banana" (ASCII: b=98, a=97, n=110)
• "cherry" (ASCII: c=99, h=104, e=101)
• "date" (ASCII: d=100, a=97, t=116)
• "grape" (ASCII: g=103, r=114, a=97)

Solution:

• apple: (97 + 112 + 112) % 7 = 321 % 7 = 6
• banana: (98 + 97 + 110) % 7 = 305 % 7 = 4
• cherry: (99 + 104 + 101) % 7 = 304 % 7 = 3
• date: (100 + 97 + 116) % 7 = 313 % 7 = 5
• grape: (103 + 114 + 97) % 7 = 314 % 7 = 6

Collision! "apple" and "grape" both hash to index 6. If we were inserting these into our table, we would need a strategy to handle this conflict.

Conclusion

In this lesson, we've unpacked the core theory behind hash tables. You've learned that they offer the potential for extremely fast data operations by directly computing an array index from a key.

Key Takeaways:

• Hashing is a technique that maps a key to an index in an array (the hash table).
• A hash function is the algorithm that performs this mapping. A good hash function is fast and distributes keys uniformly.
• The modulo operator is essential for scaling down large hash values to fit within the bounds of the array.
• A collision occurs when two different keys map to the same index. They are an inevitable consequence of hashing.
• Collision resolution strategies, like linear probing and separate chaining, are required to handle these conflicts.

Preview of the Next Lesson:
Theory is great, but practice is better. In our next session, we will roll up our sleeves and implement a basic hash table in C. We will use the separate chaining method to handle collisions, which will be a fantastic opportunity to combine our knowledge of arrays, pointers, structs, and linked lists.