Java Collections Framework Reference

This publication is not a complete analysis or analysis (does not cover the package java.util.concurrent). Rather, it is a guide that will help novice developers understand the key differences of some collections from others, and more experienced developers will simply refresh the material in memory.

What is the Java Collections Framework?

Java Collection Framework - 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 out of the box.

Basic concepts

At the top of the hierarchy in the Java Collection Framework are 2 interfaces: Collectionand Map. These interfaces divide all the 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 a part of the JDK version 1.2 c and defines the basic methods of work with a simple set of elements that will be common to all of its implementations (eg size(), isEmpty(), add(E e)etc.). The interface has been slightly modified with the advent of generics in Java 1.5. As in the Java version 8 was added several new methods for working with lambdas (such as stream(), parallelStream(), removeIf(Predicate filter)et al.).

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

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

Map Interface [ doc ]

Hashtable is an implementation of a data structure such as a hash table. It does not allow usenullas 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, itHashtableis synchronized (almost all methods are marked assynchronized). 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 interfaceMapdue to their lack of synchronization.

HashMap - The collection is an alternativeHashtable. The two main differences fromHashtablewhat isHashMapnot synchronized andHashMapallows you to usenullboth as a key and as a value. As well Hashtable, this collection is not ordered: the storage order of elements depends on the hash function. Adding an element is performed in constant time O (1), but the time of deleting, receiving, depends on the distribution of the hash function. Ideally, it is constant, but it can be linear O (n). More information about HashMapcan be read here (relevant for Java <8).

LinkedHashMap is an ordered hash table implementation. Here, in contrast to HashMap, the iteration order is equal to the order of adding elements. This feature is achieved through bidirectional connections between elements (similarlyLinkedList) But this advantage also has a drawback - the increase in memory occupied by the collection. For more information, see this article .

TreeMap is an implementation Mapbased on red-black trees. As it LinkedHashMapis ordered. By default, the collection is sorted by key using the principle of " natural ordering ", but this behavior can be customized for a specific task using the object Comparator, which is specified as a parameter when creating the object TreeMap.

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

List interface [ 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 you to store duplicates, the search result 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. VectorIntroduced in the Java 1.0 JDK, but, like Hashtable, this collection is not recommended if thread safety is not required. Because in Vector, unlike other implementations List, all data operations are synchronized. As an alternative, the analogue is often used - ArrayList.

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

ArrayList - likeVector 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, during the work with the collection, frequent access to elements by index is suggested. Due to implementation features, index-based access to elements is performed in constant time O (1). But this collection is recommended to be avoided if frequent removal / addition of elements to the middle of the collection is required. A detailed analysis and description can be found in this habratopika.

LinkedList is another implementation List. Allows you to store any data, includingnull. 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, adding and removing from the middle, access by index, value occurs in linear time O (n), and from the beginning and end for constant O (1). Also, in view of the implementation, this collection can be used as a stack or queue. For this, appropriate methods are implemented in it. There is also an article on Habré 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 software model of the mathematical concept of "multitude."

HashSet is an interface implementation Setbased on HashMap. Internally uses a HashMap object to store data. The added item is used as the key, and the dummy object (new Object ()) is used as the value. Due to the nature of the implementation, the order of the elements is not guaranteed when added.

LinkedHashSet - differs from HashSetonly in that it is based on LinkedHashMapinstead HashSet. Due to this difference, the order of elements when traversing a collection is identical to the order in which elements are added.

TreeSet - similar to other interface implementation classesSetcontains the object NavigableMap, which determines its behavior. Provides the ability to control the order of elements in a collection using an object Comparator, or saves elements using " natural ordering ".

Queue Interface [ doc ]

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

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

ArrayDeque - implementation of the Deque interface , which extends the interface with Queuemethods that allow you to implement a design of the form LIFO (last-in-first-out). Interface Deque and implementation ArrayDeque were added in Java 1.6. This collection is an implementation using arrays, likeArrayListbut does not allow access to items by index and storage null. As stated in the documentation, the collection is faster than Stackif used as a LIFO collection, and also faster than LinkedList if used as a FIFO.

Conclusion

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



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 additional material, a link to the package review java.util.concurrent. Which is a great addition to the material presented.