This page refers to Lists, Sets and Maps in the Java 2 platform. Their class hierarchy relative to the top level interfaces are as follows:
The table below was nicked from a JavaWorld.com article called Get started with the Java Collections Framework.
--- begin ---
Implementations | ||||||
---|---|---|---|---|---|---|
Hash Table
| Resizable Array
| Balanced Tree (Sorted)
| Linked List
| Legacy | ||
Interfaces
| Set
| HashSet
| *
| TreeSet
| *
| * |
List
| *
| ArrayList
| *
| LinkedList
| Vector | |
Map
| HashMap
| *
| TreeMap
| *
| Hashtable |
--- end ---
The next table is more comprehensive and was nicked from Wilson Mar, simply because it was the first detailed comparison table I found. Note that it's not the original source because it was a mess - I've tidied it up somewhat.
--- begin ---
There are several implementations of the Collection concept.
Collection Interface | New Class | Usage | Arguments & Additional Methods |
---|---|---|---|
List is an ordered collection of objects. (has a positional index), so it can have duplicate objects. List overloads add() with add(int, Object) and addAll( collectionC ) to insert objects at the specified index. |
ArrayList |
extends AbstractList for a resizable Random Access array that's not synchronized. Cloneable. |
constructor argument can be a collection or int Capacity, also in ensureCapacity()
|
Vector |
expandable array of sequenced objects. Modified to implement Collection. Synchronized. |
||
Stack |
A form of Vector to push LIFO (Last-In, First-Out) pop |
||
LinkedList |
extends AbstractSequentialList so each element references the next and previous element to emulate Stack, queue, and other end-oriented data structures. This doubly linked chain of objects speeds inserts/deletes but slow indexing. |
Use xxxFirst() to add, get, or remove at the beginning and xxxLast() at the end. |
|
Sets are unordered and so cannot contain duplicates of the same element. Implemented by the HashSet class. The Set interface does not define additional methods of its own. |
TreeSet implements SortedSet. Its constructor argument can be a collection, Comparator, or Sorted Set. |
a sorted binary tree of objects stored in ascending order. Does not allow duplicates. Cloneable. |
|
HashSet |
Unsorted, so no duplicates or null values. Cloneable. |
constructor argument capacity of elements plus a fillRatio between 0.0 and 1.0. |
|
LinkedHashSet |
New to 1.4. Extends HashSet for insertion-order iterations. |
||
Maps store objects based on the values of unique key-value associations between objects (such as IP addresses to domain names (DNS), keys to database records, or dictionary words to their definitions). A map can store duplicate objects, but not with duplicate keys. It replaces the Dictionary class deprecated in 1.2. The Map interface does not extend the Collection interface. It is implemented by classes HashTable and HashMap.
|
TreeMap implements SortedMap |
stores objects in an ascending order of their keys, so it automatically sorts objects to the default Comparator. |
|
HashMap |
reference by key. Not synchronized like Hashtable of Dictionary. Allows nulls. |
Uses .equals() to compare. |
|
WeakHashMap |
entry vanishes when its key is no longer reachable by any thread. 1.3 adds a constructor to accept a Map. |
||
IdentityHashMap |
New to 1.4. |
Uses the == operator instead of equals() method to compare. |
--- end ---
Also see
- Introduction to the Collections Framework, from Sun.