public class ChainedHashTable
1: import java.util.Scanner;
2: import java.util.List;
3: import java.util.LinkedList;
4: import java.util.ArrayList;
6: /**
7: * A program to demonstrate a simple hash table.
8: *
9: * @author Mark Young (A00000000)
10: */
11: public class ChainedHashTable {
13: public static int arraySize = 23;
15: /**
16: * @param args the command line arguments
17: */
18: public static void main(String[] args) {
19: printIntroduction();
20: pause();
22: String[] mine = getWordList();
23: printWordList(mine);
24: pause();
26: // create and fill the hash table
27: List<List<String>> hashTable = makeHashTable(arraySize);
28: for (String me : mine) {
29: addHashEntry(me, hashTable);
30: }
31: System.out.println();
32: pause();
34: // print the hash table
35: printHashTable(hashTable);
36: pause();
38: // ask user to add words
39: for (int i = mine.length; i < hashTable.size(); ++i) {
40: System.out.print("Enter another word/phrase: ");
41: String word = KBD.nextLine();
42: System.out.println();
43: addHashEntry(word, hashTable);
44: System.out.println();
45: printHashTable(hashTable);
46: pause();
47: }
48: }
50: /**
51: * Print out a hash table, one line per entry, with empty cells included.
52: *
53: * @param hashTable the table to print.
54: */
55: private static void printHashTable(List<List<String>> hashTable) {
56: System.out.printf("%4s %-15s%n", "i", "hashTable[i]");
57: System.out.printf("%4s %-15s%n", "-", "------------");
58: for (int i = 0; i < arraySize; ++i) {
59: System.out.printf("%4d %s%n",
60: i, hashTable.get(i).toString());
61: }
62: }
64: /**
65: * Add the given word to the given hash table. Uses chains to handle
66: * collioions. Does not check for a loading factor.
67: *
68: * @param me the word to add.
69: * @param hashTable the table to add the word to.
70: */
71: private static void addHashEntry(String me, List<List<String>> hashTable) {
72: System.out.println("Adding '" + me + "'");
73: int location = Math.abs(me.hashCode() % arraySize);
74: List<String> contents = hashTable.get(location);
75: if (!contents.contains(me)) {
76: hashTable.get(location).add(me);
77: System.out.println("...'" + me + "' added at location " + location);
78: } else {
79: System.out.println("...duplicate entry...");
80: }
81: }
83: /**
84: * Print a list of words together with their hash codes.
85: *
86: * @param mine the list to print.
87: */
88: private static void printWordList(String[] mine) {
89: System.out.printf("%15s %15s%n", "String", "Hash Code");
90: System.out.printf("%15s %15s%n", "------", "---------");
91: for (String me : mine) {
92: System.out.printf("%15s %,15d%n", me, me.hashCode());
93: }
94: }
96: /**
97: * Create a list of words.
98: *
99: * @return a list of perfectly cromulent words and phrases.
100: */
101: private static String[] getWordList() {
102: // make the list of words to add to the hash table
103: String[] mine = new String[]{
104: "me", "myself", "I", "mine", "Mark", "Young", "ego", "swollen head"
105: };
106: return mine;
107: }
109: /**
110: * Introduce this program.
111: */
112: private static void printIntroduction() {
113: System.out.println("This program creates a hash table. "
114: + "It uses chained list entries.");
115: }
117: /**
118: * Create an array-based List of the given size. Each element of the
119: * array-based List is a LinkedList.
120: *
121: * @param size the number of elements in the array-based List
122: * @return a List of Lists of String suitable for a hash table
123: */
124: private static List<List<String>> makeHashTable(int size) {
125: List<List<String>> result = new ArrayList<List<String>>(arraySize);
126: for (int i = 0; i < size; ++i) {
127: result.add(new LinkedList<>());
128: }
129: return result;
130: }
132: /**
133: * The one and only Scanner on System.in.
134: */
135: private static final Scanner KBD = new Scanner(System.in);
137: /**
138: * Wait for the user to press the enter key. Includes a prompt and before-
139: * after blank lines.
140: */
141: private static void pause() {
142: System.out.println();
143: System.out.print("Press enter...");
144: KBD.nextLine();
145: System.out.println();
146: }
148: }