• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Aug 26th, 2019 91 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
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)
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):
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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top