public class OpenLinear1
1: import java.util.Scanner;
3: /**
4: * A program to demonstrate a simple hash table.
5: *
6: * @author Mark Young (A00000000)
7: */
8: public class OpenLinear1 {
10: public static int arraySize = 23;
12: /**
13: * @param args the command line arguments
14: */
15: public static void main(String[] args) {
16: printIntroduction();
17: pause();
19: String[] mine = getWordList();
20: printWordList(mine);
21: pause();
23: // create and fill the hash table
24: String[] openHashTable = new String[arraySize];
25: for (String me : mine) {
26: addHashEntry(me, openHashTable);
27: }
28: System.out.println();
29: pause();
31: // print the hash table
32: printHashTable(openHashTable);
33: pause();
35: // ask user to add words
36: for (int i = mine.length; i < openHashTable.length; ++i) {
37: System.out.print("Enter another word/phrase: ");
38: String word = KBD.nextLine();
39: System.out.println();
40: addHashEntry(word, openHashTable);
41: System.out.println();
42: printHashTable(openHashTable);
43: pause();
44: }
45: }
47: /**
48: * Print out a hash table, one line per entry, with empty cells included.
49: *
50: * @param openHashTable the table to print.
51: */
52: private static void printHashTable(String[] openHashTable) {
53: System.out.printf("%4s %-15s%n", "i", "hashTable[i]");
54: System.out.printf("%4s %-15s%n", "-", "------------");
55: for (int i = 0; i < arraySize; ++i) {
56: System.out.printf("%4d %s%n",
57: i, quoteValue(openHashTable[i]));
58: }
59: }
61: /**
62: * Return the word in single quotes, or the empty string if there is no
63: * word.
64: *
65: * @param word the word to quote
66: * @return the word in single quotes, or "" if word == null
67: */
68: private static String quoteValue(String word) {
69: if (word == null) {
70: return "";
71: } else {
72: return "'" + word + "'";
73: }
74: }
76: /**
77: * Add the given word to the given hash table. Uses linear probe collision
78: * handling. This is VERY BAD. Try looking up quadratic probe and rehashing.
79: * Those are better alternatives.
80: *
81: * @param me the word to add.
82: * @param openHashTable the table to add the word to.
83: */
84: private static void addHashEntry(String me, String[] openHashTable) {
85: System.out.println("Adding '" + me + "'");
86: int location = Math.abs(me.hashCode() % arraySize);
87: while (openHashTable[location] != null) {
88: System.out.println("...location " + location + " is in use...");
89: if (openHashTable[location].equals(me)) {
90: System.out.println("Duplicate entry not added");
91: return;
92: }
94: // linear probe -- BAD open addressing rule!
95: ++location;
96: location %= arraySize;
97: }
98: openHashTable[location] = me;
99: System.out.println("...'" + me + "' added at location " + location);
100: }
102: /**
103: * Print a list of words together with their hash codes.
104: *
105: * @param mine the list to print.
106: */
107: private static void printWordList(String[] mine) {
108: System.out.printf("%15s %15s%n", "String", "Hash Code");
109: System.out.printf("%15s %15s%n", "------", "---------");
110: for (String me : mine) {
111: System.out.printf("%15s %,15d%n", me, me.hashCode());
112: }
113: }
115: /**
116: * Create a list of words.
117: *
118: * @return a list of perfectly cromulent words and phrases.
119: */
120: private static String[] getWordList() {
121: // make the list of words to add to the hash table
122: String[] mine = new String[]{
123: "me", "myself", "I", "mine", "Mark", "Young", "ego", "swollen head"
124: };
125: return mine;
126: }
128: /**
129: * Introduce this program.
130: */
131: private static void printIntroduction() {
132: System.out.println("This program creates a hash table. "
133: + "It uses a VERY BAD open-addressing rule.");
134: }
136: /**
137: * The one and only Scanner on System.in.
138: */
139: private static final Scanner KBD = new Scanner(System.in);
141: /**
142: * Wait for the user to press the enter key. Includes a prompt and before-
143: * after blank lines.
144: */
145: private static void pause() {
146: System.out.println();
147: System.out.print("Press enter...");
148: KBD.nextLine();
149: System.out.println();
150: }
152: }