DSA Hashing and Hash Tables

What is Hashing?

Hashing is a process that converts any kind of data—like a number, string, or file—into a fixed-size value, often an integer. This transformed output, known as a hash, acts like a digital shortcut to quickly locate or store the original data.

Hashing is like turning a person's name into a specific seat number so you can instantly find where they sit without checking every row. Instead of searching through every student, you just go directly to the locker.

What is a Hash Table?

A Hash Table is a special data structure that uses hashing to map keys to values. It allows you to store, search, insert, or delete data very quickly—usually in constant time, i.e., O(1) on average.

You can imagine a hash table as an array where each element is a bucket that can hold one or more key-value pairs.

How Does It Work?

• Hash Function: Translates a given key into a numerical position, acting like a formula to decide where data should go.
• Indexing: Places the corresponding value directly at the computed position for instant access.
• Collision Handling: If two keys map to the same index, we handle it using special methods (explained below).

Real-Life Analogy

Imagine you have a bookshelf with numbered compartments. If you want to store a book, you look at the title, convert it into a number (hash), and place it in that compartment. To find it later, just repeat the process.

Example

hash_table = {}  

# Insert values 
hash_table["name"] = "Alice" 
hash_table["age"] = 25 
hash_table["city"] = "Delhi"  

# Access values 
Print(hash_table["name"])  # Output: Alice 

Here, "name", "age", and "city" are the keys, and their corresponding data are the values.

Hash Collisions

Sometimes, different keys can end up with the same index. This is known as a collision. For example, both "eat" and "tea" might hash to index 5.

Collision Resolution Methods:

• Chaining: Each index holds a list of items. If multiple keys land on the same index, they're stored in a list there.
• Open Addressing: If a spot is taken, we look for the next available spot in the array.

Common Hash Functions

• For integers: index = key % size
• For strings: Add up character codes and take modulo of table size.

Example for string

def simple_hash(s, size):     
        Return sum(ord(char) for char in s) % size 

Operations and Time Complexity

Applications of Hashing

• Storing data like usernames and passwords
• Checking for duplicates
• Implementing associative arrays or dictionaries
• Caching and memory indexing
• Compiler symbol tables

Benefits of Hash Tables

• Fast data retrieval using keys
• Simple to implement using arrays
• Ideal for handling vast amounts of data when rapid access to specific entries is crucial.

Limitations

• Performance drops if too many collisions happen
• Requires good hash functions to maintain efficiency
• Hash tables don’t maintain order

Example Use Case

Let's say you're building a contact list app. Instead of scanning through each contact, you can use names as keys and store their phone numbers as values.

contacts = {     
        "Ravi": "99999 11111",     
        "Asha": "88888 22222" 
} 
Print(contacts["Asha"])  # Output: 88888 22222 

Summary

• Hashing turns a key into a number.
• Hash Table stores data at that number for fast access.
• Collisions are handled by chaining or open addressing.
• Great for speed, but needs careful design of hash functions.