DATA STRUCTURES - C++ In this lab we are going to examine how hashing can be use

Question

DATA STRUCTURES - C++

In this lab we are going to examine how hashing can be used to do direct lookup of data stored in a vector.

First begin with this program here. The program inputs a string and uses string2int to convert it to an integer. The program then uses hash2 to generate a pseudo-random number from the integer. Run the program and convert your name to a number.

Next write the code to input an integer r (the size of the name space) and generate a vector v with r random numbers. (Use the technique discussed in Lab 2.)

Next input an integer n which is the size of the address space and create a vector a with n elements all set equal to -1.

Write the code : for each element v[i] compute m = hash2(v[i])%n . Check if a[m]= -1. If a[m]=-1 set it equal to i. Otherwise output a message indicating there is a collision.

Run your program testing for various values of r and n.

Now to find the index in v with value y compute hash2(y)%n.

The PROGRAM:

Explanation / Answer

#include <iostream>
#include <string>
#include <stdlib.h>
#include <cstdlib>
#include <time.h>
#include <vector>

using namespace std;

int hash2(int n)
{
srand (n);
return rand();
}

int string2int(string s)
{  
int h=0;
int d=1;
for (int i=0; i<s.length(); i++)
{
   char x=s[i];
   h+=(x)*d;
   d=d*10;
}
return h;
}

int main()
{

srand(time(NULL));
string s;
cout << "enter string:";
cin >> s;
cout << endl;
cout << string2int(s);
cout << endl;
cout << hash2(string2int(s));

cout << " Input r:";
int r;
cin >> r;
vector <int> v(r);

for (int i = 0; i<r; i++){
     int a = rand()%100;
     v[i] = a;
}
cout << "Input n:";
int n;
cin >> n;
vector <int> a(n);
for (int i = 0; i<n; i++){
     a[i] = -1;
     //cout << a[i] << endl;
}

for (int i = 0; i<r; i++){
     //cout << v[i] << endl;
    
     int ind = hash2(v[i])%n;
     //cout << ind << " " << a[ind] << endl;
     if (a[ind] == -1){
        a[ind] = i;
     }
     else {
        cout << "There is a collision ";
     }

}

}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.