PYTHON Why am I getting an error and it doesn't show the right output? Problem 1 # Implement a hashtable using an array. Your implementation should include public methods for insertion, deletion, and # search, as well as helper methods for resizing. The hash table is resized when the loadfactor becomes greater than 0.6 # during insertion of a new item. You will be using linear probing technique for collision resolution. Assume the key to # be an integer and use the hash function h(k) = k mod m where m is the size of the hashtable. class HashTableProb: def __init__(self, size=10): # Initialize the hashtable with the given size and an empty array to hold the key-value pairs. self.__size = size # size of the hashtable self.__hashtable = [None for _ in range(size)] self.__itemcount = 0 # Keeps track of the number of items in the current hashtable def __contains__(self, key): return self.__searchkey(key) def __next_prime(self, x): def is_prime(x): return all(x % i for i in range(2, x)) return min([a for a in range(2*x+1, x*x) if is_prime(a)]) def __hash(self, key): # Hash function to be used for mapping a key to the indices in the hashtable. bucket = key % self.__size return bucket def __resize(self): # Resizes the hashtable to the next prime number after current table size. Also, rehashes all the current items. n = self.__next_prime(self.__size*2) new = [None for _ in range(n)] count = 0 while count < n: if self.__hashtable[count] is not None: key = self.__hashtable[count] new.insert(key) count = count + 1 self.__size = n return new def insert(self, key, value): # Insert a new key-value pair (as a python list) into the hashtable. When the loadfactor is greater than 0.6 # resizes the current hash table before inserting the new item. bucket = self.__hash(key) checked = 0 m = self.__size while checked < m: if self.__hashtable[bucket] is None: self.__hashtable[bucket].__searchkey = key self.__hashtable[bucket] = value self.__itemcount += 1 loadfactor = self.__itemcount/self.__size if loadfactor > 0.6: self.__resize() return True bucket = (bucket + 1) % m checked += 1 return False def delete(self, key): # Remove a key-value pair from the hashtable. You need to define a marker to differentiate deleted slots and # empty slots. bucket = self.__hash(key) checked = 0 m = self.__size while self.__hashtable[bucket] is not None and checked < m: if self.__hashtable[bucket] != -1 and self.__hashtable[bucket].__searchkey == key: self.__hashtable[bucket] = -1 self.__itemcount -= 1 return True bucket = (bucket + 1) % m checked += 1 return False def __search(self, key): # Find the item associated with a given key in the hashtable. bucket = self.__hash(key) checked = 0 m = self.__size while self.__hashtable[bucket] is not None and checked < m: if self.__hashtable[bucket] != -1 and self.__hashtable[bucket].__searchkey == key: return self.__hashtable[bucket] bucket = (bucket + 1) % m checked += 1 return False def showitems(self): # prints all the items in the hashtable. count = 0 m = self.__size while count < m: print(self.__hashtable[count]) count += 1 return False # Problem 1 Test Code testa = HashTableProb() print("Start") testa.showitems() testa.insert(3, 'first') testa.insert(5, 'second') testa.insert(0, 'third') print("Test insert") testa.showitems() testa.delete(3) print("Test delete") testa.showitems()
PYTHON
Why am I getting an error and it doesn't show the right output?
Problem 1
# Implement a hashtable using an array. Your implementation should include public methods for insertion, deletion, and
# search, as well as helper methods for resizing. The hash table is resized when the loadfactor becomes greater than 0.6
# during insertion of a new item. You will be using linear probing technique for collision resolution. Assume the key to
# be an integer and use the hash function h(k) = k mod m where m is the size of the hashtable.
class HashTableProb:
def __init__(self, size=10):
# Initialize the hashtable with the given size and an empty array to hold the key-value pairs.
self.__size = size # size of the hashtable
self.__hashtable = [None for _ in range(size)]
self.__itemcount = 0 # Keeps track of the number of items in the current hashtable
def __contains__(self, key):
return self.__searchkey(key)
def __next_prime(self, x):
def is_prime(x):
return all(x % i for i in range(2, x))
return min([a for a in range(2*x+1, x*x) if is_prime(a)])
def __hash(self, key):
# Hash function to be used for mapping a key to the indices in the hashtable.
bucket = key % self.__size
return bucket
def __resize(self):
# Resizes the hashtable to the next prime number after current table size. Also, rehashes all the current items.
n = self.__next_prime(self.__size*2)
new = [None for _ in range(n)]
count = 0
while count < n:
if self.__hashtable[count] is not None:
key = self.__hashtable[count]
new.insert(key)
count = count + 1
self.__size = n
return new
def insert(self, key, value):
# Insert a new key-value pair (as a python list) into the hashtable. When the loadfactor is greater than 0.6
# resizes the current hash table before inserting the new item.
bucket = self.__hash(key)
checked = 0
m = self.__size
while checked < m:
if self.__hashtable[bucket] is None:
self.__hashtable[bucket].__searchkey = key
self.__hashtable[bucket] = value
self.__itemcount += 1
loadfactor = self.__itemcount/self.__size
if loadfactor > 0.6:
self.__resize()
return True
bucket = (bucket + 1) % m
checked += 1
return False
def delete(self, key):
# Remove a key-value pair from the hashtable. You need to define a marker to differentiate deleted slots and
# empty slots.
bucket = self.__hash(key)
checked = 0
m = self.__size
while self.__hashtable[bucket] is not None and checked < m:
if self.__hashtable[bucket] != -1 and self.__hashtable[bucket].__searchkey == key:
self.__hashtable[bucket] = -1
self.__itemcount -= 1
return True
bucket = (bucket + 1) % m
checked += 1
return False
def __search(self, key):
# Find the item associated with a given key in the hashtable.
bucket = self.__hash(key)
checked = 0
m = self.__size
while self.__hashtable[bucket] is not None and checked < m:
if self.__hashtable[bucket] != -1 and self.__hashtable[bucket].__searchkey == key:
return self.__hashtable[bucket]
bucket = (bucket + 1) % m
checked += 1
return False
def showitems(self):
# prints all the items in the hashtable.
count = 0
m = self.__size
while count < m:
print(self.__hashtable[count])
count += 1
return False
# Problem 1 Test Code
testa = HashTableProb()
print("Start")
testa.showitems()
testa.insert(3, 'first')
testa.insert(5, 'second')
testa.insert(0, 'third')
print("Test insert")
testa.showitems()
testa.delete(3)
print("Test delete")
testa.showitems()
Step by step
Solved in 4 steps with 3 images
