Hash Tables & Collision Handling Techniques
Ishan Dev ShuklAmbassador
Aug 1, 2024
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
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
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
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: nullclass 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: nullApplications 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
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.
Was this article helpful?
Ishan Dev ShuklAmbassador
With 14+ years in test automation, Ishan specializes in building scalable automation frameworks, AI-driven testing strategies, and modern quality engineering practices. He writes about automation tools, testing architecture, and the future of QA. His mission is simple: help testers evolve into engineers who build quality into every system.
Join the QABash community
Answer challenges, earn XP, grow your testing career.
Discussion
No comments yet
Be the first to share your thoughts.