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 interfacesjava.util.List,
java.util.Set,
java.util.Queue
andjava.util.Map
.Map
is the only interface that does not inherit theCollection
interface, but is an integral part of collections. All framework interfaces are in thejava.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
.
java.util.concurrent
package. All collection classes are in thejava.util
andjava.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:
1
2
3
4
5
6
7
8
9
|
List strList = new ArrayList<>();
//добавить в конец
strList.add(0, "0");
//добавить элемент в определенное место
strList.add(1, "1");
//заменить элемент
strList.set(1, "2");
//удалить элемент
strList.remove("1");
|
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.
1
2
3
4
5
6
|
public static Collection synchronizedCollection(Collection c);
public static Set synchronizedSet(Set s);
public static List synchronizedList(List list);
public static Map synchronizedMap(Map m);
public static SortedSet synchronizedSortedSet(SortedSet s);
public static SortedMap synchronizedSortedMap(SortedMap m);
|
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:
1
2
3
4
5
6
|
public static Collection unmodifiableCollection(Collection c);
public static Set unmodifiableSet(Set s);
public static List unmodifiableList(List list);
public static Map unmodifiableMap(Map m);
public static SortedSet unmodifiableSortedSet(SortedSet s);
public static SortedMap unmodifiableSortedMap(SortedMap m);
|
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:
Collection | Okay
chivy |
Random access | Key value | Duplicate Items | Zero element | Potoko
security |
ArrayList | Yes | Yes | Not | Yes | Yes | Not |
Linkedlist | Yes | Not | Not | Yes | Yes | Not |
Hashset | Not | Not | Not | Not | Yes | Not |
Treeset | Yes | Not | Not | Not | Not | Not |
Hashmap | Not | Yes | Yes | Not | Yes | Not |
Treemap | Yes | Yes | Yes | Not | Not | Not |
Vector | Yes | Yes | Not | Yes | Yes | Yes |
Hashtable | Not | Yes | Yes | Not | Not | Yes |
Properties | Not | Yes | Yes | Not | Not | Yes |
Stack | Yes | Not | Not | Yes | Yes | Yes |
CopyOnWriteArrayList | Yes | Yes | Not | Yes | Yes | Yes |
ConcurrentHashMap | Not | Yes | Yes | Not | Not | Yes |
CopyOnWriteArraySet | Not | Not | Not | Not | Yes | Yes |
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.
Comments
To leave a comment
Structures and data processing algorithms.
Terms: Structures and data processing algorithms.