HashMap Test Output assignment
computer science
Description
Hash Map Project
Overview
This hash map project is intended to provide students with an understanding of how map-based and hash-based
data structures function. This project involves the implementation of a templated hash-table-based map with
methods that allow for its use as an associative array.
Structure
A hash map, a type of associative array, is a data structure that associates a value with a key. (Our dictionary
could be placed in a hash map, where the keys are the words and the values are their definitions.) The map's
hash function generates a hash code from the key and reduces it (usually by modulo) to an index, and the value-
key pair is placed in the table at the index (called the bucket).
Suppose our dictionary's table size is 32. If the hash code for a key (word) is the ASCII value of the first
character and we wanted to add the word “aardvark”, our hash code would be 97, so our hash function would
return an index of 1. The word “aardvark” and its definition would be stored in bucket 1 in the table.
One problem with hash maps is collision between keys. If we also wanted to store the string “amnesia”, the
hash function would generate the same hash code 97, so we’d be using bucket 1 again. If there are too many
collisions, we might consider changing our hash function or the size of our table. To deal with collisions, we
usually make each hash map bucket a linked list that can hold multiple pairs. When we want to store or retrieve
a value, we compute the bucket of the key and then step through the bucket's list until we find the correct value.
A common implementation of a hash map using linked lists as buckets
