Quick actions

cmd+k|ctrl+k

Navigation

Languages

Hash Map Implementation

Snippet info

Language

Cpp

Visibility

public

Author

dwynn

Created

2020-05-06T03:57:57Z

Updated

2020-05-11T14:57:37Z

#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;
}
INFO