Help with Data Array for Hash Table creation

[Joanna Spence]

Hello,

I am working with building Hash Tables, with Linear Probing and I have three class files.

The first is a driver file that calls the super class HashTable.
It generates random values to fit the size of the hash table indicated in the driver file

Here is the code snippet from the driver file:

 int num = 5;
     int [] sizes = {1009, 2003, 4001, 8009, 16001};
     int [] dhs = {997, 1999, 3989, 7993, 15991};
     double [] alphas = {0.5, 0.6, 0.7, 0.8, 0.9, 0.95};

     HTable LPT, DHT, SCT;

     for (int i = 0; i < sizes.length; i++)
     {
        int size = sizes[i];
        int dhmod = dhs[i];
        LPT = new LPTable(size);          // Note constructors for classes below.
        DHT = new DHTable(size, dhmod);   // Also note that ALL variables are of
        SCT = new SCTable(size);		  // class HTable

        for (int j = 0; j < alphas.length; j++)
        {
            LPT.init();  // Init method called each time through this loop to reset
            DHT.init();  // the hash tables to empty
            SCT.init();

            double alpha = alphas[j];      // Get next alpha value
            int n = (int) (size * alpha);  // How many items to insert

            int key;

            for (int k = 0; k < n; k++)
            {
                key = (int) (Math.random() * (4 * size));  // Make range of values
                                           // 4 times the size of the table
                LPT.insert(key);
                DHT.insert(key);  // insert key into each table
                SCT.insert(key);
            }

It first creates a new object called HTable which is the super class in my other class files...

and then generate random values denoted by n of how many items to insert.

It calls my "insert" method in my subclass for Linear Probing...

My problem is, in my subclass for LPTable...
I need to generate the array of values of the number of items to insert, but when I create the data array, it is only inserting one value...
I believe it is my placement of the creation of the data array in my subclass...

Here is my subclass and what I have...
I need to generate the complete data array of all the values so that I can perform the hash table functions, but I also want to print out the data array to test to see they are all there...

Here is my SuperClass code snippet:

// Method to initialize the table in any way necessary
    public abstract void init();
// Insert an int into the hash table
public abstract void insert(int key);

Here is my subclass code:

public int[] lpTableArray;
    public ArrayList<Integer> lpTableList;
    
    
    public void insert(int key)
    {
    	int addition;
    	addition=key;
    	int hashVal=h(key);
    	LPT.put(addition, hashVal);
    	System.out.println(LPT);
    	
		
    
    }

When I run my program right now, it only inserts one value...i need to insert all random values in ONE call, and then I want to print the result to see that it performed the operation correcltly.

Any help would be appreciated..I think it my placement of the declarations of the array and the call to insert but I'm not sure.

[David Newton]

Well, if you think it's in the creation of your data array, it'd be good to show the creation of the data array.

The code fragment has too many (to us) unknowns (edited to remove the unnecessary noise):

    public int[] lpTableArray; // Created where?
    public ArrayList<Integer> lpTableList; // Created where?
    
    public void insert(int key)
    {
    	LPT.put(key, h(key)); // What's h? What's LPT?
    }

[Joanna Spence]

The lpTableArray is created in the LPT subClass...

lpTableList is also created in the subClass LPT...

the "h" stands for the hash...

In the driver class; a new instance of LPT is created, and the inserts are done from the driver...

[David Newton]

*confused* But LPT is a local variable in the driver--how does a subclass have access to it?

That aside--I don't see how to help; unless your loop isn't executing as many times as you think it is, or the key you're adding is always the same, from the code given, there's no reason it would be only "inserting once". So there's some other logical error not contained in the code provided. Since we can't run it, there's nothing we can do except guess.

[Joanna Spence]

Here are the files, I tried to attach them but it wouldn't let me attach in .java or .txt format...

Here is the driver:

import java.io.*;

public class driver
{
   public static void main(String [] args)
   {

     PrintWriter ofile = null;
     try {
           ofile = new PrintWriter(new FileOutputStream("a2out.txt"));
     }
     catch (FileNotFoundException e)
     {
		 System.out.println("Output File DNE");
	 }

     int num = 5;
     int [] sizes = {1009, 2003, 4001, 8009, 16001};
     int [] dhs = {997, 1999, 3989, 7993, 15991};
     double [] alphas = {0.5, 0.6, 0.7, 0.8, 0.9, 0.95};

     HTable LPT, DHT, SCT;

     for (int i = 0; i < sizes.length; i++)
     {
        int size = sizes[i];
        int dhmod = dhs[i];
        LPT = new LPTable(size);          // Note constructors for classes below.
        DHT = new DHTable(size, dhmod);   // Also note that ALL variables are of
        SCT = new SCTable(size);		  // class HTable

        for (int j = 0; j < alphas.length; j++)
        {
            LPT.init();  // Init method called each time through this loop to reset
            DHT.init();  // the hash tables to empty
            SCT.init();

            double alpha = alphas[j];      // Get next alpha value
            int n = (int) (size * alpha);  // How many items to insert

            int key;

            for (int k = 0; k < n; k++)
            {
                key = (int) (Math.random() * (4 * size));  // Make range of values
                                           // 4 times the size of the table
                LPT.insert(key);
                DHT.insert(key);  // insert key into each table
                SCT.insert(key);
            }

            int LPFound = 0, LPFoundProbes = 0;
            int LPNot = 0, LPNotProbes = 0;
            int DHFound = 0, DHFoundProbes = 0;
            int DHNot = 0, DHNotProbes = 0;
            int SCFound = 0, SCFoundProbes = 0;
            int SCNot = 0, SCNotProbes = 0;

            final int FindRuns = 40000;  // Do 40000 searches for each setup
            for (int ii = 0; ii < FindRuns; ii++)
            {
                key = (int) (Math.random() * (4 * size));

                boolean found1 = LPT.find(key);  // The find method should
                        // initialize a "prob" instance variable to 0, then 
						// increment it for each probe needed during the find.

                if (found1 == true)
                {
                   LPFound++;
                   LPFoundProbes += LPT.probes();  // The probes() method
                          // retrieves the value obtained by the "probecout"
                          // variable during the find
                }
                else
                {
                   LPNot++;
                   LPNotProbes += LPT.probes();
                }

                boolean found2 = DHT.find(key);

                if (found2 == true)
                {
                   DHFound++;
                   DHFoundProbes += DHT.probes();
                }
                else
                {
                   DHNot++;
                   DHNotProbes += DHT.probes();
                }

                boolean found3 = SCT.find(key);

                if (found3 == true)
                {
                   SCFound++;
                   SCFoundProbes += SCT.probes();
                }
                else
                {
                   SCNot++;
                   SCNotProbes += SCT.probes();
                }
            }
            // Below I am calculating the various averages for the schemes

            double AveLPFound, AveLPNot, AveLPTotal, LPSuccess;
            double AveDHFound, AveDHNot, AveDHTotal, DHSuccess;
            double AveSCFound, AveSCNot, AveSCTotal, SCSuccess;
            
            

            AveLPFound = (double) LPFoundProbes / LPFound;
            AveLPNot = (double) LPNotProbes / LPNot;
            AveLPTotal = (double) (LPFoundProbes + LPNotProbes)/(LPFound + LPNot);
            LPSuccess = (double) LPFound /(LPFound + LPNot);

            AveDHFound = (double) DHFoundProbes / DHFound;
            AveDHNot = (double) DHNotProbes / DHNot;
            AveDHTotal = (double) (DHFoundProbes + DHNotProbes)/(DHFound + DHNot);
            DHSuccess = (double) DHFound /(DHFound + DHNot);

            AveSCFound = (double) SCFoundProbes / SCFound;
            AveSCNot = (double) SCNotProbes / SCNot;
            AveSCTotal = (double) (SCFoundProbes + SCNotProbes)/(SCFound + SCNot);
            SCSuccess = (double) SCFound /(SCFound + SCNot);

            ofile.println("-------------------------------------------------------");
            ofile.println("Table size: " + size + "    Alpha: " + alpha);
            ofile.println("      LP fraction of successful finds: " + LPSuccess);
            ofile.println("      LP Ave probes for successful find: " + AveLPFound);
            ofile.println("      LP Ave probes for unsuccess. find: " + AveLPNot);
            ofile.println("      LP Ave probes for all finds: " + AveLPTotal);

            ofile.println("Table size: " + size + "    Alpha: " + alpha);
            ofile.println("      DH fraction of successful finds: " + DHSuccess);
            ofile.println("      DH Ave probes for successful find: " + AveDHFound);
            ofile.println("      DH Ave probes for unsuccess. find: " + AveDHNot);
            ofile.println("      DH Ave probes for all finds: " + AveDHTotal);

            ofile.println("Table size: " + size + "    Alpha: " + alpha);
            ofile.println("      SC fraction of successful finds: " + SCSuccess);
            ofile.println("      SC Ave probes for successful find: " + AveSCFound);
            ofile.println("      SC Ave probes for unsuccess. find: " + AveSCNot);
            ofile.println("      SC Ave probes for all finds: " + AveSCTotal);
        }   // end inner for loop
     } // end outer for loop
     ofile.close();
   }
   
}

Here is the superclass:

public abstract class HTable
{
    protected int size;		// Size of hash table array
    protected int prob;		// number of probes required

    public HTable(int sz)	// Base constructor -- note that you
    {						// will also need a constructor for 
         size = sz;			// each of your subclasses
         prob = 0;
    }

	// Method to initialize the table in any way necessary
    public abstract void init();

	// Simple hash function.  This is inherited by the subclasses and
	// should be used in each of them.
    public int h(int key)
    {
         return (key % size);
    }

	// Insert an int into the hash table
    public abstract void insert(int key);

	// Return true if the key is found; false otherwise.  During the find
	// the prob instance variable should initialized to 0 and then updated
	// accordingly.
    public abstract boolean find(int key);

	// Return the current value of the prob variable
    public int probes()
    {
         return prob;
    }
}

Here is the subclass for LPTable:

import java.util.*;
import java.awt.*;
import java.io.IOException;

public class LPTable extends HTable
{
	public Hashtable LPT=new Hashtable();
	public int[] sizes;
	private int arraySize;
	private int probeCount;
	
	
    LPTable(int s)
    {
    	super(s);
    	arraySize=s;
    	probeCount=0;
    	
    	
    	
    	//System.out.println(size);
    	
    	
    }
    
    public int h(int key)
    {
    	
    	
    	return key % arraySize;
    }
    
    public boolean find(int n)
    {
    	boolean found=false;
    	int lpKey=n;
    	
    	return found;
    }
    
    public int[] lpTableArray;
    public ArrayList<Integer> lpTableList;
    
    
    public void insert(int key)
    {
    	int addition;
    	addition=key;
    	int hashVal=h(key);
    	LPT.put(addition, hashVal);
    	System.out.println(LPT);
    	
		
    
    }
    
    public ArrayList<Integer> lpHash2;
    public void insert2(ArrayList<Integer> item)
    {
    	lpHash2=new ArrayList<Integer>(item);
    	int hashItem=lpHash2.get(0);
    	int hashVal=h(hashItem);
    	System.out.println(hashVal);
    	while(lpHash2.get(hashVal)!=null)
    	{
    		++hashVal;
    		hashVal %= arraySize;
    	}
    	
    	
    }
    
    public int probes()
    {
    	return prob;
    }
    
        
    public void init()
    {
    	LPT.clear();
    }
    
    
    
    
    
    
}

[David Newton]

A warning that it prints the entire hash for every single insert would have been in order :( Not cool.

Now: what makes you think there's only a single insert happening, which the deluge of S.o.p's gives lie to? And what is the point of the following method, apparently used to determine if something is found in the hash table?

public class LPTable extends HTable
{
    public Hashtable LPT = new Hashtable();
    public boolean find(int n) {
        boolean found=false;
        int lpKey=n;
        return found;
    }
}

Will this ever indicate that a key is found?

Some notes:

- Pick spaces, or tabs, but not both.
- Remove code that isn't used.
- Remove code that *is* used, but is superfluous.
- Remove excess blank lines.
- Remove comments that do not add to understanding.
- Start with much, much smaller values until you actually know it works, otherwise debug runs take too long.

[David Newton]

- Why does the subclass have its own probe count? But return the superclass's prob count?
- Why does LPT re-implement h() with the same implementation?
- What's the difference between LPT's arraySize and HTable's size?
- Why does LPT.insert2() create a new array list? Named hash? Of the same size as the item you're inserting?
- Why does the program attempt to write to ofile even if there's an exception?
- Why is the average/etc. shown for every findrun rather than at the end of all of them?

(Also, Java conventions state that classes should begin with a capital letter, and non-final variables begin with lower-case letters. Following the conventions makes your code easier to read for other Java programmers :)

LPTable seems to be a mish-mash of nonsensical code; what specifically are you trying to do? You might want to consider starting over, taking care to keep only the code you actually need and know to work correctly.