Comp 271 lab 1 - ArrayList<String>

Goals

• Introduction to ArrayList
• Introduction to for loops

Overview

• Create a big ArrayList HArray in which each element is an empty ArrayList<String>. The size of the ArrayList will be HMax. (It would make sense to have HArray be an array rather than an ArrayList, but Java won't let us create an array of ArrayList<String>.) Start with HMax around 100 (it may be best to choose a prime number around 100). Note the value of HMax in the file is 1000.
• Using .add(), create HMax-many actual ArrayList<String> entries in HArray (done for you!)
• Read in each word in the file words.text. The words are in alphabetical order, one per line; there are just under 3,000 of them. The existing code reads them all into a big ArrayList<String> called lines. You can then process the words from lines, or modify the code to process the words as they are read in.
• For each word w, calculate hc = w.hashCode()
• Then reduce hc to the range 0 to HMax-1. You can set hc = hc % HMax if hc is positive. What should you do if hc<0?
• Add word w to the list HArray.get(hc)! One way is this:
          L = HArray.get(hc);
          L.add(w)
  But you can also combine all this into a single statement.
• When you're done, print out each separate list HArray.get(i), for i from 0 to HMax-1. Use a for loop. Put each separate list on one line. What does this do to the word order?

Step 2: Now try increasing HMax to 500, or 1000. Do you see any empty lines in the output?

Step 3: The file words.text contains one word that is duplicated. Find it, by checking, before adding each word, whether that word is already present:

L = HArray.get(hc);
if (L.contains(w)) System.err.format(...);
L.add(w)

A starter BlueJ project, in .zip format, is available here. The starter file includes code to open the file. Each call to br.readLine() returns one word of the file.