Java Reference
In-Depth Information
word
freq
next
for
2
7
1
2
3
4
5
6
7
the
4
-1
man
1
3
boy
1
1
girl
2
4
Figure 10-4.
Words linked in alphabetical order ( first = 6)
Thus, the first word is
boy
, which points to
for
(
1
), which points to
girl
(
7
), which points to
man
(
4
), which points
to
the
(
3
), which does not point to anything (
-1
). The words are linked in alphabetical order:
boy for girl man the
.
Note that the linking works no matter where the hash algorithm places a word.
The hash algorithm first places the word. Then, regardless of where it is placed, that location is linked to maintain
the words in order. For example, suppose the new word
kid
hashes to location
2
. Then the link of
kid
will be set to
4
(to point to
man
), and the link of
girl
will be set to
2
(to point to
kid
).
We print the alphabetical listing by traversing the linked list. Program P10.3 shows all the details.
Program P10.3
import java.io.*;
import java.util.*;
public class WordFrequencyHash {
static Scanner in;
static PrintWriter out;
final static int N = 13; //table size
final static int MaxWords = 10;
final static String Empty = "";
public static void main(String[] args) throws IOException {
in = new Scanner(new FileReader("wordFreq.in"));
out = new PrintWriter(new FileWriter("wordFreq.out"));
WordInfo[] wordTable = new WordInfo[N+1];
for (int h = 1; h <= N; h++) wordTable[h] = new WordInfo();
int first = -1; //points to first word in alphabetical order
int numWords = 0;
in.useDelimiter("[^a-zA-Z]+");
while (in.hasNext()) {
String word = in.next().toLowerCase();
int loc = search(wordTable, word);
if (loc > 0) wordTable[loc].freq++;
else //this is a new word
Search WWH ::
Custom Search