$29
CS261 Assignment 6 HashMap Implementation
Part 1 - Summary and Specific Instructions
1. Implement the HashMap class by completing the provided skeleton code in the file hash_map_sc.py. Once completed, your implementation will include the following methods:
put()
get()
remove()
contains_key()
clear()
empty_buckets()
resize_table()
table_load()
get_keys()
2. Use a dynamic array to store your hash table and implement chaining for collision resolution using a singly linked list. Chains of key / value pairs must be stored in linked list nodes. The diagram below illustrates the overall architecture of the HashMap.
3. Two pre-written classes are provided for you in the skeleton code - DynamicArray and LinkedList (file a6_include.py). You must use objects of these classes in your HashMap class implementation. Use a DynamicArray object to store your hash table and LinkedList objects to store chains of key / value pairs.
Page 4 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
4. The provided DynamicArray and LinkedList classes may provide different functionality than those described in the lectures or implemented in prior homework assignments. Review the docstrings in the skeleton code to understand the available methods, their use, and input / output parameters.
5. The number of objects stored in the HashMap will be between 0 and 1,000,000 inclusive.
6. Two pre-written hash functions are provided in the skeleton code. Make sure you test your code with both functions. We will use these two functions in our testing of your implementation.
7. RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures and / or their methods.
You are NOT allowed to directly access any variables of the DynamicArray or LinkedList classes. All work must be done only by using class methods.
8. Variables in the HashMap and SLNode classes are not private. You ARE allowed to access and change their values directly. You do not need to write any getter or setter methods for the HashMap or SLNode classes.
9. You may not use any imports beyond the ones included in the assignment source code provided.
Page 5 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
empty_buckets(self) -> int:
This method returns the number of empty buckets in the hash table.
Example #1:
m = HashMap(100, hash_function_1)
print(m.empty_buckets(), m.size, m.capacity)
m.put('key1', 10)
print(m.empty_buckets(), m.size, m.capacity)
m.put('key2', 20)
print(m.empty_buckets(), m.size, m.capacity)
m.put('key1', 30)
print(m.empty_buckets(), m.size, m.capacity)
m.put('key4', 40)
print(m.empty_buckets(), m.size, m.capacity)
Output:
100 0 100
99 1 100
98 2 100
98 2 100
97 3 100
Example #2:
• this test assumes that put() has already been correctly implemented m = HashMap(50, hash_function_1)
for i in range(150): m.put('key' + str(i), i * 100) if i % 30 == 0:
print(m.empty_buckets(), m.size, m.capacity)
Output:
49150
39 31 50
36 61 50
33 91 50
30 121 50
Page 6 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
table_load(self) -> float:
This method returns the current hash table load factor.
Example #1:
• this test assumes that put() has already been correctly implemented m = HashMap(100, hash_function_1)
print(m.table_load()) m.put('key1', 10) print(m.table_load()) m.put('key2', 20) print(m.table_load()) m.put('key1', 30) print(m.table_load())
Output:
0.0
0.01
0.02
0.02
Example #2:
• this test assumes that put() has already been correctly implemented m = HashMap(50, hash_function_1)
for i in range(50): m.put('key' + str(i), i * 100) if i % 10 == 0:
print(m.table_load(), m.size, m.capacity)
Output:
0.02 1 50
0.22 11 50
0.42 21 50
0.62 31 50
0.82 41 50
Page 7 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
clear(self) -> None:
This method clears the contents of the hash map. It does not change the underlying hash table capacity.
Example #1:
• this test assumes that put() has already been correctly implemented m = HashMap(100, hash_function_1)
print(m.size, m.capacity) m.put('key1', 10) m.put('key2', 20) m.put('key1', 30) print(m.size, m.capacity) m.clear() print(m.size, m.capacity)
Output:
• 100
2 100
• 100
Example #2:
• this test assumes that put() has already been correctly implemented m = HashMap(50, hash_function_1)
print(m.size, m.capacity) m.put('key1', 10) print(m.size, m.capacity) m.put('key2', 20) print(m.size, m.capacity) m.resize_table(100) print(m.size, m.capacity) m.clear() print(m.size, m.capacity)
Output:
• 50
1 50
2 50
2 100
• 100
Page 8 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
put(self, key: str, value: object) -> None:
This method updates the key / value pair in the hash map. If the given key already exists in the hash map, its associated value must be replaced with the new value. If the given key is not in the hash map, a key / value pair must be added.
Example #1:
m = HashMap(50, hash_function_1)
for i in range(150):
m.put('str' + str(i), i * 100)
if i % 25 == 24:
print(m.empty_buckets(), m.table_load(), m.size, m.capacity)
Output:
39 0.5 25 50
37 1.0 50 50
35 1.5 75 50
32 2.0 100 50
30 2.5 125 50
30 3.0 150 50
Example #2:
m = HashMap(40, hash_function_2)
for i in range(50):
m.put('str' + str(i // 3), i * 100)
if i % 10 == 9:
print(m.empty_buckets(), m.table_load(), m.size, m.capacity)
Output:
36 0.1 4 40
33 0.175 7 40
30 0.25 10 40
27 0.35 14 40
25 0.425 17 40
Page 9 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
contains_key(self, key: str) -> bool:
This method returns True if the given key is in the hash map, otherwise it returns False. An empty hash map does not contain any keys.
Example #1:
m = HashMap(50, hash_function_1)
print(m.contains_key('key1'))
m.put('key1', 10)
m.put('key2', 20)
m.put('key3', 30)
print(m.contains_key('key1'))
print(m.contains_key('key4'))
print(m.contains_key('key2'))
print(m.contains_key('key3'))
m.remove('key3')
print(m.contains_key('key3'))
Output:
False
True
False
True
True
False
Example #2:
m = HashMap(75, hash_function_2)
keys = [i for i in range(1, 1000, 20)]
for key in keys:
m.put(str(key), key * 42)
print(m.size, m.capacity)
result = True
for key in keys:
• all inserted keys must be present result &= m.contains_key(str(key))
• NOT inserted keys must be absent
result &= not m.contains_key(str(key + 1))
print(result)
Output:
50 75 True
Page 10 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
get(self, key: str) -> object:
This method returns the value associated with the given key. If the key is not in the hash map, the method returns None.
Example #1:
m = HashMap(30, hash_function_1)
print(m.get('key'))
m.put('key1', 10)
print(m.get('key1'))
Output:
None
10
Example #2:
m = HashMap(150, hash_function_2)
for i in range(200, 300, 7):
m.put(str(i), i * 10)
print(m.size, m.capacity)
for i in range(200, 300, 21):
print(i, m.get(str(i)), m.get(str(i)) == i * 10)
print(i + 1, m.get(str(i + 1)), m.get(str(i + 1)) == (i + 1) * 10)
Output:
15 150
200 2000 True
201 None False
221 2210 True
222 None False
242 2420 True
243 None False
263 2630 True
264 None False
284 2840 True
285 None False
Page 11 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
remove(self, key: str) -> None:
This method removes the given key and its associated value from the hash map. If the key is not in the hash map, the method does nothing (no exception needs to be raised).
Example #1:
m = HashMap(50, hash_function_1)
print(m.get('key1'))
m.put('key1', 10)
print(m.get('key1'))
m.remove('key1')
print(m.get('key1'))
m.remove('key4')
Output:
None
10
None
Page 12 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
resize_table(self, new_capacity: int) -> None:
This method changes the capacity of the internal hash table. All existing key / value pairs must remain in the new hash map, and all hash table links must be rehashed. If new_capacity is less than 1, the method does nothing.
Example #1:
m = HashMap(20, hash_function_1)
m.put('key1', 10)
print(m.size, m.capacity, m.get('key1'), m.contains_key('key1'))
m.resize_table(30)
print(m.size, m.capacity, m.get('key1'), m.contains_key('key1'))
Output:
1 20 10 True
1 30 10 True
Example #2:
m = HashMap(75, hash_function_2)
keys = [i for i in range(1, 1000, 13)]
for key in keys:
m.put(str(key), key * 42)
print(m.size, m.capacity)
for capacity in range(111, 1000, 117):
m.resize_table(capacity)
m.put('some key', 'some value')
result = m.contains_key('some key')
m.remove('some key')
for key in keys:
result &= m.contains_key(str(key))
result &= not m.contains_key(str(key + 1))
print(capacity, result, m.size, m.capacity, round(m.table_load(), 2))
Output:
77 75
111 True 77 111 0.69
228 True 77 228 0.34
345 True 77 345 0.22
462 True 77 462 0.17
579 True 77 579 0.13
696 True 77 696 0.11
813 True 77 813 0.09
930 True 77 930 0.08
Page 13 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
get_keys(self) -> DynamicArray:
This method returns a DynamicArray that contains all the keys stored in the hash map. The order of the keys in the DA does not matter.
Example #1:
m = HashMap(10, hash_function_2)
for i in range(100, 200, 10):
m.put(str(i), str(i * 10))
print(m.get_keys())
m.resize_table(1)
print(m.get_keys())
m.put('200', '2000')
m.remove('100')
m.resize_table(2)
print(m.get_keys())
Output:
['160', '110', '170', '120', '180', '130', '190', '140', '150', '100'] ['100', '150', '140', '190', '130', '180', '120', '170', '110', '160'] ['200', '160', '110', '170', '120', '180', '130', '190', '140', '150']
Page 14 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
Part 2 - Summary and Specific Instructions
1. Implement the HashMap class by completing the provided skeleton code in the file hash_map_oa.py. Once completed, your implementation will include the following methods:
put()
get()
remove()
contains_key()
clear()
empty_buckets()
resize_table()
table_load()
get_keys()
2. Use a dynamic array to store your hash table and implement Open Addressing with Quadratic Probing for collision resolution inside that dynamic array. Key / value pairs must be stored in the array. Refer to the Explorations for an example of this implementation.
3. Use the pre-written DynamicArray class in the a6_include.py file. You must use objects of this class in your HashMap class implementation. Use a DynamicArray object to store your Open Addressing hash table.
4. The provided DynamicArray class may provide different functionality than the one described in the lectures or implemented in prior homework assignments. Review the docstrings in the skeleton code to understand the available methods, their use, and input / output parameters.
5. The number of objects stored in the HashMap will be between 0 and 1,000,000 inclusive.
6. Two pre-written hash functions are provided in the skeleton code. Make sure you test your code with both functions. We will use these two functions in our testing of your implementation.
7. RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures and / or their methods.
You are NOT allowed to directly access any variables of the DynamicArray class. All work must be done only by using class methods.
8. Variables in the HashMap and HashEntry classes are not private. You ARE allowed to access and change their values directly. You do not need to write any getter or setter methods for the HashMap class.
Page 15 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
9. You may not use any imports beyond the ones included in the assignment source code provided.
Page 16 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
empty_buckets(self) -> int:
This method returns the number of empty buckets in the hash table.
Example #1:
• this test assumes that put() has already been correctly implemented m = HashMap(100, hash_function_1)
print(m.empty_buckets(), m.size, m.capacity) m.put('key1', 10) print(m.empty_buckets(), m.size, m.capacity) m.put('key2', 20) print(m.empty_buckets(), m.size, m.capacity) m.put('key1', 30) print(m.empty_buckets(), m.size, m.capacity) m.put('key4', 40) print(m.empty_buckets(), m.size, m.capacity)
Output:
100 0 100
99 1 100
98 2 100
98 2 100
97 3 100
Example #2:
• this test assumes that put() has already been correctly implemented m = HashMap(50, hash_function_1)
for i in range(150): m.put('key' + str(i), i * 100) if i % 30 == 0:
print(m.empty_buckets(), m.size, m.capacity)
Output:
49150
69 31 100
139 61 200
109 91 200
279 121 400
Page 17 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
table_load(self) -> float:
This method returns the current hash table load factor.
Example #1:
• this test assumes that put() has already been correctly implemented m = HashMap(100, hash_function_1)
print(m.table_load()) m.put('key1', 10) print(m.table_load()) m.put('key2', 20) print(m.table_load()) m.put('key1', 30) print(m.table_load())
Output:
0.0
0.01
0.02
0.02
Example #2:
• this test assumes that put() has already been correctly implemented m = HashMap(50, hash_function_1)
for i in range(50): m.put('key' + str(i), i * 100) if i % 10 == 0:
print(m.table_load(), m.size, m.capacity)
Output:
0.02 1 50
0.22 11 50
0.42 21 50
0.31 31 100
0.41 41 100
Page 18 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
clear(self) -> None:
This method clears the contents of the hash map. It does not change the underlying hash table capacity.
Example #1:
• this test assumes that put() has already been correctly implemented m = HashMap(100, hash_function_1)
print(m.size, m.capacity) m.put('key1', 10) m.put('key2', 20) m.put('key1', 30) print(m.size, m.capacity) m.clear() print(m.size, m.capacity)
Output:
• 100
2 100
• 100
Example #2:
• this test assumes that put() has already been correctly implemented m = HashMap(50, hash_function_1)
print(m.size, m.capacity) m.put('key1', 10) print(m.size, m.capacity) m.put('key2', 20) print(m.size, m.capacity) m.resize_table(100) print(m.size, m.capacity) m.clear() print(m.size, m.capacity)
Output:
• 50
1 50
2 50
2 100
• 100
Page 19 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
put(self, key: str, value: object) -> None:
This method updates the key / value pair in the hash map. If the given key already exists in the hash map, its associated value must be replaced with the new value. If the given key is not in the hash map, a key / value pair must be added.
For this hash map implementation, the table must be resized to double its current capacity when this method is called and the current load factor of the table is greater than or equal to 0.5.
Example #1:
m = HashMap(50, hash_function_1)
for i in range(150):
m.put('str' + str(i), i * 100)
if i % 25 == 24:
print(m.empty_buckets(), m.table_load(), m.size, m.capacity)
Output:
25 0.5 25 50
50 0.5 50 100
125 0.375 75 200
100 0.5 100 200
275 0.3125 125 400
250 0.375 150 400
Example #2:
m = HashMap(40, hash_function_2)
for i in range(50):
m.put('str' + str(i // 3), i * 100)
if i % 10 == 9:
print(m.empty_buckets(), m.table_load(), m.size, m.capacity)
Output:
36 0.1 4 40
33 0.175 7 40
30 0.25 10 40
26 0.35 14 40
23 0.425 17 40
Page 20 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
contains_key(self, key: str) -> bool:
This method returns True if the given key is in the hash map, otherwise it returns False. An empty hash map does not contain any keys.
Example #1:
m = HashMap(50, hash_function_1)
print(m.contains_key('key1'))
m.put('key1', 10)
m.put('key2', 20)
m.put('key3', 30)
print(m.contains_key('key1'))
print(m.contains_key('key4'))
print(m.contains_key('key2'))
print(m.contains_key('key3'))
m.remove('key3')
print(m.contains_key('key3'))
Output:
False
True
False
True
True
False
Example #2:
m = HashMap(75, hash_function_2)
keys = [i for i in range(1, 1000, 20)]
for key in keys:
m.put(str(key), key * 42)
print(m.size, m.capacity)
result = True
for key in keys:
• all inserted keys must be present result &= m.contains_key(str(key))
• NOT inserted keys must be absent
result &= not m.contains_key(str(key + 1))
print(result)
Output:
50 150
True
Page 21 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
get(self, key: str) -> object:
This method returns the value associated with the given key. If the key is not in the hash map, the method returns None.
Example #1:
m = HashMap(30, hash_function_1)
print(m.get('key'))
m.put('key1', 10)
print(m.get('key1'))
Output:
None
10
Example #2:
m = HashMap(150, hash_function_2)
for i in range(200, 300, 7):
m.put(str(i), i * 10)
print(m.size, m.capacity)
for i in range(200, 300, 21):
print(i, m.get(str(i)), m.get(str(i)) == i * 10)
print(i + 1, m.get(str(i + 1)), m.get(str(i + 1)) == (i + 1) * 10)
Output:
15 150
200 2000 True
201 None False
221 2210 True
222 None False
242 2420 True
243 None False
263 2630 True
264 None False
284 2840 True
285 None False
Page 22 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
remove(self, key: str) -> None:
This method removes the given key and its associated value from the hash map. If the key is not in the hash map, the method does nothing (no exception needs to be raised).
Example #1:
m = HashMap(50, hash_function_1)
print(m.get('key1'))
m.put('key1', 10)
print(m.get('key1'))
m.remove('key1')
print(m.get('key1'))
m.remove('key4')
Output:
None
10
None
Page 23 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
resize_table(self, new_capacity: int) -> None:
This method changes the capacity of the internal hash table. All existing key / value pairs
must remain in the new hash map, and all hash table links must be rehashed. If
new_capacity is less than 1 or less than the current number of elements in the map, the
method does nothing.
Example #1:
m = HashMap(20, hash_function_1)
m.put('key1', 10)
print(m.size, m.capacity, m.get('key1'), m.contains_key('key1'))
m.resize_table(30)
print(m.size, m.capacity, m.get('key1'), m.contains_key('key1'))
Output:
1 20 10 True
1 30 10 True
Example #2:
m = HashMap(75, hash_function_2)
keys = [i for i in range(1, 1000, 13)]
for key in keys:
m.put(str(key), key * 42)
print(m.size, m.capacity)
for capacity in range(111, 1000, 117):
m.resize_table(capacity)
m.put('some key', 'some value')
result = m.contains_key('some key')
m.remove('some key')
for key in keys:
result &= m.contains_key(str(key))
result &= not m.contains_key(str(key + 1))
print(capacity, result, m.size, m.capacity, round(m.table_load(), 2))
Output:
77 300
111 True 77 222 0.35
228 True 77 228 0.34
345 True 77 345 0.22
462 True 77 462 0.17
579 True 77 579 0.13
696 True 77 696 0.11
813 True 77 813 0.09
930 True 77 930 0.08
Page 24 of 25
CS261 Data Structures Assignment 6: HashMap Implementation
get_keys(self) -> DynamicArray:
This method returns a DynamicArray that contains all the keys stored in the hash map. The order of the keys in the DA does not matter.
Example #1:
m = HashMap(10, hash_function_2)
for i in range(100, 200, 10):
m.put(str(i), str(i * 10))
print(m.get_keys())
m.resize_table(1)
print(m.get_keys())
m.put('200', '2000')
m.remove('100')
m.resize_table(2)
print(m.get_keys())
Output:
['160', '170', '180', '190', '100', '110', '120', '130', '140', '150'] ['160', '170', '180', '190', '100', '110', '120', '130', '140', '150'] ['200', '110', '120', '130', '140', '150', '160', '170', '180', '190']
Page 25 of 25
