<转载> 5 things you didn't know about ... the Java Collections API, Part 2

原文来自： http://www.ibm.com/developerworks/java/library/j-5things3.html

The Collections classes in java.util were designed to help, namely by replacing arrays and, thus, improving Java performance. As you learned in the previous article, they're also malleable, willing to be customized and extended in all kinds of ways, in service of good, clean code.

Collections are also powerful, however, and mutable: use them with care and abuse them at your own risk.

1. Lists aren't the same as arrays

Java developers frequently make the mistake of assuming that ArrayList is simply a replacement for the Java array. Collections are backed by arrays, which leads to good performance when looking up items randomly within a collection. And, like arrays, collections use integer-ordinals to obtain particular items. Still, a collection isn't a drop-in replacement for an array.

The trick to differentiating collections from arrays is knowing the difference between order and position. For example, List is an interface that preserves the order in which items are placed into a collection, as Listing 1 shows:


Listing 1. Mutable keys
import java.util.*;

public class OrderAndPosition
{
    public static <T> void dumpArray(T[] array)
    {
        System.out.println("=============");
        for (int i=0; i<array.length; i++)
            System.out.println("Position " + i + ": " + array[i]);
    }
    public static <T> void dumpList(List<T> list)
    {
        System.out.println("=============");
        for (int i=0; i<list.size(); i++)
            System.out.println("Ordinal " + i + ": " + list.get(i));
    }
   
    public static void main(String[] args)
    {
        List<String> argList = new ArrayList<String>(Arrays.asList(args));
        //注意这里的值传递和引用传递。 new ArrayList 会产生一个新的值。 这里相当于深度copy
         //List<String> argList = Arrays.asList(args);
        dumpArray(args);
        args[1] = null;
        dumpArray(args);
       
        dumpList(argList);
        argList.remove(1);
        dumpList(argList);
    }
}

Note:


When the third element is removed from the above List, the other items "behind" it slide up to fill the empty slots. Clearly, this collections behavior differs from that of an array. (In fact, removing an item from an array is itself not quite the same thing as removing it from a List — "removing" an item from an array means overwriting its index slot with a new reference or null.)


2. Iterator, you surprise me!

There's no doubt that Java developers love the Java Collections Iterator, but when was the last time you really looked at the Iterator interface? Most of the time, we just slap Iterator inside a for() loop or enhanced for() loop and move on, so to speak.

But, for those who go digging, Iterator has two surprises in store.

First, Iterator supports the ability to remove an object from a source collection safely, by calling remove() on the Iterator itself. The point here is to avoid a ConcurrentModifiedException, which signals precisely what its name implies: that a collection was modified while an Iterator was open against it. Some collections will let you get away with removing or adding elements to a Collection while iterating across it, but calling remove() on the Iterator is a safer practice.

Second, Iterator supports a derived (and arguably more powerful) cousin. ListIterator, only available from Lists, supports both adding and removing from a List during iteration, as well as bidirectional scrolling through Lists.

Bidirectional scrolling can be particularly powerful for scenarios such as the ubiquitous "sliding set of results," showing 10 of many results retrieved from a database or other collection. It can also be used to "walk backwards" through a collection or list, rather than trying to do everything from the front. Dropping in a ListIterator is much easier than using downward-counting integer parameters to List.get() to "walk backwards" through a List.


3. Not all Iterables come from collections

Ruby and Groovy developers like to brag about how they can iterate across a text file and print its contents to the console with a single line of code. Most of the time, they say, doing the same thing in Java programming takes dozens of lines of code: open a FileReader, then a BufferedReader, then create a while() loop to call getLine() until it comes back null. And, of course, you have to do all this in a try/catch/finally block that will handle exceptions and close the file handle when finished.

It may seem like a silly and pedantic argument, but it does have some merit.

What they (and quite a few Java developers) don't know is that not all Iterables have to come from collections. Instead, an Iterable can create an Iterator that knows how to manufacture the next element out of thin air, rather than blindly handing it back from a pre-existing Collection:


Listing 2. Iterating a file
// FileUtils.java
import java.io.*;
import java.util.*;

public class FileUtils
{
    public static Iterable<String> readlines(String filename)
    throws IOException
    {
    final FileReader fr = new FileReader(filename);
    final BufferedReader br = new BufferedReader(fr);
   
    return new Iterable<String>() {
    public <code>Iterator</code><String> iterator() {
    return new <code>Iterator</code><String>() {
    public boolean hasNext() {
    return line != null;
    }
    public String next() {
    String retval = line;
    line = getLine();
    return retval;
    }
    public void remove() {
    throw new UnsupportedOperationException();
    }
    String getLine() {
    String line = null;
    try {
    line = br.readLine();
    }
    catch (IOException ioEx) {
    line = null;
    }
    return line;
    }
    String line = getLine();
    };
    }
    };
    }
}

//DumpApp.java
import java.util.*;

public class DumpApp
{
    public static void main(String[] args)
        throws Exception
    {
        for (String line : FileUtils.readlines(args[0]))
            System.out.println(line);
    }
}



This approach has the advantage of not holding the entire contents of a file in memory, but with the caveat that, as written, it doesn't close() the underlying file handle. (You could fix this by closing whenever readLine() returns null, but that won't solve cases where Iterator doesn't run to completion.)



4. Beware the mutable hashCode()

Map is a wonderful collection, bringing us the niftiness of key/value pair collections often found in other languages like Perl. And the JDK gives us a great Map implementation in the form of the HashMap, which uses hashtables internally to support fast key lookups for corresponding values. But therein lies a subtle problem: Keys that support hash codes dependent on the contents of mutable fields are vulnerable to a bug that will drive even the most patient Java developer batty.

Assuming the Person object in Listing 3 has a typical hashCode() (which uses the firstName, lastName, and age fields — all non-final — to calculate the hashCode()), the get() call to Map will fail and return null:


Listing 3. Mutable hashCode() drives me buggy
// Person.java
import java.util.*;

public class Person
    implements Iterable<Person>
{
    public Person(String fn, String ln, int a, Person... kids)
    {
        this.firstName = fn; this.lastName = ln; this.age = a;
        for (Person kid : kids)
            children.add(kid);
    }
   
    // ...
   
    public void setFirstName(String value) { this.firstName = value; }
    public void setLastName(String value) { this.lastName = value; }
    public void setAge(int value) { this.age = value; }
   
    public int hashCode() {
        return firstName.hashCode() & lastName.hashCode() & age;
    }

    // ...

    private String firstName;
    private String lastName;
    private int age;
    private List<Person> children = new ArrayList<Person>();
}


// MissingHash.java
import java.util.*;

public class MissingHash
{
    public static void main(String[] args)
    {
        Person p1 = new Person("Ted", "Neward", 39);
        Person p2 = new Person("Charlotte", "Neward", 38);
        System.out.println(p1.hashCode());
       
        Map<Person, Person> map = new HashMap<Person, Person>();
        map.put(p1, p2);
       
        p1.setLastName("Finkelstein");
        System.out.println(p1.hashCode());
       
        System.out.println(map.get(p1));
    }
}



Clearly, this approach is a pain but the solution is easy: Never use a mutable object type as a key in a HashMap.


5. equals() vs Comparable

When cruising through the Javadocs, Java developers frequently happen across the SortedSet type (and its lone implementation in the JDK, the TreeSet). Because SortedSet is the only Collection in the java.util package that offers any sorting behavior, developers often begin using it without questioning the details too closely. Listing 4 demonstrates:


Listing 4. SortedSet, I'm so glad I found you!

import java.util.*;

public class UsingSortedSet
{
    public static void main(String[] args)
    {
        List<Person> persons = Arrays.asList(
            new Person("Ted", "Neward", 39),
            new Person("Ron", "Reynolds", 39),
            new Person("Charlotte", "Neward", 38),
            new Person("Matthew", "McCullough", 18)
        );
        SortedSet ss = new TreeSet(new Comparator<Person>() {
            public int compare(Person lhs, Person rhs) {
                return lhs.getLastName().compareTo(rhs.getLastName());
            }
        });
        ss.addAll(perons);
        System.out.println(ss);
    }
}



After working with this code for a while, you might discover one of the Set's core features: that it disallows duplicates. This feature is actually described in the Set Javadoc. A Set is a "collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element."

But this doesn't actually seem to be the case — although none of the Person objects in Listing 4 are equal (according to the equals() implementation on Person), only three objects are present within the TreeSet when printed.

Contrary to the stated nature of the set, the TreeSet, which requires objects to either implement Comparable directly or have a Comparator passed in at the time of construction, doesn't use equals() to compare the objects; it uses the compare or compareTo methods of Comparator/Comparable.

So, objects stored in a Set will have two potential means of determining equality: the expected equals() method and the Comparable/Comparator method, depending on the context of who is asking.

What's worse, it isn't sufficient to simply declare that the two should be identical, because comparison for the purpose of sorting isn't the same as comparison for the purpose of equality: It may be perfectly acceptable to consider two Persons equal when sorting by last name, but not equal in terms of their contents.

Always ensure that the difference between equals() and the Comparable.compareTo()-returning-0 is clear when implementing Set. By extension, the difference should also be clear in your documentation.


In conclusion

The Java Collections library is scattered with tidbits that can make your life much easier and more productive, if only you know about them. Unearthing tidbits often involves some complexity, however, like discovering that you can have your way with HashMap, just as long as you never use a mutable object type as its key.

So far, we've dug beneath the surface of Collections, but we haven't yet hit the gold mine: Concurrent Collections, introduced in Java 5. The next five tips in this series will focus on java.util.concurrent.