The HashTable class implemented in chapter 5.5.3 of your online textbook (chapter 5.2.3.3 in the dead tree version) exhibits undesirable behavior if you use put(key,val) to add a new key-value pair when the table is full. Re-implement the put method so that the table will automatically increase in size when the method detects that the table is full. The new size should be the smallest prime number that is at least twice the original size. For example, if the original size is 11, the new size would be 23, not 22. You may assume that maximum size for the table is 1009 (which is the smallest prime number greater than 1000).

The function that needs to be edited:

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)