Hash Tables & Collision Handling Techniques

Hashing is a powerful technique used in computer science to map data of arbitrary size to fixed-size values, making data storage and retrieval efficient. This guide will delve into the concepts of hash tables, collision handling techniques, and the applications of hashing in testing, providing a comprehensive understanding for beginners.

What is Hashing?

Hashing involves transforming input data (keys) into a fixed-size value called a hash code, typically using a hash function. The primary goal of hashing is to enable fast data retrieval and storage.

Key Characteristics of Hashing

Hash Function: A function that takes an input and produces a hash code.
Hash Code: The output of the hash function, typically a fixed-size integer.
Hash Table: A data structure that stores key-value pairs, using the hash code to index the data for quick access.

Executable Hashing Examples in Java & Python

Java
Python

import java.util.Hashtable;

public class HashTableExample {
    public static void main(String[] args) {
        Hashtable<Integer, String> hashtable = new Hashtable<>();

        // Adding key-value pairs to the hash table
        hashtable.put(1, "Test Case 1");
        hashtable.put(2, "Test Case 2");
        hashtable.put(3, "Test Case 3");

        // Display the hash table
        System.out.println("HashTable: " + hashtable);

        // Retrieve value using a key
        String value = hashtable.get(2);
        System.out.println("Value for key 2: " + value);

        // Remove a key-value pair
        hashtable.remove(3);
        System.out.println("HashTable after removing key 3: " + hashtable);
    }
}

// Output:
// HashTable: {3=Test Case 3, 2=Test Case 2, 1=Test Case 1}
// Value for key 2: Test Case 2
// HashTable after removing key 3: {2=Test Case 2, 1=Test Case 1}

class HashTable:
    def __init__(self):
        self.table = [None] * 10
    
    def hash_function(self, key):
        return key % len(self.table)
    
    def insert(self, key, value):
        hash_key = self.hash_function(key)
        self.table[hash_key] = value
    
    def retrieve(self, key):
        hash_key = self.hash_function(key)
        return self.table[hash_key]
    
    def remove(self, key):
        hash_key = self.hash_function(key)
        self.table[hash_key] = None
    
    def display(self):
        print("HashTable:", self.table)

# Example usage
hash_table = HashTable()
hash_table.insert(1, "Test Case 1")
hash_table.insert(2, "Test Case 2")
hash_table.insert(3, "Test Case 3")
hash_table.display()

value = hash_table.retrieve(2)
print("Value for key 2:", value)

hash_table.remove(3)
hash_table.display()

# Output:
# HashTable: [None, 'Test Case 1', 'Test Case 2', 'Test Case 3', None, None, None, None, None, None]
# Value for key 2: Test Case 2
# HashTable: [None, 'Test Case 1', 'Test Case 2', None, None, None, None, None, None, None]

Collision Handling Techniques

Collisions occur when two different keys hash to the same index in the hash table. Several techniques can handle collisions effectively:

1. Chaining

Chaining involves storing multiple elements at the same index using a linked list. If a collision occurs, the new element is added to the list at that index.

Executable Chaining Examples in Java & Python

Java
Python

import java.util.LinkedList;

public class ChainingHashTable {
    private LinkedList<Entry>[] table;
    
    public ChainingHashTable(int size) {
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }
    
    private int hashFunction(int key) {
        return key % table.length;
    }
    
    public void insert(int key, String value) {
        int hashKey = hashFunction(key);
        table[hashKey].add(new Entry(key, value));
    }
    
    public String retrieve(int key) {
        int hashKey = hashFunction(key);
        for (Entry entry : table[hashKey]) {
            if (entry.key == key) {
                return entry.value;
            }
        }
        return null;
    }
    
    public void remove(int key) {
        int hashKey = hashFunction(key);
        table[hashKey].removeIf(entry -> entry.key == key);
    }
    
    public void display() {
        for (int i = 0; i < table.length; i++) {
            System.out.print(i + ": ");
            for (Entry entry : table[i]) {
                System.out.print(entry.value + " -> ");
            }
            System.out.println();
        }
    }
    
    private static class Entry {
        int key;
        String value;
        
        Entry(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public static void main(String[] args) {
        ChainingHashTable hashTable = new ChainingHashTable(10);
        hashTable.insert(1, "Test Case 1");
        hashTable.insert(11, "Test Case 11"); // Collision with key 1
        hashTable.insert(2, "Test Case 2");
        hashTable.display();

        String value = hashTable.retrieve(11);
        System.out.println("Value for key 11: " + value);

        hashTable.remove(11);
        hashTable.display();
    }
}

// Output:
// 0: 
// 1: Test Case 1 -> Test Case 11 -> 
// 2: Test Case 2 -> 
// 3: 
// 4: 
// 5: 
// 6: 
// 7: 
// 8: 
// 9: 
// Value for key 11: Test Case 11
// 0: 
// 1: Test Case 1 -> 
// 2: Test Case 2 -> 
// 3: 
// 4: 
// 5: 
// 6: 
// 7: 
// 8: 
// 9:

class ChainingHashTable:
    def __init__(self):
        self.table = [[] for _ in range(10)]
    
    def hash_function(self, key):
        return key % len(self.table)
    
    def insert(self, key, value):
        hash_key = self.hash_function(key)
        self.table[hash_key].append((key, value))
    
    def retrieve(self, key):
        hash_key = self.hash_function(key)
        for k, v in self.table[hash_key]:
            if k == key:
                return v
        return None
    
    def remove(self, key):
        hash_key = self.hash_function(key)
        self.table[hash_key] = [(k, v) for k, v in self.table[hash_key] if k != key]
    
    def display(self):
        for i, bucket in enumerate(self.table):
            print(f"{i}: ", end="")
            for k, v in bucket:
                print(f"{v} -> ", end="")
            print()

# Example usage
hash_table = ChainingHashTable()
hash_table.insert(1, "Test Case 1")
hash_table.insert(11, "Test Case 11")  # Collision with key 1
hash_table.insert(2, "Test Case 2")
hash_table.display()

value = hash_table.retrieve(11)
print("Value for key 11:", value)

hash_table.remove(11)
hash_table.display()

# Output:
# 0: 
# 1: Test Case 1 -> Test Case 11 -> 
# 2: Test Case 2 -> 
# 3: 
# 4: 
# 5: 
# 6: 
# 7: 
# 8: 
# 9: 
# Value for key 11: Test Case 11
# 0: 
# 1: Test Case 1 -> 
# 2: Test Case 2 -> 
# 3: 
# 4: 
# 5: 
# 6: 
# 7: 
# 8: 
# 9:

2. Open Addressing

Open addressing involves finding the next available slot in the hash table when a collision occurs. There are several open addressing techniques, such as linear probing, quadratic probing, and double hashing.

Linear Probing

Linear probing handles collisions by checking the next slot in the array. If it’s occupied, it continues checking subsequent slots until an empty one is found.

Executable Chaining Examples in Java & Python

Java
Python

public class LinearProbingHashTable {
    private Entry[] table;
    private int size;
    
    public LinearProbingHashTable(int size) {
        this.size = size;
        table = new Entry[size];
    }
    
    private int hashFunction(int key) {
        return key % size;
    }
    
    public void insert(int key, String value) {
        int hashKey = hashFunction(key);
        while (table[hashKey] != null && table[hashKey].key != key) {
            hashKey = (hashKey + 1) % size;
        }
        table[hashKey] = new Entry(key, value);
    }
    
    public String retrieve(int key) {
        int hashKey = hashFunction(key);
        while (table[hashKey] != null && table[hashKey].key != key) {
            hashKey = (hashKey + 1) % size;
        }
        return table[hashKey] != null ? table[hashKey].value : null;
    }
    
    public void remove(int key) {
        int hashKey = hashFunction(key);
        while (table[hashKey] != null && table[hashKey].key != key) {
            hashKey = (hashKey + 1) % size;
        }
        table[hashKey] = null;
    }
    
    public void display() {
        for (int i = 0; i < size; i++) {
            if (table[i] != null) {
                System.out.println(i + ": " + table[i].value);
            } else {
                System.out.println(i + ": null");
            }
        }
    }
    
    private static class Entry {
        int key;
        String value;
        
        Entry(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public static void main(String[] args) {
        LinearProbingHashTable hashTable = new LinearProbingHashTable(10);
        hashTable.insert(1, "Test Case 1");
        hashTable.insert(11, "Test Case 11"); // Collision with key 1
        hashTable.insert(2, "Test Case 2");
        hashTable.display();

        String value = hashTable.retrieve(11);
        System.out.println("Value for key 11: " + value);

        hashTable.remove(11);
        hashTable.display();
    }
}

// Output:
// 0: null
// 1: Test Case 1
// 2: Test Case 2
// 3: null
// 4: null
// 5: null
// 6: null
// 7: null
// 8: null
// 9: null
// Value for key 11: Test Case 11
// 0: null
// 1: Test Case 1
// 2: Test Case 2
// 3: null
// 4: null
// 5: null
// 6: null
// 7: null
// 8: null
// 9: null

class LinearProbingHashTable:
    def __init__(self, size=10):
        self.table = [None] * size
        self.size = size
    
    def hash_function(self, key):
        return key % self.size
    
    def insert(self, key, value):
        hash_key = self.hash_function(key)
        while self.table[hash_key] is not None and self.table[hash_key][0] != key:
            hash_key = (hash_key + 1) % self.size
        self.table[hash_key] = (key, value)
    
    def retrieve(self, key):
        hash_key = self.hash_function(key)
        while self.table[hash_key] is not None and self.table[hash_key][0] != key:
            hash_key = (hash_key + 1) % self.size
        return self.table[hash_key][1] if self.table[hash_key] is not None else None
    
    def remove(self, key):
        hash_key = self.hash_function(key)
        while self.table[hash_key] is not None and self.table[hash_key][0] != key:
            hash_key = (hash_key + 1) % self.size
        self.table[hash_key] = None
    
    def display(self):
        for i, entry in enumerate(self.table):
            if entry is not None:
                print(f"{i}: {entry[1]}")
            else:
                print(f"{i}: null")

# Example usage
hash_table = LinearProbingHashTable()
hash_table.insert(1, "Test Case 1")
hash_table.insert(11, "Test Case 11")  # Collision with key 1
hash_table.insert(2, "Test Case 2")
hash_table.display()

value = hash_table.retrieve(11)
print("Value for key 11:", value)

hash_table.remove(11)
hash_table.display()

# Output:
# 0: null
# 1: Test Case 1
# 2: Test Case 2
# 3: null
# 4: null
# 5: null
# 6: null
# 7: null
# 8: null
# 9: null
# Value for key 11: Test Case 11
# 0: null
# 1: Test Case 1
# 2: Test Case 2
# 3: null
# 4: null
# 5: null
# 6: null
# 7: null
# 8: null
# 9: null

Applications of Hashing in Testing

Efficient Data Storage

Hash tables provide efficient data storage, making it easy to store and retrieve test cases based on unique identifiers. This is particularly useful in large test suites where quick access to specific test cases is essential.

Managing Test Execution States

Hashing can be used to manage the state of test executions, storing results and statuses of individual test cases. This allows for quick updates and retrieval of test case states during testing cycles.

Detecting Duplicate Test Cases

Hashing can help detect duplicate test cases by hashing the content of each test case and comparing hash values. This ensures that only unique test cases are executed, reducing redundancy.

Executable Examples in Java & Python for Managing Test Cases

Java
Python

import java.util.Hashtable;

public class TestCaseManager {
    private Hashtable<Integer, String> testCases;

    public TestCaseManager() {
        testCases = new Hashtable<>();
    }

    public void addTestCase(int id, String testCase) {
        testCases.put(id, testCase);
    }

    public String getTestCase(int id) {
        return testCases.get(id);
    }

    public void removeTestCase(int id) {
        testCases.remove(id);
    }

    public void displayTestCases() {
        System.out.println("Test Cases: " + testCases);
    }

    public static void main(String[] args) {
        TestCaseManager manager = new TestCaseManager();
        manager.addTestCase(1, "Test Case 1");
        manager.addTestCase(2, "Test Case 2");
        manager.displayTestCases();

        String testCase = manager.getTestCase(1);
        System.out.println("Retrieved Test Case 1: " + testCase);

        manager.removeTestCase(1);
        manager.displayTestCases();
    }
}

// Output:
// Test Cases: {2=Test Case 2, 1=Test Case 1}
// Retrieved Test Case 1: Test Case 1
// Test Cases: {2=Test Case 2}

class TestCaseManager:
    def __init__(self):
        self.test_cases = {}
    
    def add_test_case(self, id, test_case):
        self.test_cases[id] = test_case
    
    def get_test_case(self, id):
        return self.test_cases.get(id)
    
    def remove_test_case(self, id):
        if id in self.test_cases:
            del self.test_cases[id]
    
    def display_test_cases(self):
        print("Test Cases:", self.test_cases)

# Example usage
manager = TestCaseManager()
manager.add_test_case(1, "Test Case 1")
manager.add_test_case(2, "Test Case 2")
manager.display_test_cases()

test_case = manager.get_test_case(1)
print("Retrieved Test Case 1:", test_case)

manager.remove_test_case(1)
manager.display_test_cases()

# Output:
# Test Cases: {1: 'Test Case 1', 2: 'Test Case 2'}
# Retrieved Test Case 1: Test Case 1
# Test Cases: {2: 'Test Case 2'}

Conclusion

Hashing is a crucial technique in computer science, providing efficient data storage and retrieval. Understanding hash tables, collision handling techniques, and their applications in testing will enhance your ability to manage test cases effectively.