Java collections

Java Collections are one of the pillars of the Java Core. They are used in almost every application, so we simply must be able to use the Java Collections Framework effectively.

What are Collections?

Collections are containers, groups of elements that constitute a unit.

For example: a candy pot, a list of names, etc. Collections are used in almost every programming language and Java is no exception. As soon as the collections appeared in Java, there were only a few classes: Vector, Stack, Hashtable, Array. But already in Java 1.2, a full-fledged Java Collections Framework appeared, with which we will get acquainted today.

Java collections consist of several parts.

• Interfaces: In collections, interfaces provide an abstract data type for representing the java.util.Collection collection - the framework root interface. It is at the top of the collections hierarchy. It contains the most important methods: size() , iterator() , add() , remove() , clear() . Each collection must implement these methods. There are also other important interfaces java.util.List, java.util.Set, java.util.Queue and java.util.Map . Map is the only interface that does not inherit the Collection interface, but is an integral part of collections. All framework interfaces are in the java.util package.
• Implementation: Java provides ready-made classes with the implementation of the above collections. We can use them to create new types of collections in our program. With the ArrayList, LinkedList, HashMap, TreeMap, HashSet, TreeSet you can solve a huge number of tasks, but if we need a special implementation of a particular collection, we can inherit it and work with our implementation. In Java 1.5, thread-safe collections were invented that allowed us to change the contents of the collection while iterating over the elements. The most popular are: CopyOnWriteArrayList, ConcurrentHashMap, CopyOnWriteArraySet . These classes are in the java.util.concurrent package. All collection classes are in the java.util and java.util.concurrent packages.
• Algorithms: Algorithms are useful methods that solve trivial tasks, for example: searching, sorting and shuffling elements of a collection.
• The class diagram below shows the Java Collections Framework hierarchy. For simplicity, I have included only frequently used interfaces and classes.

Benefits of the Java Collections Framework

The Java Collections Framework has the following benefits:

• Requires less effort. The framework has many common types of collections and useful methods for manipulating data. Thus, we can focus on business logic, rather than developing our APIs.
• Excellent quality - the use of well-proven collections increases the quality of our program.
• Reuse and compatibility

Collection interfaces

Interfaces are the foundation of the Java Collections Framework. Note that all interfaces are Generic, for example, public interface Collection . The use of is an indication of the type of object that the collection may contain. This helps to reduce runtime errors by checking the types of objects at compile time.

It should be noted that the Java platform does not provide separate interfaces for each type of collection. If an operation is not supported, then the collection implementation throws UnsupportedOperationException.

Briefly for each collection

Iterator Interface (Iterator)

The iterator provides methods for iterating over elements of any collection. We can get an instance of an iterator from the collection using the iterator method. Iterators allow you to remove items from the base collection while iterating.

Set Interface

A collection is a collection that cannot contain duplicate elements. This interface represents a mathematical abstraction for representing sets in the form of a deck of cards.

The Java platform contains three Set implementations: HashSet, TreeSet and LinkedHashSet.И And the Set interface does not allow random access to an item in the collection. We can use an iterator or loop for each element to iterate over the elements.

Interface List (List)

The list is an ordered set of elements and may contain duplicate elements. You can access any item by index. The list is a dynamic array. The list is one of the most used types of collections. ArrayList and LinkedList classes are implementations of the List interface.

Here is a small example of use:

Interface Queue

A queue is a collection that is used to store multiple items.

In the queue, usually, but not necessarily, the elements are arranged according to the FIFO principle (first-in, first-out = first entered, first left). In the FIFO queue, all new items are inserted at the end of the queue.

Interface dequeue

The Dequeue collection supports inserting an element and deleting an element both at the beginning and at the end of the collection. The name Deque is an abbreviation for “double-end” and, as a rule, is pronounced “deck”. Most of the implementations of DEQUE do not set limits on the number of elements.

This interface defines methods for accessing elements at the ends of the deck. Methods are provided for inserting, deleting, retrieving an item.

Map Interface

A map is an object that contains keys and values. Map cannot contain duplicate keys: Each key can have only one value.

The Java platform contains three Map implementations: HashMap, TreeMap and LinkedHashMap.

Interface listiterator

ListIterator (an iterator for lists) allows the programmer to go through the list in any direction, change the list in the iteration, and get the current position of the iterator in the list.

SortedSet interface

SortedSet is a set in which elements are stored in ascending order.

SortedMap interface

SortedMap contains items in ascending order of keys. This Map is an analogue of SortedSet. SortedMap is used for naturally ordered key / value pairs, such as dictionaries and telephone directories.

Classes implementing Java collections

The Java Collections framework provides a large number of classes with implementation of collection interfaces. The most used and common implementations are ArrayList , HashMap and HashSet . Typically, classes that implement collections are not thread-safe.

Later in this article we will examine the most used classes in the Java Collections framework.

HashSet Class

This is the basic implementation of the Set interface, which is based on a HashMap .

This class offers the same execution time for basic operations (add, remove , contains и size ) . We can set the initial capacity and load factor for this collection.

Class treeset

NavigableSet is based on TreeMap. Elements can be ordered in the order they are added or using a comparator.

This implementation provides log (n) execution time for basic operations ( add, remove and contains ).

Class ArrayList

ArrayList - the implementation of the List interface as a variable-length array. Implements all list operations. Plus, ArrayList provides methods for manipulating the size of the array, which is used to store the list. (This class roughly corresponds to a vector, but is not synchronized ).

LinkedList class

LinkedList - the implementation of the List and Deque interfaces in the form of a doubly linked list. Performs all additional operations with the list.

Class HashMap

HashMap is an implementation of the Map interface. This implementation provides all additional Map operations and allows null values ​​and keys with a null value. The HashMap class is roughly equivalent to Hashtable , except that it is not synchronized and allows null . This class makes no guarantees for the orderly placement of items.

Class treemap

TreeMap is a red-black tree based on NavigableMap. Map sorted by comparator.

This implementation provides log (n) execution time for the containsKey, get, put and remove operations.

PriorityQueue class

Queuing elements are given in the FIFO order, but sometimes we want to add elements based on their priority. In this case, we can use PriorityQueue, while providing a implementation of the comparator for PriorityQueue elements. It should be noted that PriorityQueue does not allow storing null

Collections class

This class consists solely of static methods that work or return collections. It contains polymorphic algorithms that are used when working with collections.

This class contains the methods of the basic algorithms of the framework framework, namely the methods of binary search, sorting, mixing, as well as a method that returns the reverse order of elements and many others.

Synchronized shells

Synchronized shells add automatic synchronization (thread-safe) to a specific collection. Each of the six main collection interfaces ( Collection, Set, List, Map, SortedSet , and SortedMap ) has a static factory synchronization method.

Each of these methods returns a synchronized (thread-safe) collection.

Immutable shells

Immutable wrappers / wrappers do not allow changing the collection, intercepting all operations that change collections and throw an UnsupportedOperationException in the event that someone wants to do this. These methods are:

Which collection to choose?

This question is often asked by programmers when choosing between the many collections represented in the Java Collections Framework. Below is a table that contains all the most significant characteristics of the collections:

In this review, we learned the basic components of the Java Collections Framework. In the following articles, we will analyze popular collections and learn how to use each collection as intended.