ASSIGNMENT WEEK – 15
Name – HIMANSHU RAJ
Register No. - EA2331201010152
Program - B.C.A.-Data Science
Subject – Data Structure & Algorithm (DSA)
Semester – II Semester
EA2331201010152
Q. Implement hash table where collisions are handled using linear probing.
Take the hash table implementation that uses chaining and modify methods to
use linear probing. Keep MAX size of arr in hashtable as 10.
Ans. Python
class HashTable:
def __init__(self, max_size=10):
self.MAX_SIZE = max_size
[Link] = [None] * self.MAX_SIZE
[Link] = 0 # Keep track of filled slots
def hash_function(self, key):
# Replace with your desired hash function (e.g., mod
by MAX_SIZE)
return key % self.MAX_SIZE
def __setitem__(self, key, value):
"""Inserts a key-value pair into the hash table."""
index = self.hash_function(key)
probing_index = index
# Linear probing to find an empty slot
while [Link][probing_index] is not None:
probing_index = (probing_index + 1) %
self.MAX_SIZE # Wrap around if needed
# Check for full table
if probing_index == index:
raise Exception("Hash table overflow")
[Link][probing_index] = (key, value)
[Link] += 1
def __getitem__(self, key):
"""Retrieves the value associated with a key."""
index = self.hash_function(key)
probing_index = index
# Linear probing to find the key or an empty slot
while [Link][probing_index] is not None:
stored_key, _ = [Link][probing_index]
if stored_key == key:
return [Link][probing_index][1] # Return
the value
probing_index = (probing_index + 1) %
self.MAX_SIZE
EA2331201010152
# Key not found in the probed positions
if probing_index == index:
raise KeyError("Key not found")
raise KeyError("Key not found")
def __delitem__(self, key):
"""Deletes the key-value pair from the hash table."""
index = self.hash_function(key)
probing_index = index
# Linear probing to find the key
while [Link][probing_index] is not None:
stored_key, _ = [Link][probing_index]
if stored_key == key:
[Link][probing_index] = None # Mark the
slot as empty
[Link] -= 1
return
probing_index = (probing_index + 1) %
self.MAX_SIZE
# Key not found in the probed positions
if probing_index == index:
raise KeyError("Key not found")
raise KeyError("Key not found")
Explanation:
1. Initialization:
o MAX_SIZE defines the maximum size of the hash table array.
o arr is an array of slots, initially set to None to represent empty slots.
o size keeps track of the number of filled slots in the hash table.
2. Hash Function:
o Replace hash_function with your chosen hashing function (e.g., modulo by
MAX_SIZE for simplicity).
3. setitem (Insert):
o Calculates the initial index using the hash function.
o Uses a probing_index variable to iterate through the array linearly.
o While the slot at probing_index is not empty:
▪ Increment probing_index (wrapping around if needed) to find the
next available slot.
▪ Checks for a full table and raises an exception if all slots are occupied.
o Once an empty slot is found, stores the (key, value) pair there.
EA2331201010152
o Increments size to reflect the new element.
4. getitem (Get):
o Calculates the initial index using the hash function.
o Uses a probing_index variable to iterate through the array linearly.
o While the slot at probing_index is not empty:
▪ Checks if the stored key matches the search key. If so, returns the
associated value.
▪ Increment probing_index (wrapping around if needed) to continue
probing.
▪ Raises a KeyError if the key is not found after probing all possible
positions.
o Raises a KeyError if the initial slot and all probed positions are empty
EA2331201010152
