Hash maps using (Separate) Chaining, and Open Addressing with Quadratic Probing
Go to file
Andrew Scott 155571e227
Fix testing indentation
2022-06-25 13:50:01 -04:00
.gitignore Initial commit 2022-06-01 05:13:31 +02: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
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



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.