Session J6: Arrays and Hash Tables

In this laboratory session, you will learn about two of Java's key built-in objects for managing groups of data: arrays and hash tables. The goals of this laboratory are to:

• motivate grouping of objects;
• consider design issues pertaining to size of groups and indexing of objects within groups;
• introduce two key grouping mechanisms in Java: arrays and hash tables;
• compare and contrast these mechanisms; and
• apply these mechanisms to a variety of problems.

Your instructor will tell you which of the proposed experiments you are to perform.

Prerequisite skills:

• Familiarity with objects in Java
• Java's looping mechanisms: while and for loops
• Java's conditional execution statements: if and switch

Required files:

• CountWords.java
• NewScoreCounter.java
• ScoreCounter.java
• SimpleInput.java
• SimpleOutput.java

Discussion

In this laboratory session, we will move on from dates into other issues. In particular, we will consider how one might count a variety of things.

Counting scores

The CoolStuff company has recently done a survey on the usefulness of their CoolStuff brand thingamabobs. Each participant in the survey gave the thingamabobs an integer score between one and three. The company would like you to write a program to read in all the scores and print out the count for each score.

How might we approach this problem? We could possibly create a Score object for each score. However, since scores are integers, it is likely to be sufficient to use an integer variable for each one. Then, we step through the input until we reach the end of input. For each number read, we increment the appropriate counter.

How do we know when we've reached the end of the input? We'll require that a value of 0 be entered to mark the end of input. How do we select which counter to update? A switch statement is an appropriate solution.

Putting it all together,

import SimpleInput;
import SimpleOutput;

/**
 * Count the number of scores assigned to something.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of September 1998
 */
public class ScoreCounter {
  /**
   * Read in a sequence of scores, count them, and print out
   * the results.
   */
  public static void main(String[] args) {
    SimpleInput in = new SimpleInput();
    SimpleOutput out = new SimpleOutput();
    int count1 = 0;  // Count of scores with value 1
    int count2 = 0;  // Count of scores with value 2
    int count3 = 0;  // Count of scores with value 3
    int score;       // The next score to be read.  

    // Prompt the user
    out.println("Enter the sequence of scores terminated by a 0.");
    
    // Read the first score.
    score = in.readInt();

    // Keep reading scores until we hit the "end of scores" mark (0).
    while (score != 0) {
      // Process the score
      switch (score) {
        case 1:
          count1 = count1 + 1;
          break;
        case 2:
          count2 = count2 + 1;
          break;
        case 3:
          count3 = count3 + 1;
          break;
        default:
          out.println("Invalid entry: " + score);
          break;
      } // switch
      // Read the next score
      score = in.readInt();
    } // while

    // Print out the results
    out.println(count1 + " people enetered a score of 1.");
    out.println(count2 + " people received a score of 2.");
    out.println(count3 + " people received a score of 3.");
  } // main(String[])
} // class ScoreCounter

In Experiment J6.1 you will use this class to count scores.

Arrays

While this solution works relatively well for a few counters, it does not work as well for more counters. For example, it would be tedious (and, therefore, error prone) to support one hundred different counters. At the same time, there seems to be a gap between the comment we write (e.g., ``update the counter corresponding to score'') and the corresponding code (e.g., a switch statement).

In fact, this program has places where it would be natural and appropriate to apply our newly formed skills with loops. In particular, when printing out the counts of the individual scores, we would like to be able to write

    for (score = 1; score < 3; ++score) {
       out.println(countscore + "  people entered " + score);
    }

Unfortunately, Java will treat countscore as a new variable and not as count1 (when score is 1), count2, and count3.

Fortunately, Java provides structures for creating groups of variables that can be indexed by numbers. These structures are called arrays and have a special syntax.

You declare an array of integers with

    int[] array-name;

For example, to declare an array of integers called scores, you would write

    int[] scores;

Once you have declared an array, you can refer to an element of the array by writing the array name, a left brace, an index into the array (the number of the element you want to use), and a right brace. For example, to add 5 to the third element of scores, I might write

    scores[3] += 5;

Because arrays are objects, you need to create them with new (or more precisely, a variant of new).

    name = new int[size];

This says to create a new array that will hold up to size integers. So if we wanted to have scores hold three integers, we would write

    scores = new int[3];

What are the valid indices for this array? You might assume they are 1, 2, and 3. However, Java starts numbering at 0. Hence, if scores holds three integers, then they are numbered 0, 1, and 2. Similarly, if scores holds five integers, then they are numbered 0, 1, 2, 3, and 4.

We can use arrays to simplify our counter program as follows

import SimpleInput;
import SimpleOutput;

/**
 * Count the number of scores assigned to something.
 *
 * @author Samuel A. Rebelsky
 * @version 1.2 of February 1998
 */
public class NewScoreCounter {
  /**
   * Read in a sequence of scores, count them, and print out
   * the results.
   */
  public static void main(String[] args) {
    // Prepare for input and output.
    SimpleInput in = new SimpleInput();
    SimpleOutput out = new SimpleOutput();
    // A count of scores with values 1,2,3.  A score with value i
    // is stored in counts[i-1].
    int[] counts = new int[3];
    // Keep track of the next score read.
    int score;

    // Prompt the user.
    out.println("Enter the sequence of scores terminated by a 0.");
    
    // Read the first score.
    score = in.readInt();

    // Keep reading scores until we hit the "end of scores" mark (0).
    while (score != 0) {
      // Process the score.
      if ((score < 0) || (score > 3)) {
        out.println("Invalid entry: " + score);
      } // if it's an invalid score
      else { // it's a valid score
        counts[score-1] += 1;
      } // a valid score
      // Read the next score.
      score = in.readInt();
    } // while

    // Print out the results.
    for (score = 1; score <= 3; ++score) {
      out.println(counts[score-1] + 
                  " people enetered a score of " + 
                  score + ".");
    } // for each score
  } // main(String[])
} // class NewScoreCounter

Note that arrays work particularly well with for loops. If we want to do something to every element of an array, then we can use a for loop to do so.

In Experiment J6.2 you will use NewScoreCounter to begin your investigation of arrays.

Some important details

As you may have noticed, arrays are objects in Java. That means that the variables that store arrays really store references to those arrays. Why is this important? For the same reason that it's important with object. Often, when you change one array, you end up changing another array (which is, in fact, a reference to the same array).

What can you do about this? Be careful and copy arrays when necessary.

Are there other problems you are likely to encounter? Because arrays are objects, they must be created with new. If you fail to do so, you are likely to receive serious error messages.

In addition, you should be careful to ensure that the indices you use for your arrays fall within the appropriate range. Your program will crash with an error message if you do not. (However, in a subsequent lab we will learn how to deal with such errors.)

A final note: It is often useful to determine the number of elements in an array. (Believe it or not, you may forget. More precisely, you may pass the array to another method that needs to determine how many elements are in the array.) You can determine the number of elments in an array, A, with A.length.

In Experiment J6.3 you will consider what happens when you assign the same array to different variables.

Counting words

Let us now turn our attention to a more complicated counting problem: counting the number of times each word appears in an essay. How might we approach this problem? This is a complicated enough problem that it is appropriate to use multiple objects. In particular, we will create a WordCounter object that provides two methods, count(String word) and getCount(String word). The first method increments the count for a particular word. The second method retrieves the count.

For example, the code

    SimpleOutput out = new SimpleOutput();
    WordCounter words = new WordCounter();
    words.count("Hello");
    words.count("Hello");
    words.count("Hi");
    words.count("Hello");
    out.println("Hello appears " + words.getCount("Hello") + " times.");
    out.println("Hi appears " + words.getCount("Hi") + " times.");
    out.println("Goodbye appears " + words.getCount("Goodbye") + " times.");

will print

Hello appears 3 times.
Hi appears 1 times.
Goodbye appears 0 times.

Given a WordCounter class, it is fairly easy to count the number of words in a text. Simply read each word and count it. Note that this does not give us any output (yet), but should give us correct counts if we can get to them.

import SimpleInput;
import SimpleOutput;
import WordCounter;

/**
 * Count the occurences of each of the words given on input.
 * Print out the number of appearences of "The" and "A".
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of September 1998
 */
public class CountWords {
  /**
   * Read all the words in standard input, count them, and print
   * out some interesting statistics.
   */
  public static void main(String[] args) {
    SimpleInput in = new SimpleInput();
    SimpleOutput out = new SimpleOutput();
    WordCounter words = new WordCounter();
    String word;
 
    // Count all the input words.  
    // Stop when you hit the last word.   
    word = in.readString();
    while (!word.equals("")) {
      words.count(word);
      word = in.readString();
    } //while

    // Print out selected results
    out.println("'The' appears " + words.getCount("The") + " times.");
    out.println("'A' appears " + words.getCount("A") + " times.");
  } // main
} // class CountWords

Now, how can we build WordCounter? One simple way is to work with two parallel arrays. One array, words, will

contain all the words being counted. The other array, counts, will have the corresponding counts. For example, if words[1] is hello, then counts[1] will count the number of times hello occurs.

Given those arrays, it is reasonably easy to count words already entered in the words array.

  for(i = 0; i < words.length; ++i) {
    if (words[i].equals(word)) {
      ++counts[i];
    } // if
  } // for

How do we declare an array of strings? The same way we declare an array of integers, except that we change the type slightly.

String[] words;

How do we add a new word to be counted? We find an empty element of words and set it to the word to be counted.

In Experiment J6.4 you will use arrays and CountWords to count words.

Hash tables

Obviously, this solution to the problem is not very elegant. In particular, the for loops may seem a little bit excessive. It would be much more convenient to have a structure, like an array, but indexed by words. Such structures are typically called dictionaries. In Java, java.util.Hashtable provides a particular implementation of dictionaries.

In particular, hash tables are structures that store groups of objects and index those objects by objects (usually strings).

How does that differ from arrays? Arrays are structures that store groups of objects and index those objects by integers.

The big difference appears to be in the indexing mechanism. However, other differences include the following:

• Hash tables use the syntax of standard objects, rather than the brackets that arrays use.
• Hash tables do not have a specified size, while arrays do.
• It is difficult (at least at this stage of your learning) to step through hash tables, while it is very easy to step through arrays.

What methods do hash tables provide? Given a hash table, ht, you can add an index/value pair to the hash table with ht.put(index,value). You can look up an element in the hash table with ht.get(index). You can determine whether there is an element corresponding to a particular index with containsKey(index).

For example, suppose that Professors Smith and Jones are writing a program to store class grades. They may create a hash table, grades, that associates a letter grade with each student. To print out the grade for John Doe, they might write

if (grades.containsKey("John Doe")) {
  out.println("John Doe's current grade is " +
              grades.get("John Doe"));
}
else {
  out.println("John Doe does not seem to be enrolled.");
}

Similarly, to set Jane Doe's grade to A minus, they might write

grades.set("Jane Doe", "A-");

In Experiment J6.5 you will use hash tables to do grading.

Experiments

Name: ________________
ID:_______________

Experiment J6.1: Counting scores

Required file:

• ScoreCounter.java

Step 1. Make a copy of ScoreCounter.java. Compile and execute it. Enter the sequence 1 1 2 22 3 2 1 0. (Here, and in the subequent steps, you should enter only one value per line.) Record the results.

Step 2. Execute ScoreCounter. Enter the sequence 0 1 1 1. Record the results. Explain the results.

Step 3. Execute ScoreCounter. Enter the sequence 1 2 3 01 012 03 1 01 0. Explain the results.

Step 4. Update ScoreCounter so that it indicates which score was most frequently entered (1, 2, or 3). Summarize your changes to the code. (If more than one score was entered the most number of times, you can print all top scores, or just one such score.)

After entering an answer, you may with to look at the notes on this problem.

Step 5. Update ScoreCounter so that it counts the number of invalid entries that were given. Summarize your changes to the code.

Step 6. Run your modified version on input 1 3 2 1 22 -5 012 01 0. Record and explain your output.

Step 7. Update ScoreCounter so that it counts scores between 1 and 5 (inclusive). You need no longer print out the most frequently entered score. Summarize your changes to the code.

Step 8. How might you update ScoreCounter to handle scores between 1 and 10? How long would it take you to make those changes? (Don't make the changes; just speculate on what they would be.)

Experiment J6.2: Introducing arrays

Required file:

• NewScoreCounter.java

Step 1. Make a copy of NewScoreCounter.java. Compile and execute it. Enter the sequence 1 1 2 22 3 2 1 0. (In this and the subsequent steps, enter one score per line.) Record the results.

Step 2. Update NewScoreCounter so that it reports on the score most frequently entered. Summarize your changes.

Step 3. Was it easier to update ScoreCounter or NewScoreCounter to report this count? Why?

Step 4. Update NewScoreCounter so that it reports on the number of invalid scores entered. Summarize your changes.

Step 5. Was it easier to update ScoreCounter or NewScoreCounter to report this count? Why?

Step 6. Update NewScoreCounter so that it counts scores between 1 and 5 inclusive. You should still print out the score that appears most frequently. Summarize your changes.

Step 7. Was it easier to update ScoreCounter or NewScoreCounter to handle the greater range of scores? Why?

Step 8. What changes would you need to make to support scores between 1 and 100? How long would it take you to make those changes?

Step 9. If there an overall change we can make to NewScoreCounter so that it's even easier to change the number of scores?

Step 10. What changes would you need to make to have NewScoreCounter handle scores between -5 and 5?

After recording your answer, you may wish to look at the notes on this problem.

Experiment J6.3: Arrays and references

Step 1. Write a class, ArrayTester, with a main method that includes the following two lines

    int[] A;
    A[1] = 2;

What happens when you try to compile that program?

Step 2. Update that program so that A is an array containing one integer. What happens when you try to compile the program? If you successfully compile the program, what happens when you try to execute the program?

Step 3. What do you expect to happen when you try to compile or execute a program that includes the following code?

    SimpleOutput out = new SimpleOutput();
    int[] stuff = new int[10];
    out.println(stuff[1]);

Step 4. Add the lines from step 3 to the main method of your ArrayTester class. What happens when you try to compile the program? If it successfully compiles, what happens when you try to execute the program?

Step 5. Add the following lines to your main method. Compile and execute the program. Record your results.

    int[] alpha = new int[10];
    int[] beta = alpha;
    int i;
    for (i = 0; i < 10; ++i) {
      alpha[i] = i;
      beta[i] = 2*i;
    } // for
    for (i = 0; i < 10; ++i) {
      out.print(alpha[i] + " ");
    } // for
    out.println();
    for (i = 0; i < 10; ++i) {
      out.print(beta[i] + " ");
    } // for
    out.println();

Experiment J6.4: Counting words

Required files:

• CountWords.java

Step 1. Make a copy of CountWords.java. Create a new class, WordCounter (stored in WordCounter.java), with two methods, void count(String word) and int getCount(String word). For now, the methods should be empty. That is, count need not count words, and getCount can return 0. Compile your classes. Execute CountWords. Type in a phrase of your choice.

Step 2. Add two fields, words and counts to WordCounter. Add a constructor that initializes those fields. You must initialize array fields in a constructor! You cannot simply assign to them. Recompile WordCounter and execute CountWords.

Step 3. Add the following lines to count

    int i;
    for(i = 0; i < words.length; ++i) {
      if (words[i].equals(word)) {
        ++counts[i];
      } // if
    } // for

Replace the body of getCount with

    int i;
    // Try all the words we know
    for(i = 0; i < words.length; ++i) {
      if (words[i].equals(word)) {
        return counts[i];
      } // if
    } // for
    // We don't know the word, assume the count is 0
    return 0;

Recompile WordCounter and execute CountWords. Type in ``The The The A The''. Record your results. Are they what you expected? Why or why not?

Step 4. Add the following lines to your constructor

    words[0] = "The";

Recompile WordCounter and execute CountWords. Type in ``The The The A The''. Record and explain your results.

Step 5. Update WordCounter to add new words when they appear. Recompile WordCounter and execute CountWords. Type in ``The The The A The''. Record and explain your results.

Step 6. Rerun CountWords using ``the The the a A A'' as input. Record your results. What do your results suggest?

Experiment J6.5: Hash tables

Step 1. Create a new class, GradeReporter, with a main method that includes the following lines.

    Hashtable grades = new Hashtable();
    SimpleOutput out = new SimpleOutput();
    grades.put("Fred", "B+");
    grades.put("Amy", "B");
    grades.put("Elaine", "A");
    out.println("Elaine's grade is " + grades.get("Elaine"));

Note that you will need to import java.util.Hashtable in order to use hash tables. Compile and execute your program. Record the output.

Step 2. Add the following lines to your program. Recompile and execute. Record the output.

    if (grades.containsKey("Bennett")) {
      out.println("Bennett's grade is " + grades.get("Bennett"));
    }
    else {
      out.println("Bennett has no recorded grade.");
    }

Step 3. Add the following lines to your program. Do not recompile the program. What do you think the new output will be?

    if (grades.containsKey("fred")) {
      out.println("Fred's grade is " + grades.get("fred"));
    }
    else {
      out.println("Fred has no recorded grade.");
    }

Step 4. Recompile and run your program. Record the output. Is that what you expected? Explain why the given output was produced.

Step 5. Add the following lines to your program. Do not recompile the program. What do you think the new output will be?

    out.println("Michelle's grade is " + grades.get("Michelle"));

Step 6. Recompile and run your program. Record the output. Is that what you expected? Explain why the given output was produced.

Step 7. Add the following lines to the end of your program. Do not recompile the program. What do you think the new output will be?

    grades.put("Lloyd", "C");
    out.println("Lloyd's grade is currently " + grades.get("Lloyd"));
    grades.put("Lloyd", "A");
    out.println("Lloyd's grade is currently " + grades.get("Lloyd"));
    grades.put("lloyd", "F");
    out.println("Lloyd's grade is currently " + grades.get("Lloyd"));

Step 8. Recompile and run your program. Record the output. Is that what you expected? Explain why the given output was produced.

Post-Laboratory Problems

Problem J6-A: Improving daysUntilStartOfMonth

In an earlier lab, we developed a daysUntilStartOfMonth method for the SimpleDate class that computed the number of days until the start of a month. Our solution was relatively elegant; rather than computing this value by hand, we computed the sum of the days in the previous months. Unfortunately, this comes at some computational cost. For example, if we need to compute the days until the start of November again and again and again, we are clearly doing extra work. We can do less work by precomputing an array that contains the number of days until the beginning of each month.

Update your SimpleDate class to do just that. That is, add an array to your class that, for each month, stores the number of days until the start of that month (perhaps for a normal year). Update the constructors for the class to initialize that array. Finally, update daysUntilStartOfMonth to use that array.

Problem J6-B: Counting grades

Often, when instructors look at trends in classes, they do not count individual grades, but rather ranges of grades. For example, one might count the number of 90s, 80s, 70s, and so on down the line. Write a Java program that reads in a sequence of grades terminated by a -1 and prints out the number of entries in each range.

Problem J6-C: Counting different scores

Update NewScoreCounter so that it counts scores between -5 and 5, inclusive.

Problem J6-D: Copying arrays

Create a class, ArrayUtils, that will contain a number of utility functions for dealing with arrays. Write the following method and add it to the class.

  /** 
   * Make a real copy of an integer array (as opposed to
   * just a copy of the reference).
   */
  public int[] copyIntegerArray(int[] copyme) {
    ...
  } // copyIntegerArray(int[])

Test your method with the following (which you will need to place within a main routine).

  SimpleOutput out = new SimpleOutput();
  ArrayUtils helper = new ArrayUtils();
  int[] A = new int[3];
  A[1] = 2;
  int[] B = helper.copyIntegerArray(A);
  B[1] = 1;
  if (B[1] == A[1]) {
    out.println("You failed to make a real copy!");
  }
  else {
    out.println("You successfully made a real copy.");
  }

Problem J6-E: Hashing words

Rewrite your WordCounter class to use a hash table. You will likely need to create a Counter class and store a Counter for each word in the hash table.

Problem J6-F: Game boards

Java permits you to create multidimensional arrays. For example, you can create a 4x4 matrix of integers with

int[][] fourbyfour = new int[4][4];

Using multidimensional arrays, create a GameBoard class that supports 8x8 game boards. You can assume that pieces on the board are represented by integers, and that a square with a value of 0 is empty. Include a print method that prints out the board and a set(int row, int col, int val) method that sets the value of a particular position on the board.

Notes

Experiment J6.1, Step 4. The simplest way (without loops) to print the most frequently occurring score is something like the following.

    if ((count1 >= count2) && (count1 >= count3)) {
      out.println("1 was among the most frequently occurring scores");
    }
    if ((count2 >= count1) && (count2 >= count3)) {
      out.println("2 was among the most frequently occurring scores");
    }
    if ((count3 >= count1) && (count3 >= count2)) {
      out.println("3 was among the most frequently occurring scores");
    }

One disadvantage of this is that it may do extra work. It also prints all of the most frequently occurring scores.

As an alternative, you might consider nesting tests, as in the following code.

    if (count1 > count2) {
      // We know that count2 cannot be one of the top scores, so
      // it must be 1 or 3.
      if (count1 > count3) {
        out.println("Score 1 occured most frequently.");
      }
      else {
        out.println("Score 3 occured most frequently.");
      }
    } // (count1 > count2)
    else {
      // We know that count1 cannot be one of the top scores, so
      // it must be 2 or 3.
      if (count2 > count3) {
        out.println("Score 2 occured most frequently.");
      }
      else {
        out.println("Score 3 occured most frequently.");
      }
    } // (count1 <= count2)

This code only prints one of the most frequently occurring scores. Can you tell which one in each case? It may also be more difficult to extend than the previous solution.

Experiment J6.2, Step 10. One significant problem with using such a range is that 0 can no longer serve as the input terminator.