Hash Map Implementation
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204
#include <iostream>
#include <map>
#include <string> //for string manipulations! also can use string.length() function
using namespace std;
class hashh{
private:
static const int tableSize = 2;
struct item{
string name;
string drink;
item *next;
};
item *HashTable[tableSize]; //array of pointers, points to item struct elements!
public:
hashh(){ //constructor!!!
for(int i = 0; i < tableSize; i++)
{
HashTable[i] = new item; //inititialize has table pointer
HashTable[i]-> name = "empty"; //initialize name for new item
HashTable[i]-> drink = "empty"; //iniitalize drink for new item
HashTable[i]-> next = NULL; //inititialize next for new item
}
}
int Hash(string key)
{
int has = 0; //to keep total
int index; //to find index
index = key.length(); //finds the length of the string
for(int i = 0; i < key.length(); i ++) //loop through the string
{
has = (has + (int)key[i]) * 17; //adding the character values
}
index = has%tableSize; //divide by tableSize to make sure it doesn't go past the size of hte table
return index;
}
void Additem(string Name, string Drink){ //to add an item!
int index = Hash(Name); //to get the index for it to be stored
if(HashTable[index]->name == "empty") //overwrite values if nothing there
{
HashTable[index]-> name = Name;
HashTable[index]-> drink = Drink;
}
else{
item* Ptr = HashTable[index]; //point to beginning
item* n = new item; //create new item
n->name = Name; //create value name
n->drink = Drink; //create value drink
n->next = NULL; //pointer for new item points to nothing
while(Ptr->next != NULL) //Pointer looking for the end
{
Ptr = Ptr->next; //keep moving Pointer
}
Ptr->next = n; //make last item point to the new item
}
}
int NumberOfItemsAtIndex(int index)
{
int count = 0;
if(HashTable[index]->name == "empty") //if nothing's there
{
return count; //return count amount
}
else{ //index isn't empty
count++; //count the first item
item* Ptr = HashTable[index];
while(Ptr->next != NULL) //keep incrementing until the end
{
count++;
Ptr = Ptr->next;
}
return count;
}
}
void printTable() //prints the table
{
int number;
for(int i = 0; i < tableSize; i++) //goes through every index
{
number = NumberOfItemsAtIndex(i);
if(number) //checks if there are items there
cout << "# of items at index " << i << " = " << number << endl;
printItemsInIndex(i); //function that prints the values at the index
}
}
void printItemsInIndex(int index)
{
item* Ptr = HashTable[index]; //points at beginning of index
int counter = 0; //to keep track of what item at index
if(Ptr->name == "empty") // checks if the index is empty
{
cout << "Nothing to print at index " << index << endl;
return; //end program
}
while(Ptr) //while the pointer is pointed at something with substance
{
counter++; //increment
//-----------------------------Print The Item-----------------------------
cout << "Item " << counter << " at index " << index << endl;
cout << "------------------" << endl;
cout << "name = " << Ptr-> name << endl;
cout << "drink = " << Ptr-> drink << endl;
cout << "------------------" << endl;
Ptr = Ptr->next; //Move Pointer
}
}
void findKey(string key)
{
int index = Hash(key);
item* Ptr = HashTable[index];
int counter = 1;
while(Ptr)
{
if(Ptr->name == key)
{
cout << key << " @ item " << counter << " of index " << index << endl;
cout << "Favorite Drink = " << Ptr->drink << endl;
return;
}
counter++;
Ptr = Ptr->next;
}
if(!Ptr)
cout << "key not found" << endl;
return;
}
void removeItem(string key)
{
int index = Hash(key);
item* Ptr = HashTable[index]; //go to correct hash index
item* rm; //so the data can be removed
if(Ptr->name == "empty" && Ptr->drink == "empty"){ //if there's nothing there
cout << "Nothing at the index" << endl;
return;
}
if(Ptr->name == key && NumberOfItemsAtIndex(index) == 1) //its there but the only thing at that index
{
Ptr->name = "empty"; //reset it
Ptr->drink = "empty"; //reset it
return; //end it
}
if(Ptr->name == key) //its the first item but there's more
{
HashTable[index] = Ptr->next;
delete Ptr;
cout << "It has been deleted" << endl;
return;
}
while(Ptr) //as long as Pointer is pointing to something
{
if(Ptr->next && Ptr-> next-> name == key)
{
rm = Ptr->next; //point rm at the correct place
Ptr->next = rm->next; //have Ptr point to rm's next
delete rm; //delete the contents at rm
cout << key << " has been deleted " << endl; //display saying it's finished
return; //stop the function
}
Ptr = Ptr->next; //keep going
}
if(!Ptr) //if Ptr reached the end it didn't find anything to delete
{
cout << key << " wasn't here " << endl; //display message
return; //stop the function
}
}
};
int main() {
hashh Object1;
Object1.Additem("Blake", "none");
Object1.Additem("Dayday", "water");
Object1.Additem("Daddy", "Milk");
Object1.Additem("Blake", "none");
Object1.Additem("Dayday", "water");
Object1.Additem("Jared", "Milk");
Object1.printTable();
Object1.findKey("Jared");
Object1.removeItem("Jared");
return 0;
}
Cpp
INFO