# Untitled

a guest
Aug 26th, 2019
120
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
2. """Is a child class of OpenAddressHashTable.
3. If a collision then uses a quadratic probing function to find a free slot
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)
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
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):
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'