NEED HELP PLEASE Exercise Due TOMORROW NIGHT. Python Map Exercise Using Python,
ID: 3567481 • Letter: N
Question
NEED HELP PLEASE Exercise Due TOMORROW NIGHT.
Python Map Exercise
Using Python, start with the code below. Change the code to use chaining instead of the rehash function shown.
You must re-implement put and get to correctly do chaining.
Chaining is most easily accomplished in python by each hash slot holding a list instead of a single data element, so an empty list should be added to every slot for both data and for the slots list.
*Note do not do [ [ ] ]*size to do this, it will have every slot point to the same list. Instead use [list() for x in range(size) ] list comprehension or use a loop to set each slot to a list().
Keep the size of the map at 11 for the test code. The test code is added to the end of the map.py file to test your implementation. Do not change the test code in anyway.
#START WITH PROGRAM BELOW and implement using instructions above:
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))
start = nextslot
while self.slots[nextslot] != None and
self.slots[nextslot] != key:
nextslot = self.rehash(nextslot,len(self.slots))
if nextslot == start: # error, we have loop all the way round
raise RuntimeError("Map is full")
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)
#END OF PROGRAM.
# Keep the size of the map at 11 for the test code.
#test your implementation. Do not change the test code below in anyway.
h = HashTable() # create new hash table
nums = [1, 3, 5, 50, 1000] # some keys
nums = nums + [ len(h.slots)*i for i in range(20)] # some keys that have same hash
vals = vals = [ chr(x) for x in range(ord('A'),ord('Z')) ] # list of single letters from A to Z
# add key/values
for i in range(len(nums)):
# print("adding (%d, %s)"%(nums[i],vals[i]),end=" ")
h[nums[i]] = vals[i]
for i in range(len(nums)):
key = nums[i]
value = vals[i]
gotValue = h[key]
assert gotValue == value,"expected key: %d to lookup value: %s but got value %s instead " % (key, value, gotValue)
print(" All TESTS PASSED")
Explanation / Answer
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))
start = nextslot
while self.slots[nextslot] != None and
self.slots[nextslot] != key:
nextslot = self.rehash(nextslot,len(self.slots))
if nextslot == start: # error, we have loop all the way round
raise RuntimeError("Map is full")
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)
#END OF PROGRAM.
h = HashTable() # create new hash table
nums = [1, 3, 5, 50, 1000] # some keys
nums = nums + [ len(h.slots)*i for i in range(20)] # some keys that have same hash
vals = vals = [ chr(x) for x in range(ord('A'),ord('Z')) ] # list of single letters from A to Z
# add key/values
for i in range(len(nums)):
# print("adding (%d, %s)"%(nums[i],vals[i]),end=" ")
h[nums[i]] = vals[i]
for i in range(len(nums)):
key = nums[i]
value = vals[i]
gotValue = h[key]
assert gotValue == value,"expected key: %d to lookup value: %s but got value %s instead " % (key, value, gotValue)
print(" All TESTS PASSED")
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.