In the hash table map implementation, the hash table size was chosen to be 101.
ID: 3579564 • Letter: I
Question
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. hash file so far
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
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.