Hash Tables and Hashing in C++

Hash Tables and Hashing

Similar to maps, a hash table is an associative array with keys and values. Hash tables turn the key into a hash code and then index the values based on the hash code. Since there can be an infinite amount of keys and a limited amount of hash codes, values sometimes have to share an index in the array. This means that the array itself has to be of some sort of list type to store multiple values (this is called chaining, there are other methods though). When values do have to share an index, it's called a collision. To find the value that you're looking for after values have collided, you must search through the list inside the index of the array.

The process of turning the key into a hash code is called hashing. Although hashing could be put into the algorithm section of these articles, it only makes sense to put it here so we can understand the entire process used with hash tables. There are many different ways to hash because it is essentially turning one value into another. The first value is the key (which can be of any type) and the second value is an int (within the bounds of a pre-made array). A common hashing practice is to turn a key into an integer (however you want) and then modulus it by the number of elements the array can hold. This will always give you an int value that is a valid index.

For this hash table, we are going to use linked lists to hold each key-value pair, and an array to hold all of the linked lists. For the hash function we will use the length of the string % 4, because 4 is the length of our example array.

using namespace std;

#include<iostream>

#include<array>

//the node class for the linked list

class Node {

public:

string value;

Node* next;

Node(){}

};

class LinkedList {

public:

Node* root = nullptr;

LinkedList() {}

};

this hash function takes the length of the string and modulus' it by 4 to

give a value 0-3, the return value is the index that the value will be stored in

int hashFunction(string value) {

int length = value.length();

int index = length % 4;

return index;

};

class HashTable {

//with an array of size 4 we will input a variety of values to get a collision

//Node* hashArray[4];

public:

LinkedList* hashArray[4];

HashTable() {

hashArray[0] = new LinkedList();

hashArray[1] = new LinkedList();

hashArray[2] = new LinkedList();

hashArray[3] = new LinkedList();

}

insert tales in a string (the value) hashes it, and puts it into the

correct index based on its key

void insert(string value) {

Node* hash_to_add = new Node();

hash_to_add->value = value;

//hashing the string to know what index to put the node in

int index = hashFunction(value);

//inserting the node into the array index and organizing the nodes to point to each other

if (hashArray[index]->root == nullptr) {

hashArray[index]->root = hash_to_add;

hash_to_add->next = nullptr;

}

else {

Node* currentNode = hashArray[index]->root;

while (currentNode->next != nullptr) {

currentNode = currentNode->next;

}

currentNode->next = hash_to_add;

currentNode->next->next = nullptr;

}

//could return an array of strings

void printValues(int index) {

Node* currentNode = hashArray[index]->root;

cout << "The values of key " << index << " are: \n";

while (currentNode != nullptr) {

cout << currentNode->value << "\n";

currentNode = currentNode->next;

}

int findIndexOf(string value) {

int index = hashFunction(value);

LinkedList* nestedList = hashArray[index];

//searching through the list in the index to see if the value exists

Node* currentNode = nestedList->root;

while (currentNode != nullptr) {

if (currentNode->value == value) {

return index;

}

currentNode = currentNode->next;

}

throw new exception("Value does not exist in the hash table");

}

};

int main() {

HashTable h;

h.insert("Pizza");

h.insert("Burgers");

h.insert("French Fries");

h.insert("Tacos");

h.insert("Spaghetti");

h.printValues(0);

h.printValues(1);

h.printValues(2);

h.printValues(3);

cout << "\nThe index of 'Pizza' is: ";

cout << h.findIndexOf("Pizza");

cout << "\nThe index of 'Burgers' is: ";

cout << h.findIndexOf("Burgers");

}

Output:

The values of key 0 are:

French Fries

The values of key 1 are:

Pizza

Tacos

Spaghetti

The values of key 2 are:

The values of key 3 are:

Burgers

The index of 'Pizza' is: 1

The index of 'Burgers' is: 3

Next section: Sequential Search