HashMap Test Output assignment

computer science


Hash Map Project


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.


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

Related Questions in computer science category