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:

#include  #include  #include  #include  #include  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; cout << endl; cout << string2int(s); cout << endl; cout << hash2(string2int(s)); }