Fork 0
Hash maps using (Separate) Chaining, and Open Addressing with Quadratic Probing
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Andrew Scott 155571e227
Fix testing indentation
3 months ago
hash_map_oa.py Update docstrings, clean up testing output 3 months ago
hash_map_sc.py Fix testing indentation 3 months ago



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.