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