· 8 years ago · Dec 04, 2017, 09:32 AM
1#!python
2
3from linkedlist import LinkedList
4
5class HashTable(object):
6
7 def __init__(self, init_size=8):
8 """Initialize this hash table with the given initial size."""
9 self.buckets = [LinkedList() for i in range(init_size)]
10 self.size = 0 # Number of key-value entries
11
12 def __str__(self):
13 """Return a formatted string representation of this hash table."""
14 items = ['{!r}: {!r}'.format(key, val) for key, val in self.items()]
15 return '{' + ', '.join(items) + '}'
16
17 def __repr__(self):
18 """Return a string representation of this hash table."""
19 return 'HashTable({!r})'.format(self.items())
20
21 def _bucket_index(self, key):
22 """Return the bucket index where the given key would be stored."""
23 return hash(key) % len(self.buckets)
24
25 def load_factor(self):
26 """Return the load factor, the ratio of number of entries to buckets.
27 Best and worst case running time: Theta(n) it always depends on the number
28 of items that need to be counted, one by one"""
29 return float(self.size) / (len(self.buckets))
30
31 def keys(self):
32 """Return a list of all keys in this hash table.
33 Best and worst case running time: O(n^2)"""
34 # Collect all keys in each of the buckets
35 all_keys = []
36 for bucket in self.buckets:
37 for key, value in bucket.items():
38 all_keys.append(key)
39 return all_keys
40
41 def values(self):
42 """Return a list of all values in this hash table.
43 Best and worst case running time: O(n^2)"""
44 # Collect all values in each of the buckets
45 all_values = []
46 for bucket in self.buckets:
47 for key, value in bucket.items():
48 all_values.append(value)
49 return all_values
50
51 def items(self):
52 """Return a list of all entries (key-value pairs) in this hash table.
53 Best and worst case running time: O(n^2)"""
54 # Collect all pairs of key-value entries in each of the buckets
55 all_items = []
56 for bucket in self.buckets:
57 all_items.extend(bucket.items())
58 return all_items
59
60 def length(self):
61 """Return the number of key-value entries by traversing its buckets.
62 Best and worst case running time: O(1)"""
63 return self.size
64
65 def contains(self, key):
66 """Return True if this hash table contains the given key, or False.
67 Best case running time: O(1) near beginning of list of keys
68 Worst case running time: O(n) near end of list of keys """
69 # Find the bucket the given key belongs in
70 index = self._bucket_index(key)
71 bucket = self.buckets[index]
72 entry = bucket.find(lambda key_value: key_value[0] == key)
73 return entry is not None # True or False
74
75 def get(self, key):
76 """Return the value associated with the given key, or raise KeyError.
77 Best case running time: O(1) if entry is near beginning of list in first bucket
78 Worst case running time: O(n) in most cases it will be theta(n) and depend
79 on where it is located in the list of items"""
80 # Find the bucket the given key belongs in
81 index = self._bucket_index(key)
82 bucket = self.buckets[index]
83 # # Find the entry with the given key in that bucket, if one exists
84 entry = bucket.find(lambda key_value: key_value[0] == key)
85 # Return the given key's associated value
86 if entry is not None:
87 assert isinstance(entry, tuple)
88 assert len(entry) == 2
89 return entry[1]
90 else:
91 raise KeyError('Key not found: {}'.format(key))
92
93 def set(self, key, value):
94 """Insert or update the given key with its associated value.
95 Best case running time: O(1) if it's near beginning of LL
96 Worst case running time: O(n) in most cases, depends on position in LL"""
97 # Find the bucket the given key belongs in
98 index = self._bucket_index(key)
99 bucket = self.buckets[index]
100 # Find the entry with the given key in that bucket, if one exists
101 # Check if an entry with the given key exists in that bucket
102 entry = bucket.find(lambda key_value: key_value[0] == key)
103 if entry is not None: # Found
104 # In this case, the given key's value is being updated
105 # Remove the old key-value entry from the bucket first
106 bucket.delete(entry)
107 else:
108 # If not found, increase size by one to account for new item
109 self.size += 1
110 # Insert the new key-value entry into the bucket in either case
111 bucket.append((key, value))
112 # Check if load_factor exceeds threshold, if it does, resize hashtable
113 if self.load_factor() > 0.75:
114 self._resize()
115
116 def delete(self, key):
117 """Delete the given key and its associated value, or raise KeyError.
118 Best case running time: O(1) if near beginning of LL
119 Worst case running time: O(n) in most cases, depends on position in LL"""
120 # Find the bucket the given key belongs in
121 index = self._bucket_index(key)
122 bucket = self.buckets[index]
123 # Find the entry with the given key in that bucket, if one exists
124 entry = bucket.find(lambda key_value: key_value[0] == key)
125 if entry is not None: # Found
126 # Remove the key-value entry from the bucket
127 bucket.delete(entry)
128 self.size -= 1
129 else: # Not found
130 raise KeyError('Key not found: {}'.format(key))
131
132 def _resize(self, new_bucket_count=None):
133 """Resize this hash table's buckets and rehash all key-value entries.
134 Should be called automatically when load factor exceeds a threshold
135 such as 0.75 after an insertion (when set is called with a new key).
136 Best and worst case running time: ??? under what conditions? [TODO]
137 Best and worst case space usage: ??? what uses this memory? [TODO]"""
138 # If unspecified, choose new size dynamically based on current size
139 if new_bucket_count is None:
140 new_bucket_count = len(self.buckets) * 2 # Double the bucket
141 # Option to reduce size if buckets are sparsely filled (low load factor)
142 elif new_bucket_count is 0:
143 new_bucket_count = len(self.buckets) // 2 # Half the bucket
144 # Get a list to temporarily hold all current key-value entries
145 old_items = self.items()
146 # Create a list of new buckets to be used for rehashing
147 self.buckets = [LinkedList() for _ in range(new_bucket_count)]
148 # Reset size
149 self.size = 0
150 # Insert each key-value entry into the new list of buckets,
151 for key, value in old_items:
152 self.set(key, value)
153
154
155def test_hash_table():
156 ht = HashTable(4)
157 print('HashTable: ' + str(ht))
158
159 print('Setting entries:')
160 ht.set('I', 1)
161 print('set(I, 1): ' + str(ht))
162 ht.set('V', 5)
163 print('set(V, 5): ' + str(ht))
164 print('size: ' + str(ht.size))
165 print('length: ' + str(ht.length()))
166 print('buckets: ' + str(len(ht.buckets)))
167 print('load_factor: ' + str(ht.load_factor()))
168 ht.set('X', 10)
169 print('set(X, 10): ' + str(ht))
170 ht.set('L', 50) # Should trigger resize
171 print('set(L, 50): ' + str(ht))
172 print('size: ' + str(ht.size))
173 print('length: ' + str(ht.length()))
174 print('buckets: ' + str(len(ht.buckets)))
175 print('load_factor: ' + str(ht.load_factor()))
176
177 print('Getting entries:')
178 print('get(I): ' + str(ht.get('I')))
179 print('get(V): ' + str(ht.get('V')))
180 print('get(X): ' + str(ht.get('X')))
181 print('get(L): ' + str(ht.get('L')))
182 print('contains(X): ' + str(ht.contains('X')))
183 print('contains(Z): ' + str(ht.contains('Z')))
184
185 print('Deleting entries:')
186 ht.delete('I')
187 print('delete(I): ' + str(ht))
188 ht.delete('V')
189 print('delete(V): ' + str(ht))
190 ht.delete('X')
191 print('delete(X): ' + str(ht))
192 ht.delete('L')
193 print('delete(L): ' + str(ht))
194 print('contains(X): ' + str(ht.contains('X')))
195 print('size: ' + str(ht.size))
196 print('length: ' + str(ht.length()))
197 print('buckets: ' + str(len(ht.buckets)))
198 print('load_factor: ' + str(ht.load_factor()))
199
200
201if __name__ == '__main__':
202 test_hash_table()
203
204
205
206#!python
207
208from hashtable import HashTable
209import unittest
210# Python 2 and 3 compatibility: unittest module renamed this assertion method
211if not hasattr(unittest.TestCase, 'assertCountEqual'):
212 unittest.TestCase.assertCountEqual = unittest.TestCase.assertItemsEqual
213
214
215class HashTableTest(unittest.TestCase):
216
217 def test_init(self):
218 ht = HashTable(4)
219 assert len(ht.buckets) == 4
220 assert ht.length() == 0
221 assert ht.size == 0
222
223 def test_keys(self):
224 ht = HashTable()
225 assert ht.keys() == []
226 ht.set('I', 1)
227 assert ht.keys() == ['I']
228 ht.set('V', 5)
229 self.assertCountEqual(ht.keys(), ['I', 'V']) # Ignore item order
230 ht.set('X', 10)
231 self.assertCountEqual(ht.keys(), ['I', 'V', 'X']) # Ignore item order
232
233 def test_values(self):
234 ht = HashTable()
235 assert ht.values() == []
236 ht.set('I', 1)
237 assert ht.values() == [1]
238 ht.set('V', 5)
239 self.assertCountEqual(ht.values(), [1, 5]) # Ignore item order
240 ht.set('X', 10)
241 self.assertCountEqual(ht.values(), [1, 5, 10]) # Ignore item order
242
243 def test_items(self):
244 ht = HashTable()
245 assert ht.items() == []
246 ht.set('I', 1)
247 assert ht.items() == [('I', 1)]
248 ht.set('V', 5)
249 self.assertCountEqual(ht.items(), [('I', 1), ('V', 5)])
250 ht.set('X', 10)
251 self.assertCountEqual(ht.items(), [('I', 1), ('V', 5), ('X', 10)])
252
253 def test_length(self):
254 ht = HashTable()
255 assert ht.length() == 0
256 ht.set('I', 1)
257 assert ht.length() == 1
258 ht.set('V', 5)
259 assert ht.length() == 2
260 ht.set('X', 10)
261 assert ht.length() == 3
262
263 def test_size(self):
264 ht = HashTable()
265 assert ht.size == 0
266 ht.set('I', 1)
267 assert ht.size == 1
268 ht.set('V', 5)
269 assert ht.size == 2
270 ht.set('X', 10)
271 assert ht.size == 3
272
273 def test_resize(self):
274 ht = HashTable(2) # Set init_size to 2
275 assert ht.size == 0
276 assert len(ht.buckets) == 2
277 assert ht.load_factor() == 0
278 ht.set('I', 1)
279 assert ht.size == 1
280 assert len(ht.buckets) == 2
281 assert ht.load_factor() == 0.5
282 ht.set('V', 5) # Should trigger resize
283 assert ht.size == 2
284 assert len(ht.buckets) == 4
285 assert ht.load_factor() == 0.5
286 ht.set('X', 10)
287 assert ht.size == 3
288 assert len(ht.buckets) == 4
289 assert ht.load_factor() == 0.75
290 ht.set('L', 50) # Should trigger resize
291 assert ht.size == 4
292 assert len(ht.buckets) == 8
293 assert ht.load_factor() == 0.5
294
295 def test_contains(self):
296 ht = HashTable()
297 ht.set('I', 1)
298 ht.set('V', 5)
299 ht.set('X', 10)
300 assert ht.contains('I') is True
301 assert ht.contains('V') is True
302 assert ht.contains('X') is True
303 assert ht.contains('A') is False
304
305 def test_set_and_get(self):
306 ht = HashTable()
307 ht.set('I', 1)
308 ht.set('V', 5)
309 ht.set('X', 10)
310 assert ht.get('I') == 1
311 assert ht.get('V') == 5
312 assert ht.get('X') == 10
313 assert ht.length() == 3
314 assert ht.size == 3
315 with self.assertRaises(KeyError):
316 ht.get('A') # Key does not exist
317
318 def test_set_twice_and_get(self):
319 ht = HashTable()
320 ht.set('I', 1)
321 ht.set('V', 4)
322 ht.set('X', 9)
323 assert ht.length() == 3
324 assert ht.size == 3
325 ht.set('V', 5) # Update value
326 ht.set('X', 10) # Update value
327 assert ht.get('I') == 1
328 assert ht.get('V') == 5
329 assert ht.get('X') == 10
330 assert ht.length() == 3 # Check length is not overcounting
331 assert ht.size == 3 # Check size is not overcounting
332
333 def test_delete(self):
334 ht = HashTable()
335 ht.set('I', 1)
336 ht.set('V', 5)
337 ht.set('X', 10)
338 assert ht.length() == 3
339 assert ht.size == 3
340 ht.delete('I')
341 ht.delete('X')
342 assert ht.length() == 1
343 assert ht.size == 1
344 with self.assertRaises(KeyError):
345 ht.delete('X') # Key no longer exists
346 with self.assertRaises(KeyError):
347 ht.delete('A') # Key does not exist
348
349
350if __name__ == '__main__':
351 unittest.main()