import java

Subject:Computer SciencePrice: Bought3

Share With

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);
	}
}