Hash maps using (Separate) Chaining, and Open Addressing with Quadratic Probing
Go to file
2022-06-25 13:50:01 -04:00
.gitignore Initial commit 2022-06-01 05:13:31 +02:00
hash_map_oa.py Update docstrings, clean up testing output 2022-06-25 13:49:07 -04:00
hash_map_sc.py Fix testing indentation 2022-06-25 13:50:01 -04:00
hm_include.py Rename file, add citation for Oregon State 2022-06-25 13:48:31 -04:00
LICENSE Add name and year 2022-06-01 05:14:11 +02:00
README.md Update README.md 2022-06-25 13:47:52 -04:00

HashMaps

These two hash map implementations feature open addressing with quadratic probing and separate chaining to handle collisions. The hm_include module provides the underlying data structures, and two hash functions.

Both implementations use the included DynamicArray class for the underlying hash table, however hash_map_sc.py uses a singly linked list for each bucket while hash_map_oa.py uses a HashEntry object. Additionally, hash_map_sc.py includes a seperate function, find_mode(), that provides a mechanism for finding the value that occurs most frequently in the hash map and how many times it occurs with an O(n) time complexity. Finally, both implementations include some basic testing when run as a script.