Java : How to make this hash table function work on a much larger scale

Question

I have the following code, that will take 30 strings (that are numbers) and put them into a hash table after computing them with "%29"

import java.util.Arrays;


public class HashFunction {

    String[] theArray;
    int arraySize;
    int itemsInArray = 0;

    public static void main(String[] args) {

        HashFunction theFunc = new HashFunction(30); // this is where you should be able to control the number of spaces availble in the hash table!!!

        // Simplest Hash Function

        // String[] elementsToAdd = { "1", "5", "17", "21", "26" };

        // theFunc.hashFunction1(elementsToAdd, theFunc.theArray);

        // Mod Hash Function
        // This contains exactly 30 items to show how collisions
        // will work

        String[] elementsToAdd2 = { "100", "510", "170", "214", "268", "398",
                "235", "802", "900", "723", "699", "1", "16", "999", "890",
                "725", "998", "978", "988", "990", "989", "984", "320", "321",
                "400", "415", "450", "50", "660", "624" };

        theFunc.hashFunction2(elementsToAdd2, theFunc.theArray);

        // Locate the value 660 in the Hash Table

        //theFunc.findKey("660");

        theFunc.displayTheStack();

    }

    // Simple Hash Function that puts values in the same
    // index that matches their value

    public void hashFunction1(String[] stringsForArray, String[] theArray) {

        for (int n = 0; n < stringsForArray.length; n++) {

            String newElementVal = stringsForArray[n];

            theArray[Integer.parseInt(newElementVal)] = newElementVal;

        }

    }



    public void hashFunction2(String[] stringsForArray, String[] theArray) {

                        int sumOfCollisions = 0;
                        float averageOfCollisions = 0;
                        int numberOfCollisions = 0;                        

        for (int n = 0; n < stringsForArray.length; n++) {

            String newElementVal = stringsForArray[n];

            // Create an index to store the value in by taking
            // the modulus

            int arrayIndex = Integer.parseInt(newElementVal) % 29;

            System.out.println("Modulus Index= " + arrayIndex + " for value "
                    + newElementVal);

            // Cycle through the array until we find an empty space


            while (theArray[arrayIndex] != "-1") {
                ++arrayIndex;
                                numberOfCollisions++;

                //System.out.println("Collision Try " + arrayIndex + " Instead");
                                //System.out.println("Number of Collisions = " + numberOfCollisions);
                // If we get to the end of the array go back to index 0

                arrayIndex %= arraySize;
            }


                        if (numberOfCollisions > 0)
                        {
                            System.out.println("                       Number of Collisions = " + numberOfCollisions);
                        }                       

            theArray[arrayIndex] = newElementVal;

        }

                        sumOfCollisions += numberOfCollisions;

                        averageOfCollisions = sumOfCollisions / 30;

                        System.out.println("Sum of Collisions = " + sumOfCollisions);

                        System.out.println("Average of Collisions = " + averageOfCollisions);                

    }

    // Returns the value stored in the Hash Table

    public String findKey(String key) {

        // Find the keys original hash key
        int arrayIndexHash = Integer.parseInt(key) % 29;

        while (theArray[arrayIndexHash] != "-1") {

            if (theArray[arrayIndexHash] == key) {

                // Found the key so return it
                System.out.println(key + " was found in index "
                        + arrayIndexHash);

                return theArray[arrayIndexHash];

            }

            // Look in the next index

            ++arrayIndexHash;

            // If we get to the end of the array go back to index 0

            arrayIndexHash %= arraySize;

        }

        // Couldn't locate the key

        return null;

    }

    HashFunction(int size) {

        arraySize = size;

        theArray = new String[size];

        Arrays.fill(theArray, "-1");

    }

    public void displayTheStack() {

        int increment = 0;

        for (int m = 0; m < 3; m++) {

            increment += 10;

            for (int n = 0; n < 71; n++)
                System.out.print("-");

            System.out.println();

            for (int n = increment - 10; n < increment; n++) {

                System.out.format("| %3s " + " ", n);

            }

            System.out.println("|");

            for (int n = 0; n < 71; n++)
                System.out.print("-");

            System.out.println();

            for (int n = increment - 10; n < increment; n++) {

                if (theArray[n].equals("-1"))
                    System.out.print("|      ");

                else
                    System.out
                            .print(String.format("| %3s " + " ", theArray[n]));

            }

            System.out.println("|");

            for (int n = 0; n < 71; n++)
                System.out.print("-");

            System.out.println();

        }

    }

}

For convenience, here is the output:

    run:
Modulus Index= 13 for value 100
Modulus Index= 17 for value 510
Modulus Index= 25 for value 170
Modulus Index= 11 for value 214
Modulus Index= 7 for value 268
Modulus Index= 21 for value 398
Modulus Index= 3 for value 235
Modulus Index= 19 for value 802
Modulus Index= 1 for value 900
Modulus Index= 27 for value 723
Modulus Index= 3 for value 699
                       Number of Collisions = 1
Modulus Index= 1 for value 1
                       Number of Collisions = 2
Modulus Index= 16 for value 16
                       Number of Collisions = 2
Modulus Index= 13 for value 999
                       Number of Collisions = 3
Modulus Index= 20 for value 890
                       Number of Collisions = 3
Modulus Index= 0 for value 725
                       Number of Collisions = 3
Modulus Index= 12 for value 998
                       Number of Collisions = 3
Modulus Index= 21 for value 978
                       Number of Collisions = 4
Modulus Index= 2 for value 988
                       Number of Collisions = 7
Modulus Index= 4 for value 990
                       Number of Collisions = 9
Modulus Index= 3 for value 989
                       Number of Collisions = 14
Modulus Index= 27 for value 984
                       Number of Collisions = 15
Modulus Index= 1 for value 320
                       Number of Collisions = 23
Modulus Index= 2 for value 321
                       Number of Collisions = 31
Modulus Index= 23 for value 400
                       Number of Collisions = 31
Modulus Index= 9 for value 415
                       Number of Collisions = 37
Modulus Index= 15 for value 450
                       Number of Collisions = 40
Modulus Index= 21 for value 50
                       Number of Collisions = 43
Modulus Index= 22 for value 660
                       Number of Collisions = 47
Modulus Index= 15 for value 624
                       Number of Collisions = 61
Sum of Collisions = 61
Average of Collisions = 2.0
-----------------------------------------------------------------------
|   0  |   1  |   2  |   3  |   4  |   5  |   6  |   7  |   8  |   9  |
-----------------------------------------------------------------------
| 725  | 900  |   1  | 235  | 699  | 988  | 990  | 268  | 989  | 320  |
-----------------------------------------------------------------------
-----------------------------------------------------------------------
|  10  |  11  |  12  |  13  |  14  |  15  |  16  |  17  |  18  |  19  |
-----------------------------------------------------------------------
| 321  | 214  | 998  | 100  | 999  | 415  |  16  | 510  | 450  | 802  |
-----------------------------------------------------------------------
-----------------------------------------------------------------------
|  20  |  21  |  22  |  23  |  24  |  25  |  26  |  27  |  28  |  29  |
-----------------------------------------------------------------------
| 890  | 398  | 978  | 400  |  50  | 170  | 660  | 723  | 984  | 624  |
-----------------------------------------------------------------------
BUILD SUCCESSFUL (total time: 0 seconds)

So as you can see, I have it set up so that it tells me the average number of collisions that occurred when constructing this particular hash table. There are 30 numbers and 30 spaces for them to occupy. I tried changing the parameter for the amount of available spaces from 30 to 60, but that didn't change anything, and I want to figure out how to fix this.

This is important to me because I want to take this code up a notch. I would like to try this program out for a larger set of numbers, maybe a thousand or more, but I don't want to just manually input a thousand more string numbers. How would I write a loop that would do this for me? For example, if I put 1000 in its parameter, it will produce a thousand numbers in string notation (as seen in the code) that will be used.

I also want to make it so that I can have multiple of these string numbers run in a single program execution. For example, the hash table can hold 1000 numbers, so then it will run the program with 1 number, then 2,3, etc... until it has done so all the way up to 1000. And for each time it does this, I want it to output the average number of collisions that occurred in that particular run. With only 1 number there will be no collision, and eventually collisions will occur as the amount of numbers increases.

By doing this, I could then make a graph that shows how the amount of collisions changes as the ratio of numbers to available spots changes. For example, the x-axis would be the average collisions, and the y-axis would be the ratio of the amount of inputed numbers compared with the total available spaces (meaning that it would have a value range from 0 to 1.00)

Thank you in advance to all that take the time to teach me. I really appreciate it.

Answer 1

To have your program randomly generate numbers for you, you should create a method that takes an integer parameter that loops through an array of that size and inserts a random number.

int size_of_hash = Integer.parseInt( args[1] );

The above code will take a argument from the command line and use it to create a variable that determines how big the hash table is. You can use this variable to create the hash function and you can use it to create the array

You can call a method

public int[] createRandomArray( int size ) {
    Random r = new Random(); //java.util.Random - this class will randomly generate integers for you
     int random_array = //instantiate the array

     for( int i = 0; i <= size; i++ ) {
         //insert logic
      }

      return random_array;
 }

The method is incomplete. The best way to learn is to do. The important thing to notice here is that this method is essentially taking a simple repetitive task and having the program do it for you. Javadocs are a great resource for learning about new resources inside of the java ecosystem. Just google "javadoc random", and the class should come up.

I would recommend changing the main method to be a constructor for the class, and rewriting the main method to call a number of trials that you can specify in the arguments for the program. This would help you get more accurate data by running a large number of trials instead of just one.

Answer 2

Use the following :

import java.util.Random; //that's where it is.
...
...//directly to the class
private Random r = new Random();
public String randomString(int limit)
{
    int n = r.nextInt(limit);
    return n+"";
}
...

This returns a random number in the form of a String within the limit(0 to limit -1). If you want a String of n digits, do this

StringBuilder s = new StringBuilder();
for(int i = 0; i < n; i++)
    s.append(r.nextInt(10));
return s.toString();