Java Collection Framework

As early as before Java 2, Java provided ad hoc classes. For example: Dictionary, Vector, Stack, and Properties, these classes were used to store and manipulate groups of objects.

Although these classes are very useful, they lack a core, unified theme. For this reason, the way to use the Vector class is quite different from the way to use the Properties class.

The collection framework was designed to meet the following goals.

  • The framework must be high-performance. The implementations of basic collections (dynamic arrays, linked lists, trees, hash tables) must also be efficient.

  • The framework allows different types of collections to work in a similar manner, with a high degree of interoperability.

  • Extensions and adaptations of a collection must be simple.

To this end, the entire collection framework is designed around a set of standard interfaces. You can directly use the standard implementations of these interfaces, such as:LinkedList, HashSet, andTreeSet, etc. In addition, you can also implement your own collections through these interfaces.

From the collection framework diagram above, it can be seen that the Java collection framework mainly includes two types of containers: one is Collection, which stores a collection of elements; the other is Map, which stores key/value pair mappings. The Collection interface has 3 subtypes: List, Set, and Queue. Below these are some abstract classes, and finally concrete implementation classes. Commonly used ones includeArrayList、LinkedList、HashSet、LinkedHashSet、HashMap, LinkedHashMap, and so on.

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

  • Interfaces:

    These are abstract data types that represent collections. For example: Collection, List, Set, Map, etc. The reason multiple interfaces are defined is to manipulate collection objects in different ways.

  • Implementations (classes):These are concrete implementations of the collection interfaces. In essence, they are reusable data structures, for example: ArrayList, LinkedList, HashSet, HashMap.

  • Algorithms:These are some useful computations performed by methods in objects that implement collection interfaces, for example: searching and sorting. These algorithms achieve polymorphism because the same method can have different implementations on similar interfaces.

In addition to collections, the framework also defines several Map interfaces and classes. Maps store key/value pairs. Although Maps are not collections, they are fully integrated into collections.

The collection framework system is shown in the figure below.

The Java collection framework provides a set of high-performance, easy-to-use interfaces and classes. The Java collection framework is located in the java.util package, so you need to import the package when using the collection framework.

Collection Interfaces

The collection framework defines some interfaces. This section provides an overview of each interface:

No. Interface Description
1 Collection Interface

Collection is the most basic collection interface. A Collection represents a group of Objects, i.e., the elements of the Collection. Java does not provide classes that directly inherit from Collection; it only provides subinterfaces that inherit from it (such as List and Set).

The Collection interface stores a group of non-unique, unordered objects.
2 List Interface

The List interface is an ordered Collection. With this interface, you can precisely control the position where each element is inserted, and access elements in the List by index (the position of the element in the List, similar to an array subscript). The first element has an index of 0, and duplicate elements are allowed.

The List interface stores a group of non-unique, ordered (insertion order) objects.
3 Set

Set has exactly the same interface as Collection, but behaves differently; Set does not store duplicate elements.

The Set interface stores a group of unique, unordered objects.
4 SortedSet
Inherits from Set and stores an ordered collection.
5 Map

The Map interface stores a group of key-value objects and provides a mapping from key to value.
6 Map.Entry
Describes an element (key/value pair) in a Map. It is an inner interface of Map.
7 SortedMap
Inherits from Map, keeping keys in ascending order.
8 Enumeration
This is a legacy interface and defined methods through which elements in a collection of objects can be enumerated (obtained one at a time). This legacy interface has been replaced by iterators.

Differences between Set and List

  • 1. Instances of the Set interface store unordered, non-duplicate data. Instances of the List interface store ordered, repeatable elements.

  • 2. Set has low retrieval efficiency but high deletion and insertion efficiency; insertion and deletion will not cause element position changes.<Implementation classes include HashSet, TreeSet>。

  • 3. List is similar to an array and can grow dynamically; the length of the List automatically increases according to the length of the actually stored data. It has high efficiency in finding elements and low efficiency in insertion and deletion, because it causes position changes of other elements.<Implementation classes include ArrayList, LinkedList, Vector> 。

Collection Implementation Classes (Collection Classes)

Java provides a set of standard collection classes that implement the Collection interface. Some of these are concrete classes and can be used directly, while others are abstract classes that provide partial implementations of the interface.

The standard collection classes are summarized in the following table:

No. Class Description
1 AbstractCollection 
Implements most of the collection interfaces.
2 AbstractList 
Inherits from AbstractCollection and implements most of the List interface.
3 AbstractSequentialList 
Inherits from AbstractList and provides chained access to data elements rather than random access.
4 LinkedList

This class implements the List interface and allows null elements. It is mainly used to create linked list data structures. This class has no synchronized methods. If multiple threads access a List simultaneously, you must implement access synchronization yourself. The solution is to construct a synchronized List when creating the List. For example:

List list=Collections.synchronizedList(newLinkedList(...));

LinkedList has low lookup efficiency.
5 ArrayList

This class also implements the List interface and implements a variable-size array, providing better performance when randomly accessing and traversing elements. This class is also non-synchronized and should not be used in multi-threaded situations. ArrayList grows by 50% of its current length, and insertion/deletion efficiency is low.
6 AbstractSet 
Inherits from AbstractCollection and implements most of the Set interface.
7 HashSet

This class implements the Set interface. Duplicate elements are not allowed, the order of elements in the set is not guaranteed, and elements with a value of null are allowed, but at most one.
8 LinkedHashSet
Has a predictable iteration orderSetThe hash table and linked list implementation of the interface.
9 TreeSet

This class implements the Set interface and can implement sorting and other functions.
10 AbstractMap 
Implements most of the Map interface.
11 HashMap
HashMap is a hash table; its stored content is key-value pair mappings.
This class implements the Map interface, stores data according to the HashCode value of the key, has very fast access speed, allows at most one record with a null key, and does not support thread synchronization.
12 TreeMap
Inherits from AbstractMap and uses a tree.
13 WeakHashMap
Inherits the AbstractMap class and uses a hash table with weak keys.
14 LinkedHashMap
Inherits from HashMap and sorts elements using their natural order.
15 IdentityHashMap
Inherits the AbstractMap class and uses reference equality when comparing documents.

Earlier in the tutorial, the classes defined in the java.util package have been discussed, as shown below:

No. Class Description
1 Vector

This class is very similar to ArrayList, but this class is synchronized and can be used in multi-threaded situations. This class allows setting the default growth length, and the default expansion method is 2 times the original.
2 Stack
Stack is a subclass of Vector; it implements a standard last-in, first-out stack.
3 Dictionary
The Dictionary class is an abstract class used to store key/value pairs, and its function is similar to the Map class.
4 Hashtable

Hashtable is a subclass of the Dictionary class and is located in the java.util package.
5 Properties
Properties inherits from Hashtable and represents a persistent set of properties. In the property list, each key and its corresponding value are strings.
6 BitSet
A BitSet class creates a special type of array to hold bit values. The size of the array in BitSet will increase as needed.

Collection Algorithms

The collection framework defines several algorithms that can be used on collections and maps. These algorithms are defined as static methods of collection classes.

When attempting to compare incompatible types, some methods can throw a ClassCastException. When trying to modify an unmodifiable collection, an UnsupportedOperationException is thrown.

The collections define three static variables: EMPTY_SET, EMPTY_LIST, and EMPTY_MAP. These variables are all immutable.

Serial No. Algorithm Description
1 Collection Algorithms
Here is a list of all algorithm implementations.

How to Use Iterators

Usually, you will want to traverse the elements in a collection. For example, display each element in the collection.

Generally, traversing arrays uses a for loop or an enhanced for loop. These two methods can also be used in the collection framework, but there is another method that uses an iterator to traverse the collection framework. It is an object that implements theIteratorIterator interface or the ListIterator interface.

Iterators allow you to obtain or delete collection elements through a loop. ListIterator inherits Iterator to allow bidirectional traversal of lists and modification of elements.

Serial No. Iterator Method Description
1 Using Java Iterator
Here, through examples, all methods provided by the Iterator and ListIterator interfaces are listed.

Traversing ArrayList

Example

import java.util.*; public class Test{ public static void main(String[] args) { List<String> list=new ArrayList<String>(); list.add("Hello"); list.add("World"); list.add("HAHAHAHA"); //The first traversal method uses For-Each to traverse the List. for (String str : list) { //It can also be rewritten in the form for(int i=0;i<list.size();i++) System.out.println(str); } //The second traversal converts the list into an array-related content for traversal. String[] strArray=new String[list.size()]; list.toArray(strArray); for(int i=0;i<strArray.length;i++) //It can also be rewritten in the form for(String str:strArray) { System.out.println(strArray[i]); } //The third traversal uses an iterator for the relevant traversal. Iterator<String> ite=list.iterator(); while(ite.hasNext())//Determine whether there is a value after the next element. { System.out.println(ite.next()); } } }

Analysis:

All three methods are used to traverse the ArrayList collection. The third method uses an iterator, which avoids worrying about exceeding the length of the collection during traversal.

Traversing Map

Example

import java.util.*; public class Test{ public static void main(String[] args) { Map<String, String> map = new HashMap<String, String>(); map.put("1", "value1"); map.put("2", "value2"); map.put("3", "value3"); //First: commonly used, retrieve the value a second time. System.out.println("Traverse key and value through Map.keySet:"); for (String key : map.keySet()) { System.out.println("key= "+ key + " and value= " + map.get(key)); } //Second System.out.println("Use iterator through Map.entrySet to traverse key and value:"); Iterator<Map.Entry<String, String>> it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry<String, String> entry = it.next(); System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue()); } //Third: recommended, especially when the capacity is large. System.out.println("Traverse key and value through Map.entrySet"); for (Map.Entry<String, String> entry : map.entrySet()) { System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue()); } //Fourth System.out.println("Traverse all values through Map.values(), but cannot traverse keys."); for (String v : map.values()) { System.out.println("value= " + v); } } }

How to Use Comparators

TreeSet and TreeMap store elements in sorted order. However, it is a comparator that precisely defines what sort order is used.

This interface allows us to sort a collection in different ways.

Serial No. Comparator Method Description
1 Using Java Comparator
Here, through examples, all methods provided by the Comparator interface are listed.

Summary

The Java collections framework provides programmers with pre-packaged data structures and algorithms to manipulate them.

A collection is an object that can hold references to other objects. The collection interfaces declare the operations that can be performed on each type of collection.

The classes and interfaces of the collections framework are all in the java.util package.

After any object is added to a collection class, it is automatically converted to the Object type, so when it is retrieved, a forced type conversion is required.

Other Extensions