The Java Tutorials have been written for JDK 8. Examples and practices described in this page don't take advantage of improvements introduced in later releases and might use technology no longer available.
SeeDev.java for updated tutorials taking advantage of the latest releases.
SeeJava Language Changes for a summary of updated language features in Java SE 9 and subsequent releases.
SeeJDK Release Notes for information about new features, enhancements, and removed or deprecated options for all JDK releases.

Lesson: Implementations

Implementations are the data objects used to store collections, which implement the interfaces described inthe Interfaces section. This lesson describes the following kinds of implementations:

• General-purpose implementations are the most commonly used implementations, designed for everyday use. They are summarized in the table titled General-purpose-implementations.
• Special-purpose implementations are designed for use in special situations and display nonstandard performance characteristics, usage restrictions, or behavior.
• Concurrent implementations are designed to support high concurrency, typically at the expense of single-threaded performance. These implementations are part of thejava.util.concurrent package.
• Wrapper implementations are used in combination with other types of implementations, often the general-purpose ones, to provide added or restricted functionality.
• Convenience implementations are mini-implementations, typically made available via static factory methods, that provide convenient, efficient alternatives to general-purpose implementations for special collections (for example, singleton sets).
• Abstract implementations are skeletal implementations that facilitate the construction of custom implementations — described later in theCustom Collection Implementations section. An advanced topic, it's not particularly difficult, but relatively few people will need to do it.

The general-purpose implementations are summarized in thefollowing table.

As you can see from the table, the Java Collections Framework provides several general-purpose implementations of theSet,List , andMap interfaces. In each case, one implementation —HashSet,ArrayList, andHashMap — is clearly the one to use for most applications, all other things being equal. Note that theSortedSet and theSortedMap interfaces do not have rows in the table. Each of those interfaces has one implementation(TreeSet andTreeMap) and is listed in theSet and theMap rows. There are two general-purposeQueue implementations —LinkedList, which is also aList implementation, andPriorityQueue, which is omitted from the table. These two implementations provide very different semantics:LinkedList provides FIFO semantics, whilePriorityQueue orders its elements according to their values.

Each of the general-purpose implementations provides all optional operations contained in its interface. All permitnull elements, keys, and values. None are synchronized (thread-safe). All havefail-fast iterators, which detect illegal concurrent modification during iteration and fail quickly and cleanly rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. All areSerializable and all support a publicclone method.

The fact that these implementations are unsynchronized represents a break with the past: The legacy collectionsVector andHashtable are synchronized. The present approach was taken because collections are frequently used when the synchronization is of no benefit. Such uses include single-threaded use, read-only use, and use as part of a larger data object that does its own synchronization. In general, it is good API design practice not to make users pay for a feature they don't use. Furthermore, unnecessary synchronization can result in deadlock under certain circumstances.

If you need thread-safe collections, the synchronization wrappers, described in theWrapper Implementations section, allowany collection to be transformed into a synchronized collection. Thus, synchronization is optional for general-purpose implementations, whereas it is mandatory for legacy implementations. Moreover, thejava.util.concurrent package provides concurrent implementations of theBlockingQueue interface, which extendsQueue, and of theConcurrentMap interface, which extendsMap. These implementations offer much higher concurrency than mere synchronized implementations.

As a rule, you should be thinking about the interfaces,not the implementations. That is why there are no programming examples in this section. For the most part, the choice of implementation affects only performance. The preferred style, as mentioned in theInterfaces section, is to choose an implementation when aCollection is created and to immediately assign the new collection to a variable of the corresponding interface type (or to pass the collection to a method expecting an argument of the interface type). In this way, the program does not become dependent on any added methods in a given implementation, leaving the programmer free to change implementations anytime that it is warranted by performance concerns or behavioral details.

The sections that follow briefly discuss the implementations. The performance of the implementations is described using words such asconstant-time,log,linear,n log(n), andquadratic to refer to the asymptotic upper-bound on the time complexity of performing the operation. All this is quite a mouthful, and it doesn't matter much if you don't know what it means. If you're interested in knowing more, refer to any good algorithms textbook. One thing to keep in mind is that this sort of performance metric has its limitations. Sometimes, the nominally slower implementation may be faster. When in doubt, measure the performance!