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

Print Friendly, PDF & Email

Looking for sample code for a Hash Map? Click here!

Before we get into the code, what is a Hash Table? Simply put, a Hash Table is a data structure used to implement an associative array; one that can map unique “keys” to specific values. While a standard array requires that indice subscripts be integers, a hash table can use a floating point value, a string, another array, or even a structure 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 table 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, compare a standard array full of data (100 elements). If the position was known for the specific item that we wanted to access within the array, we could quickly access it. For example, if we wanted to access the data located at index #5 in the array, we could access it by doing:


array[5]; // do something with the data

Here, we dont have to search through each element in the array to find what we need, we just access it at index #5. The question is, how do we know that index #5 stores the data that we are looking for? If we have a large set of data, doing a sequential search over each item within the array can be very inefficient. That is where hashing comes in handy. Given a “key,” we can apply a hash function to a unique index or bucket to find the data that we wish to access.

So in essence, a hash table is a data structure that stores key/value pairs, and is 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 items 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 values within one bucket – should any collisions occur.

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

Looking for sample code for a Hash Map? Click here!

=== CUSTOM TEMPLATE HASH TABLE WITH ITERATOR ===


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

The iterator class starts on line #368, 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.

Looking for sample code for a Hash Map? Click here!

===== 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:

Bucket #0 has 10 items
The first element in bucket #0 is Homer

Now bucket #0 has 9 items
The first element in bucket #0 is Tamra

The unsorted items in strHash bucket #0:
it[] = Tamra
it[] = Lyndon
it[] = Johanna
it[] = Perkins
it[] = Alva
it[] = Jordon
it[] = Neville
it[] = Lawrence
it[] = Jetta

The sorted items in strHash bucket #0:
it[] = Alva
it[] = Jetta
it[] = Johanna
it[] = Jordon
it[] = Lawrence
it[] = Lyndon
it[] = Neville
it[] = Perkins
it[] = Tamra


SAMPLE OUTPUT:


strHash Bucket #0:
*it = Cinderella
*it = Perkins
*it = Krystal
*it = Roger
*it = Roger

strHash Bucket #1:
*it = Lilliam
*it = Lilliam
*it = Theda

strHash Bucket #2:
*it = Arie

strHash Bucket #3:
*it = Magda

strHash Bucket #6:
*it = Edda
*it = Irvin
*it = Kati
*it = Lyndon

strHash Bucket #7:
*it = Deb
*it = Jaime

strHash Bucket #8:
*it = Neville
*it = Victoria

strHash Bucket #9:
*it = Chery
*it = Evelia

--------------------------------------------

intHash Bucket #0:
it[] = 2449
it[] = 6135

intHash Bucket #1:
it[] = 1120
it[] = 852

intHash Bucket #2:
it[] = 5727

intHash Bucket #3:
it[] = 1174

intHash Bucket #4:
it[] = 2775
it[] = 3525
it[] = 8375

intHash Bucket #5:
it[] = 4322
it[] = 8722
it[] = 5016

intHash Bucket #6:
it[] = 5053
it[] = 7231
it[] = 1571

intHash Bucket #7:
it[] = 1666
it[] = 4510
it[] = 1548
it[] = 3646

intHash Bucket #9:
it[] = 2756

--------------------------------------------

strctHash Bucket #0:
it-> = Cherilyn
it-> = Roger

strctHash Bucket #1:
it-> = Tamra
it-> = Alex
it-> = Theda

strctHash Bucket #2:
it-> = Nigel
it-> = Alva
it-> = Arie

strctHash Bucket #4:
it-> = Basil

strctHash Bucket #5:
it-> = Tod

strctHash Bucket #6:
it-> = Irvin
it-> = Lyndon

strctHash Bucket #7:
it-> = Amina
it-> = Hillary
it-> = Kenneth
it-> = Amina

strctHash Bucket #8:
it-> = Gene
it-> = Lemuel
it-> = Gene

strctHash Bucket #9:
it-> = Albertina

Leave a Reply