Monthly Archives: June 2013

C++ || Custom Template Hash Map With Iterator Using Separate Chaining

Before we get into the code, what is a Hash Map? Simply put, a Hash Map is an extension of a Hash Table; which is a data structure used to map unique “keys” to specific “values.” The Hash Map demonstrated on this page is different from the previous Hash Table implementation in that key/value pairs do not need to be the same datatype, they can be completely different. So for example, if you wish to map a string “key” to an integer “value“, utilizing a Hash Map is ideal.

In its most simplest form, a Hash Map can be thought of as an associative array, or a “dictionary.” Hash Map’s are composed of a collection of key/value pairs, such that each possible key appears atleast once in the collection for a given value. While a standard array requires that indice subscripts be integers, a hash map can use a string, an integer, or even a floating point value as the index. That index is called the “key,” and the contents within the array at that specific index location is called the “value.” A hash map uses a hash function to generate an index into the table, creating buckets or slots, from which the correct value can be found.

To illustrate, suppose that you’re working with some data that has values associated with strings — for instance, you might have student names and you wish to assign them grades. How would you store this data? Depending on your skill level, you might use multiple arrays during the implementation. For example, in terms of a one dimensional array, if we wanted to access the data for a student located at index #25, we could access it by doing:


studentNames[25]; // do something with the data
studentGrades[25];

Here, we dont have to search through each element in the array to find what we need, we just access it at index #25. The question is, how do we know that index #25 holds the data that we are looking for? If we have a large set of data, not only will keeping track of multiple arrays become tiresome, but doing a sequential search over each item within the separate arrays can become very inefficient. That is where hashing comes in handy. Using a Hash Map, we can use the students name as the “key,” and the students grade as the data “value.” Given this “key” (the students name), we can apply a hash function to map a unique index or bucket within the hash table to find the data “value” (the students grade) that we wish to access.

So in essence, a Hash Map is an extension of a hash table, which is a data structure that stores key/value pairs. Hash tables are typically used because they are ideal for doing a quick search of items.

Though hashing is ideal, it isnt perfect. It is possible for multiple “keys” to be hashed into the same location. Hash “collisions” are practically unavoidable when hashing large data sets. The code demonstrated on this page handles collisions via separate chaining, utilizing an array of linked list head nodes to store multiple keys within one bucket – should any collisions occur.

A special feature of this current hash map class is that its implemented as a multimap, meaning that more than one “value” can be associated with a given “key.” For example, in a student enrollment system where students may be enrolled in multiple classes simultaneously, there might be an association for each enrollment where the “key” is the student ID, and the “value” is the course ID. In this example, if a given student is enrolled in three courses, there will be three associated “values” (course ID’s) for one “key” (student ID) in the Hash Map.

An iterator was also implemented, making data access that much more simple within the hash map class. Click here for an overview demonstrating how custom iterators can be built.

=== CUSTOM TEMPLATE HASH MAP WITH ITERATOR ===

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The iterator class starts on line #381, and is built to support most of the standard relational operators, as well as arithmetic operators such as ‘+,+=,++’ (pre/post increment). The * (star), bracket [] and -> arrow operators are also supported. Click here for an overview demonstrating how custom iterators can be built.

The rest of the code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

===== DEMONSTRATION HOW TO USE =====

Use of the above template class is the same as many of its STL template class counterparts. Here are sample programs demonstrating its use.

SAMPLE OUTPUT:

The key 'CPSC' appears in the hash map 6 time(s)

The first item with the key 'CPSC' is: 386

These are all the items in the hash map whose key is 'CPSC':
Key-> CPSC Value-> 386
Key-> CPSC Value-> 462
Key-> CPSC Value-> 301
Key-> CPSC Value-> 240
Key-> CPSC Value-> 131
Key-> CPSC Value-> 120

[REMOVE THE VALUE '386' FROM THE KEY 'CPSC']

Now the key 'CPSC' only appears in the hash map 5 time(s)

These are the sorted items in the hash map whose key is 'CPSC':
Key-> CPSC Value-> 120
Key-> CPSC Value-> 131
Key-> CPSC Value-> 240
Key-> CPSC Value-> 301
Key-> CPSC Value-> 462

These are all of the items in the entire hash map:
Key-> CIS Value-> 465

Key-> DANCE Value-> 134

Key-> PE Value-> 145
Key-> PE Value-> 125

Key-> MATH Value-> 270
Key-> MATH Value-> 150

Key-> GEOL Value-> 201
Key-> GEOL Value-> 101

Key-> CPSC Value-> 120
Key-> CPSC Value-> 131
Key-> CPSC Value-> 240
Key-> CPSC Value-> 301
Key-> CPSC Value-> 462

Key-> BIOL Value-> 585
Key-> BIOL Value-> 134

Key-> ART Value-> 101
Key-> ART Value-> 345

Key-> CHEM Value-> 185

Key-> HIST Value-> 251

The total number of items in the hash map is: 19

SAMPLE OUTPUT:

'Kenneth' owns 3 cars

These are all of the cars in the hash map:
Jessica's car(s)
Car: Nissan Altima
Year: 2011
MPG: 30.7

Kenneth's car(s)
Car: Ford Fusion
Year: 2006
MPG: 28.5

Car: BMW 535i
Year: 2014
MPG: 25.4

Car: Acura Integra
Year: 2001
MPG: 20.2
-----------------------------------------------------

The total number of cars in the hash map is: 4

Sorting the cars that 'Kenneth' owns by name..

Again, these are all of the cars in the hash map:
Jessica's car(s)
Car: Nissan Altima
Year: 2011
MPG: 30.7

Kenneth's car(s)
Car: Acura Integra
Year: 2001
MPG: 20.2

Car: BMW 535i
Year: 2014
MPG: 25.4

Car: Ford Fusion
Year: 2006
MPG: 28.5
-----------------------------------------------------

'Acura Integra' has been removed from 'Kenneth's' inventory..

'Kenneth' now owns only 2 cars

These are all of the cars in the hash map with the 'Acura Integra' removed:
Jessica's car(s)
Car: Nissan Altima
Year: 2011
MPG: 30.7

Kenneth's car(s)
Car: BMW 535i
Year: 2014
MPG: 25.4

Car: Ford Fusion
Year: 2006
MPG: 28.5
-----------------------------------------------------

The total number of cars in the hash map is: 3