Understanding Hashing

What Is Hashing?

Hashing is a powerful technique for storing and retrieving data quickly. It uses a hash function to convert a key (such as a name or ID) into a fixed-size index, which helps with fast searching.

Hashing is the foundation for many fast data structures, especially Hash Tables.

Why Hashing Is Important

Hashing allows you to:

• Search in O(1) average time

• Insert in O(1) time

• Delete in O(1) time

This is faster than arrays, linked lists, stacks, and queues for searching.

Real systems like compilers, caching systems, and databases rely heavily on hashing.

What Is a Hash Table?

A hash table stores data in key–value pairs.

Example:

Key: "John"
Value: 9876543210

The key is processed using a hash function to decide where to store the value.

How a Hash Function Works

A hash function takes a key and returns an index.

Example:

index = hash(key)

A good hash function should:

• Distribute keys uniformly

• Avoid collisions

• Be fast to compute

What Is a Collision?

A collision occurs when two keys produce the same index.

Example:

"Tom"  -> index 4
"Sam"  -> index 4 (collision)

Since collisions are unavoidable, we need ways to handle them.

Collision Handling Techniques

1. Chaining (Linked Lists)

Each index of the hash table stores a linked list.

Index 4 -> [Tom] -> [Sam] -> null

2. Open Addressing

When a collision happens, find another empty slot.

Common strategies:

• Linear probing

• Quadratic probing

• Double hashing

Example (Linear Probing):

Index 4 occupied ? try 5 ? try 6 ? store there

Implementing a Hash Table (Chaining Method)

public class HashTable
{
    private List<int>[] table;

    public HashTable(int size)
    {
        table = new List<int>[size];
        for (int i = 0; i < size; i++)
        {
            table[i] = new List<int>();
        }
    }

    private int Hash(int key)
    {
        return key % table.Length;
    }

    public void Insert(int key)
    {
        int index = Hash(key);
        table[index].Add(key);
    }

    public bool Search(int key)
    {
        int index = Hash(key);
        return table[index].Contains(key);
    }

    public void Delete(int key)
    {
        int index = Hash(key);
        table[index].Remove(key);
    }
}

Applications of Hashing

Hashing is used almost everywhere:

1. Databases

Fast lookup of records.

2. Caches

Quick access to frequently used data.

3. Compilers

Symbol tables.

4. Password Storage

Using cryptographic hash functions.

5. File systems

Detecting duplicates.

6. Dictionaries and Maps

Built-in structures like:

• Dictionary<TKey, TValue> in C#

• HashMap in Java

• Map in C++

Example: HashTable Using Dictionary in C#

Dictionary<string, string> phoneBook = new Dictionary<string, string>();
phoneBook["John"] = "9876543210";
phoneBook["Alice"] = "8765432109";
Console.WriteLine(phoneBook["John"]);

Time and Space Complexity

Time Complexity

Worst-case happens when all keys collide and form a long chain.

Space Complexity

• O(n)

Summary

Hashing is a fast and efficient technique used for searching, inserting, and deleting data. It is the backbone for many modern systems and data structures.

Key takeaways:

• Uses a hash function to generate an index

• Supports O(1) average time operations

• Collisions are handled using chaining or open addressing

• Used in databases, compilers, caches, and dictionaries