Collection

Collection is a superset of List, Queue and Set, which is directly inherited from Iterable, that is, all Collection collection classes support for-each loop. In addition, Collection is also a model of Interface-oriented programming, through which it can transform between classes, which is also one of the charms of object-oriented programming.

Method Definition

Before reading the source code, we can imagine for ourselves what functions we need to encapsulate if we want to encapsulate arrays or linked lists for easy operation. For example: statistical size, insertion or deletion of data, emptying, whether to include a data, and so on. Collection is to extract these common operations, but it is very comprehensive and general. Now let's see what methods it provides.

//Returns the length of the collection, if it is longer than Integer.MAX_VALUE, returns Integer.MAX_VALUE
int size();

//If the total number of collection elements is 0, return true
boolean isEmpty();

//The basis for determining whether a set contains a specified element is the equals() method
boolean contains(Object o);

//Returns an array containing all elements in the collection
Object[] toArray();

//Similar to the previous one, only type conversion has been added.
<T> T[] toArray(T[] a);

//Add an element to the collection, return true if it succeeds, false if it fails, or because the collection itself already contains the same element without adding it.
boolean add(E e);

//Delete a single instance of a specified element from a collection
boolean remove(Object o);

//Returns true if the collection contains all elements in the specified collection
boolean containsAll(Collection<?> c);

//Adds all elements of the specified collection to the collection, but in the meantime, if the specified collection changes, something unexpected may occur
boolean addAll(Collection<? extends E> c);

//Delete all elements contained in a specified collection from the collection
boolean removeAll(Collection<?> c);

//Only the elements contained in the specified collection are retained
boolean retainAll(Collection<?> c);

//Empty Set
void clear();

//To abstract this method is to ensure that all subclasses override this method to ensure the correct behavior of equals.
boolean equals(Object o);

//Ditto
int hashCode();

//This method provides a default implementation in JDK 1.8, which uses Iterator to delete eligible elements.
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;
}

Super Implementation Class: AbstractCollection

Many methods defined in Collection, based on existing definitions and inherited Iterable, can be implemented in abstract classes, which can reduce the number of methods that need to be implemented in the implementation class, which is AbstractCollection.

First of all, we look at its documentation, which contains two statements that may affect our inheritance:

To implement an unmodifiable collection, the programmer needs only to extend this class and provide implementations for the iterator and size methods. (The iterator returned by the iterator method must implement hasNext and next.)

To implement a modifiable collection, the programmer must additionally override this class's add method (which otherwise throws an UnsupportedOperationException), and the iterator returned by the iterator method must additionally implement its remove method.

In general, if you want to implement an immutable collection, you just need to rewrite the iterator and size interfaces, and the returned Iterator needs to implement hasNext and next. To achieve a set that can be modified, you must also override the add method (which throws an exception by default), and the returned Iterator also needs to implement the remove method.

Method Definition

//There is no doubt that this is directly available.
public boolean isEmpty() {
    return size() == 0;
}

//This method can be consistently encapsulated because of the existence of Iterator. What we need to note here is that the comparison of objects is through the equals method, because it.next() and it.hasNext() are called, which is why document annotations overwrite the two methods of Iterator to implement collection classes.
public boolean contains(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}

//Similar to contains, it is also implemented through Iterator, but it calls the it.remove() method, which is why document annotations need to override Iterator's remove method when they write collections that can be modified.
public boolean remove(Object o) {
    //... ellipsis, where the it.remove() method is called
}

Similar methods include ContainsAll (Collection <?> c), addAll (Collection <? Extends E > c), removeAll (Collection <?> c), retainAll (Collection <?> c) and clear(), all of which need to take advantage of the characteristics of Iterator, which will not be discussed here.

There is also a slightly different implementation of toArray(), which you can see in detail.

//This implementation is relatively complex. You can see that the most important means of expansion is the Arrays.copyOf() method.
//That is to say, we need to copy the original array into the new array.
//Note that the order returned here is the same as that of Iterator.
//The purpose of implementation here is to facilitate the conversion of different concrete implementation classes. We will see this method many times in the future.
public Object[] toArray() {
    //First declare an array based on the current collection size
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        //There aren't so many elements in the collection, which means that you don't need such a large array.
        if (! it.hasNext()) 
            return Arrays.copyOf(r, i); //Returns only the portion of the assignment.
        r[i] = it.next();
    }
    //If you have more elements than you get from size(), you need to adjust the array size further.
    return it.hasNext() ? finishToArray(r, it) : r;
}

private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
    //Record current size
    int i = r.length;
    while (it.hasNext()) {
        int cap = r.length;
        //r is not long enough to continue allocating
        if (i == cap) {
            //The expansion mode is cap+cap/2+1, which means 1.5 times expansion.
            int newCap = cap + (cap >> 1) + 1;
            // Over the maximum capacity, MAX_ARRAY_SIZE=Integer.MAX_VALUE-8
            if (newCap - MAX_ARRAY_SIZE > 0)
                //Reset the cap value
                newCap = hugeCapacity(cap + 1);
            
            //Expansion of r
            r = Arrays.copyOf(r, newCap);
        }
        //Assignment, into the next cycle
        r[i++] = (T)it.next();
    }
    // Since the previous expansion was 1.5 times larger, it was finally set to the same size as the actual requirement of r.
    return (i == r.length) ? r : Arrays.copyOf(r, i);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // It exceeds the maximum positive integer, that is, the negative integer.
        throw new OutOfMemoryError
            ("Required array size too large");
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

//Similar to the toArray() method, you can see the source code without further elaboration.
public <T> T[] toArray(T[] a) {
    //...
}

In addition to the above methods, AbstractCollection also implements the toString method, which is done by splicing each element into toString by StringBuilder, and is not complicated. Here you can see the source code:

public String toString() {
    Iterator<E> it = iterator();
    if (! it.hasNext())
        return "[]";

    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (;;) {
        E e = it.next();
        sb.append(e == this ? "(this Collection)" : e);
        if (! it.hasNext())
            return sb.append(']').toString();
        sb.append(',').append(' ');
    }
}

Thank you for seeing it. If you can help me, please give me a compliment.

More experience and technology are welcome to come and learn together. A Little Classroom - Online Learning Platform for Dreams http://www.yidiankt.com/

[Pay attention to the public number and reply to "1" for free - [java Core Knowledge Points]

QQ discussion group: 616683098

QQ: 3184402434

Students who want to study in depth can study and discuss with QQ ~and have a full set of resources to share, experience to explore, wait for you!