Java Hash Table

Java Hash TableWelcome to my Java Hash Table tutorial. A Hash Table is a data structure offers fast insertion and searching capabilities. The negative is that they are limited in size because they are based on arrays. They are also hard to order.

People get confused about them because of the Hash Function. A hash function is used to generate a unique key for every item in the array. Since every item is entered using a calculation, this allows you to reverse the calculation to immediately find the proper index. This way you can find items without the need to search through the whole array.

If you like videos like this, it helps to tell Google+ with a click

Code From the Video

Java Hash Table HashFunction.java

import java.util.Arrays;

// If we think of a Hash Table as an array
// then a hash function is used to generate
// a unique key for every item in the array.
// The position the item goes in is known
// as the slot. Hashing doesn't work very well
// in situations in which duplicate data
// is stored. Also it isn't good for searching
// for anything except a specific key. 
// However a Hash Table is a data structure that 
// offers fast insertion and searching capabilities.

public class HashFunction {

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

	public static void main(String[] args) {

		HashFunction theFunc = new HashFunction(30);

		// 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;

		}

	}

	// Now let's say we have to hold values between 0 & 999
	// but we never plan to have more than 15 values in all.
	// It wouldn't make sense to make a 1000 item array, so
	// what can we do?

	// One way to fit these numbers into a 30 item array is
	// to use the mod function. All you do is take the modulus
	// of the value versus the array size

	// The goal is to make the array big enough to avoid
	// collisions, but not so big that we waste memory

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

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

		}

	}

}

20 Responses to “Java Hash Table”

  1. VH says:

    Hi Derek,

    Great tutorial.

    The implementation given above, is it linear probing (open addressing) collision avoidance strategy?

    Thanks.

  2. Anonymous says:

    a dumb question:

    Why do u need to do the following line?

    arrayIndex%=arraySize;

    is it coz if u keep on incrementing the value might go above 30(arraysize)

  3. Sri says:

    Hi Derek, excellent tutorial.

    in the findKey method, shouldn’t you be using equals method instead of == check ( int this line
    if (theArray[arrayIndexHash] == key)

  4. Anonymous says:

    great job

  5. Edward says:

    I am studying for a google interview and I came across your tutorial, really awesome!

    Just a quick note, doesn’t the system go into infinite loop because at line 135:
    135 arrayIndexHash %= arraySize;

    you return to the start of the hash and you keep going until you “find” it. If I enter 411, the system go into finite loop mode.

    Otherwise, really awesome tutorial and nicely commented code Derek, thanks!

    • Derek Banas says:

      Yes you are correct. I was supposing that the key would be in there and I shouldn’t have done that. Sorry about that. That is what happens sometimes when i write code out of my head.

      Good luck on your interview 🙂

  6. anoper says:

    Hi, I am not sure, but don’t you have bug in findKey?

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

    – in case, that the value is presented in the array and the array is full, the loop will be infinite. Other case is that I miss something.

    Anyway, great job with algorithms ;D,

    thanks a lot.

  7. Channabasappa says:

    Hi Derek,

    The tutorials are really great and i would expect from you that you come up with more and more tutorials like this on complete Java, J2EE, Frameworks like Spring Hibernate Ant Maven etc. Also if you could creat DVDs of all the topics (and many more), i mentioned above that would be really great and we can purchase them. As i would like to acquire indepth knowledge on Java and related stuffs.

    Thanks
    Channa

    • Derek Banas says:

      Hi Channa,

      I will definitely cover all of the J2EE topics you mentioned. I just want to get the Android tutorial and C tutorial done first. Thank you for the requests. I’ll always provide my videos for free. I don’t plan on ever selling them.

  8. Essey says:

    Thank you, Derek!
    I was wondering how to get out of the while loop, when the value is not found.

  9. Naga says:

    Hi Derek,

    point to point explanation. excellent tutorials. expecting more Java J2ee framework tutorials from you. Thank you very much.

  10. Balaji says:

    115 int arrayIndexHash = Integer.parseInt(key) % 29;

    in the above statement can we choose any integer in the place of 29 which is less than 30? why have we chosen 29 instead of 30?

Leave a Reply

Your email address will not be published.

Google+