Blakes 21 Days Chapter 08 Document

• External Links
  • Version (24) | Blakes 21 Days | Book's Website | 21 Days | Download JDK 8 (Oracle) | Download NetBeans 8.0.2 (netbeans) || www.learnjavaonline.org | reserve
  • Chapter 1 & Appendix A | (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) | (9) | (10) | (11) | (12) | (13) | (14) | (15) | (16) | (17) | (18) | (19) | (20) | (21) | (A) | (B) | (C) | (D) | (E) | reserve | Project Files | Grid | Blank

• Internal Links
  • Chapter 8 pages 225 to 253 | 253 - 225 = 28 pages | 13 is the mid way point for this chapter | Current Page 252 - 225 = 27 | Comments: 1 more pages till the end | reserve
  • page 225 | Moving Beyond Arrays | Java Structures | Iterator | Bit Sets | First Program | The Explanantion | Array Lists | Looping Through Data Structures | reserve
  • Second Program | The Explanantion | Stacks | Map | Hash Maps | Third Program | The Explanation | Generics | Fourth Program | reserve
  • Enumerations | Summary | reserve

Day 8, Data Structures

• Top
• 225 During the first week, you learned about the core elements of the Java language, objects, classes, and interfaces, along with keywords, statements, expressions, and operators they contain.
• 225 For the second week, the focus shifts from classes you create to the ones that have been created for you.
  • The Java Class Library is a set of standard packages from Oracle that has more than 4,200 classes you can use in your own Java programs.
• 225 Today you start with classes that represent data.
  • The following data structures are covered:
    • Bit sets, which hold Boolean values
    • Array lists, arrays that can grow and shrink in size
    • Stacks, structures stored in last-in, first-out (LIFO) order
    • Hash maps, which store items using keys

Moving Beyond Arrays

• Top
• 226 The Java Class Library provides a set of data structures in the java.util package that gives you more flexibility in organizing and manipulating data.
  • A solid understanding of data structures and when to employ them will be useful throughout your Java programming efforts.
  • Many Java programs that you create rely on some means of storing and manipulating data with a class.
    • Up to this point, you have used three structures to store and retrieve data: variables, String objects, and arrays.
  • These are just a few of the data classes available in Java.
    • If you don't understand the full range of data structures, you'll find yourself trying to use arrays or strings when other options would be more efficient or easier to implement.
  • Outside of primitive types and strings, arrays are the simplest data structure that Java supports.
    • An array is a series of data elements of the same primitive type or class.
    • It's treated as a single object but contains multiple elements that can be accessed independently.
    • Arrays are useful when you need to store and access related information.

• Top
• 226 NOTE: Unlike the data structures provided by the java.util package, arrays are considered such a core component of Java that they are implemented in the language itself.
  • Therefore, you can use arrays in Java without using an object to hold their data.

Java Structures

• Top
• 226 The data structures provided by the java.util package perform a wide range of functions.
  • These data structures consist of the Iterator interface, Map interface, and classes such as the following:
    • BitSet
    • ArrayList
    • Stack
    • HashMap

• Top
• 227 Each of these data structures provides a way to store and retrieve information in a well-defined manner.
  • The Iterator interface itself isn't a data structure, but it defines a means to retrieve successive elements from a data structure.
  • For example, Iterator defines a method called next() that gets the next element in a data structure containing multiple elements.

• 227 NOTE: Iterator is an expanded and improved version of the Enumeration interface from early versions of the language.
  • Although Enumeration is still supported, Iterator should be used instead because it has simpler method names and support for removing items.
  • Iterator also has been designed to detect a problem-prone situation with threads:
    • It fails with a ConcurrentModificationException when one thread changes an item while another one is looping through the elements.

• Top
• 227 The BitSet class implements a group of bits, or flags, that can be set and cleared individually.
  • This class is useful when you need to keep up with a set of Boolean values,
    • you simply assign a bit to each value and set or clear it as appropriate.
  • A flag is a Boolean value that represents one of a group of on/off type states in a program.

• 227 The ArrayList class is similar to an array, except that it can grow as necessary to accommodate new elements and also shrink.
  • Like an array, elements of an ArrayList object can be accessed via an index value.
  • The nice thing about using an array list is that you aren't required to give it a specific size upon creation,
    • it shrinks and grows automatically as needed.

• 227 The Stack class implements a last-in, first-out stack of elements.
  • You can think of a stack as a verticle stack of objects.
  • When you add a new element, it's stacked on top of the others.
  • When you pull an element off the stack, it comes off the top.
  • The capability to remove an item differs from a structure like array, where the elements always are avaiable.

• 227 The HashMap class implements Dictionary, an abstract class that defines a data structure for mapping keys to values.
  • This is useful when you want to access data through a particular key rather than an integer index.
  • Because the Dictionary class is abstract, it provides only the framework for a key-mapped data structure rather than a specific implementation.
  • A key is an identifier used to reference, or look up, a value in a data structure.

• Top
• 227 The HashMap class provides an implementation of a key-mapped data structure.
  • HashMap organizes data based on a user-defined key structure.
  • For example, in a ZIP Code list stored in a hash map, you could store data using each code as a key.
  • The specific meaning of keys in a hash map depends on how the map is used and the data it contains.

• 228 The next section looks at these data structures in more detail to show how they work.

Iterator

• Top
• 228 The Iterator interface provides a standard means of progressing through a list of elements in a defined sequence, which is a common task for many data structures.
  • Even though you can't use the interface outside a particular data structure, understanding how the Iterator interface works helps you understand other Java data structures.
  • With that in mine, take a look at three methods defined by the Iterator interface:
    • public boolean hasNext();
    • public Object next();
    • public void remove();
  • These methods lack code because interfaces don't have implementations.
    • The class that implements the interface must provide the code to define the methods.
  • The hasNext() method determines whether the structure contains any more elements.
    • You can call this method to see whether you can continue iterating through a structure.
  • The next() method retrieves the next element in a structure.
    • If there are no more elements, next() throws a NoSuchElementException exception.
    • To avoid this, you can use hasNext() in conjunction with next() to make sure that there is another element to retrieve.

• Top
• 228 The following while loop uses these two methods to iterate through a data structure called users that implements the Iterator interface:
  • 
    while (users.hasNext()) {
        Object ob = users.next();
        System.out.println(ob);
    }
    
    
  • This simple code displays the contents of each list item by using the hasNext() and next() methods.
  • The next() method returns an object of the class Object.
  • You can cast this to another class that the structure holds.
  • Here's an example for a data structure that holds String objects:
  • 
    while (users.hasNext()) {
        String ob = (String) users.next();
        System.out.println(ob);
    }
    

• Top
• 229 NOTE: Because Iterator is an interface, you never use it directly as a data structure.
  • Instead, you use the methods defined by Iterator for structures that implement the interface.
  • This provides a consistent way to work with many of Java's standard data structures, which makes them easier to learn and use.

Bit Sets

• Top
• 229 The BitSet class is useful when you need to represent a large amount of binary data - bit values that equal either 0 or 1.
  • These also are called on-or-off values (with 1 representing on and 0 representing off) or Boolean values (with 1 true and 0 false).
• 229 With the BitSet class, you can use individual bits to store Boolean values without requiring bitwise operations to extract bit values.
  • You simply refer to each bit using an index.
  • Another nice feature of BitSet is that it automatically grows to represent the number of bits that a program requires.
  • Figure 8.1 shows the logical organization of a bit set data structure.

Figure 8.1 The Organization of a bit set.

• Top
• 229 You can use a BitSet object to hold attributesthat easily can be modeled by Boolean values.
  • Because the individual bits in a set are accessed via an index, you can define each attribute as a constant index value, as in this class:
  • 
    class ConnectLocAttributes {
        public static final int READABLE = 0;
        public static final int WRITABLE = 1;
        public static final int STREAMABLE = 2;
        public static final int FLEXIBLE = 3;
    }
    

• Top
• 230 In this class, the attributes are assigned increasing values begining with 0.
  • You can use these values to get and set the appropriate bits in a set.
  • First, you need to create a BitSet object:
  • BitSet connex = new BitSet();

• 230 This constructor creates a set with no specific size.
  • You also can create a set with a specific size:
  • BitSet connex = new BitSet(4);
  • This creates a set containing four Boolean bits.
  • Regardless of the constructor used, all bits in new sets initially are set to false.
  • After you have a set, you can set and clear the bits by using set(int) and clear(int) methods with the bit constants you defined:
  • 
    connex.set(ConnectionAttributes.WRITABLE);
    connex.set(ConnectionAttributes.STREAMABLE);
    connex.set(ConnectionAttributes.FLEXIBLE);
    
    connex.clear(ConnectionAttributes.WRITABLE);
    
    
  • In this code, the WRITABLE, STREAMABLE, and FLEXIBLE attributes are set, and then the WRITABLE bit is cleared.
    • The class name is used for each attribute because the constants are class variables in the ConnectionAttributes class.
  • You can get the value of individual bits in a set by using the get() method:
    • boolean isWritable = connex.get(ConnectionAttributes.WRITABLE);
  • You can find out how many bits a set represents with the size method:
    • int numBits = connex.size();
  • The BitSet class also provides other methods for performing comparisons and bitwise operations on sets, such as AND, OR and XOR.
  • All these methods take a BitSet object as their only argument.

• Top
• 230 Today's first project is HolidaySked, a Java class that uses a set to keep track of which days in a year are holidays.
• 230 A set is employed because HolidaySked must be able to take any day of the year and answer the same yes/no question: Are you a holiday ?
• 230 Enter the code shown in Listing 8.1 into an empty Java file in NetBeans named HolidaySked in the com.java21days package.

Listing 8.1

• Top
• page 231
  
  package com.java21days;
  
  import java.util.*;
  
  public class HolidaySked {
      BotSet sked;
  
      public HolidaySked() {
          sked = new BitSet(365);
          int[] holiday = new { 1, 15, 50, 148, 185, 246,
              281, 316, 326, 359 };
          for (int i = 0; i < holiday.length; i++) {
              addHoliday(holiday[i]);
          }
      }
  
      public void addHoliday(int dayToAdd) {
          asked.set(dayToAdd);
      }
  
      public boolean isHoliday(int dayToCheck) {
          boolean result = sked.get(dayToCheck);
          return result;
      }
  
      public static void main(String[] arguments) {
          HolidaySked cal = new HolidaySked();
          if (arguments.length > 0) {
              try {
                  int whichDay = Integer.parseInt(arguments[0]);
                  if (cal.isHoliday(whichDay)) {
                      System.out.println("Day number " + whichDay +
                          " is not a holiday.");
                  } else {
                      System.out.println("Day number " + whichDay +
                          " is not a holiday.");
                  }
              } catch (NumberFormatException nfe) {
                  System.out.println("Error: " + nfe.getMessage());
              }
          }
      }
  }
  

The Explanation

• Top
• 231 This application requires one command-line argument: a number from 1 to 365 that represents the day of the year, in sequence.
  • (These numbers are defined in lines 10 - 11 and would be different for each year.)

• 231 Use the command Run, Set Project Configuration, Customize to set the argument.

• 232 Test this application with values such as 15 (Martin Luther King Day) or 103, sadly is not.

• 232 The output of the application for day 170 is shown in Figure 8.2.

Figure 8.2 Trying out the BitSet data structure

• Top
• The output pane is displayed below:
  
  run:
  Day number 170 is not a holiday.
  BUILD SUCCESSFUL (total time: 0 seconds)
  
  

• Top
• 232 The HolidaySked class contains only one instance variable: sked, a BitSet that holds values for each day in a year.
  • The constructor of the class creates the sked bit set with 365 positions, with a value of 0 (lines 8 - 15).
    • All bit sets are filled with 0 values when they are created.
  • Next, an integer array called holiday is created.
    • This array holds the number of each work holiday in the year, beginning with 1 (New Year's Day) and ending with 359 (Christmas).
  • The holiday array is used to add each holiday to the bit set.
    • A for loop iterates through the holiday array and calls the method addHoliday(int) with each one (lines 12 - 14).
  • The addHoliday(int) method is defined in lines 17 - 19.
    • The argument represents the day that should be added.
    • The bit set's set(int) method is called to set the bit at the specified position to 1.
    • For example, if set(359) is called, the bit at position 359 is given the value of 1.
  • The HolidaySked class also can determine whether a specified day is a holiday.
    • This is handled by the isHoliday(int) method (lines 21 - 24).
    • The method calls the bit set's get(int) method, which returns true if the specified position has the value 1 and false otherwise.
  • The class can be run as an application because of the main() method (lines 26 - 42).
    • The application takes a single command-line argument: a number from 1 to 365 that represents one of the days of the year.
    • The application displays whether that day is a holiday according to the schedule of the HolidaySked class.

Array Lists

• Top
• 233 One of the most popular data structures in Java, the ArrayList class implements an expandable and contractible array of objects, making it more flexible and useful than arrays.
  • Because the ArrayList class is responsible for changing size as necessary, it has to decide when and how much to grow or shrink as elements are added or removed.
• 233 An array list can be created with a constructor taking no arguments:
  • ArrayList golfer = new ArrayList();
  • This constructor creates a default array list containing no elements.
  • All lists are empty upon creation.
  • One of the attributes that determines how a list sizes itself is its initial capacity - the number of elements for which it allocates memory to hold.
  • The size of the array list is the number of elements currently stored in it.
    • A list's capacity is always greater than or equal to the size.
  • The following code shows how to create an array list with a specified capacity:
    • ArrayList golfer = new ArrayList(30);
  • This list allocates enough memory to support 30 elements.
    • If the capacity fills up, the list automatically expands by half the initial size.
    • So if a 30th element is put in golfer, it expands to make room for 45 elements.
  • Because allocating additional space for the list takes time and consumes memory, it's best to create a list with as many elements as you expect to use.
  • You can't just use square brackets [] to access the elements in an array list, as you can in an array.
    • You must use methods of the ArrayList class.

• Top
• 233 Use the add(Object) method to add an element to an array list, like this:
• 
  golfer.add("Park");
  golfer.add("Lewis");
  golfer.add("Ko");
  

• 233 The lastElement() method returns an Object because the ArrayList class supports all classes of the objects.
  • You must cast it to the class that was put into the list.
  • Here, because strings were stored in golfer, the returned object is cast to a string.

• 233 The get() method retrieves a list element using numeric index, as shown in the following code:
  • 
    String s1 = (String) golfer.get(0);
    String s1 = (String) golfer.get(2);
    
    
  • Because the array list numbering is zero-based, the first call to get() retrieves the "Park" string, and the second call retrieve the "Lewis" string.

• Top
• 234 Just as you can retrieve an element at a particular index, you also can add and remove elements at an index by using the add(int, Object) and remove(int) methods:
  • 
    golfer.add(1, "Kim");
    golfer.add(0, "Thompson");
    golfer.remove(3);
    
    
  • The first call to add() inserts an element at index 1, between "Park" and "Lewis" strings.
    • The "Lewis" and "Ko" strings are moved by an element in the list to accommodate the inserted "Ko" string.
    • The second call to add() inserts an element at index 0, which is the beginning of the list.
    • All existing elements are moved up one space in the list to accommodate the inserted "Thompson" string.
    • At this point, the contents of the list look like this:
    • 
      0. "Thompson"
      1. "Park"
      2. "Kim"
      3. "Lewis"
      4. "Ko"
      
• 234 The call to remove() removes the element at index 3, which is the "Lewis" string.
  • The resulting lists consists of the following strings:
    • 
      0. "Thompson"
      1. "Park"
      2. "Kim"
      3. "Ko"
      
      
  • You can use the set() method to change a specific element:
    • 
      golfer.set(1, "Pressel");
      
      
  • This method replaces the "Park" string with the "Pressel" string, resulting in the following list:
    • 
      0. "Thompson"
      1. "Pressel"
      2. "Kim"
      3. "Ko"
      

• Top
• 235 If you want to clear out the array list, you can remove all the elements with the clear() method:
  • 
    golfer.clear();
    
    

• 235 The ArrayList class also provides some methods for working with elements without using indexes.
  • These methods search through the list for a particular element.
  • The first of these methods is the contains(Object) method, which simply checks whether an object is in the list:
    • 
      boolean isThere = golfer.contains("Kerr");

• 235 Another method for searching is the indexOf(Object) method, which finds the index of an element matching the object:
  • 
    int i = glofer.indexOf("Ko");
    
    
  • The indexOf() method returns the index or -1 if the object is not in the list.
    • The remove(Object) method works similarly, removing an object from the list, as in this statement:
    • golfer.remove("Pressel");

• Top
• 235 The ArrayList class offers a few methods for determining and manipulating a list's size.
  • First, the size method determines the number of elements in the list
  • 
    int size = glofer.size();
    

• 235 Recall that lists have two attributes relating to size: size and capacity.
  • The size is the number of elements in the list, and the capacity is the amount of memory allocated to hold all the elements.
  • The capacity always is greater than or equal to the size.
  • You can force the capacity to exactly match the size by using the trimToSize() method:
  • 
    golfer.trimToSize();
    

• Top
• 235 CAUTION: The Java Class Library also includes Vector, a data structure that works a lot like array lists.
  • When you use vectors in NetBeans, a warning is displayed that calls the class as "obsolete collection."
  • This occurs because array lists are considered a superior version of vectors.

Looping Through Data Structures

• Top
• 235 If you're interested in working sequentially with all the elements in a list,
  • you can use the iterator() method, which returns an Iterator that holds a list of the elements you can loop through:
  • 
    Iterator it = golfer.iterator();
    

• 236 As you learned earlier today, you can use an iterator to step thru elements sequentially.
  • In this example, you can work with the it list using the methods defined by the Iterator interface.

• 236 The following for loop uses an iterator and its methods to traverse an entire arry list:
  • 
    for (Iterator i = golfer.iterator(); i.hasNext(); ) {
        String name = (String) i.next();
        System.out.println(name);
    }

Second Program

• Top
• 236 Today's next project demonstrates the care and feeding of array lists.
  • The CodeKeeper class, shown in Listing 8.2, holds a set of text codes, some provided by the class and others provided by users.
  • Because the amount of space needed to hold the codes isn't known until the program is run, an array list is used to store the data instead of an array.
  • Create this class in NetBeans, rembering to put it in the com.java21days package.

Listing 8.2

• Top
• page 236 - 237
  
  package com.java21days;
  
  import java.util.*;
  
  public class CodeKeeper {
      ArrayList list;
      String[] codes = ( "alpha", "lambda", "gamma", "delta", "zeta" };
  
      public CodeKeeper(String[] userCodes) {
          list = new ArrayList();
          // load built-in codes
          for (int i = 0; i < codes.length; i++) {
              addCode(codes[i]);
          }
          // load user code
          for (int j = 0; j < userCodes.length; j++) {
              addCode(userCodes[j]);
          }
          // display all codes
          for (Iterator ite = list.iterator(); ite.hasNext(); ) {
              String output = (String) ite.next();
              System.out.println(output);
          }
      }
  
      private void addCode(String code) {
          if (!list.contains(code)) {
              list.add(code);
          }
      }
  
      public boolean isHoliday(int dayToCheck) {
          boolean result = sked.get(dayToCheck);
          return result;
      }
  
      public static void main(String[] arguments) {
          CodeKeeper keeper = new CodeKeeper(arguments);
      }
  }
  

The Explanantion

• Top
• 237 NetBeans may display a warning that this class uses "unchecked or unsafe operations."
  • This isn't as severe as it sounds.
  • The code works properly as written and is not unsafe.
• 237 The warning serves as a strong hint that there's a better way to work with array lists and other data structures.
  • You'll learn about this technique later today.
• 237 The CodeKeeper class uses an ArryList instance variable named list to hold the text codes.

• Top
• 237 First, five built-in codes are read from a string array into the list (lines 12 - 14).
• 237 Next, any codes provided by the user as command-line arguments are added (lines 16 - 18).
• 237 Codes are added by calling the addCode() method (lines 26 - 30).
  • addCode() adds a new text code only if it isn't already present, using the list's contains(Object) method to make this determination.

• 237 You add command-line arguments in NetBeans by selecting Project, Set Project Configuration, Customize.
  • The arguments should be a list of codes separated by spaces.

• 237 After the codes have been added to the list, its contents are displayed.
  • Running the class with the command-line arguments "beta" and "epsilon" produces the output shown in Figure 8.3

Figure 8.3 goes here

• Top
• the Ouput Pane
  run:
  alpha
  lambda
  gamma
  delta
  zeta
  beta
  epsilon
  BUILD SUCCESSFUL (total time: 0 seconds)
  

• Top
• 237 A simpler for loop can be employed to iterate through a data structure.
  • The loop takes the form for (variable : structure), where structure is a data structure that implements the Iterator interface.
  • The variable section declares an object that holds each element of the structure as the loop progresses.

• Top
• 238 This for loop uses an iterator and its methods to traverse an array list named golfer :
  • 
    for (Object name : golfer) {
        System.out.println(name);
    }
    
    
  • The loop can be used with any data structure that works with Iterator.

Stacks

• Top
• 238 Stacks are a data structure used to model information accessed in a specific order.
  • The Stack class in Java is implemented as a last-in, first-out stack, which means that the last item added to the stack is the first one to be removed
  • Figure 8.4 shows the logical organization of a stack.

• Top
• 238 You might wonder why the numbers of the elements don't match their positions from the top of the stack.
  • Keep in mind that elements are added to the top, so Element0, which is on the bottom, was the first element added to the stack.
  • Likewise, Element3, which is on top, was the last element added to the stack.
  • Also, because Element3 is at the top of the stack, it will be the first to be removed.
• 238 The Stack class defines only one constructor, which is a default constructor that creates an empty stack.
  • You use this constructor to create a tack like this:
    • 
      Stack s = new Stack();
      
      
  • Stacks in Java contain methods to manipulate the stack.

• Top
• 239 You can add new elements to a stack by using the push() method, which pushes an element onto the top of the stack:
  • 
    s.push("One");
    s.push("Two");
    s.push("Three");
    s.push("Four");
    s.push("Five");
    s.push("Six");
    
    
  • This code pushes six strings onto a stack, with the last string ("Six") ending up on top.
    • You remove elements from the stack by using the pop() method, which pops them off the top:
  • 
    String s1 = (String) s.pop();
    String s2 = (String) s.pop();
    
    
  • This code pops the last two strings off the stack, leaving the first four strings.
• This code results in the s1 variable's containing the "Six" string and the s2 variable's containing the "Five" string.
• If you want to use the top element on the stack without actually popping it off the stack, you can use the peek() method:
• 
  Stack s3 = (String) s.peek();
  
  
• This call to peek() returns the "Four" string but leaves the string on the stack.
  • You can search for an element on the stack by using the search() method:
  • 
    int i = s.search("Two");
    
    
• The search() method returns the distance from the top of the stack to the element if it is found, or -1 if not.
  • In this case, the "Two" string is the third element from the top, so the search() method returns 2.

• Top
• 239 NOTE: As in all Java data structures that deal with indexes or lists, the Stack class reports element positions in a zero-based fashion: The top element in a stack has a location of 0, the fourth element down has a location of 3, and so on.

• 239 The last method defined in the Stack class is empty(), which indicates whether a stack is empty:
  • 
    boolean isEmpty = s.empty();
    

Map

• Top
• 240 The Map interface defines a framework for implementing a key-mapped data structure, a place to store objects each referenced by a key.
  • The key serves the same purpose as an element number is an array, it's a unique value used to access the data stored at a position in the data structure.
• 240 You can put the key-mapped approach to work by using the HashMap class or one of the other classes that implement the Map interface.
  • You learn about the HashMap class in the next section.
• 240 The Map interface defines a means of storing and retrieving information based on a key.
  • This is similar in some ways to the ArrayList class, in which elements are accessed thru an index, which is a specific type of key.
  • However, keys in the Map interface can be just about anything.
  • You can create your own classes to use as the keys for accessing and manipulating data in a dictionary.
  • Figure 8.5 shows how keys map to data in a dictionary.

• Top
• 240 The Map interface declares a variety of methods for working with the data stored in a dictionary.
  • Implementing classes have to implement all those methods to be truly useful.
  • The put(String, Object) and get(String, Object) methods are used to store objects in the dictionary and retrieve them.
• 240 Assuming that look is an object that implements the Map interface, the following code shows how to use the put() method to add elements:
  • 
    Rectangle r1 = new Rectangle(0, 0, 5, 5);
    look.put("small", r1);
    Rectangle r2 = new Rectangle(0, 0, 15, 15);
    look.put("medium", r2);
    Rectangle r3 = new Rectangle(0, 0, 25, 25);
    look.put("large", r3);
    
    
• 241 This code adds three Rectangle objects to the map (from the java.awt package), using strings as the keys.
  • To get an element, use the get() method and specify the appropriate key:
  • 
    Rectangle r = (Rectangle) look.get("medium");
    
    
  • You also can remove an element with a key by using the remove() method:
  • 
    look.remove("large");
    
    
  • You can find out how many elements are in a structure by using the size() method, as in the ArrayList class:
  • 
    int size = look.size();
    
    
  • You also can check whether the structure is empty by using the isEmpty() method:
  • 
    boolean isEmpty = look.isEmpty();
    

Hash Maps

• Top
• 241 The HashMap class implements the Map interface and provides a complete implementation of a key-mapped data structure.
  • Hash maps let you store data based on some type of key and have an efficiency defined by the map's load factor.
  • The load factor is a floating-point number between 0.0 and 1.0 that determines how and when the hash map allocates space for more elements.
• 241 Like array lists, hash maps have a capacity, or an amount of allocated memory.
  • Hash maps allocate memory by comparing the map's current size with the product of the capacity and the load factor.
  • If the size of the hash map exceeds this product, the map increases its capacity by rehashing itself.
• 241 Load factors closer to 1.0 result in a more efficient use of memory at the expense of a longer lookup time for each element.
  • Similary, load factors closer to 0.0 result in more efficient lookups but tend to be more wasteful with memory.
  • Determining the load factor for your own hash maps depends on how you use each map and whether your priority is performance or memory efficiency.
• 241 You can create hash maps in one of three ways.
  • The first constructor creates a default hash map with an initial capacity of 16 elements and a load factor of 0.75:
  • 
    HashMap hash = new HashMap();
    
    
  • The second constructor creates a hash map with the specified initial capacity and a load factor of 0.75:
  • 
    HashMap hash = new HashMap(20);
    
    
  • Fianally, the third constructor creates a hash map with the specified initial capacity and load factor:
  • 
    HashMap hash = new HashMap(20, 0.5F);
    
    
• 242 All the abstract methods defined in Map are implemented in the HashMap class.
  • In addition, the HashMap class implements a few others that perform functions specific to supporting maps.
  • One of these is the clear() method, which clears a map of all its keys and elements:
  • 
    hash.clear();
    
    
  • The containsValue(Object) method checks whether an object is stored in the hash map:
  • 
    Rectangle box = new Rectangle(0, 0, 5, 5);
    boolean isThere = hash.containsValue(box);
    
    
  • The containsKey(string) method searches a map for a key:
  • 
    boolean isThere = hash.containsKey("Small");
    
    
  • The practical use of a hash map comes from its capability to represent data that is too time-consuming to search or reference by value.
    • The data structure comes in handy when you're working with complex data and it's more efficient to access the data by using a key rather than comparing the data objects themselves.
  • This key, which is called a hash code, is a computed key that uniquely identifies each element in a hash map.
  • This technique of computing and using hash codes for object storage and reference is exploited heavily thoughout the Java Class Library.
    • The parent of all classes, Object, defines a hashCode() method overridden in most standard Java classes.
    • Any class that defines a hashCode() method can be efficiently stored and accessed in a hash map.
    • A class that wants to be hashed also must implement the equals() method, which defines a way of telling whether two objects are equal.
    • The equals() method usually just performs a straight comparison of all the member variables defined in a class.

The Third Program

• Top
• 242 The next project you undertake today uses maps for a shopping application.

• 242 The ComicBooks application prices collectible comic books according to their base value and condition.
  • The condition is described as one of the following: mint, near mint, very fine, fine, good, or poor.
  • Each condition has a specific effect on a comic's value:
    • "Mint" books are worth 3 times their base price.
    • "Near mint" books are worth 2 times their base price.
    • "Very fine" books are worth 1.5 times their base price.
    • "Fine" books are worth their base price.
    • "Good" books are worth 0.5 times their base price.
    • "Poor" books are worth 0.25 times their base price.

• Top
• 243 To associate text such as "mint" or "very fine" with a numeric value, they are put into a hash map.
  • The keys to the map are the condition descriptionsm and the values are floating-point numbers such as 3.0, 1.5, and 0.25.

• 243 Enter the code shown in Listing 8.3 in NetBeans as the class ComicBooks in the package com.java21days.

Listing 8.3

• Top
• page 243 - 244
  
  package com.java21days;
  
  import java.util.*;
  
  public class ComicBooks {
  
      public ComicBooks() {
      }
  
      public static void main(String[] arguments) {
          // set up hash map
          HashMap quality = new HashMap();
          float price1 = 3.00F;
          quality.put("mint", price1);
          float price2 = 2.00F;
          quality.put("near mint", price2);
          float price3 = 1.50F;
          quality.put("very fine", price3);
          float price4 = 1.00F;
          quality.put("fine", price4);
          float price5 = 0.50F;
          quality.put("good", price5);
          float price6 = 0.25F;
          quality.put("poor", price6);
          // set up collection
          Comic[] comix = new Comic[3];
          comix[0] = new Comic("Amazing Spider-Man", "1A", "very fine",
              12_000.00F);
          comix[0].setPrice( (Float) quality.get(comix[0].condition) );
          comix[1] = new Comic("Incredible Hulk", "181", "near mint",
              680.00F);
          comix[1].setPrice( (Float) quality.get(comix[1].condition) );
          comix[2] = new Comic("Cerebus", "1A", "good", 190.00F);
          comix[2].setPrice( (Float) quality.get(comix[2].condition) );
          for (int i = 0; i < comix.length; i++) {
              System.out.println("Title: " + comix[i].title);
              System.out.println("Issue: " + comix[i].issueNumber);
              System.out.println("Condition: " + comix[i].condition);
              System.out.println("Price: $" + comix[i].price + "\n");
          }
      }
  }
  
  class Comic {
      String title;
      String issueNumber;
      String condition;
      float basePrice;
      float price;
  
      Comic(String inTitle, String inIssueNumber, String inCondition,
          float inBasePrice {
  
          title = inTitle;
          issueNumber = inIssueNumber;
          condition = inCondition;
          basePrice = inBasePrice;
      }
  
      void setPrice(float factor) {
          price = basePrice * factor;
      }
  }
  

• Top
• 244 When you run the ComicBooks application, it produces the output in Figure 8.6

Figure 8.6 Storing comic book values in a hash map.

• Output - Java21(run)#2 x
• run:
  Title: Amazing Spider-Man
  Issue: 1A
  Condition: very fine
  basePrice: 18000.0
  
  Title: Incredible Hulk
  Issue: 181
  Condition: near mint
  basePrice: 1360.0
  
  Title: Cerebus
  Issue: 1A
  Condition: good
  basePrice: 95.0
  
  BUILD SUCCESSFUL (total time: 0 seconds)
  

The Explanation

• Top
• 245 The ComicBooks application is implemented as two classes: an application class called ComicBooks and a helper class called Comic.
• 245 In the application, the hash map is created in lines 12 - 24.
  • First the map is created in line 12.
• 245 Next a float called price1 is created with the value 3.00.
  • This value is added to the map and assiciated with the key "mint".
    • ( Remember that hash maps, like other data structures, can hold only objects.
    • The float value is automatically converted to a Float object through autoboxing. )
  • The process is repeated for each of the other comic book conditions, from "near mint" to "poor".
  • After the hash map is set up, an array of Comic objects called comix is created to hold each comic book currently for sale.
  • The Comic constructor is called with four arguments: the book's title, issue number, condition, and base price.
    • The first three are strings, and the last is a float.
  • After a Comic has been created, its setPrice(float) method is called to set the book's price based on its condition.
    • Here's an example, line 29:
    • 
      comix[0].setPrice( (Float) quality.get(comix[0].condition) );
      
      
  • The hash map's get(String) method is called with the book's condition, a string that is one of the keys in the map.
    • An Object is returned that represents the value associated with that key.
    • ( In line 29, because comix[0].condition is equal to "very fine", get() returns the floating-point value 3.00F. )
  • Because get() returns an Object, it must be cast as a Float.
    • The Float argument is unboxed as a float value automatically thru unboxing.
  • This process is repeated for two more books.

• Top
• 245 Lines 35 - 40 display information about each comic book in the comix array.
• 245 The Comic class is defined in lines 44 - 63.
  • It has five instance variables - the String object's title, issueNumber, and condition, and the floating-point value's basePrice and price.

• 245 The constructor method of the class, located in lines 51 - 58, sets the value of four instance variables to the argument sent to the constructor.

• 245 The setPrice(Float) method in lines 60 - 62 sets the price of a comic book.
  • The argument sent to the method is a float value.
  • A comic's price is calculated by multiplying this float by the comic's base price.
  • Consequently, if a book is worth $1,000, and its multiplier is 2.0, the book is priced at $2,000.

• 246 Hash maps are a powerful data structure for manipulating large amounts of data.
  • The fact that these maps are so widely supported in the Java Class Library via the Object class should give you a clue as to their importance in Java programming.

Generics

• Top
• 246 The data structures that you learned about today are some of the most essential utility classes in the Java Class Library.
  • Hash maps, array lists, stacks, and other structures in the java.util package are useful regardless of the kind of programs you want to develop.
  • Almost every software program handles data in some manner.
• 246 These data structures are well-suited for use in code that applies generically to a wide range of classes of objects.
  • A method written to manipulate array lists could be written to function equally well on strings, string buffers, character arrays, or other objects that represent text.
  • A method in an accounting program could take objects that represent integers, floating-point numbers, and other math classes, using each to calculate a balance.
• 246 This flexibility comes at a price:
  • When a data structure works with any kind of object, the Java compiler can't display a warning when the structure is being misused.
  • For instance, the ComicBooks application uses a hash map named quality to associate condition descriptions such as "mint" and "good" with price multipliers.
  • Here's the statement for "near mint":
  • 
    quality.put("near mint", 1.50F);
    
    
  • By design, the quality map should hold only floating-point values (as Float objects).
    • However, the class compiles successfully regardless of the class of the value added to a map.
  • You might goof and unintentionally add a string to the map, as in this revised statement:
  • 
    quality.put("near mint", "1.50");
    
    
  • The class compiles successfully, but when it is run, it fails with a ClassCastException error in the following statement:
  • 
    comix[1].setPrice( (Float) quality.get(comix[1].condition) );
    
    
  • The reason for the error is that the statement tries to cast the map's "near mint" value to a Float, which fails because it recieves the string "1.50" instead.

• Top
• 247 Runtime errors are much more troublesome for programmers than compiler errors.
  • A compiler error stops you in your tracks and must be fixed before you continue.
  • A runtime error might creep its way into the code, unbeknownst to you, and cause problems for users of your software.

• 247 You can specify the class or classes expected in a data structure using a feature of the language called generics.
  • The expected class information is added to statements where the structure is assigned a variable or created with a constructor.
  • The class or classes are placed within < and > characters and follow the name of the class, as in this statement:
  • 
    ArrayList<Integer> zipCodes = new ArrayList<>();
    
    
  • This statement creates an array list that will be used to hold Integer objects.
    • The compiler uses inference to correctly guess the type of the class the second time the < and > characters appear.
    • The <> after a class name sometimes is called a diamond operator.
    • Here's another example:
    • 
      HashMap<String, Float> quality = new HashMap<String, Float>();
      
      
    • The diamond operator <> infers the classes based on what they would have to be for the statement to make sense.
    • Because the list is declared with a class specified, the following statements cause a compiler error that NetBeans will flag in the source code editor:
    • 
      zipCodes.add("90210");
      zipCodes.add("02134");
      zipCodes.add("20500");
      
      
    • The compiler recognizes that String objects do not belong in this array list.
    • The proper way to add elements to the list is to use integer values:
    • 
      zipCodes.add(90210);
      zipCodes.add(02134);
      zipCodes.add(20500);
      
      
    • These integers are converted to Integer objects by autoboxing.

• Top
• 247 Data structures that use multiple classes, such as hash maps, take these class names separated by commas within the < and > characters.
  • The ComicBooks application can take advantage of generics by changing line 10 of Listing 8.3 to the following:
  • 
    HashMap<String, Float> quality = new HashMap<>();
    

• 248 This sets up a map to use String objects for keys and Float objects for values.
  • With this statement in place, a string no longer can be added as the value for a condition such as "near mint".
  • A compiler error flags a problem of this kind.
• 248 Generics also make it easier to retrieve an object from a data structure, because you don't have to use casting to convert them to the desired class.
  • For example, the quality map no longer requires a cast to produce Float objects in statements like this one:
  • 
    comix[1].setPrice(quality.get(comix[1].condition));
    
    
  • From a stylistic standpoint, the addition of generics in variable declarations and constructor methods is likely to appear intimidating.
  • However, after you become accustomed to working with them (and using autoboxing, unboxing, and the new for loops),
    • data structures are significantly easier to work with and less error-prone.

The Fourth Program

• Top
• 248 The CodeKeeper2 class, shown in Listing 8.4, is a new version of CodeKeeper that has been rewritten to use generics, type inference, and the for loop that can iterate thru data structures such as array lists.

Listing 8.4 - The full Text of CodeKeeper2.java

• Top
• page 248 - 249
  
  package com.java21days;
  
  import java.util.*;
  
  public class CodeKeeper2 {
      ArrayList<String> list;
      String[] codes = ( "alpha", "lambda", "gamma", "delta", "zeta" };
  
      public CodeKeeper2(String[] userCodes) {
          list = new ArrayList<>();
          // load built-in codes
          for (int i = 0; i < codes.length; i++) {
              addCode(codes[i]);
          }
          // load user code
          for (int j = 0; j < userCodes.length; j++) {
              addCode(userCodes[j]);
          }
          // display all codes
          for (String code : list) {
              System.out.println(code);
          }
      }
  
      private void addCode(String code) {
          if (!list.contains(code)) {
              list.add(code);
          }
      }
  
      public static void main(String[] arguments) {
          CodeKeeper2 keeper = new CodeKeeper2(arguments);
      }
  }
  

• Top
• 249 The only modifications to the class are in line 6, where the generics declaration for an array list of strings is made;
  • line 10, where type inference figures out the proper generics declaration;
  • and lines 20 - 22, the simpler for loop that displays all the codes.

Enumerations

• Top
• 249 A common use of constants in Java is to attach a meaningful label to a series of integers, which you did earlier today as you worked with bit sets:
  • 
    class ConnectLocAttributes {
        public static final int READABLE = 0;
        public static final int WRITABLE = 1;
        public static final int STREAMABLE = 2;
        public static final int FLEXIBLE = 3;
    }
    
    
  • These constants are useful because of the extra information provided in statements that constrain them.
  • Compare these two statements, which do the samething:
  • 
    setConnectionType(1);
    
    setConnectionType(ConnectLocAttributes.WRITABLE);
    
    
  • The latter is much easier to understand for a programmer examining the code.
  • Java has a data type called enumerations that serve the same purpose and have advantages over using constants in a class.
  • The enum keyword is used in place of class and the values are separated by commas.

• Top
• 249 Here's a simple enumeration called Compass for the eight compass directions:
  • 
    public enum Compass {
        NORTH,
        EAST,
        SOUTH,
        WEST,
        NORTHEAST,
        SOUTHEAST,
        SOUTHWEST,
        NORTHWEST,
    }
    

• Top
• 250 Each of these values is implicitly static and final, just like constants.
  • They can appear in statements, method calls, and other code just like they were class constants.
  • Here's an application that uses the enumeration:
  • 
    public class DirectionSetter {
        Compass current;
        public void setDirection(Compass dir) {
            current = dir;
        }
    
        public static void main(String[] arguments) {
            DirectionSetter app = new DirectionSetter();
            app.setDirection(Compass.WEST);
            System.out.println(app.current);
        }
    }
    

• Top
• 250 This class sets the current instance variable to WEST from the Compass enumeration and displays the variable, which is output as the text "WEST".
  • An advantage to using enum over class constants is that the compiler can detect errors when an invalid value is used.
  • The only acceptable values that can be sent to the setDirection(Compass) method are the values of the Compass enumeration.

• 250 By comparison, a method that took ConnectionAttributes values as an argument could be called with any integer value.

• 250 There are other advantages to enumerations, which can function like a class with methods and variables of their own.

• 250 Anytime you need a fixed set of constants, you can make them an enumeration.

Summary

• Top
• 250 Today you learned about several data structures you can use in your Java programs:
  • Bit sets - Large sets of Boolean on-or-off values
  • Array lists - Arrays that can change in size dynamically and be shrunken or expanded as needed
  • Stacks - Structures in which the last item added is the first item removed
  • Hash maps - Objects stored and retrieved using unique keys
• 250 These data structures are part of the java.util package, a collection of useful classes for handling data, dates, strings, and other things.
  • The addition of generics and the new for loops for iteration enhances their capabilities.
• 251 You also were introduced to enumerations, a data type for representing a set of related values as constants.
• 251 Learning about the ways in which you can organize data in Java has benefits in all aspects of software development.
  • Whether you're learning the language to write servlets, desktop applications, apps, or something else, you need to represent data in numerous ways.

Q & A

• Top
• Q The HolidaySked project from today could be implemented as an array of Boolean values. Is one way preferable to the other ?
• A That depends. One thing you'll find as you work with data structures is that there are often many ways to implement something.
  • Bit sets are somewhat preferable to a Boolean array when the size of your program matters, because a bit set is smaller.
  • An array of a primitive type such as Boolean is preferable when the speed of your program matters, because arrays are somewhat faster.
  • In the example of the HolidaySked class, it's so small that the difference is negligible, but as you develop your own robust, real-world applications, these kinds of decisions can sometimes make a difference.

• Q The Java compiler's warning for data structures that don't use generics is pretty ominous.
  • It doesn't sound like a very good idea to release a class that has "unchecked or unsafe operations."
  • Is there any reason to stick with old code or not use generics with data structures ?
• A The compiler's warning about safety is a bit overstated.
  • Java programmers have been using array lists, hash maps, and other structures for years in their classes, creating software that runs reliably and safely.
    • The lack of generics meant that more work was necessary to ensure that runtime problems didn't occur because of wrong classes being placed in a structure.
  • It's more accurate to state that data structures can be made more safe thru the use of generics, rather than suggesting that previous versions of Java were unsafe.
  • My personal rule is to use generics in new code and old code that's being reorganized or significantly rewritten, but leave alone old code that works correctly.

Quiz - Questions

• Top

1. Which of the following kinds of data cannot be stored in a hash map ?
   1. String
   2. int
   3. Both can be stored in a map.
2. An array list is created, and three strings, "Tinker", "Evers", and "Chance", are added to it. The method remove("Evers") is called. Which of the following ArrayList methods retrieves the string "Chance" ?
   1. get(1);
   2. get(2);
   3. get("Chance");
3. Which of these classes implements the Map interface ?
   1. Stack
   2. HashMap
   3. BitSet

Answers

• Top | Note A is 1, B is 2, and C is 3

1. C. In the past versions of Java, to store primitive types such as int in a map, objects had to be used to represent their values (such as Integer for integers).
   • This is no longer true.
   • Primitive types are converted automatically to the corresponding object class thru a process called autoboxing.
2. A. The index numbers of each item in an array list can change as items are added or removed.
   • Because "Chance" becomes the second item in the list after "Evers" is removed, it is retrieved by calling get(1)
3. B. HashMap implements the interface, as does a similar class called Hashable.

Certification Practice

• Top
• 252 The following question is the kind of thing you could expect to be asked on a Java programming certification test. Answer it without looking at today's material or using the Java compiler to test the code.
• The answer is available on the book's website at www.java21days.com for Day 8.

• Given:
• 
  public class Recursion {
      public int dex = -1;
  
      public Recursion() {
          dex = getValue(17);
      }
  
      public int getValue(int dexValue) {
          if (dexValue > 100) {
              return dexValue;
          } else {
              return dexValue(dexValue * 2);
          }
      }
  
      public static void main(String[] arguments) {
          Recursion r = new Recursion();
          System.out.println(r.dex);
      }
  }
  

1. What will be the output of this application ?
   1. -1
   2. 17
   3. 34
   4. 136

Exercise

• Top
• To extend your knowledge of the subjects covered today, try the following exercises:
  1. Add two more conditions to the ComicBooks application: "pristine mint" for books that should sell at 5 times their base price, and "coverless" for books that should sell at one-tenth of their base price.
  2. Rewrite the ComicBooks application so that the set of possible conditions of a comic is an enumeration.