# Java Hash Table 2

Welcome to the 2nd part of my Java Hash Tables tutorial. If you missed part 1, definitely watch it first here Java Hash Table.

In this tutorial, I will cover all of the following and more: 1. Why We Use Prime sized hash tables 2. How to Increase Hash Table Size 3. How to Avoid Clustering 4. How Double Hashing Works 5. How to Find Values in a Double Hashed Hash Table

This video provides many useful algorithms aside from the info on hash tables.

Code From the Video

Java Hash TablesÂ HashFunction2.java

```import java.util.ArrayList;
import java.util.Arrays;

public class HashFunction2 {

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

public static void main(String[] args) {

HashFunction2 theFunc = new HashFunction2(31);

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

// Demonstrate how data normally follows patterns and how
// a non-prime sized array can cause havoc

String[] elementsToAdd3 = { "30", "60", "90", "120", "150", "180",
"210", "240", "270", "300", "330", "360", "390", "420", "450",
"480", "510", "540", "570", "600", "989", "984", "320", "321",
"400", "415", "450", "50", "660", "624" };

// theFunc.modThirty();

theFunc.increaseArraySize(60);

theFunc.displayTheStack();

theFunc.fillArrayWithNeg1();

theFunc.displayTheStack();

theFunc.findKeyDblHashed("990");

}

// Outputs the matches that would put an item in
// index 0 if arraySize was 31

public void modThirty() {

for (int i = 1; i < 999; i++) {

if (i % 30 == 0) {

System.out.println(i);

}

}

}

public boolean isPrime(int number) {

// Eliminate the need to check versus even numbers

if (number % 2 == 0)
return false;

// Check against all odd numbers

for (int i = 3; i * i <= number; i += 2) {

if (number % i == 0)
return false;

}

// If we make it here we know it is odd

return true;

}

// Receives a number and returns the next prime
// number that follows

public int getNextPrime(int minNumberToCheck) {

for (int i = minNumberToCheck; true; i++) {

if (isPrime(i))
return i;

}

}

// Increase array size to a prime number

public void increaseArraySize(int minArraySize) {

// Get a prime number bigger than the array
// requested

int newArraySize = getNextPrime(minArraySize);

// Move the array into a bigger array with the
// larger prime size

moveOldArray(newArraySize);

}

public void moveOldArray(int newArraySize) {

// Create an array that has all of the values of
// theArray, but no empty spaces

String[] cleanArray = removeEmptySpacesInArray(theArray);

// Increase the size for theArray

theArray = new String[newArraySize];

arraySize = newArraySize;

// Fill theArray with -1 in every space

fillArrayWithNeg1();

// Send the values previously in theArray into
// the new larger array

hashFunction2(cleanArray, theArray);

}

// Will remove all empty spaces in an array

public String[] removeEmptySpacesInArray(String[] arrayToClean) {

ArrayList<String> stringList = new ArrayList<String>();

// Cycle through the array and if a space doesn't
// contain -1, or isn't empty add it to the ArrayList

for (String theString : arrayToClean)
if (!theString.equals("-1") && !theString.equals(""))

return stringList.toArray(new String[stringList.size()]);

}

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

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

// Store value in array index

String newElementVal = stringsForArray[n];

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

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

// Get the distance to skip down in the array
// after a collision occurs. We are doing this
// rather than just going to the next index to
// avoid creating clusters

int stepDistance = 7 - (Integer.parseInt(newElementVal) % 7);

System.out.println("step distance: " + stepDistance);

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

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

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

arrayIndex += stepDistance;

// System.out.println("Collision Try " + arrayIndex +

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

arrayIndex %= arraySize;

}

theArray[arrayIndex] = newElementVal;

}

}

// Returns the value stored in the Double Hashed Hash Table

public String findKeyDblHashed(String key) {

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

// Find the keys original step distance

int stepDistance = 5 - (Integer.parseInt(key) % 5);

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 += stepDistance;

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

arrayIndexHash %= arraySize;

}

// Couldn't locate the key

return null;

}

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

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) % arraySize;

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

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

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

++arrayIndex;

// System.out.println("Collision Try " + arrayIndex +

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

arrayIndex %= arraySize;

}

theArray[arrayIndex] = newElementVal;

}

}

// Returns the value stored in the Hash Table

public String findKey(String key) {

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

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;

}

HashFunction2(int size) {

arraySize = size;

theArray = new String[size];

// Fill Array with -1 for each empty space

fillArrayWithNeg1();

}

public void fillArrayWithNeg1() {

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

}

public void displayTheStack() {

int increment = 0;

int numberOfRows = (arraySize / 10) + 1;

for (int m = 0; m < numberOfRows; 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 (n >= arraySize)
System.out.print("|      ");

else 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();

}

}

}
```

### 2 Responses to “Java Hash Table 2”

1. AK says:

Is possible another way of dealing with collisions is to make a 2D array ([x][y]) and instead of moving a value with a index up the array by [i++] you move the value using the same index [x] but inputting into an empty portion of the array in the [y] portion of the 2D array?

2. Phil says:

Am I missing something in the functions doubleHashFunc() and findKeyDblHashed()? The stepDistance variable is calculated differently. In doubleHashFunc() you have it calculated as

int stepDistance = 7 – (Integer.parseInt(key) % 7);

and in findKeyDblHashed() you have it calculated as:

int stepDistance = 5 – (Integer.parseInt(key) % 5);

Was this just an overlooked mistake or should I be understanding something that I don’t seem to be?

Thanks!

Phil