1. Consider the following ListDict class implementation.class ListDict(object): """A list-based implementation of a dictionary.""" def __init__(self): self._table = [] def __getitem__(self, key): """Returns the value associated with key or returns None if key does not exist.""" entry = Entry(key, None) try: index = self._table.index(entry) return self._table[index].value except: return None def pop(self, key): """Removes the entry associated with key and returns its value or returns None if key does not exist.""" entry = Entry(key, None) try: index = self._table.index(entry) return self._table.pop(index).value except: return None def __setitem__(self, key, value): """Inserts an entry with key/value if key does not exist or replaces the existing value with value if key exists.""" entry = Entry(key, value) try: index = self._table.index(entry) self._table[index] = entry except: self._table.append(entry) # The methods __len__(), __str__(), keys(), # __contains__, and values() are exercisesData Structures (810:052) Lecture 21Name:_________________Lecture 21 Page 1ListDictobject_table. . .01 2 3 4 5Python list objecta) Explain how the __getitem__ methodlooks up a key?b) What is the average-case theta notation ofeach operation?__getitem__(self, key):pop(self, key):__setitem__(self, key, value):__contains__(key):""" File: dictionary.py """class Entry(object): """A key/value pair.""" def __init__(self, key, value): self.key = key self.value = value def __eq__(self, other): return self.key == other.key def __str__(self): return str(self.key) + ":" + str(self.value)2. Consider the following HashDict class implementation.from arrays import Arrayclass HashEntry(Entry): def __init__(self, key, value, next): Entry.__init__(self, key, value) self.next = nextclass HashDict(object): """A hashing implementation of a dictionary.""" DEFAULT_CAPACITY = 3 def __init__(self, capacity = None): if capacity is None: self._capacity = HashDict.DEFAULT_CAPACITY else: self._capacity = capacity self._table = Array(self._capacity) self._size = 0 self._priorEntry = None self._foundEntry = None self._index = None def __contains__(self, key): """Returns True if key is in the dictionary or False otherwise.""" self._index = abs(hash(key)) % self._capacity self._priorEntry = None self._foundEntry = self._table[self._index] while self._foundEntry != None: if self._foundEntry.key == key: return True else: self._priorEntry = self._foundEntry self._foundEntry = self._foundEntry.next return False def __getitem__(self, key): """Returns the value associated with key or returns None if key does not exist.""" if key in self: return self._foundEntry.value else: return None def pop(self, key): """Removes the entry associated with key and returns its value or returns None if key does not exist.""" if not key in self: return None else: if self._priorEntry is None: self._table[self._index] = self._foundEntry.next else: self._priorEntry.next = self._foundEntry.next self._size -= 1 return self._foundEntry.valueData Structures (810:052) Lecture 21Name:_________________Lecture 21 Page 2 def __setitem__(self, key, value): """Inserts an entry with key/value if key does not exist or replaces the existing value with value if key exists.""" if not key in self: newEntry = HashEntry(key, value, self._table[self._index]) self._table[self._index] = newEntry self._size += 1 return None else: returnValue = self._foundEntry.value self._foundEntry.value = value return returnValue def __len__(self): return self._size def __str__(self): result = "HashDict: capacity = " + \ str(self._capacity) + ", load factor = " + \ str(len(self) / float(self._capacity)) for i in xrange(self._capacity): rowStr = "" entry = self._table[i] while entry != None: rowStr += str(entry) + " " entry = entry.next if rowStr != "": result += "\nRow " + str(i) + ": " + rowStr return result # The methods keys() and values() are exercisesa) Explain how the __getitem__ method looks up a key?b) What is the average-case theta notation of eachoperation? (Let α be load factor (n/Array size))__getitem__(self, key):pop(self, key):__setitem__(self, key, value):__contains__(key):3. Consider the following HashTable class implementation.Data Structures (810:052) Lecture 21Name:_________________Lecture 21 Page 3""" File: hashtable.py Case study for Chapter 19. """from arrays import Arrayclass HashTable(object): "Represents a hash table.""" EMPTY = None DELETED = True def __init__(self, capacity = 29, hashFunction = hash, linear = True): self._table = Array(capacity, HashTable.EMPTY) self._size = 0 self._hash = hashFunction self._homeIndex = -1 self._actualIndex = -1 self._linear = linear self._probeCount = 0 def insert(self, item): """Inserts item into the table Preconditions: There is at least one empty cell or one previously occupied cell. There is not a duplicate item.""" self._probeCount = 0 # Get the home index self._homeIndex = abs(self._hash(item)) % len(self._table) distance = 1 index = self._homeIndex # Stop searching when an empty cell is encountered while not self._table[index] in (HashTable.EMPTY, HashTable.DELETED): # Increment the index and wrap around to first # position if necessary if self._linear: increment = index + 1 else: # Quadratic probing increment = self._homeIndex + distance ** 2 distance += 1 index = increment % len(self._table) self._probeCount += 1 # An empty cell is found, so store the item self._table[index] = item self._size += 1 self._actualIndex = index def search(self, item): """Search for item in the table.""" self._probeCount = 0 # Get the home index self._homeIndex = abs(self._hash(item)) % len(self._table) distance = 1 index = self._homeIndex # Stop searching when an empty cell is encountered while not self._table[index] in (HashTable.EMPTY, item): # Increment the index and wrap around to first # position if necessary if self._linear: increment = index + 1 else: # Quadratic probing increment = self._homeIndex + distance ** 2 distance += 1 index = increment % len(self._table) self._probeCount += 1 # An empty cell is found, so return None if self._table[index] == HashTable.EMPTY: