Chrystal Mingo

CSC 212 Final Project

Hash Tables Implementation

Final Essay:

Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string.

For my project I implemented a Hash Table which could do the following: create a hash, add items to the hash table, prints the number of indexes and the number of items in that location, print the Hash Table, print all the items that fall under one index in the hash table, a function that would allow me to search for my key, and remove items from my Hash Table. In the end my project collected student names, and used the name of their college as a key. My hash table did a great job of allowing me to store the student’s information as well, to search for it immediately thanks to the hash function.

I am going to explain the purpose of each of my functions, found in my hash.cpp. I implemented a hash table because to me it was the perfect data structure to store information, and allows me to easily and efficiently access my elements within the table. The first function was the hash function. This function called hash, is what hashes the strings. Taking the key, then its length. The for loop adds up all the values that represent the each character of the string. I took the sum of the word and mod it by the size of the hash table, to find a unique hash key (or index) within range for the string. This is the process of hashing, with a time complexity of O(n).The second function called AddItem, would add Items to the Hash Table, the item would include the person’s name and college. This function has a time complexity of O(n).The next item was called the NumberOfItemsInIndex which informs you of how much Items are in one Index of the Hash Table. This function has a time complexity of O(n).The next two called PrintTable and PrintItemsInIndex, the first one printed the entire hash table, and it’s items. This first function has a time complexity of O(n). The next one would print the Items if a Index had more than one item. This function has a time complexity of O(n).The remove function, was able to delete the entire hash table, and specific cases. The last function was called FindCollege, as I stated before College was my key, with this function I was able to search for my key, which is one of the great capabilities of hash tables, since it allows one to freely search for a element, or item, or in this case someone’s information relating to their name and institution they attend. This function has a time complexity of O(n).

I decided to implement the Hash Tables to learn about how hashing works, how to create a hash, display the table with information, add information, just learn overall. It was definitely worth it, because it was quite similar to linked list and served as a refresher. Since I implemented a specific type of hash that’s called chained hashing. I used chained hashing to be able to deal with the collisions my function might face if for example, people had the same name and went to the same college. Also it was amazing to see what different applications can be done to the program, I used it to gather information on students names and their colleges, but it could have gathered more information like the person’s last name, instead of college looked into what country or nationality these individuals are from. I found hash table to be a perfect data structure to store and search for items easily. I also feel like I learned so much from implementing it, and overall feel like a stronger programmer in c++.

I used the Hash table because it could allow me to store and search for items efficiently. The Hash data structure capability to hash giving an element a unique key, fascinated me. I choose it to store information on students, but hashing is used day to day for real world applications such as Contact List, Cryptography, Message Digest, Hash values or codes, Blockchain, Hash Tables like I used it for, Password Verification and there is so much other uses for hashing.

The biggest issue with Hashing is collisions. As a result I used chained hashing, I dealt with collisions by creating a linked list within each array. Therefore if someone had the same name, and college I would would find each one by referencing the index, each one would be its own item within the hash table, and could be found in the same index, however the first one entered was in the first node, and the second one below. The challenge was this issue with collision but the chained hashing helped deal with the issues if items fell under the same “unique” key, the uniquenesses of the key stayed true because they fell within their own unique index within that unique key.

The overall benefit of hash tables is their speed, its capability to access elements in a short amount of time because the elements are hashed away and the unique keys allow faster access to elements. With a time complexity of O(n) hash tables are quite efficient. For this project I could have used Binary Search Trees to search for my elements, however I choose a hash table because of its ability to store large sums of information, and allows for easy access.