Java Collections Framework Reference

This publication is not a complete parse or analysis (does not cover the java.util.concurrent package). Rather, it’s a handbook that will help novice developers understand the key differences between some collections and others, and more experienced developers simply refresh the memory.

What is the Java Collections Framework?

Java Collection Framework is a hierarchy of interfaces and their implementations, which is part of the JDK and allows the developer to use a large number of data structures from the "box".

Basic concepts

At the top of the hierarchy in the Java Collection Framework are 2 interfaces: Collection and Map . These interfaces separate all collections included in the framework into two parts according to the type of data storage: simple sequential sets of elements and sets of key-value pairs (dictionaries).
')


Collection - this interface is included in the JDK c version 1.2 and defines the basic methods of working with simple sets of elements that will be common to all its implementations (for example, size() , isEmpty() , add(E e) , etc.). The interface was slightly refined with the arrival of generics in Java 1.5. Also, in Java 8, several new methods were added for working with lambdas (such as stream() , parallelStream() , removeIf(Predicate<? super E> filter) , etc.).

It is also important to note that these methods were implemented directly in the interface as default medodes.

Map . This interface is also included in the JDK c version 1.2 and provides the developer with basic methods for working with key-value data. Like the Collection , it was supplemented with generics in Java 1.5 and in the Java 8 version additional methods for working with lambdas, as well as methods that were often implemented in the application logic ( getOrDefault(Object key, V defaultValue) , putIfAbsent(K key, V value) ).

Interface Map [ doc ]

Hashtable - the implementation of such a data structure as a hash table. It does not allow null to be used as a value or key. This collection was implemented earlier than the Java Collection Framework, but was later included in its composition. Like other collections from Java 1.0, Hashtable is synchronized (almost all methods are marked as synchronized ). Because of this feature, it has significant performance problems and, starting with Java 1.2, in most cases it is recommended to use other implementations of the Map interface due to their lack of synchronization.

HashMap - the collection is an alternative to Hashtable . The two main differences from Hashtable are that HashMap not synchronized and HashMap allows you to use null as a key and as a value. Like Hashtable , this collection is not ordered: the order in which items are stored depends on the hash function. Adding an element is done in constant time O (1), but the time it takes to delete, to receive, depends on the distribution of the hash function. Ideally, it is constant, but it can also be linear O (n). More information about HashMap can be read here (relevant for Java <8).

LinkedHashMap is an ordered implementation of a hash table. Here, unlike HashMap , the order of iteration is equal to the order of adding elements. This feature is achieved through bidirectional links between elements (similar to LinkedList ). But this advantage also has a drawback - an increase in memory that the collection will occupy. More information is provided in this article .

TreeMap is a Map implementation based on red-black trees. Like LinkedHashMap is streamlined. By default, the collection is sorted by keys using the principle of " natural ordering ", but this behavior can be customized for a specific task using the Comparator object, which is specified as a parameter when creating the TreeMap object.

WeakHashMap is a hash table implementation that is organized using weak references . In other words, the Garbage Collector will automatically remove an item from the collection at the next garbage collection, if there are no hard links to the key of this item.

Interface List [ doc ]

Implementations of this interface are ordered collections. In addition, the developer is given the opportunity to access the elements of the collection by index and by value (since implementations allow storing duplicates, the search by value will be the first occurrence found).

Vector - implementation of a dynamic array of objects. Allows you to store any data, including null as an element. Vector appeared in the JDK version of Java 1.0, but, like Hashtable , this collection is not recommended, unless thread safety is required. Because in the Vector , unlike other implementations of the List , all data operations are synchronized. As an alternative, the analogue is often used - ArrayList .

Stack - this collection is an extension of the Vector collection. It was added to Java 1.0 as an implementation of the LIFO stack (last-in-first-out). It is a partially synchronized collection (except for the push() addition method). After adding the Deque interface to Java 1.6, it is recommended to use implementations of this interface, for example, ArrayDeque .

ArrayList - like Vector is an implementation of a dynamic array of objects. Allows you to store any data, including null as an element. As the name suggests, its implementation is based on a regular array. This implementation should be used if in the process of working with a collection, frequent access to the elements by index is suggested. Due to the nature of the implementation, an indexing call to the elements is performed in a constant time O (1). But this collection is recommended to be avoided if frequent removal / addition of elements in the middle of the collection is required. A detailed analysis and description can be found in this habratopic.

LinkedList is another implementation of the List . Allows you to store any data, including null . A feature of the implementation of this collection is that it is based on a bidirectional linked list (each element has a link to the previous and next). Due to this, addition and removal from the middle, access by index, value occurs in linear time O (n), and from the beginning and end beyond the constant O (1). Also, due to the implementation, this collection can be used as a stack or a queue. To do this, it implemented the appropriate methods. On Habré also there is an article with a detailed analysis and description of this collection.

Interface Set [ doc ]

It is an unordered collection that cannot contain duplicate data. It is a program model of the mathematical concept of "set."

HashSet is a Set interface implementation based on a HashMap . Inside it uses a HashMap object to store data. The key to be used is the added element, and the value is the dummy object (new Object ()). Due to the nature of the implementation, the order of the elements is not guaranteed when added.

LinkedHashSet - differs from HashSet only in that it is based on LinkedHashMap instead of HashSet . Due to this difference, the order of elements when traversing a collection is identical to the order of adding elements.

TreeSet - similar to other implementation classes of the Set interface, contains the NavigableMap object, which determines its behavior. Provides the ability to control the order of items in a collection using the Comparator object, or save items using " natural ordering ".

Interface Queue [ doc ]

This interface describes collections with a predefined way of inserting and extracting elements, namely the FIFO (first-in-first-out) queue. In addition to the methods defined in the Collection interface, it defines additional methods for extracting and adding items to the queue. Most implementations of this interface are in the java.util.concurrent package and are discussed in detail in this review.

PriorityQueue - is the only direct implementation of the Queue interface (it was added, like the Queue interface, in Java 1.5), not counting the LinkedList class, which also implements this interface, but was implemented much earlier. A feature of this queue is the ability to control the order of the elements. By default, items are sorted using “natural ordering”, but this behavior can be overridden using the Comparator object, which is set when the queue is created. This collection does not support null as items.

ArrayDeque is an implementation of the Deque interface, which extends the Queue interface with methods that allow you to implement a LIFO view (last-in-first-out). The Deque interface and the ArrayDeque implementation were added in Java 1.6. This collection is an implementation using arrays, like an ArrayList , but does not allow accessing elements by index and storing null . As stated in the documentation, the collection is faster than the Stack if it is used as a LIFO collection, and also faster than LinkedList if it is used as a FIFO.

Conclusion

The Java Collections Framework contains a large number of different data structures available in the out-of-the-box JDK, which in most cases cover all needs when implementing application logic. Comparison of the temporal characteristics of the main collections, which are often used in application development, is given in the table below:



If necessary, the developer can create his own implementation by expanding or redefining the existing logic, or by creating his own implementation of a suitable interface from scratch. There are also a number of ready-made solutions that are an alternative or addition to the Java Collections Framework. The most popular are Google Guava and Commons Collections .

In addition, I would like to indicate, as an additional material, a link to the review of the java.util.concurrent package. Which is a great addition to the stated material.