Java Collections Framework

What Is a Collections Framework?

A collections framework is a unified architecture for representing and manipulating collections. All collections frameworks contain the following:

• Interfaces: These are abstract data types that represent collections. Interfaces allow collections to be manipulated independently of the details of their representation. In object-oriented languages, interfaces generally form a hierarchy.
• Implementations: These are the concrete implementations of the collection interfaces. In essence, they are reusable data structures.
• Algorithms: These are the methods that perform useful computations, such as searching and sorting, on objects that implement collection interfaces. The algorithms are said to be polymorphic: that is, the same method can be used on many different implementations of the appropriate collection interface. In essence, algorithms are reusable functionality.

Interfaces

The core collection interfaces encapsulate different types of collections, which are shown in the figure below. These interfaces allow collections to be manipulated independently of the details of their representation. Core collection interfaces are the foundation of the Java Collections Framework. As you can see in the following figure, the core collection interfaces form a hierarchy.

The core collection interfaces.

Note that all the core collection interfaces are generic. For example, this is the declaration of the Collection interface.

public interface Collection<E>...

The <E> syntax tells you that the interface is generic. When you declare a Collection instance you can and should specify the type of object contained in the collection. Specifying the type allows the compiler to verify (at compile-time) that the type of object you put into the collection is correct, thus reducing errors at runtime. For information on generic types, see the Generics (Updated) lesson.

Summary of Interfaces

The core collection interfaces are the foundation of the Java Collections Framework.

The Java Collections Framework hierarchy consists of two distinct interface trees:

• The first tree starts with the Collection interface, which provides for the basic functionality used by all collections, such as add and remove methods. Its subinterfaces — Set, List, and Queue — provide for more specialized collections.

• The Set interface does not allow duplicate elements. This can be useful for storing collections such as a deck of cards or student records. The Set interface has a subinterface, SortedSet, that provides for ordering of elements in the set.

• The List interface provides for an ordered collection, for situations in which you need precise control over where each element is inserted. You can retrieve elements from a List by their exact position.

• The Queue interface enables additional insertion, extraction, and inspection operations. Elements in a Queue are typically ordered in on a FIFO basis.

• The Deque interface enables insertion, deletion, and inspection operations at both the ends. Elements in a Deque can be used in both LIFO and FIFO.

• The second tree starts with the Map interface, which maps keys and values similar to a Hashtable.

• Map's subinterface, SortedMap, maintains its key-value pairs in ascending order or in an order specified by a Comparator.

These interfaces allow collections to be manipulated independently of the details of their representation.

Summary of Implementations

The Java Collections Framework provides several general-purpose implementations of the core interfaces:

• For the Set interface, HashSet is the most commonly used implementation.

• For the List interface, ArrayList is the most commonly used implementation.

• For the Map interface, HashMap is the most commonly used implementation.

• For the Queue interface, LinkedList is the most commonly used implementation.

• For the Deque interface, ArrayDeque is the most commonly used implementation.

Each of the general-purpose implementations provides all optional operations contained in its interface.

Java™ Platform, Standard Edition 7 API Specification

package java.util;

Comparison of Collection Comparison of Lists
	ArrayList	LinkedList
Description	Dynamic (a.k.a. growable, resizable) array	Doubly-linked list
Random Access with index (get())	O(1)	O(n)
Insertion (add()) / removal at the back	amortized O(1)	O(1)
Insertion / removal at the front	O(n)	O(1)
One step of iteration through an Iterator	O(1)	O(1)
Insertion / removal in the middle through an Iterator / ListIterator	O(n)	O(1)
Insertion / removal in the middle through the index	O(n)	O(n)
Search contains() / removal remove() by object	O(n)	O(n)

Comparison of Sets
	HashSet	TreeSet
Description	Hash table	Self-balancing binary search tree
Requirements	Objects need to implement a hash function (hashCode()) which is consistent with equals()	Either objects need to implement the Comparable interface and be able to compare to each other; or a Comparator for the objects must be provided; the ordering must satisfy a "total ordering"
Test for membership (contains())	O(1) average O(n) worst-case	O(log n)
Insertion (add()) / removal (remove())	O(1) average O(n) worst-case	O(log n)
One step of iteration through an Iterator	O(1)	O(1)
Iterates through elements in ascending order	No	Yes

Java Map Comparison :

• HashMap is the fastest map with O(1) search and insertion times.
• LinkedHashMap is a little slower for inserts, but maintains the insertion order.
• TreeMap is the slowest map, but lets you iterate over the keys in a sorted order.

Java - How to use Iterator?

Метод entrySet(), определенный в интерфейсе Map, позволят получить все элементы ассоциативного массива в виде множества объектов типа Map.Entry.

Map.Entry предоставляет три основных метода:

• getKey() — возвращает ключ элемента;
• getValue() — возвращает значение элемента;
• setValue(Object value) — меняет значение элемента.

Map<Integer, String> map = new HashMap<Integer, String>();

Map.Entry<Integer, String> entry;

for ( entry : map.entrySet()) {
Integer key = entry.getKey();
    String value = entry.getValue();
}