C++ question: Using a standard dictionary, and a table size that approximates a load factor of...

Question

Question

C++ question: Using a standard dictionary, and a table size that approximates a load factor of...

C++ question:

Using a standard dictionary, and a table size that approximates a load factor of 1,
compare the number of collisions produced by the hash function in Figure 5.4 and
the hash function in Figure 5.55. (Please program in C++ with explanations)

/** Figure 5.4
* A hash routine for string objects.
*/
unsigned int hash( const string & key, int tableSize )
{
unsigned int hashVal = 0;

for( char ch : key )
hashVal = 37 * hashVal + ch;

return hashVal % tableSize;
}

/** Figure 5.55
* FNV-1a hash routine for string objects.
*/
unsigned int hash( const string & key, int tableSize )
{
unsigned int hashVal = 2166136261;

for( char ch : key )
hashVal = ( hashVal ˆ ch )* 16777619;

return hashVal % tableSize;
}

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

```
#include<iostream>
```
```
#include<cstdlib>
```
```
#include<string>
```
```
#include<cstdio>
```
```
using namespace std;
```
```
const int TABLE_SIZE = 128;
```
```
 
```
```
/*
```
```
 * HashEntry Class Declaration
```
```
 */
```
```
class HashEntry
```
```
{
```
```
    public:
```
```
        int key;
```
```
        int value;
```
```
        HashEntry(int key, int value)
```
```
        {
```
```
            this->key = key;
```
```
            this->value = value;
```
```
        }
```
```
};
```
```
 
```
```
/*
```
```
 * HashMap Class Declaration
```
```
 */
```
```
class HashMap
```
```
{
```
```
    private:
```
```
        HashEntry **table;
```
```
    public:   
```
```
        HashMap()
```
```
        {
```

            table = new HashEntry * [TABLE_SIZE];

            for (int i = 0; i< TABLE_SIZE; i++)

```
            {
```
```
                table[i] = NULL;
```
```
            }
```
```
        }
```
```
        /*
```
```
         * Hash Function
```
```
         */
```
```
        int HashFunc(int key)
```
```
        {
```
```
            return key % TABLE_SIZE;
```
```
        }
```
```
        /*
```
```
         * Insert Element at a key
```
```
         */
```
```
        void Insert(int key, int value)
```
```
        {
```
```
            int hash = HashFunc(key);
```

            while (table[hash] != NULL && table[hash]->key != key)

```
            {
```

                hash = HashFunc(hash + 1);

```
            }
```
```
            if (table[hash] != NULL)
```
```
                delete table[hash];
```

            table[hash] = new HashEntry(key, value);

```
        }
```
```
        /*
```
```
         * Search Element at a key
```
```
         */
```
```
        int Search(int key)
```
```
        {
```
```
            int  hash = HashFunc(key);
```

            while (table[hash] != NULL && table[hash]->key != key)

```
            {
```

                hash = HashFunc(hash + 1);

```
            }
```
```
            if (table[hash] == NULL)
```
```
                return -1;
```
```
            else
```

                return table[hash]->value;

```
        }
```
```
 
```
```
        /*
```
```
         * Remove Element at a key
```
```
         */
```
```
        void Remove(int key)
```
```
        {
```
```
            int hash = HashFunc(key);
```
```
            while (table[hash] != NULL)
```
```
            {
```

                if (table[hash]->key == key)

```
                    break;
```

                hash = HashFunc(hash + 1);

```
            }
```
```
            if (table[hash] == NULL)
```
```
            {
```

                cout<<"No Element found at key "<<key<<endl;

```
                return;
```
```
            }
```
```
            else
```
```
            {
```
```
                delete table[hash];
```
```
            }
```

            cout<<"Element Deleted"<<endl;

```
        }
```
```
        ~HashMap()
```
```
        {
```

            for (int i = 0; i < TABLE_SIZE; i++)

```
            {
```
```
                if (table[i] != NULL)
```
```
                    delete table[i];
```
```
                delete[] table;
```
```
            }
```
```
        }
```
```
};
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main()
```
```
{
```
```
    HashMap hash;
```
```
    int key, value;
```
```
    int choice;
```
```
    while (1)
```
```
    {
```

        cout<<"\n----------------------"<<endl;

        cout<<"Operations on Hash Table"<<endl;

        cout<<"\n----------------------"<<endl;

        cout<<"1.Insert element into the table"<<endl;

        cout<<"2.Search element from the key"<<endl;

        cout<<"3.Delete element at a key"<<endl;

```
        cout<<"4.Exit"<<endl;
```
```
        cout<<"Enter your choice: ";
```
```
        cin>>choice;
```
```
        switch(choice)
```
```
        {
```
```
        case 1:
```

            cout<<"Enter element to be inserted: ";

```
            cin>>value;
```

            cout<<"Enter key at which element to be inserted: ";

```
            cin>>key;
```
```
            hash.Insert(key, value);
```
```
            break;
```
```
        case 2:
```

            cout<<"Enter key of the element to be searched: ";

```
            cin>>key;
```
```
            if (hash.Search(key) == -1)
```
```
            {
```

                cout<<"No element found at key "<<key<<endl;

```
                continue;
```
```
            }
```
```
            else
```
```
            {
```

                cout<<"Element at key "<<key<<" : ";

                cout<<hash.Search(key)<<endl;

```
            }
```
```
            break;
```
```
        case 3:
```

            cout<<"Enter key of the element to be deleted: ";

```
            cin>>key;
```
```
            hash.Remove(key);
```
```
            break;
```
```
        case 4:
```
```
            exit(1);
```
```
        default:
```

           cout<<"\nEnter correct option\n";

```
       }
```
```
    }
```
```
    return 0;
```
```
}
```

Add a comment

Answer 2

C++ question: Using a standard dictionary, and a table size that approximates a load factor of...

Homework Answers

Add Answer to:
C++ question: Using a standard dictionary, and a table size that approximates a load factor of...

Post as a guest

Earn Coins

4. Hashing and Hash Tables. You need to use the ASCII table in the last page for this question. Study the following hash functions for ASCII C strings that are at least 3-char long unsigned hash1(con...

In C++: Please help me correct this code .... All parts with (FIX ME) #include <algorithm> #include <climits&gt...

Following class is only part of my program that uses a hash table to simulate a...

Java using data structures The objective is to create your own Hash Table class to hold...

1 Overview For this assignment you are required to write a Java program that plays (n,...

Implement a rabin_hash method to make the following code work: int rabin_karp_batchmatch(int bsz, /* size of...

How to write the insert, search, and remove functions for this hash table program? I'm stuck......

QUIZ 9 QUESTION 1 An enumeration contains enumerators that represent a. the functions for the enumeration...

My C++ program is not compiling. Please explain how you fixed with detailed inline comments. I am using Visual Studio 2017. It's a character count program that keeps and displays a count of all th...

C++ question: Using a standard dictionary, and a table size that approximates a load factor of...

Homework Answers

Add Answer to: C++ question: Using a standard dictionary, and a table size that approximates a load factor of...

Post as a guest

Earn Coins

Add Answer to:
C++ question: Using a standard dictionary, and a table size that approximates a load factor of...