Program #7 Hashing Input file: file.dat Output: results.dat In this assignment,

Question

Program #7

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.***

458988
339823
293980
280340
112766

Explanation / Answer

HashTable.java

public class HashTable {

   private int MAXSIZE = 100000;
   private int HASHSIZE = 100003;
   private String[] keys;

   public HashTable() {
       keys = new String[MAXSIZE];
   }

   private int hash(String key) {
       return key.hashCode() % HASHSIZE;
   }

   public boolean insert(String key) {
       int tmp = hash(key);
       int i = tmp, h = 1;
       int numberOfTries = 1;
       boolean stored = true;
       do {
           //System.out.println("i: " + i);
           if (keys[i] == null) {
               keys[i] = key;
               break;
           }
           if (numberOfTries >= 10) {
               break;
           }
           i = (i + h * h++) % HASHSIZE;
           numberOfTries++;
       } while (true);
       //System.out.println("numberofTries: "+numberOfTries);
       if(numberOfTries >=10){
           stored = false;
       }
       return stored;
   }

   public int get(String key) {
       int i = hash(key), h = 1;
       int count = 0;
       boolean found = false;
       try {
           while (keys[i] != null) {
               count++;
               if (keys[i].equals(key)) {
                   // System.out.println("Index: "+i);
                   found = true;
                   break;
               }
               i = (i + h * h++) % HASHSIZE;
           }
       } catch (IndexOutOfBoundsException e) {

       }
       if (!found) {
           count = 0;
       }
       return count;
   }

   public void print() {
       for (int i = 0; i < 10; i++) {
           System.out.print(keys[i]);
       }
       System.out.println();
   }
}

HashTableTest.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class HashTableTest {

   public HashTableTest() {
       // TODO Auto-generated constructor stub
   }

   public static void main(String[] args) throws IOException {

       HashTable ht = null;
       BufferedReader br = null;
       BufferedWriter bw = null;
       FileReader fr = null;
       FileWriter fw = null;

       String INPUTFILENAME = "file.dat";
       String OUTPUTFILENAME = "results.dat";
       int MAXSIZE = 100000;

       try {
           ht = new HashTable();
           fr = new FileReader(INPUTFILENAME);
           br = new BufferedReader(fr);

           fw = new FileWriter(OUTPUTFILENAME);
           bw = new BufferedWriter(fw);

           String sCurrentLine;
           int count = 0;

           bw.write("Creating Hash Table ");
           while ((sCurrentLine = br.readLine()) != null) {

               if (count++ < MAXSIZE) {

                   // System.out.println(sCurrentLine);
                   boolean stored = ht.insert(sCurrentLine);
                   if (!stored) {
                       bw.write("Not Stored:" + sCurrentLine + " ");
                   }
                   //ht.print();
               }
               else if(count-1 == MAXSIZE){
                   bw.write(" Searching Hash Table ");
               }
               else {
                   int searches = ht.get(sCurrentLine);
                   if (searches != 0) {
                       bw.write("Found " + sCurrentLine + " " + searches + "probes ");
                   } else {
                       bw.write("NotFound " + sCurrentLine+" ");
                   }
               }
           }
           System.out.println("Successfully executed!");
       } catch (IOException e) {
           e.printStackTrace();
       } finally {
           try {
               if (bw != null)
                   bw.close();
               if (fw != null)
                   fw.close();
           } catch (IOException ex) {
               ex.printStackTrace();
           }
       }
   }

}

Note: Make sure that you have given the correct relative path for inputfile

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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