Hashing in Data Structures: Types and Functions [With Examples]

Hashing is a technique that maps data of arbitrary size to fixed-size values (hash codes) using a hash function. It is widely used to enable efficient O(1) average-case search, insertion, and deletion operations. Hash tables are the underlying data structure for dictionaries, sets, and caches in many programming languages.

Core Concepts

• Hash Function: A function that takes a key and returns an integer index (hash code).
• Hash Table: An array that stores key-value pairs at indices computed by the hash function.
• Collision: Occurs when two different keys map to the same index.
• Load Factor: The ratio of the number of entries to the table size. A higher load factor increases collision probability.

Types of Hash Functions

1. Division Method

The most common method: h(key) = key % table_size. Choose table_size as a prime number to reduce collisions.

def division_hash(key, table_size):
    return key % table_size

2. Multiplication Method

h(key) = floor(table_size * (key * A mod 1)) where A is a constant between 0 and 1 (often Knuth's golden ratio: 0.6180339887).

def multiplication_hash(key, table_size):
    A = 0.6180339887
    return int(table_size * ((key * A) % 1))

3. Universal Hashing

Uses a family of hash functions to randomly select one at runtime, making it harder for an adversary to cause collisions.

4. Cryptographic Hash Functions

Designed for security (e.g., SHA‑256, MD5). They are collision-resistant and one-way, used in passwords, digital signatures, and blockchain.

5. Hash Functions for Strings

def string_hash(s, table_size):
    hash_val = 0
    for char in s:
        hash_val = (hash_val * 31 + ord(char)) % table_size
    return hash_val

Collision Resolution Techniques

1. Chaining (Separate Chaining)

Each bucket of the hash table stores a linked list (or another data structure) of all entries that hash to that index. This is the simplest and most commonly used method.

class HashTableChaining:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return key % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))

    def search(self, key):
        index = self.hash_function(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

    def delete(self, key):
        index = self.hash_function(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index].pop(i)
                return True
        return False

2. Open Addressing

All entries are stored directly in the table array. When a collision occurs, the algorithm probes for the next available slot.

a. Linear Probing

Checks the next slot sequentially: h(key, i) = (h(key) + i) % size.

class HashTableLinearProbing:
    def __init__(self, size):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size

    def hash_function(self, key):
        return key % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        i = 0
        while i < self.size:
            probe = (index + i) % self.size
            if self.keys[probe] is None or self.keys[probe] == key:
                self.keys[probe] = key
                self.values[probe] = value
                return
            i += 1
        raise Exception("Hash table is full")

    def search(self, key):
        index = self.hash_function(key)
        i = 0
        while i < self.size:
            probe = (index + i) % self.size
            if self.keys[probe] is None:
                return None
            if self.keys[probe] == key:
                return self.values[probe]
            i += 1
        return None

    def delete(self, key):
        index = self.hash_function(key)
        i = 0
        while i < self.size:
            probe = (index + i) % self.size
            if self.keys[probe] is None:
                return False
            if self.keys[probe] == key:
                self.keys[probe] = None
                self.values[probe] = None
                return True
            i += 1
        return False

b. Quadratic Probing

Uses a quadratic function to probe: h(key, i) = (h(key) + c₁*i + c₂*i²) % size.

def quadratic_probe(key, i, size, c1=1, c2=1):
    return (key % size + c1 * i + c2 * i * i) % size

c. Double Hashing

Uses a second hash function to determine the probe step: h(key, i) = (h₁(key) + i * h₂(key)) % size.

def double_hash(key, i, size):
    h1 = key % size
    h2 = 1 + (key % (size - 1))
    return (h1 + i * h2) % size

Implementation in Python (Built-in)

# Python built-in dictionary (hash table)
hash_table = {}
hash_table["apple"] = 10
hash_table["banana"] = 20
hash_table["orange"] = 30

print(hash_table["banana"])  # 20
hash_table["apple"] = 15
del hash_table["orange"]
print(hash_table.get("grape", "Not found"))  # Not found

# Python built-in set
s = {1, 2, 3, 4}
s.add(5)
s.remove(3)
print(2 in s)  # True

Implementation in Java

Custom Implementation with Chaining

import java.util.LinkedList;

class HashTableChaining {
    private class Entry {
        int key;
        String value;
        Entry(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    private LinkedList[] table;
    private int size;

    @SuppressWarnings("unchecked")
    public HashTableChaining(int size) {
        this.size = size;
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }

    private int hashFunction(int key) {
        return key % size;
    }

    public void insert(int key, String value) {
        int index = hashFunction(key);
        for (Entry entry : table[index]) {
            if (entry.key == key) {
                entry.value = value;
                return;
            }
        }
        table[index].add(new Entry(key, value));
    }

    public String search(int key) {
        int index = hashFunction(key);
        for (Entry entry : table[index]) {
            if (entry.key == key) {
                return entry.value;
            }
        }
        return null;
    }

    public boolean delete(int key) {
        int index = hashFunction(key);
        for (Entry entry : table[index]) {
            if (entry.key == key) {
                table[index].remove(entry);
                return true;
            }
        }
        return false;
    }
}

Using Java's Built-in HashMap

import java.util.HashMap;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        // HashMap
        HashMap map = new HashMap<>();
        map.put("apple", 10);
        map.put("banana", 20);
        map.put("orange", 30);
        System.out.println(map.get("banana"));  // 20
        map.put("apple", 15);
        map.remove("orange");
        System.out.println(map.getOrDefault("grape", -1));  // -1

        // HashSet
        HashSet set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        set.remove(2);
        System.out.println(set.contains(3));  // true
    }
}

Implementation in C++

Custom Implementation with Chaining

#include 
#include 
#include 
using namespace std;

class HashTable {
private:
    vector>> table;
    int size;

    int hashFunction(int key) {
        return key % size;
    }

public:
    HashTable(int s) : size(s), table(s) {}

    void insert(int key, string value) {
        int index = hashFunction(key);
        for (auto& entry : table[index]) {
            if (entry.first == key) {
                entry.second = value;
                return;
            }
        }
        table[index].push_back({key, value});
    }

    string search(int key) {
        int index = hashFunction(key);
        for (auto& entry : table[index]) {
            if (entry.first == key) {
                return entry.second;
            }
        }
        return "Not found";
    }

    bool remove(int key) {
        int index = hashFunction(key);
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (it->first == key) {
                table[index].erase(it);
                return true;
            }
        }
        return false;
    }
};

Using C++ STL

#include 
#include 
#include 
using namespace std;

int main() {
    // unordered_map (hash table)
    unordered_map map;
    map["apple"] = 10;
    map["banana"] = 20;
    map["orange"] = 30;
    cout << map["banana"] << endl;  // 20
    map["apple"] = 15;
    map.erase("orange");
    cout << (map.find("grape") != map.end() ? "Found" : "Not found") << endl;

    // unordered_set
    unordered_set set = {1, 2, 3, 4};
    set.insert(5);
    set.erase(3);
    cout << (set.count(4) ? "Found" : "Not found") << endl;
    return 0;
}

Complexity Analysis

Note: Worst-case occurs when all keys collide (a poor hash function or malicious input).

Advantages & Disadvantages

Advantages

• Fast Operations: O(1) average-time search, insert, and delete.
• Simplicity: Easy to implement and use.
• Flexibility: Can store any type of key-value pair.

Disadvantages

• Collisions: Can degrade performance to O(n) in worst case.
• Memory Overhead: May use more memory than other structures (especially with chaining).
• Unordered: Does not preserve insertion order (unless using LinkedHashMap).
• Need for Good Hash Function: Performance heavily depends on the quality of the hash function.

Applications

• Dictionaries and Maps: Key-value stores in databases, programming languages, and frameworks.
• Sets: Removing duplicates, membership testing.
• Cache Implementation: LRU caches, web caches.
• Database Indexing: Hash-based indexes for fast lookups.
• Symbol Tables: Compilers and interpreters store variable names and their attributes.
• Password Storage: Storing hashed passwords (using cryptographic hash functions).
• Distributed Systems: Consistent hashing for load balancing.

Choosing a Good Hash Function

• Deterministic: Always returns the same hash for the same key.
• Uniform Distribution: Distributes keys evenly across the table to minimize collisions.
• Fast Computation: Should be quick to compute.
• Minimize Collisions: For cryptographic applications, should be collision-resistant.

Key Takeaways

• Hashing enables O(1) average-case operations for search, insert, and delete.
• Common hash functions: division method, multiplication method, and universal hashing.
• Collision resolution: chaining (linked lists) and open addressing (linear probing, quadratic probing, double hashing).
• Built-in implementations include Python's dict/set, Java's HashMap/HashSet, and C++'s unordered_map/unordered_set.
• Performance depends on a good hash function and an appropriate load factor.
• Hashing is used in databases, caches, security, and distributed systems.