Python: Hash Table Implementation

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

1. Introduction

A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array in which an element will be inserted or searched. By using hash tables, we can achieve constant-time average complexity for search operations.

2. Program Overview

In this program, we will:

1. Implement a basic hash table from scratch.

2. Use a simple hash function.

3. Handle collisions using chaining (linked list).

3. Code Program

class HashTable: def __init__(self, capacity=50): # Initialize the hash table with given capacity self.capacity = capacity self.size = 0 self.slots = [None] * self.capacity def _hash(self, key): # Compute the hash value of a given key return hash(key) % self.capacity def insert(self, key, value): # Insert a key-value pair into the hash table key_hash = self._hash(key) key_value = [key, value] if self.slots[key_hash] is None: self.slots[key_hash] = list([key_value]) self.size += 1 return True else: for pair in self.slots[key_hash]: if pair[0] == key: pair[1] = value return True self.slots[key_hash].append(key_value) return True def search(self, key): # Search for a key in the hash table and return its value key_hash = self._hash(key) if self.slots[key_hash] is not None: for pair in self.slots[key_hash]: if pair[0] == key: return pair[1] return None def delete(self, key): # Delete a key-value pair from the hash table key_hash = self._hash(key) if self.slots[key_hash] is None: return False for i in range(0, len(self.slots[key_hash])): if self.slots[key_hash][i][0] == key: self.slots[key_hash].pop(i) return True return False # Test the HashTable class ht = HashTable() ht.insert("apple", 1) ht.insert("banana", 2) ht.insert("orange", 3) print("Value of apple:", ht.search("apple")) print("Value of banana:", ht.search("banana")) print("Value of orange:", ht.search("orange")) ht.delete("apple") print("Value of apple after deletion:", ht.search("apple")) 

Output:

Value of apple: 1 Value of banana: 2 Value of orange: 3 Value of apple after deletion: None 

4. Step By Step Explanation

1. The HashTable class initializes an empty hash table with a specified capacity (default is 50).

2. The _hash method computes the hash of the key, which is used to find an index for storing key-value pairs.

3. The insert method adds key-value pairs to the table. If there's a collision (same index for different keys), the value is added to a list at that slot (chaining).

4. The search method looks for a key and returns its corresponding value.

5. The delete method removes a key-value pair from the table.

In the example, we've added three fruit names as keys with numbers as values. After searching for the values, we then delete the key "apple" and check its value, which returns None as expected.