Program #7 in C++ programming Hashing Input file: file.dat Output: results.dat I

Question

Program #7 in C++ programming

Hashing

Input file: file.dat

Output: results.dat

In this assignment, you are going to build a hash table for integers using the file.dat as input.

The input file contains 200,000 integers. You will read in the first 100,000 integers and hash them into an array using modulo-division hashing. The values range from 100,000 to 500,000 and contain duplicate numbers. You will use quadratic probe collision detection. In order to simplify the problem, you will only probe 10 times. If you can’t store (or find) the result after 10 probs, you won’t store the value. If you can’t store a value, you need to generate output that tells the number can’t be stored. After you create the hash table, you will read the next 100,000 items and see if you can find the key in the hashed array. You need to indicate how many times you probed to find the data.

Some things to consider:

How large should the array be? (Hint: Remember that we discussed using storage that is about 25% larger. )

What would be a good number to use for hashing? (Hint: Prime numbers work better. Consider using 100,003.

Input will be from file.dat. You will need to read in 100,000 and hash them.

Output will be to a file. There could be 2 parts to the output. First, any numbers that can’t be stored. Second, any numbers that can’t be found in the hash table or that take more than 1 probe to find.

Sample output file:

Creating Hash Table

Not stored:

150,000

450,000

Searching Hash Table

Found               123457              5 probes

Not found         150,000

*** Input File has 200,000 integers, first 5 listed below for reference.***

458988
339823
293980
280340
112766

Explanation / Answer

#include <iostream>
#include <fstream>

#include <cstdlib>
#include <ctime>

using namespace std;

#define arraySize 125000

class Hash{
   int MOD;
   int array[ arraySize ];
public:
   Hash(){
       for(int i = 0; i < arraySize; i++){
           array[i] = -1; //-1 meaning no number stored
       }
       MOD = 100003;
   }
   bool insertInHash(int number ){ //returns if insertion is successful or not
       int location = number%MOD;
       if( array[location] != -1 ){
           for(int probe = 1; probe<= 10; probe++){
               int newLocation = location + probe*probe;
               if( array[newLocation] == -1 ){
                   array[ newLocation ] = number;
                   return true;
               }
           }
           //all probes failed, wont store value
           return false;
       }
       else{
           array[location] = number;
       }
       return true;
   }
   int searchHash( int number ){ //returns if it is searched
       int location = number%MOD;
       if( array[location] == -1 ){
           //we never delete from hash, i.e. if number is not here, there wasnt here ever
           //so we wont probe, as we never did probe, if no number ever existed here
           return -1;
       }
       if( array[location] == number ){
           return 0;
       }
       else
       {
           for(int probe=1; probe<= 10; probe++ ){
               int newLocation = location + probe*probe;
               if( array[newLocation] == -1 ){ return -1; }
               if( array[newLocation] == number ){ return probe; }
           }
       }
       return -1;
   }
};

int main(){
   Hash myHash;

   int number;
   ifstream in("file.dat");
   ofstream out("results.dat");

   out << "Not stored:" << endl;
   for(int i = 0; i < 100000; i++){
       in >> number;
       if( !myHash.insertInHash( number ) ){
           out << number << endl;
       }
   }

   out << "Searching Hash Table" << endl;
   for(int i = 0; i < 100000; i++){
       in >> number;
       int found = myHash.searchHash( number );
       if( found == -1 ){
           out << "Not found " << number << endl;
       }
       else{
           out << "Found " << number << " " << found << " probes" << endl;
       }
   }

   return 0;
   /*srand(time(NULL));
   ofstream out("file.dat");
   for(int i = 0; i < 200000; i++){
       out << rand()%200000 << endl;
   }*/
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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