Welcome to the World of Hash Tables!

Have you ever wondered how a computer can find a single username among millions of accounts in a split second? If the computer had to check every name one by one (like Linear Search), it would take forever! Instead, it uses a clever "shortcut" called a Hash Table. In this chapter, we will explore how this data structure works, how it turns keys into addresses, and what happens when two items try to sit in the same seat.

1. What is a Hash Table?

A Hash Table is a data structure that stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

The Library Analogy: Imagine a library where instead of searching every shelf for a book, you put the book's title into a magic calculator. The calculator gives you a number, say "42," and you go straight to shelf 42. The book is guaranteed to be there! That magic calculator is our Hash Function.

Key Components

  • Key: The unique identifier you are looking for (e.g., a Student ID or Username).
  • Value: The actual data associated with that key (e.g., the Student's Name and Grades).
  • Hash Function: The formula that transforms the Key into an Index (a position in the array).
  • Hash Table (Array): The actual container where the values are stored.
Quick Review

A Hash Table maps Keys to Indices using a Hash Function for near-instant data retrieval.

2. The Magic of Hash Functions

A Hash Function is a mathematical formula that takes a key and returns an integer that represents a position in the hash table. For your syllabus, you will usually be given a hash function to work with.

The Modulo Method

The most common simple hash function uses the Modulo Operator \( \% \). The formula looks like this:
\( Index = Key \% TableSize \)

Example:
Suppose we have a Hash Table of size 10. We want to store the ID 157.
\( 157 \% 10 = 7 \)
The data for ID 157 will be stored at Index 7.

Why use Modulo? It ensures that the resulting index is always a valid position within the array (between \( 0 \) and \( TableSize - 1 \)).

3. Collision Handling

Sometimes, two different keys might result in the same index. For example, in a table of size 10, both ID 157 and ID 247 result in an index of 7 (\( 157 \% 10 = 7 \) and \( 247 \% 10 = 7 \)).

This "traffic jam" is called a Collision. Since two pieces of data cannot occupy the same physical spot in an array, we need a strategy to handle this.

Strategy A: Linear Probing (Open Addressing)

If a collision occurs, Linear Probing tells the computer to look for the next available empty slot in the array (going down one by one).

  1. Calculate the index using the hash function.
  2. If that slot is full, check index \( +1 \).
  3. If that is also full, check \( +2 \), and so on.
  4. If you reach the end of the table, "wrap around" to index 0.

Example: Keys {22, 32} in a table of size 10.
1. \( 22 \% 10 = 2 \). Slot 2 is empty. Store 22 at Index 2.
2. \( 32 \% 10 = 2 \). Slot 2 is FULL. Move to Index 3. Slot 3 is empty. Store 32 at Index 3.

Strategy B: Chaining (Closed Addressing)

In Chaining, each slot in the hash table doesn't just hold one item; it holds a Linked List (or a pointer to one). If a collision occurs, we simply add the new item to the list at that index.

(Cross-reference: For more on how lists work, see the chapter on "Linked Lists".)

Example: Keys {22, 32} in a table of size 10.
1. \( 22 \% 10 = 2 \). Add 22 to the list at Index 2.
2. \( 32 \% 10 = 2 \). Add 32 to the list at Index 2. Now Index 2 contains both [22, 32].

Key Takeaway

Linear Probing finds a new empty home for the data elsewhere in the table, while Chaining allows multiple items to share the same address using a list.

4. Efficiency and Big-O Notation

How fast are Hash Tables? We use Big-O Notation to describe the worst-case time complexity.

Searching and Inserting

  • Average Case: \( O(1) \) (Constant Time). In a well-designed table, we go straight to the index and find the item immediately. This is much faster than Binary Search \( O(\log n) \) or Linear Search \( O(n) \).
  • Worst Case: \( O(n) \) (Linear Time). This happens if the hash function is poor and every single item collides into the same index. In this case, the hash table basically turns into a long list that we have to search through one by one.

Did you know? To keep the efficiency close to \( O(1) \), computer scientists try to keep the table only about 70% full. If it gets too crowded, collisions become very frequent!

5. Operations on Hash Tables

To implement a hash table, you need to handle these basic operations:

  • Create: Initialise an empty array of a fixed size.
  • Insert: Calculate the hash, handle collisions if necessary, and store the value.
  • Search: Calculate the hash and look at that index. If the key there isn't what you want (and you used Linear Probing), keep looking at the next slots until you find it or hit an empty slot.
  • Delete/Update: Find the item using the search logic and then remove or change its value.

6. Summary Table

Feature Linear Probing Chaining
Storage All data stays within the array. Uses extra memory for linked lists.
Searching Look at next indices until found. Traverse the list at the specific index.
Worst Case Table becomes completely full. Lists grow very long at one index.

Common Mistakes to Avoid

  1. Forgetting the Modulo: When implementing a hash function, always ensure the result fits the array size using \( \% \).
  2. Stopping Search too Early: When using Linear Probing, if you are searching for an item and find a different item at the hashed index, don't stop! You must keep looking until you find your item or an empty slot.
  3. Ignoring Wrap-Around: In Linear Probing, if you reach the last index of the array, you must reset your search to index 0.
Quick Review Box

Hash Table Summary:
- Hash Function: Turns Key \(\rightarrow\) Index.
- Collision: Two keys hitting the same index.
- Linear Probing: Check \( Index+1, Index+2... \)
- Chaining: Use a Linked List at each index.
- Complexity: \( O(1) \) average, \( O(n) \) worst case.