Solution for QID #48066: import java.io.*; import java.util.*; public class MyHas | StudyHelpMe

import java.io.*; import java.util.*; public class MyHashSet implements HS_Interface { private int numBuckets; private Node[] bucketArray; private int size; // total # keys stored in set right now // THIS IS A TYPICAL AVERAGE BUCKET SIZE. IF YOU GET A LOT BIGGER THEN YOU ARE MOVING AWAY FROM (1) private final int MAX_ACCEPTABLE_AVE_BUCKET_SIZE = 20; public MyHashSet( int numBuckets ) { size=0; this.numBuckets = numBuckets; bucketArray = new Node[numBuckets]; // array of linked lists System.out.format("IN CONSTRUCTOR: INITIAL TABLE LENGTH=%d RESIZE WILL OCCUR EVERY TIME AVE BUCKET LENGTH EXCEEDS %dn", numBuckets, MAX_ACCEPTABLE_AVE_BUCKET_SIZE ); } public boolean add( String key ) { ADD THE KEY TO THE TABLE ++size; if ( size > MAX_ACCEPTABLE_AVE_BUCKET_SIZE * this.numBuckets) upSize_ReHash_AllKeys(); // DOUBLE THE ARRAY .length THEN REHASH ALL KEYS return true; } private void upSize_ReHash_AllKeys() { System.out.format("KEYS HASHED=%10d UPSIZING TABLE FROM %8d to %8d REHASHING ALL KEYSn", size, bucketArray.length, bucketArray.length*2 ); Node[] biggerArray = new Node[ bucketArray.length * 2 ]; this.numBuckets = biggerArray.length; <== DONT FORGET TO DO THIS AS SOON AS YOU UPSIZE FOR EACH BUCKET FOR EACH NODE IN THE LIST HASH THAT KEY BACK INTO THE BIGGER TABLE BE SURE YOU ARE USING THE BIGGER .LENGTH AS MODULUS !! this.bucketArray = biggerArray; } // END UPSIZE & REHASH } //END MyHashSet CLASS class Node { String data; Node next; public Node ( String data, Node next ) { this.data = data; this.next = next; } } import java.io.*; import java.util.*; public class HashTester { public static void main(String[] args) throws Exception { double mainStartTime = System.currentTimeMillis(); if (args.length < 2) die("usage: java HashTester <fileOfStrings> <numOfBuckets>"); String infileName = args[0]; int numOfBuckets = Integer.parseInt(args[1]); MyHashSet hset = new MyHashSet( numOfBuckets ); // BufferedReader infile = new BufferedReader(new FileReader(infileName)); double startTime = System.currentTimeMillis(); boolean AllAddsSucceed = true; // they SHOULD all succeed while (infile.ready()) { if ( !hset.add(infile.readLine()) ) AllAddsSucceed = false; // THIS IS BAD! } infile.close(); infile = new BufferedReader(new FileReader(infileName)); boolean AllAddsFail = true; // they SHOULD all fail while (infile.ready()) if ( hset.add(infile.readLine()) ) AllAddsFail = false; // THIS IS BAD! infile.close(); public interface HS_Interface { public boolean add( String key ); // dupes must be rejected and return false public boolean remove( String key ); // if not found return false else remove & return true public boolean contains( String key ); // true if foound false if not public boolean isEmpty(); // use the call to size public int size(); // number of keys currently stored in the container public void clear(); } // end DictionaryInterface double stopTime = System.currentTimeMillis(); System.out.println("AllAddsSucceed: " + AllAddsSucceed); // SHOULD PRINT TRUE System.out.println("AllAddsFail: " + AllAddsFail); // SHOULD PRINT TRUE System.out.format( "Runtime: %1.5f sec.n", (stopTime-startTime) / 1000.0D ); // NOW DO REMOVES // ALL THESE SHOULD SUCCEED startTime = System.currentTimeMillis(); boolean AllRemovesSucceed = true; // they SHOULD all succeed infile = new BufferedReader(new FileReader(infileName)); while (infile.ready()) { if ( !hset.remove(infile.readLine()) ) AllRemovesSucceed = false; // THIS IS BAD! } infile.close(); // RUN IT AGAIN BUT NOW THESE SHOULD ALL FAIL (WE JUST REMOVED THEM ALL) infile = new BufferedReader(new FileReader(infileName)); boolean AllRemovesFail = true; while (infile.ready()) if ( hset.remove(infile.readLine()) ) AllRemovesFail = false; // THIS IS BAD! infile.close(); stopTime = System.currentTimeMillis(); System.out.println("AllRemovesSucceed: " + AllRemovesSucceed); // SHOULD PRINT TRUE System.out.println("AllRemovesFail: " + AllRemovesFail); // SHOULD PRINT TRU System.out.format( "Runtime: %1.5f sec.n", (stopTime-startTime) / 1000.0D ); double mainStopTime = System.currentTimeMillis(); System.out.format( "OVERALL Runtime: %1.5f sec.n", (mainStopTime-mainStartTime) / 1000.0D ); } static void die(String errMsg) { System.out.println(errMsg); System.exit(0); } }