Guest User

Untitled

a guest
Aug 26th, 2019
120
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class QuadraticHashTable():
  2. """Is a child class of OpenAddressHashTable.
  3. If a collision then uses a quadratic probing function to find a free slot
  4. >>> hash_table = QuadraticHashTable(11)
  5. >>> hash_table.store('Dianna')
  6. >>> hash_table.store('Bobby')
  7. >>> hash_table.store('Dirk')
  8. >>> hash_table.store('Darlene')
  9. >>> hash_table.store('Paul')
  10. >>> hash_table.store('Paula')
  11. >>> hash_table.store('David')
  12. >>> hash_table.store('Harry')
  13. >>> print(hash_table)
  14. QuadraticOpenAddressHashTable:
  15. slot 0 = David
  16. slot 1 = Darlene
  17. slot 2 = Paul
  18. slot 3 = -
  19. slot 4 = Paula
  20. slot 5 = Harry
  21. slot 6 = Dirk
  22. slot 7 = -
  23. slot 8 = -
  24. slot 9 = Dianna
  25. slot 10 = Bobby
  26. n_slots = 11
  27. n_items in table = 8
  28. Load factor = 0.727
  29. <BLANKLINE>
  30. >>> 'Harry' in hash_table
  31. True
  32. >>> 'Paul' in hash_table
  33. True
  34. >>> 'Paula' in hash_table
  35. True
  36. >>> 'David' in hash_table
  37. True
  38. >>> 'Bobby' in hash_table
  39. True
  40. >>> 'Dianna' in hash_table
  41. True
  42. >>> 'Dirk' in hash_table
  43. True
  44. >>> 'Darlene' in hash_table
  45. True
  46. >>> 'Dingus' in hash_table
  47. False
  48.  
  49. """
  50.  
  51. def __init__(self, slots=11):
  52. """
  53. Creates a new hashtable with a number of slots (default: 10).
  54. Remember we can't have a load factor greater than 1 for an open hash...
  55. """
  56. self._data = [None for i in range(slots)]
  57. self.n_slots = slots
  58. self.n_items = 0
  59.  
  60. def _next_free_slot(self, first_hash):
  61. """
  62. Keeps incrementing hash index until an empty slot is found.
  63. Then returns the index of that slot.
  64. Used by the store method to help deal with a collisions.
  65. Note: this method isn't useful in __contains__ but you shoul
  66. follow a similar series of probing there.
  67. """
  68. curr_index = first_hash
  69. try_number = 0
  70. tried = []
  71. #print self._data
  72. while self._data[curr_index] is not None:
  73. tried.append(curr_index)
  74. try_number += 1
  75. if try_number > self.n_slots // 2:
  76. #print self._data
  77. print('Size = ' + str(self.n_slots))
  78. print('Number of items = ' + str(self.n_items))
  79. print('Failed to find an empty slot...')
  80. print('Try number = ' + str(try_number))
  81. print('List of tried slots = ' + str(tried))
  82. print('Current table = ' + str(self._data))
  83. print('*** Failed to find an empty slot!!!! ')
  84. print('*** This can happen with quadratic probing')
  85. print('*** if the table is over half full')
  86. raise ValueError('Failed to find an empty slot!!!!')
  87. else:
  88. curr_index = (first_hash + try_number**2) % self.n_slots
  89. return curr_index
  90.  
  91. def store(self, item):
  92. """Stores an item in the hashtable."""
  93. if self.n_slots == self.n_items:
  94. #Argh - crash, who made the hashtable too small?
  95. print(self._data)
  96. print('Size = ' + str(self.n_slots))
  97. print('Slots used = ' + str(self.n_items))
  98. print("Hash table is full!!!! You eeediot")
  99. print("A good Hasher would have resized the hash table by now!")
  100. raise ValueError("Hash table is full!!!!")
  101. # **************************************************
  102. # ---start student section---
  103. index_initial = self._hash(item)
  104. index_current = self._hash(item)
  105. i_counter = 0
  106. if not self.__contains__(item):
  107. slot_found = False
  108. while slot_found == False:
  109. if self._data[index_current] == None:
  110. self._data[index_current] = item
  111. slot_found = True
  112. else:
  113. index_current = index_initial + i_counter^2
  114. i_counter += 1
  115. if index_current == self.n_slots:
  116. index_current = 1
  117. # ===end student section===
  118. self.n_items += 1
  119.  
  120. def _hash(self, item):
  121. """Computes the hash of an item."""
  122. return nice_hash(item) % self.n_slots
  123.  
  124. def __contains__(self, item):
  125. """
  126. Checks to see if an item is stored within the hashtable.
  127. Returns True if it is, otherwise it returns False.
  128. Note: The function should give up and return False if
  129. the try_number reaches the number of slots in the table.
  130. At this stage we definitely know we are in a never ending
  131. cycle and will never find the item...
  132. You can call this method using Python's 'in' keyword:
  133. ht = HashTable()
  134. ...
  135. if 'foo' in ht:
  136. ...
  137. """
  138. first_hash = self._hash(item)
  139. i_counter = 0
  140. try_number = 0
  141. current_index = first_hash
  142. # ---start student section---
  143. first_hash = self._hash(item)
  144. have_wrapped = False
  145. if self._data[first_hash] == item:
  146. return True
  147. else:
  148. current_index = first_hash
  149. while self._data[current_index] is not None:
  150. if self._data[current_index] == item:
  151. # horay we found it
  152. return True
  153. if (current_index == first_hash) and have_wrapped:
  154. # back to original hash and didn't find item
  155. # phew - the hashtable is full!
  156. return False
  157. if current_index == (self.n_slots -1):
  158. # wrap back to start of hash table
  159. current_index = 0
  160. have_wrapped = True
  161. else:
  162. current_index = (first_hash + i_counter^2) % self.n_slots
  163. # ===end student section===
  164.  
  165. def __str__(self):
  166. output = 'QuadraticOpenAddressHashTable:\n'
  167. for i in range(self.n_slots):
  168. output += f'slot {i:8} = '
  169. item = self._data[i]
  170. if item == None:
  171. output = output + '-'
  172. else:
  173. output = output + str(item)
  174. output += '\n'
  175. load_factor = float(self.n_items) /self.n_slots
  176. output += f'n_slots = {self.n_slots}\n'
  177. output += f'n_items in table = {self.n_items}\n'
  178. output += f'Load factor = {load_factor:6.3f}\n'
  179. return output
  180.  
  181. def __repr__(self):
  182. return str(self)
RAW Paste Data