Question

In C++

Use vectors instead of linked lists

Create a Hash table program using H(key) = key%tablesize with Chaining and Linear probing for a text file that has a list of 50 numbers

Ask the user to enter the file name, what the table size is, and which of the two options they want to use between chaining and linear probing

Answer 1

Code in C++

#include<bits/stdc++.h>
using namespace std;

int hashValue(int key, int tableSize)
{
    return key % tableSize;
}
int main()
{
    string filename;
    cin>>filename;
    
    int tableSize, choice;
    cin>>tableSize>>choice;

    freopen(filename.c_str(), "r", stdin);  //open file to read 50 number
    int n;
    cin>>n;
    int num[n];
    for(int i=0;i<n;i++)    cin>>num[i];

    vector<int>hashTable1[tableSize];
    vector<int>hashTable2(tableSize, -1);           // -1 means unoccupied
    // use switch case
    switch (choice)
    {
    //for chaining
    case 1:
        //use array of vectors, here vector (instead of linkedlist) use for chaining
        

        //insert into hashtable
        for(int i=0;i<n;i++)
        {
            int hashed = hashValue(num[i], tableSize);
            hashTable1[hashed].push_back(num[i]);
        }
        cout<<"Hash table:\n";
        for(int i=0;i<tableSize;i++)
        {
            cout<<i<<" -> ";
            for(int j=0;j<hashTable1[i].size();j++)
                cout<<hashTable1[i][j]<<" ";
            cout<<"\n";
        }
        break;

    //for linear probe
    case 2:
  
        for(int i=0;i<n;i++)
        {
            int hashed = hashValue(num[i], tableSize);
            while(hashTable2[hashed] != -1)
            {
                hashed = (hashed + 1)%tableSize;
            }
            hashTable2[hashed] = num[i];
        }

        cout<<"Hash Table:\n";
        for(int i=0;i<tableSize;i++)
            cout<<i<<" -> "<<hashTable2[i]<<"\n";

        break;
    default:
        cout<<"Enter correct choice!";
        break;
    }

}

Input file

input & output