python language In the hash table map implementation, the hash table size was ch
ID: 3576952 • Letter: P
Question
python language
In the hash table map implementation, the hash table size was chosen to be 101. If the table gets full, this needs to be increased. Re-implement the put method so that the table will automatically resize itself when the loading factor reaches a predetermined value (you can decide the value based on your assessment of load versus performance). Remember that all current data will have to be re-hashed based on the new table size.
Add the len method (__len__) and the in method (__contains__) for the has table Map ADT.
implement quadratic probing as a rehash technique. Test this new feature for both adding items to the hash table and finding items that are in the hash table. Be sure to test for items that hash to the same location.
Test all of the above. Also, write a paragraph explaining why you chose the loading factor you used in the put function.
============================================Hash=======================================
class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
def put(self, key, data):
hashValue = self.hashfunction(key, len(self.slots))
if self.slots[hashValue] == None:
self.slots[hashValue] = key
self.data[hashValue] = data
else:
if self.slots[hashValue] == key:
self.data[hashValue] = data # replace
else:
nextslot = self.rehash(hashValue, len(self.slots))
while self.slots[nextslot] != None and
self.slots[nextslot] != key:
nextslot = self.rehash(nextslot, len(self.slots))
if self.slots[nextslot] == None:
self.slots[nextslot] = key
self.data[nextslot] = data
else:
self.data[nextslot] = data # replace
def hashfunction(self, key, size):
return key % size
def rehash(self, oldhash, size):
return (oldhash + 1) % size
def get(self, key):
startslot = self. hashfunction(key, len(self.slots))
data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and
not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position = self.rehash(position, len(self.slots))
if position == startslot:
stop = True
return data
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key, data)
def main():
H = HashTable()
H[54] = "cat"
H[26] = "dog"
H[93] = "lion"
H[17] = "tiger"
H[31] = "bird"
H[44] = "cow"
H[55] = "pig"
H[20] = "chicken"
print("After adding 8 items")
print(H.slots)
print("Hash 20: ", H[20])
print("Hash 17: ", H[17])
H[20] = "duck"
print("Change Hash 20 from chicken to duck: ", H[20])
print("Hash data")
print(H.data)
main()
Explanation / Answer
class HashTable:
def __init__(self, size = 11):
self.MAXLOADFACTOR = 0.75
self.MINLOADFACTOR = 0.25
self.MINSIZE = size
self.size = size
self.totalItems = 0
self.slots = [None] * self.size
self.data = [None] * self.size
def put(self, key, data):
hashvalue = self.hashfunction(key)
if self.slots[hashvalue] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = data
self.totalItems += 1
self.checkGrow()
else:
if self.slots[hashvalue] == key:
self.data[hashvalue] = data
else:
nextslot = self.rehash(hashvalue, len(self.slots))
while self.slots[nextslot] != None and self.slots[nextslot] != key:
nextslot = self.rehash(nextslot,len(self.slots))
if self.slots[nextslot] == None:
self.slots[nextslot] = key
self.data[nextslot] = data
self.totalItems += 1
self.checkGrow()
else:
self.data[nextslot] = data
def hashfunction(self, key):
if isinstance(key, int):
return key % self.size
else:
s = str(key)
return sum([ord(c) for c in s]) % self.size
def rehash(self, oldhash, size):
return (oldhash + 1) % size
def get(self, key):
startslot = self.hashfunction(key)
data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position = self.rehash(position, len(self.slots))
if position == startslot:
stop = True
return data
def remove(self, key):
hashvalue = self.hashfunction(key)
if self.slots[hashvalue] == None:
return False
else:
if self.slots[hashvalue] == key:
self.slots[hashvalue] = None
self.data[hashvalue] = None
self.totalItems -= 1
self.checkShrink()
else:
nextslot = self.rehash(hashvalue, len(self.slots))
while self.slots[nextslot] != None and self.slots[nextslot] != key:
nextslot = self.rehash(nextslot,len(self.slots))
if self.slots[nextslot] == None:
return False
else:
self.slots[nextslot] = None
self.data[nextslot] = None
self.totalItems -= 1
self.checkShrink()
def checkGrow(self):
if self.totalItems > self.MAXLOADFACTOR * self.size:
self.grow()
def grow(self):
newSize = 2 * self.size
newHashTable = HashTable(newSize)
for key in self.slots:
if key != None:
newHashTable.put(key, self.get(key))
self.size = newSize
self.slots = copy.deepcopy(newHashTable.slots)
self.data = copy.deepcopy(newHashTable.data)
del newHashTable
def checkShrink(self):
if self.totalItems < self.MINLOADFACTOR * self.size and self.size >= self.MINSIZE * 2:
self.shrink()
def shrink(self):
newSize = self.size // 2
newHashTable = HashTable(newSize)
for key in self.slots:
if key != None:
newHashTable.put(key, self.get(key))
self.size = newSize
self.slots = copy.deepcopy(newHashTable.slots)
self.data = copy.deepcopy(newHashTable.data)
del newHashTable
def clearTable(self, size = 11):
self.MAXLOADFACTOR = 0.75
self.MINLOADFACTOR = 0.25
self.MINSIZE = size
self.size = size
self.totalItems = 0
self.slots = [None] * self.size
self.data = [None] * self.size
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key, data)
def __str__(self):
s=''
for k in self.slots:
if k != None:
s = s + str(k) + ': ' + str(self.get(k)) + ' '
return s[:-1]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.