One, foreword

Standing on the shoulders of giants, the Java Collections Framework series references Skywang12345 — the Java Collections series, which is really well spoken and can be referred to. JDK 6.0 and JDK 8.0 have changed the collection framework quite a bit, so this series of articles is based on JDk_1.8.0_161.

Second, description,

Let’s take a look at the Collection architecture diagramCollection architecture for Java Collection series 02

As you can see from the figure, Collection is a highly abstract interface divided into two main branches: List and Set. List and Set are also interfaces that inherit from Collection. A List is an ordered queue that can have repeating elements; And a Set is a mathematical Set that cannot contain the same elements. List and Set have their own implementation classes.

For our convenience. The JDK abstracts AbstractCollection from an abstract class that implements most of the functions in a Collection. Therefore, in the implementation class of a Collection, we can inherit AbstractCollection from it without repeating the encoding. AbstractList and AbstractSet both inherit from AbstractCollection. AbstractList implementation classes inherit from AbstractList, and Set implementation classes inherit from AbstractSet.

In addition, the Collection has an iterator() function that returns an Iterator interface. In general, collections are iterated through iterators. ListIterator is unique to the List interface, where ListIterator() returns a ListIterator object. Next, let’s look at the various interfaces and abstract classes; Then, we’ll look at the implementation classes in detail.

Three, parsing,

1, Collection,

Let’s start with the Collection interface definition:

public interface Collection<E> extends 可迭代<E>
Copy the code

It is an interface, a highly abstract collection that contains the basic operations of the collection: add, delete, empty, traverse (read), empty, size, protect, and so on. The following are all the methods of the Collection interface. It is important to note that, since JDK 8.0, the interface can add methods that use default or static modifications. These methods can have a method body, just like normal methods. And methods decorated with default or static do not need to be overridden by subclasses, which inherit the method directly.

int size(a);

boolean isEmpty(a);

boolean contains(Object o);

Iterator<E> iterator(a);

Object[] toArray();

<T> T[] toArray(T[] a);

boolean add(E e);

boolean remove(Object o);

boolean containsAll(Collection
        c);

boolean addAll(Collection<? extends E> c);

boolean removeAll(Collection
        c);

/ * * *@since1.8 * /
default boolean removeIf(Predicate<? super E> filter) {
	Objects.requireNonNull(filter);
	boolean removed = false;
	final Iterator<E> each = iterator();
	while (each.hasNext()) {
		if (filter.test(each.next())) {
			each.remove();
			removed = true; }}return removed;
}

boolean retainAll(Collection
        c);

void clear(a);

boolean equals(Object o);

int hashCode(a);

/ * * *@since1.8 * /
@Override
default Spliterator<E> spliterator(a) {
	return Spliterators.spliterator(this.0);
}

/ * * *@since1.8 * /
default Stream<E> stream(a) {
	return StreamSupport.stream(spliterator(), false);
}

/ * * *@since1.8 * /
default Stream<E> parallelStream(a) {
	return StreamSupport.stream(spliterator(), true);
}
Copy the code

As you can see in the source code, several default methods have been added since 1.8. All subclasses of the Collection interface (direct and indirect) must implement two kinds of constructors: constructors that take no arguments and constructors that take Collection. A constructor with arguments that can be used to convert the type of a Collection.

2, the List

List interface definition:

public interface List<E> extends Collection<E>
Copy the code

A List is an interface that inherits from a Collection, that is, a List is a type of Collection. A List is an ordered queue, and each element in the List has an index; The index value of the first element is 0, and the index value of subsequent elements is +1. Unlike sets, lists allow repeating elements.

int size(a);

boolean isEmpty(a);

boolean contains(Object o);

Iterator<E> iterator(a);

Object[] toArray();

<T> T[] toArray(T[] a);

boolean add(E e);

boolean remove(Object o);

boolean containsAll(Collection
        c);

boolean addAll(Collection<? extends E> c);

boolean addAll(int index, Collection<? extends E> c);

boolean removeAll(Collection
        c);

boolean retainAll(Collection
        c);

/ * * *@since1.8 * /
default void replaceAll(UnaryOperator<E> operator) {
	Objects.requireNonNull(operator);
	final ListIterator<E> li = this.listIterator();
	while(li.hasNext()) { li.set(operator.apply(li.next())); }}/ * * *@since1.8 * /
@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
	Object[] a = this.toArray();
	Arrays.sort(a, (Comparator) c);
	ListIterator<E> i = this.listIterator();
	for(Object e : a) { i.next(); i.set((E) e); }}void clear(a);

boolean equals(Object o);

int hashCode(a);

E get(int index);

E set(int index, E element);

void add(int index, E element);

E remove(int index);

int indexOf(Object o);

int lastIndexOf(Object o);

ListIterator<E> listIterator(a);

ListIterator<E> listIterator(int index);

List<E> subList(int fromIndex, int toIndex);

@Override
default Spliterator<E> spliterator(a) {
	return Spliterators.spliterator(this, Spliterator.ORDERED);
}
Copy the code

Since the List inherits from the Collection interface, it naturally contains all the function interfaces in the Collection; Since a List is an ordered queue, it also has its own API in addition. Add, delete, get, modify the element in the specified position, get the subqueue in the List, etc.

3, Set

Set interface definition:

public interface Set<E> extends Collection<E>
Copy the code

Set is an interface that inherits from Collection, that is, Set is a type of Collection. A Set is a Set with no repeating elements.

int size(a);

boolean isEmpty(a);

boolean contains(Object o);

Iterator<E> iterator(a);

Object[] toArray();

<T> T[] toArray(T[] a);

boolean add(E e);

boolean remove(Object o);

boolean containsAll(Collection
        c);

boolean addAll(Collection<? extends E> c);

boolean retainAll(Collection
        c);

boolean removeAll(Collection
        c);

void clear(a);

boolean equals(Object o);

int hashCode(a);

/ * * *@since1.8 * /
@Override
default Spliterator<E> spliterator(a) {
	return Spliterators.spliterator(this, Spliterator.DISTINCT);
}
Copy the code

In terms of the API, the Set API and Collection are the same except for the new default methods in JDK 1.8.

4, AbstractCollection

AbstractCollection interface definition:

public abstract class AbstractCollection<E> implements Collection<E>
Copy the code

AbstractCollection is an abstract class that implements functions in a Collection other than iterator() and size(). AbstractCollection’s main purpose: It implements most of the functions in the Collection interface. This makes it easier for other classes to implement collections, such as ArrayList, LinkedList, etc. Classes that want to implement the Collection interface already implement most of the interfaces by inherits AbstractCollection.

5, AbstractList

AbstractList interface definition:

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>
Copy the code

AbstractList is an abstract class that extends from AbstractCollection and implements the List interface. It implements all functions in the List except size() and get(int index). AbstractList’s main purpose: It implements most of the functions in the List interface. This makes it easy for other classes to inherit lists. In addition, compared with those of AbstractCollection AbstractList abstract class, to implement the iterator () interface.

6, AbstractSet

AbstractSet interface definition:

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>
Copy the code

AbstractSet is an abstract class that extends from AbstractCollection and implements the Set interface. Because the Set and Collection apis are identical except for the new default methods in JDK 1.8, Set does not have its own API. Like AbstractCollection, it implements all functions in a List other than iterator() and size(). AbstractSet’s main purpose: It implements most of the functions in the Set interface. This makes it easy for other classes to implement the Set interface.

7, the Iterator

Iterator interface definition:

public interface Iterator<E>
Copy the code

Iterator is an interface that is an Iterator of a collection. Sets can be iterated through the elements of the set. Iterator provides an API for checking whether the next element exists, getting the next element, and deleting the current element.

Note that the Iterator iterates through a Collection in fail-fast mode. That is, if the contents of A collection are changed by another thread while iterator traverses the collection; Then thread A access to the collection, will throw ConcurrentModificationException, produce fail – fast. We will explain the details of Fail-Fast later.

boolean hasNext(a);

E next(a);

default void remove(a) {
	throw new UnsupportedOperationException("remove");
}

/ * * *@since1.8 * /
default void forEachRemaining(Consumer<? super E> action) {
	Objects.requireNonNull(action);
	while (hasNext())
		action.accept(next());
}
Copy the code

In JDK 1.8, remove() is implemented by default, which differs from JDK 1.6, and the forEachRemaining default method is added.

8 a ListIterator.

ListIterator interface definition:

public interface ListIterator<E> extends Iterator<E>
Copy the code

ListIterator is an interface inherited from Iterator, which is a queue Iterator. Designed to facilitate lists, it provides forward/backward traversal. Compared to Iterator, it has new APIS for adding, whether the previous element exists, getting the previous element, and so on.

boolean hasNext(a);

E next(a);

boolean hasPrevious(a);

E previous(a);

int nextIndex(a);

int previousIndex(a);

void remove(a);

void set(E e);

void add(E e);
Copy the code

Four, reference

Collection architecture for Java Collection series 02