Java Hash Tables 3

Java Hash Tables 3Welcome to the 3rd part of my Java Hash Tables Tutorial. If you missed the previous parts you should watch them Java Hash Table & Java Hash Tables 2.

I will review linked lists because I’ve received many requests on them. I’ll also show you how to hash strings, so that we can make a tool that can be used as a dictionary, spell checker, or something like Google Instant. I also show how to use lists in hash tables to demonstrate something called Separate Chaining.

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

Code From the Video

Java Hash Tables : HashFunction3.java

import java.util.Scanner;

public class HashFunction3 {

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

	public String[][] elementsToAdd = {
			{ "ace", "Very good" },
			{ "act", "Take action" },
			{ "add", "Join (something) to something else" },
			{ "age", "Grow old" },
			{ "ago", "Before the present" },
			{ "aid", "Help, assist, or support" },
			{ "aim", "Point or direct" },
			{ "air", "Invisible gaseous substance" },
			{ "all", "Used to refer to the whole quantity" },
			{ "amp",
					"Unit of measure for the strength of an electrical current" },
			{ "and", "Used to connect words" }, { "ant", "A small insect" },
			{ "any", "Used to refer to one or some of a thing" },
			{ "ape", "A large primate" },
			{ "apt", "Appropriate or suitable in the circumstances" },
			{ "arc", "A part of the circumference of a curve" },
			{ "are", "Unit of measure, equal to 100 square meters" },
			{ "ark", "The ship built by Noah" },
			{ "arm", "Two upper limbs of the human body" },
			{ "art", "Expression or application of human creative skill" },
			{ "ash", "Powdery residue left after the burning" },
			{ "ask", "Say something in order to obtain information" },
			{ "asp", "Small southern European viper" },
			{ "ass", "Hoofed mammal" },
			{ "ate", "To put (food) into the mouth and swallow it" },
			{ "atm", "Unit of pressure" },
			{ "awe", "A feeling of reverential respect" },
			{ "axe", "Edge tool with a heavy bladed head" },
			{ "aye", "An affirmative answer" } };

	public int stringHashFunction(String wordToHash) {

		int hashKeyValue = 0;

		for (int i = 0; i < wordToHash.length(); i++) {

			// 'a' has the character code of 97 so subtract
			// to make our letters start at 1

			int charCode = wordToHash.charAt(i) - 96;

			int hKVTemp = hashKeyValue;

			// Calculate the hash key using the 26 letters
			// plus blank

			hashKeyValue = (hashKeyValue * 27 + charCode) % arraySize;

			System.out.println("Hash Key Value " + hKVTemp
					+ " * 27 + Character Code " + charCode + " % arraySize "
					+ arraySize + " = " + hashKeyValue);

		}
		System.out.println();

		return hashKeyValue;

	}

	HashFunction3(int size) {

		arraySize = size;

		theArray = new WordList[size];

		// Fill the array with WordLists

		for (int i = 0; i < arraySize; i++) {

			theArray[i] = new WordList();

		}

		addTheArray(elementsToAdd);

	}

	public void insert(Word newWord) {

		String wordToHash = newWord.theWord;

		// Calculate the hashkey for the Word

		int hashKey = stringHashFunction(wordToHash);

		// Add the new word to the array and set
		// the key for the word

		theArray[hashKey].insert(newWord, hashKey);

	}

	public Word find(String wordToFind) {

		// Calculate the hash key for the word

		int hashKey = stringHashFunction(wordToFind);

		// NEW

		Word theWord = theArray[hashKey].find(hashKey, wordToFind);

		return theWord;

	}

	public void addTheArray(String[][] elementsToAdd) {

		for (int i = 0; i < elementsToAdd.length; i++) {

			String word = elementsToAdd[i][0];
			String definition = elementsToAdd[i][1];

			// Create the Word with the word name and
			// definition

			Word newWord = new Word(word, definition);

			// Add the Word to theArray

			insert(newWord);

		}

	}

	public void displayTheArray() {

		for (int i = 0; i < arraySize; i++) {

			System.out.println("theArray Index " + i);

			theArray[i].displayWordList();

		}

	}

}

class Word {

	public String theWord;
	public String definition;

	public int key;

	// Reference to next Word made in the WordList

	public Word next;

	public Word(String theWord, String definition) {

		this.theWord = theWord;
		this.definition = definition;

	}

	public String toString() {

		return theWord + " : " + definition;

	}

}

class WordList {

	// Reference to first Link in list
	// The last Link added to the LinkedList

	public Word firstWord = null;

	public void insert(Word newWord, int hashKey) {

		Word previous = null;
		Word current = firstWord;

		newWord.key = hashKey;

		while (current != null && newWord.key > current.key) {

			previous = current;
			current = current.next;

		}

		if (previous == null)
			firstWord = newWord;

		else
			previous.next = newWord;

		newWord.next = current;

	}

	public void displayWordList() {

		Word current = firstWord;

		while (current != null) {

			System.out.println(current);
			current = current.next;

		}

	}

	public Word find(int hashKey, String wordToFind) {

		Word current = firstWord;

		// Search for key, but stop searching if
		// the hashKey < what we are searching for
		// Because the list is sorted this allows
		// us to avoid searching the whole list

		while (current != null && current.key <= hashKey) {

			// NEW

			if (current.theWord.equals(wordToFind))
				return current;

			current = current.next;

		}

		return null;

	}

	public static void main(String[] args) {

		Scanner input = new Scanner(System.in);

		// Make a 11 item array that will hold words
		// and definitions

		HashFunction3 wordHashTable = new HashFunction3(11);

		String wordLookUp = "a";

		// Keep retrieve requests until x is entered

		while (!wordLookUp.equalsIgnoreCase("x")) {

			System.out.println(": ");

			wordLookUp = input.nextLine();

			// Look for the word requested and print
			// it out to screen

			System.out.println(wordHashTable.find(wordLookUp));

		}

		// Display every item in the array with
		// the index they are associated with

		wordHashTable.displayTheArray();

	}
}

One Response to “Java Hash Tables 3”

  1. Ronnie says:

    If I wanted to do a two letter word dictionary. How would I implement that. Thanks

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Google+