【面接必須】Introduction to the Collections Framework

Collectionがどれほど重要かは言わないが、面接でも実際のプログラミングでも、Collectionを上手に応用することはプログラミング効率を高め、プログラム効率を高める妙薬だ.
このチュートリアルは昔からありますが、素晴らしいです.同時集合前のJava Collections Frameworkについて完全に紹介しています.
http://java.sun.com/developer/onlineTraining/collections/Collection.html
この文書では、同時集合以前のJava Collections Frameworkについて詳しく説明します.
主な内容の整理:
basic properties of sets:
Sets contains only one instance of each item
Sets may be finite or infinite
Sets can define abstract concepts
A map is a special kind of set. It is a set of pairs, each pair representing a one-directional "mapping"from one element to another.

The Collection interface is a group of objects, with duplicates allowed
Set extends Collection but forbids duplicates
List extends Collection also, allows duplicates and introduces positional indexing
Map extends neither Set nor Collection
The Collections Framework provides two general-purpose implementations of the Set interface: HashSet and TreeSet. The TreeSet implementation is useful when you need to extract elements from a collection in a sorted manner. In order to work property, elements added to a TreeSet must be sortable.
Both HashSet and TreeSet implement the Cloneable interface.

import java.util.*;

public class SetExample {
  public static void main(String args[]) {
    Set set = new HashSet();
    set.add("Bernadine");
    set.add("Elizabeth");
    set.add("Gene");
    set.add("Elizabeth");
    set.add("Clara");
    System.out.println(set);
    Set sortedSet = new TreeSet(set);
    System.out.println(sortedSet);
  }
}

The List interface extends the Collection interface to define an ordered collection, permitting duplicates. The interface adds position-oriented operations, as well as the ability to work with just a part of the list.
If you need to support random access, without inserting or removing elements from any place other than the end, than ArrayList offers the optimal collection. If, however, you need to frequently add and remove elements from the middle of the list and only access the list elements sequentially then LinkedList offers the better implementation.

import java.util.*;

public class ListExample {
  public static void main(String args[]) {
    List list = new ArrayList();
    list.add("Bernadine");
    list.add("Elizabeth");
    list.add("Gene");
    list.add("Elizabeth");
    list.add("Clara");
    System.out.println(list);
    System.out.println("2: " + list.get(2));
    System.out.println("0: " + list.get(0));
    LinkedList queue = new LinkedList();
    queue.addFirst("Bernadine");
    queue.addFirst("Elizabeth");
    queue.addFirst("Gene");
    queue.addFirst("Elizabeth");
    queue.addFirst("Clara");
    System.out.println(queue);
    queue.removeLast();
    queue.removeLast();
    System.out.println(queue);
  }
}

The Collections Framework provides two general-purpose Map implementations: HashMap and TreeMap . As with all the concrete implementations, which implementation you use depends on your specific needs. For inserting, deleting, and locating elements in a Map, the HashMap offers the best alternative. If, however, you need to traverse the keys in a sorted order, then TreeMap is your better alternative. Depending upon the size of your collection, it may be faster to add elements to a HashMap, then convert the map to a TreeMap for sorted key traversal. Using a HashMap requires that the class of key added have a well-defined hashCode() implementation. With the TreeMap implementation, elements added to the map must be sortable.
To optimize HashMap space usage, you can tune the initial capacity and load factor. The TreeMap has no tuning options, as the tree is always balanced.

import java.util.*;

public class MapExample {
  public static void main(String args[]) {
    Map map = new HashMap();
    Integer ONE = new Integer(1);
    for (int i=0, n=args.length; i<n; i++) {
      String key = args[i];
      Integer frequency = (Integer)map.get(key);
      if (frequency == null) {
        frequency = ONE;
      } else {
        int value = frequency.intValue();
        frequency = new Integer(value + 1);
      }
      map.put(key, frequency);
    }
    System.out.println(map);
    Map sortedMap = new TreeMap(map);
    System.out.println(sortedMap);
  }
}

The Comparable interface, in the java.lang package, is for when a class has a natural ordering. Given a collection of objects of the same type, the interface allows you to order the collection into that natural ordering.
The compareTo() method compares the current instance with an element passed in as an argument. If the current instance comes before the argument in the ordering, a negative value is returned. If the current instance comes after, then a positive value is returned. Otherwise, zero is returned. It is not a requirement that a zero return value signifies equality of elements. A zero return value just signifies that two objects are ordered at the same position.

Comparator comparator = Collections.reverseOrder();
Set reverseSet = new TreeSet(comparator);
reverseSet.add("Bernadine");
reverseSet.add("Elizabeth");
reverseSet.add("Gene");
reverseSet.add("Elizabeth");
reverseSet.add("Clara");
System.out.println(reverseSet);

Because sets must hold unique items, if comparing two elements when adding an element results in a zero return value (from either the compareTo() method of Comparable or the compare() method of Comparator), then the new element is not added. If the elements are equal, then that is okay. However, if they are not, then you should modify the comparison method such that the comparison is compatible with equals().

Comparator comparator = 
  new CaseInsensitiveComparator();
Set set = new TreeSet(comparator);
set.add("Tom");
set.add("tom");
set.add("thom");
set.add("Thom");
set.add("Thomas");

After you've added all the necessary elements to a collection, it may be convenient to treat that collection as read-only, to prevent the accidental modification of the collection. To provide this capability, the Collections class provides six factory methods, one for each of Collection, List, Map, Set, SortedMap, and SortedSet.
Collection unmodifiableCollection(Collection collection)
List unmodifiableList(List list)
Map unmodifiableMap(Map map)
Set unmodifiableSet(Set set)
SortedMap unmodifiableSortedMap(SortedMap map)
SortedSet unmodifiableSortedSet(SortedSet set)

import java.util.*;

public class ReadOnlyExample {
  public static void main(String args[]) {
    Set set = new HashSet();
    set.add("Bernadine");
    set.add("Elizabeth");
    set.add("Gene");
    set.add("Elizabeth");
    set = Collections.unmodifiableSet(set);
    set.add("Clara");
  }
}

Thread-Safe Collections
The key difference between the historical collection classes and the new implementations within the Collections Framework is the new classes are not thread-safe. This was done such that if you don't need the synchronization, you don't use it, and everything works much faster. If, however, you are using a collection in a multi-threaded environment, where multiple threads can modify the collection simultaneously, the modifications need to be synchronized. The Collections class provides for the the ability to wrap existing collections into synchronized ones with another set of six methods:
Collection synchronizedCollection(Collection collection)
List synchronizedList(List list)
Map synchronizedMap(Map map)
Set synchronizedSet(Set set)
SortedMap synchronizedSortedMap(SortedMap map)
SortedSet synchronizedSortedSet(SortedSet set)
Unlike when making a collection read-only, you synchronize the collection immediately after creating it. You also must make sure you do not retain a reference to the original collection, or else you can access the collection unsynchronized. The simplest way to make sure you don't retain a reference is to never create one:

Set set = Collection.synchronizedSet(new HashSet());

Multiple Copy Collections
If you need an immutable list with multiple copies of the same element, the nCopies(int n, Object element) method of the Collections class returns just such the List:

List fullOfNullList = Collection.nCopies(10, null);

By itself, that doesn't seem too useful. However, you can then make the list modifiable by passing it along to another list:

List anotherList = new ArrayList(fullOfNullList);

This now creates 10 element ArrayList, where each element is null. You can now modify each element at will, as it becomes appropriate.
Searching
Besides sorting, the Collections and Arrays classes provide mechanisms to search a List or array, as well as to find the minimum and maximum values within a Collection.
While you can use the contains() method of List to find if an element is part of the list, it assumes an unsorted list. If you've previously sorted the List, using Collections.sort(), then you can do a much quicker binary search using one of the two overridden binarySearch() methods. If the objects in the List implement Comparable, then you don't need to provide a Comparator. Otherwise, you must provide a Comparator. In addition, if you sorted with a Comparator, you must use the same Comparator when binary searching.

public static int binarySearch(List list, Object key) 
public static int binarySearch(List list, Object key, Comparator comparator) 

If the List to search subclasses the AbstractSequentialList class (like LinkedList), then a sequential search is actually done.
Array searching works the same way. After using one of the Arrays.sort() methods, you can take the resulting array and search for an element. There are seven overridden varieties of binarySearch() to search for a primitive (all but boolean), and two to search an Object array, both with and without a Comparator.
If the original List or array is unsorted, the result is non-deterministic.
Besides searching for specific elements within a List, you can search for extreme elements within any Collection: the minimum and maximum. If you know your collection is already sorted, just get the first or last element. However, for unsorted collections, you can use one of the min() or max() methods of Collections. If the object in the collection doesn't implement Comparable, then you must provide a Comparator.

Object max(Collection collection) 
Object max(Collection collection, Comparator comparator) 
Object min(Collection collection) 
Object min(Collection collection, Comparator comparator) 

Manipulating
The Collections and Arrays classes offer several ways of manipulating the elements within a List or array. There are no additional ways to manipulate the other key framework interfaces (Set and Map).
With a List, the Collections class lets you replace every element with a single element, copy an entire list to another, reverse all the elements, or shuffle them around. When copying from one list to another, if the destination list is larger, the remaining elements are untouched.

void fill(List list, Object element) 
void copy(List source, List destination) 
void reverse(List list) 
void shuffle(List list) 
void shuffle(List list, Random random) 

The Arrays class allows you to replace an entire array or part of an array with one element via eighteen overridden versions of the fill() method. All the methods are of the form fill(array, element) or fill(array, fromIndex, toIndex, element).

String names[] = {"Bernadine",
  "Elizabeth", "Gene", "Clara"};
List list = Arrays.asList(names);