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.
If you like videos like this, it helps to tell Google+ with a click here [googleplusone]
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.hashFunction2(elementsToAdd2, theFunc.theArray);
// theFunc.modThirty();
theFunc.increaseArraySize(60);
theFunc.displayTheStack();
theFunc.fillArrayWithNeg1();
theFunc.doubleHashFunc(elementsToAdd2, theFunc.theArray);
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(""))
stringList.add(theString);
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 +
// " Instead");
// 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 +
// " Instead");
// 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();
}
}
}
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?
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