Java collections are toolkits provided by Java, which contain commonly used data structures: collections, linked lists, queues, stacks, arrays, maps, etc. The location of the Java collection toolkit is java.util.*
Java collections can be divided into 4 parts: List list, Set collection, Map map, tool classes (Iterator iterator, Enumeration enumeration class, Arrays and Collections).
The Java collection toolkit framework is shown below.
Note: Looking at the framework diagram above, first grasp its trunk, namely Collection and Map.
Collection is an interface, a highly abstract collection, which contains the basic operations and properties of the collection.
Collection includes two branches: List and Set.
(01) List is an ordered queue, and each element has its index. The index value of the first element is 0.
List implementation classes include LinkedList, ArrayList, Vector, Stack.
(02) Set is a collection that does not allow duplicate elements.
Set implementation classes include HastSet and TreeSet. HashSet relies on HashMap, which is actually implemented through HashMap; TreeSet relies on TreeMap, which is actually implemented through TreeMap.
Map is a mapping interface, namely key-value key-value pairs. Each element in the map contains "a key" and "a value corresponding to the key".
AbstractMap is an abstract class that implements most of the APIs in the Map interface. HashMap, TreeMap, and WeakHashMap are all inherited from AbstractMap.
Although Hashtable inherits from Dictionary, it implements the Map interface.
Next, let’s look at Iterator. It is a tool for traversing collections, that is, we usually traverse collections through Iterator iterator. We say that Collection depends on Iterator because the implementation classes of Collection must implement the iterator() function and return an Iterator object.
ListIterator exists specifically for traversing List.
Let’s look at Enumeration again, it is an abstract class introduced by JDK 1.0. Like Iterator, it is also traversing a collection; but Enumeration has less functions than Iterator. In the above block diagram, Enumeration can only be used in Hashtable, Vector, Stack.
Finally, look at Arrays and Collections. They are two tool classes that operate arrays and collections.
With the above overall framework, we will analyze each class separately.
Collection architecture
Below, we will summarize the Collection. Let’s take a look at the relationship diagrams of some framework classes in Collection:
Collection is an interface, and its main two branches are: List and Set.
List and Set are interfaces, and they inherit from Collection. List is an ordered queue, and there can be repeated elements in List; while Set is a collection in mathematical concepts, and there are no repeat elements in Set!
List and Set have their own implementation classes.
For easy implementation, the AbstractCollection abstract class is defined in the collection, which implements most functions in the Collection; in this way, in the Collection implementation class, we can save duplicate encoding by inheriting AbstractCollection. AbstractList and AbstractSet both inherit from AbstractCollection, the specific List implementation class inherits from AbstractList, and the Set implementation class inherits from AbstractSet.
In addition, there is an iterator() function in the Collection, which is used to return an Iterator interface. Usually, we traverse the collection through the Iterator iterator. ListIterator is unique to the List interface. In the List interface, a ListIterator object is returned through ListIterator().
Next, let’s take a look at the introduction of each interface and abstract class; then, we will have a detailed understanding of the implementation class.
1. Introduction to Collection
The definition of Collection is as follows:
public interface Collection<E> extends Iterable<E> {} It is an interface, a highly abstracted collection, which contains the basic operations of the collection: adding, deleting, clearing, traversing (reading), whether it is empty, getting the size, whether it is protected by a certain element, etc.
All subclasses of the Collection interface (direct subclass and indirect subclass) must implement two constructors: constructors without parameters and constructors with parameters Collection. A constructor with parameters can be used to convert the type of the Collection.
// Collection APIabstract boolean add(E object)abstract boolean addAll(Collection<? extends E> collection)abstract void clear()abstract boolean contains(Object object)abstract boolean containsAll(Collection<?> collection)abstract boolean equals(Object object)abstract int hashCode()abstract boolean isEmpty()abstract Iterator<E> iterator()abstract boolean remove(Object object)abstract boolean removeAll(Collection<?> collection)abstract boolean retainAll(Collection<?> collection)abstract int size()abstract <T> T[] toArray(T[] array)abstract Object[] toArray()
2. Introduction to List
The definition of List is as follows:
public interface List<E> extends Collection<E> {} List is an interface inherited from Collection, that is, List is a type of collection. List is an ordered queue, and each element in List has an index; the index value of the first element is 0, and the index value of the subsequent elements +1 in turn. Unlike Set, duplicate elements are allowed in List. List's official introduction is as follows:
A List is a collection which maintains an ordering for its elements. Every element in the List has an index. Each element can thus be accessed by its index, with the first index being zero. Normally, Lists allow duplicate elements, as compared to Sets, where elements have to be unique.
About API. Since List inherits from the Collection interface, it naturally contains all the functional interfaces in the Collection; since List is an ordered queue, it also has its own API interface. The main ones include "add, delete, obtain, and modify elements in the specified location", "get subqueues in List", etc.
// Collection APIabstract boolean add(E object)abstract boolean addAll(Collection<? extends E> collection)abstract void clear()abstract boolean contains(Object object)abstract boolean containsAll(Collection<?> collection)abstract boolean equals(Object object)abstract int hashCode()abstract boolean isEmpty()abstract Iterator<E> iterator()abstract boolean remove(Object object)abstract boolean removeAll(Collection<?> collection)abstract boolean retainAll(Collection<?> collection)abstract int size()abstract <T> T[] toArray(T[] array)abstract Object[] toArray()// Compared with Collection, List's new API: abstract void add(int location, E object)abstract boolean addAll(int location, Collection<? extends E> collection)abstract E get(int location)abstract int indexOf(Object object)abstract int lastIndexOf(Object object)abstract ListIterator<E> listIterator(int location)abstract ListIterator<E> listIterator()abstract E remove(int location)abstract E set(int location, E object)abstract List<E> subList(int start, int end)
3. Introduction to Set
Set is defined as follows:
public interface Set<E> extends Collection<E> {} Set is an interface inherited from Collection, that is, Set is also a type of collection. Set is a collection without duplicate elements.
About API. Set's API is exactly the same as Collection.
// Set's APIabstract boolean add(E object)abstract boolean addAll(Collection<? extends E> collection)abstract void clear()abstract boolean contains(Object object)abstract boolean containsAll(Collection<?> collection)abstract boolean equals(Object object)abstract int hashCode()abstract boolean isEmpty()abstract Iterator<E> iterator()abstract boolean remove(Object object)abstract boolean removeAll(Collection<?> collection)abstract boolean retainAll(Collection<?> collection)abstract int size()abstract <T> T[] toArray(T[] array)abstract Object[] toArray()
4. AbstractCollection
The definition of AbstractCollection is as follows:
public abstract class AbstractCollection<E> implements Collection<E> {} AbstractCollection is an abstract class that implements functions in the Collection except iterator() and size().
The main function of AbstractCollection: It implements most functions in the Collection interface. This facilitates other classes to implement Collection, such as ArrayList, LinkedList, etc. If these classes want to implement the Collection interface, most of the interfaces have been implemented by inheriting AbstractCollection.
5. AbstractList
The definition of AbstractList is as follows:
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {} AbstractList is an abstract class that inherits from AbstractCollection and implements the List interface. It implements functions in List except size() and get(int location).
The main function of AbstractList: It implements most functions in the List interface. This facilitates other classes to inherit List.
In addition, compared with AbstractCollection, the iterator() interface is implemented in the AbstractList abstract class.
6. AbstractSet
The definition of AbstractSet is as follows: public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {} AbstractSet is an abstract class that inherits from AbstractCollection and implements the Set interface. Since the Set interface and the API in the Collection interface are exactly the same, Set does not have its own separate API. Like AbstractCollection, it implements functions in List except iterator() and size().
The main function of AbstractSet: It implements most functions in the Set interface. This facilitates other classes to implement Set interfaces.
7. Iterator
The definition of Iterator is as follows:
public interface Iterator<E> {} Iterator is an interface, which is an iterator of the collection. A collection can be traversed through the elements in the collection through Iterator. The API interface provided by Iterator includes: whether the next element exists, obtain the next element, and delete the current element.
Note: When iterator traverses the Collection, it is based on the fail-fast mechanism. That is, when a certain thread A traverses a set through an iterator, if the content of the set is changed by other threads; then when thread A accesses the set, a ConcurrentModificationException exception will be thrown, resulting in a fail-fast event. Regarding the detailed content of fail-fast, we will explain it specifically after the fail-fast summary.
// Iterator's APIabstract boolean hasNext()abstract E next()abstract void remove()
8. ListIterator
The definition of ListIterator is as follows:
public interface ListIterator<E> extends Iterator<E> {} ListIterator is an interface inherited from Iterator, which is a queue iterator. Specially used for convenient List, it can provide forward/backward traversal. Compared with Iterator, it adds API interfaces such as adding, whether the previous element exists, and obtaining the previous element.
// ListIterator's API// Inherited from Iterator's interface abstract boolean hasNext()abstract E next()abstract void remove()// Add API interface abstract void add(E object)abstract boolean hasPrevious()abstract int nextIndex()abstract E previous()abstract int previousIndex()abstract void set(E object)