How to insert random ints into hashing table?

Question

The data structure & algorithm class that I'm taking now is a lot of pen and paper understanding of how algorithms work, but very little actual coding. I'm kind of a programming noob, so this may be a stupid question to some of you.

Conceptually, I understand hashing, and the reasons for the different methods, but am lost on how to code this assignment.

Basically we can use any source code that we want. The codes from the book are http://users.cis.fiu.edu/~weiss/dsaajava3/code/SeparateChainingHashTable.java and http://users.cis.fiu.edu/~weiss/dsaajava3/code/QuadraticProbingHashTable.java

When using either of these codes, I seem to have trouble inserting the keys into the table. I'm using this block to insert:

Random randomGenerator = new Random();
int randomInt = randomGenerator.nextInt(99999);
for (int i = 0; i < 100; i++) {
    H.insert(""+randomInt);
}

This doesn't seem to actually insert anything into the table, however, the size remains constant despite the amount of insertions. Also, I have no idea how to determine how many probes were needed.

Answer 1

Random randomGenerator = new Random();

for (int i = 0; i < 100; i++) {
    int randomInt = randomGenerator.nextInt(99999);
    H.insert(""+randomInt);
}

Try this, you have one line in bad place.

I case of probing:

/**
     * Method that performs quadratic probing resolution.
     * @param x the item to search for.
     * @return the position where the search terminates.
     */
    private int findPos( AnyType x )
    {
        int offset = 1;
        int currentPos = myhash( x );

        while( array[ currentPos ] != null &&
                !array[ currentPos ].element.equals( x ) )
        {
            currentPos += offset;  // Compute ith probe
            offset += 2;
            if( currentPos >= array.length )
                currentPos -= array.length;
        }

        return currentPos;
    }

If I correctly understand: This method is performing probing, yes? So You have to count how many times this method is called in two options: duplicate, and not duplicate. Use some flag if current element added is duplicated and two integers. In this method add if for checking flag and increase one of counters. You will have number of probes.

Edit:

[LIN-np]: Linear probing with a non-prime table-size 1000 [LIN-p]: Linear probing with a prime table-size 1019. Note that 1019 is minPrime(1000), i.e., the minimum prime number larger than 1000. [QDR-p]: Quadratic probing with a prime table-size 1019 [DBL-p]: Double hashing with a prime table-size 1019 and collision resolution hashing on a prime number 97.

You have to use HashTable which use probing and test the amount of probing(average). You have quadric probing algorithm in public class QuadraticProbingHashTable<AnyType>. And you have to set hash table length to 1019. In first exercise you have to use linear probing. So Basically you have to use HashTables with specified preconditions when you start adding elements.

This is linear probing algorithm

This is double hash alhorithm

You have to implement this in your hash table and check how many times it will be used. I think that it will somehow show how many collisions it generates. Happy coding. Quadric algorithm is done, only you have to set preconditions)(hardcode starting value to 1019).