Storing Objects in Data Structures - Moving into Advanced Topics - Sams Teach Yourself Java in 24 Hours, 7th Edition (2014)

Sams Teach Yourself Java in 24 Hours, 7th Edition (2014)

Part V: Moving into Advanced Topics

Hour 17. Storing Objects in Data Structures

THIS HOUR’S TO-DO LIST:

Image Create an array list.

Image Add and remove items from the list.

Image Use generics to improve list reliability.

Image Search a list for an object.

Image Loop through the contents of a list.

Image Create a hash map of keys and values.

Image Add and remove items from the map.

Image Retrieve a map entry’s key.

Image Retrieve a map entry’s value.

Image Loop through the keys and values of a map.

Programmers are hoarders.

In computer programming, you spend a lot of time collecting information and looking for a place to store it. The information can come in the form of a primitive data type, such as a float or as an object of a particular class. It can be read from disk, retrieved from an Internet server, entered by a user, or gathered through other means.

After you have the information, you must decide where to put it while a program is running in the Java Virtual Machine. Several items that are related to each other by data type or class can be stored in an array.

This is sufficient for many purposes, but as your programs grow in sophistication, your needs as a hoarder will increase.

During this hour you learn about some classes in Java that are designed for information hoarders: array lists and hash maps.

Array Lists

In Hour 9, “Storing Information with Arrays,” you were introduced to arrays, an extremely handy way to work with groups of variables and objects in programs. Arrays are so essential to Java that they are a built-in data type like integers and characters. An array packages together elements of the same data type or class.

As useful as arrays can be, they are limited by the fact that the size of an array does not change. After an array is created to hold 90 elements, it can’t be altered to hold more or fewer. The size is fixed. (The fancy way of saying this is to call the array “immutable.”)

There’s a class in the java.util package that does everything an array can do without that limitation: ArrayList.

An array list is a data structure that holds objects of the same class or a common superclass. The list can grow or shrink as needed as a program is running.

The simplest way to create an array list is by calling its constructor with no arguments:

ArrayList servants = new ArrayList();

Array lists can be created by specifying an initial capacity, which provides some guidance on how many elements the list might hold. The capacity is set as an integer argument to the constructor:

ArrayList servants = new ArrayList(30);

Although this looks like creating an array and determining its exact size, the capacity is just a hint. If the capacity is exceeded, the array list will be adjusted accordingly and continue to function properly. (The better you estimate the capacity, the more efficient the program will be.)

The list holds objects that belong to the same class or share a superclass.

When you create an array list, you know the class or superclass the list is intended to hold. This can be specified in the constructor within < and > signs, a feature of the language called generics. Here’s an improvement on the constructor for a list that holds String objects:

ArrayList<String> servants = new ArrayList<String>();


Note

If you have some experience with earlier versions of Java, you might have heard of vectors and wonder why they’re so much like array lists. They are another data structure that functions almost identically to the ArrayList class, and they are in the same package asjava.util.Vector. The major difference between the two is that vectors require synchronization, so any class that makes use of vectors will run more slowly. For this reason array lists are generally the preferred choice.


To add an object, call the array list’s add(Object) method with that object as the argument. Here are statements that add five strings:

servants.add("Bates");
servants.add("Anna");
servants.add("Thomas");
servants.add("Mrs. O'Brien");
servants.add("Daisy");

Each element is added to the end of the list, so the first string in servants is “Bates” and the last is “Daisy”.

There’s a corresponding remove(Object) method that takes the object out of the list:

servants.remove("Mrs. O'Brien");

The size of an array list is the number of elements it currently holds. Retrieve this information by calling the list’s size() method, which returns an integer:

int servantCount = servants.size();

When you have used generics to specify the class the list contains, it’s simple to use a for loop to iterate through each element of the list:

for (String servant : servants) {
System.out.println(servant);
}

The first argument to for is a variable where an element should be stored. The second is the array list. Other data structures can employ the same loop.

The add(Object) method stores the object at the end of the list. Objects also can be added to a list by specifying the position within the list where the object should be stored. This requires the add(int, Object) method, which takes the position as the first argument:

ArrayList<String> aristocrats = new ArrayList<String>();
aristocrats.add(0, "Lord Robert");
aristocrats.add(1, "Lady Mary");
aristocrats.add(2, "Lady Edith");
aristocrats.add(3, "Lady Sybil");
aristocrats.add(0, "Lady Grantham");

The last statement in the preceding example adds “Lady Grantham” at the top of the list instead of the bottom, putting her above “Lord Robert” and the others.

The position specified as the first argument must be no greater than the size() of the list. If “Lord Robert” had been added with 1 as the position instead of 0, the program would fail with an IndexOutOfBoundsException.

An element can be removed from a list by specifying its position as the argument to remove(int):

aristocrats.remove(4);

The element at a specified position in a list can be retrieved by calling get(int) with that position. Here’s a for loop that pulls each string out of a list and displays it:

for (int i = 0; i < aristocrats.size(); i++) {
String aristocrat = aristocrats.get(i);
System.out.println(aristocrat);
}

Often it is necessary to find out whether an array list contains a specific object. This can be determined by calling the list’s indexOf(Object) method with that object as the argument. The method returns the position of the object or –1 if it cannot be found in the list:

int hasCarson = servants.indexOf("Carson");

The hour’s first project employs these techniques on a simple game in which shots are fired at (x,y) points on a 10-by-10 grid. Some points contain a target and others do not.

The targets are represented by the Point class in the java.awt package. A point is created by calling the Point(int, int) constructor with the x and y coordinates as the two arguments.

This statement creates a point at (5,9):

Point p1 = new Point(5,9);

Here’s a 10-by-10 grid with that point marked by an X and empty spaces marked by a “.” period character:

Output

1 2 3 4 5 6 7 8 9
1 . . . . . . . . .
2 . . . . . . . . X
3 . . . . . . . . .
4 . . . . . . . . .
5 . . . . . . . . .
6 . . . . . . . . .
7 . . . . . . . . .
8 . . . . . . . . .
9 . . . . . . . . .

Columns go from left to right and represent the x coordinate. Rows extend from top to bottom and mark the y coordinate.

Before this project, you saw how array lists could hold strings. They can hold Point or any other class of objects. This statement creates a list of points:

ArrayList<Point> targets = new ArrayList<Point>();

The Java compiler won’t allow any class other than Point or its subclasses to be added to the array list.

In NetBeans or another programming tool, create a Java file named Battlepoint and designate com.java24hours as its package. Enter the text of Listing 17.1 into the file.

LISTING 17.1 The Full Text of Battlepoint.java


1: package com.java24hours;
2:
3: import java.awt.*;
4: import java.util.*;
5:
6: public class Battlepoint {
7: ArrayList<Point> targets = new ArrayList<Point>();
8:
9: public Battlepoint() {
10: // create targets to shoot at
11: createTargets();
12: // display the game map
13: showMap();
14: // shoot at three points
15: shoot(7,4);
16: shoot(3,3);
17: shoot(9,2);
18: // display the map again
19: showMap();
20: }
21:
22: private void showMap() {
23: System.out.println("\n 1 2 3 4 5 6 7 8 9");
24: for (int column = 1; column < 10; column++) {
25: for (int row = 1; row < 10; row++) {
26: if (row == 1) {
27: System.out.print(column + " ");
28: }
29: System.out.print(" ");
30: Point cell = new Point(row, column);
31: if (targets.indexOf(cell) > -1) {
32: // a target is at this position
33: System.out.print("X");
34: } else {
35: // no target is here
36: System.out.print(".");
37: }
38: System.out.print(" ");
39: }
40: System.out.println();
41: }
42: System.out.println();
43: }
44:
45: private void createTargets() {
46: Point p1 = new Point(5,9);
47: targets.add(p1);
48: Point p2 = new Point(4,5);
49: targets.add(p2);
50: Point p3 = new Point(9,2);
51: targets.add(p3);
52: }
53:
54: private void shoot(int x, int y) {
55: Point shot = new Point(x,y);
56: System.out.print("Firing at (" + x + "," + y + ") ... ");
57: if (targets.indexOf(shot) > -1) {
58: System.out.println("you sank my battlepoint!");
59: // delete the destroyed target
60: targets.remove(shot);
61: } else {
62: System.out.println("miss.");
63: }
64: }
65:
66: public static void main(String[] arguments) {
67: new Battlepoint();
68: }
69: }


Comments in the Battlepoint application describe each part of the constructor and important parts of the conditional logic in the program.

The application creates targets as three Point objects and adds them to an array (Lines 45–52). A map is displayed showing these targets (Lines 22–43).

Next, shots are taken at three points by calling the shoot(int, int) method (Lines 54–64). Each time, the application reports back whether the shot hit one of the targets. If it does, the target is removed from the array list.

Finally, the map is displayed again and the application terminates.

The output is shown in Figure 17.1.

Image

FIGURE 17.1 Putting Point objects in an array list and shooting at them.

The three targets are shown in the top map of Figure 17.1. One target is removed after it is hit. The bottom map in the output reflects this change.

When a target is hit by a shot, it is removed from the targets array list by calling the remove(Object) method with the shot’s point as the argument.


Caution

In the shoot() method of the Battlepoint application, the Point object that will be removed from the array list is the one that represents the shot. This has the same (x,y) coordinates as the target that was hit.


Hash Maps

The ability to use one piece of information to access another is common in programming. An array list is the simplest example of this among the data structures, where an index number can be used to retrieve one object from the list. Here’s an example that pulls the first string from thearistocrats array list:

String first = aristocrats.get(0);

Arrays also use index numbers to retrieve each item in the array.

Hash maps are a data structure in Java that use an object to retrieve another object. The first object is the key and the second is the value. They are implemented as the HashMap class in the java.util package.

The name refers to how keys are mapped to values. An example of this kind of structured data is a phone book. A person’s name (a string) can be used to retrieve the person’s phone number.

A hash map can be created by calling its constructor with no arguments:

HashMap phonebook = new HashMap();


Note

Just as array lists have another class called Vector that does the same thing in a more resource-intensive way, hash maps have Hashtable. Hash tables are synchronized and hash maps are not, so any class that makes use of hash tables takes longer to run. Hash maps generally are preferred.


Two things can be specified in a new hash map that control how efficient it is: the initial capacity and the load factor. These are set with two arguments, in that order:

HashMap phonebook = new HashMap(30, 0.7F);

The capacity is the number of buckets in which hash map values can be stored. The load factor is the number of buckets that can be used before the capacity automatically is increased. The value is a floating-point number from 0 (empty) to 1.0 (full), so a 0.7 means that when the buckets are 70 percent full, the capacity increases. The defaults are a capacity of 16 and load factor of .75, which often are sufficient.

Generics should be used to indicate the classes of the keys and values. They are placed within < and > characters and the class names are separated by a comma, as in this example:

HashMap<String, Long> phonebook = new HashMap<>();


Note

These statements are putting Long objects in the hash map using long values. This would have been an error in early versions of Java, because a primitive data type such as long couldn’t be used where an object was required.

But it’s no longer an error because of autoboxing and unboxing, a feature of Java that automatically converts between primitive types and their equivalent object classes. When the Java compiler sees a long like 8002888372, it converts it to a Long object for that value.


This creates a hash map called phonebook with keys that are strings and values that are Long objects. The second set of < and > characters is empty, which assumes the same classes as those in the previous < and > on the statement.

Objects are stored in a hash map by calling its put(Object, Object) method with two arguments: the key and value:

phonebook.put("Butterball Turkey Line", 8002888372);

This stores an item in the map with the key “Butterball Turkey Line” and a Long object for the value 8002888372, the phone number of that service.

An object can be retrieved from the map with its key by calling get(Object) with the key as the only argument:

int number = phonebook.get("Butterball Turkey Line");

The get() method returns null if there’s no value matching that key. This would cause a problem with the preceding example, because null is not a suitable long value.

Another way to handle that potential problem is to call getOrDefault(Object, Object). If the key specified as the first argument is not found, the second argument is returned by default, as in this statement:

int number = phonebook.getOrDefault("Betty Crocker", -1);

If a number matching the key “Betty Crocker” is found in the map, that number is returned. Otherwise, –1 is returned.

There are two methods that indicate whether a key or value is present in the map: containsKey(Object) and containsValue(Object). These return a Boolean of either true or false.

Hash maps, like array lists, have a size() method that indicates the number of items in the data structure.

Looping through a map can be performed by using an entry set, a collection of all the entries in the map. The entrySet() method returns these entries as a Set object (using the Set interface in java.util).

Each item in the set is represented by Map.Entry, an inner class in the Map class of java.util. When you have an Entry object, you can call its getKey() method to retrieve the key and getValue() to retrieve the value.

The following for loop uses entry sets and entries to access all keys and values in a phonebook hash map:

for (Map.Entry<String, Font> entry : map.entrySet()) {
String key = entry.getKey();
Font value = entry.getValue();
// ...
}

The FontMapper project puts all of this together, using a hash map to manage a collection of fonts.

The Font class in the java.awt package is used to create fonts and use them to display text in a graphical user interface. A font includes the name of the font, the point size, and whether it is plain, bold, or italic in style.

Hash maps can contain any class of objects. In NetBeans create a Java file in the com.java24hours package and give it the name FontMapper. Enter Listing 17.2 into the file and save it.

LISTING 17.2 The Full Text of FontMapper.java


1: package com.java24hours;
2:
3: import java.awt.*;
4: import java.util.*;
5:
6: public class FontMapper {
7: public FontMapper() {
8: Font courier = new Font("Courier New", Font.PLAIN, 6);
9: Font times = new Font("Times New Roman", Font.BOLD, 12);
10: Font verdana = new Font("Verdana", Font.ITALIC, 25);
11: HashMap<String, Font> fonts = new HashMap<>();
12: fonts.put("smallprint", courier);
13: fonts.put("body", times);
14: fonts.put("headline", verdana);
15: for (Map.Entry<String, Font> entry : fonts.entrySet()) {
16: String key = entry.getKey();
17: Font value = entry.getValue();
18: System.out.println(key + ": " + value.getSize() + "-pt "
19: + value.getFontName());
20: }
21: }
22:
23: public static void main(String[] arguments) {
24: new FontMapper();
25: }
26: }


The FontMapper application creates three Font objects in Lines 8–10 and then adds them to a hash map called fonts in Lines 12–14. They’re stored in the map with a string key that describes the font’s purpose: “smallprint”, “body”, and “headline”.

A for loop in Lines 15–20 loops through the hash map using an entry set and each individual entry in the set.

The output of the application is displayed in Figure 17.2.

Image

FIGURE 17.2 Storing Font objects in a hash map.

Summary

Array lists and hash maps are two of the more useful data structures in the java.util package. The array list class expands on the functionality of arrays, making it possible to overcome the fixed-size limitation of that data type. Hash maps enable any kind of object to be used as the key to retrieve a value.

There also are bit sets (the BitSet class), which hold 0- and 1-bit values; stacks (Stack), which are a last-in, first-out collection of data similar to array lists; and properties (Properties), a specialized hash map that holds configuration properties for a program in a file or another permanent storage place.

Workshop

Q&A

Q. What does it mean when a class is synchronized?

A. Synchronization is how the Java Virtual Machine ensures that an object’s instance variables and methods are accessed in a consistent and accurate manner by other users of the object.

This concept will make more sense when you learn about threads in Hour 19, “Creating a Threaded Program.” Java programs can be designed to do more than one task simultaneously. Each task is put in its own thread.

When multiple threads are accessing the same object, it’s vital that the object acts the same in each thread. So when the method of a class requires synchronization, as vectors and hash tables do, the Java Virtual Machine has to work harder and can encounter errors that may cause a thread to stop running.

This is why array lists and hash maps replicate the functionality of vectors and hash tables. Data structures were needed that don’t require synchronization and run much more efficiently as a consequence.

Q. Have the Washington Generals ever beaten the Harlem Globetrotters?

A. The Generals have beaten the Globetrotters seven times over the decades, most recently in 1971. Playing in Martin, TN, the Generals won 100–99 on a shot by team owner Louis “Red” Klotz.

Although the Generals are known today for being patsies, they began in 1921 as the Philadelphia Sphas, a legitimate team that played in the Eastern and American basketball leagues. The Sphas—an acronym for South Philadelphia Hebrew Association—won 10 championships. Klotz was a former Sphas player who bought the team and changed the name to the Generals in 1952 when they became the permanent touring partner of Harlem’s famous team.

The 1971 victory ended a 2,495-game winning streak for the Globetrotters.

Quiz

The following questions test how much knowledge you’ve hoarded about data structures.

1. Which of the following cannot grow or shrink in size after it is created?

A. Array lists

B. Arrays

C. Hash maps

2. What’s the name of the method to find out how many items are in an array list or hash map?

A. length()

B. size()

C. count()

3. What data type or class can be used as the keys in a hash map?

A. int or Integer

B. String

C. Any class of object

Answers

1. B. The size of an array is determined when it is created and cannot be altered. Array lists and hash maps change size as needed.

2. B. The size() method indicates the current number of items in that data structure.

3. A, B, or C. Hash maps can use any class as the keys and any class as the values.

Activities

You can apply your well-structured programming knowledge with the following activities:

Image Write a program that uses one of this hour’s data structures for a company email address list, with each email associated with that person’s name.

Image Extend the FontMapper program to take a new font’s name, size, and style as command-line arguments and add it to the hash map before its keys and values are displayed.

To see Java programs that implement these activities, visit the book’s website at www.java24hours.com.