Java Hash Tables 3
Welcome 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 [googleplusone]
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();
}
}
If I wanted to do a two letter word dictionary. How would I implement that. Thanks