Summary of collections interfaces
Collection - This is a basic set of methods for working with data structures. A group of objects. No assumptions are made about the order of the collection (if any), or whether it may contain duplicate elements.
List extends Collection - An ordered collection. The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.
Map (does NOT extend Collection) - An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value. Stores key/value pairs, rapidly accessible by key.
SortedMap extends Map - A map that further guarantees that it will be in ascending key order, sorted according to the natural ordering of its keys, or by a comparator provided at sorted map creation time. All keys inserted into a sorted map MUST implement the Comparable interface (or be accepted by the specified comparator).
Set extends Collection - 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.
SortedSet extends Set - A set that further guarantees that its iterator will traverse the set in ascending element order, sorted according to the natural ordering of its elements (see Comparable), or by a Comparator provided at sorted set creation time.
Summary of general-purpose implementations
HashSet implements Set - Hash table implementation of the Set interface. The best all-around implementation of the Set interface. This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.
This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.
Note that this implementation is not synchronized.
Class without overriden hashCode() and equals(...) methods:
/**
* The WeirdString class uses the derived from 'Object'
* implemenations of 'equals' and 'hashCode' methods
*/
public class WeirdString {
private String str;
WeirdString(String str ){
this.str = str;
}
public String toString() {
return "WeirdString : '" + str + "'";
}
}
import java.util.HashSet;
public class CollClient {
public static void main(String ... sss) {
HashSet myMap = new HashSet();
String s1 = new String("abcdef");
String s2 = new String("abcdef");
WeirdString s3 = new WeirdString("abcdef");
WeirdString s4 = new WeirdString("abcdef");
myMap.add(s1);
myMap.add(s2);
myMap.add(s3);
myMap.add(s4);
System.out.println(myMap);
}
}
The output (3 objects in the set):
[abcdef, WeirdString : 'abcdef', WeirdString : 'abcdef']
The next example shows class with correctly overriden hashCode() and equals(...) methods:
/**
* The WeirdStringFixed class correctly
* implements 'equals' and 'hashCode' methods
*/
public class WeirdStringFixed {
private String str;
WeirdStringFixed(String str ){
this.str = str;
}
public String getStr() {
return str;
}
public boolean equals(Object o){
if (!(o instanceof WeirdStringFixed)) {
return false;
}
return ((WeirdStringFixed) o).getStr().equals(str);
}
public int hashCode() {
return 12345; // pretty legal
}
public String toString() {
return "WeirdStringFixed : '" + str + "'";
}
}
import java.util.HashSet;
public class CollClientFixed {
public static void main(String ... sss) {
HashSet myMap = new HashSet();
String s1 = new String("abcdef");
String s2 = new String("abcdef");
WeirdStringFixed s3 = new WeirdStringFixed("abcdef");
WeirdStringFixed s4 = new WeirdStringFixed("abcdef");
myMap.add(s1);
myMap.add(s2);
myMap.add(s3);
myMap.add(s4);
System.out.println(myMap);
}
}
The output (2 objects left in the set - duplicates were removed):
[abcdef, WeirdStringFixed : 'abcdef']
TreeSet implements SortedSet - Red-black tree implementation of the SortedSet interface. This class guarantees that the sorted set will be in ascending element order, sorted according to the natural order of the elements (see Comparable), or by the comparator provided at set creation time, depending on which constructor is used.
Note that this implementation is not synchronized.
The add(...) method may throw ClassCastException if the specified object cannot be compared with the elements currently in the set:
/** Non-Comparable class */
public class WeirdString {
private String str;
WeirdString(String str ){
this.str = str;
}
}
import java.util.TreeSet;
public class CollClient {
public static void main(String ... sss) {
TreeSet myMap = new TreeSet();
String s1 = new String("abcdef");
String s2 = new String("abcdef");
WeirdString s3 = new WeirdString("abcdef");
WeirdString s4 = new WeirdString("abcdef");
myMap.add(s1);
myMap.add(s2);
myMap.add(s3); // ClassCastException at runtime !!!
myMap.add(s4);
System.out.println(myMap);
}
}
LinkedHashSet extends HashSet implements Set - Hash table and linked list implementation of the Set interface. An insertion-ordered Set implementation that runs nearly as fast as HashSet. Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order).
Note that this implementation is not synchronized.
ArrayList implements List - Resizable-array implementation of the List interface. (Essentially an unsynchronized Vector.) The best all-around implementation of the List interface.
Note that this implementation is not synchronized.
LinkedList implements List, Queue - Doubly-linked list implementation of the List interface. May provide better performance than the ArrayList implementation if elements are frequently inserted or deleted within the list. Can be used as a double-ended queue (deque). Also implements the Queue interface. When accessed via the Queue interface, LinkedList behaves as a FIFO queue.
Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (including null). In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue (deque).
Note that this implementation is not synchronized.
HashMap implements Map - Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
Note that this implementation is not synchronized.
TreeMap implements SortedMap - Red-black tree based implementation of the SortedMap interface. This class guarantees that the map will be in ascending key order, sorted according to the natural order for the key's class (see Comparable), or by the comparator provided at creation time, depending on which constructor is used.
Note that this implementation is not synchronized.
LinkedHashMap extends HashMap implements Map - Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
Note that this implementation is not synchronized.
Summary of legacy implementations
Vector implements List, RandomAccess - Synchronized resizable-array implementation of the List interface with additional "legacy methods."
The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created.
Unlike the new collection implementations, Vector is synchronized
Hashtable implements Map - Synchronized hash table implementation of the Map interface that DOES NOT allow null keys or values, with additional "legacy methods."
To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method.
Unlike the new collection implementations, Hashtable is synchronized
Ordering
Comparable - This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method.
Lists (and arrays) of objects that implement this interface can be sorted automatically by Collections.sort (and Arrays.sort). Objects that implement this interface can be used as keys in a sorted map or elements in a sorted set, without the need to specify a comparator.
package java.lang;
public interface Comparable<T> {
/**
* Compares this object with the specified object for order. Returns a
* negative integer, zero, or a positive integer as this object is less
* than, equal to, or greater than the specified object.
*/
public int compareTo(T o);
}
Comparator - Represents an order relation, which may be used to sort a list or maintain order in a sorted set or map. Can override a type's natural ordering, or order objects of a type that does not implement the Comparable interface.
A comparison function, which imposes a total ordering on some collection of objects. Comparators can be passed to a sort method (such as Collections.sort) to allow precise control over the sort order. Comparators can also be used to control the order of certain data structures (such as TreeSet or TreeMap).
package java.util;
public interface Comparator<T> {
/**
* Compares its two arguments for order. Returns a negative integer,
* zero, or a positive integer as the first argument is less than, equal
* to, or greater than the second.
*/
int compare(T o1, T o2);
boolean equals(Object obj);
}