In this lab we are going to examine how hashing can be used to do direct lookup

Question

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

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.

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 I
• Subjects

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