Java collection source code analysis (I): collection and abstractcollection
summary
As we know, the container in Java is divided into map set and collection set, and the container in collection is divided into three sub interfaces: queue, list and set.
Among them, list should be the interface with which we deal most frequently. According to the instructions of Javadoc, list is a kind of:
We focus on the three implementations of vector, ArrayList and LinkedList under list. The following is a relationship diagram between them. Among them, red represents an abstract class and blue represents an interface.
According to the class diagram in the figure above, let's study the relationship between classes in the source code and how the method changes from abstract to concrete.
1、 Iterable interface
Iterable is the top-level interface, and the classes that inherit this interface can be iterated.
2、 Collection interface
Collection is the top-level interface of the collection container. It inherits the iteratable interface, that is, all collection implementation classes can be iterated, and list is also a sub interface of collection, so it also has this feature.
It can be seen that the collection interface provides nineteen abstract methods, and the names of these methods intuitively reflect the functions of these methods. Through these methods, some basic characteristics of the implementation class of collection are specified: it can be iterated, transformed into an array, nodes can be added and deleted, collections can be merged or filtered, and stream can be used for streaming processing.
1. Abstract method
We can introduce the methods provided by the collection interface according to the simple classification of functions.
Judgment class:
Operation class:
Auxiliary class:
2. New abstract method in jdk8
In addition, four abstract methods are added in jdk8, all of which provide default implementations:
3. Equals and hashcode
It is worth mentioning that the collection also rewrites the equals () and hashcode () methods of the object (or becomes an abstract method?), In this way, the class implementing the collection must re implement the equals () and hashcode () methods.
3、 Abstractcollection abstract class
Abstractcollection is an abstract class that implements some basic methods of the collection interface. Javadoc is also described in this way:
Through the class diagram, there is also a sub abstract class abstractlist under abstractcollection, which further provides the implementation of the list interface. It is not difficult to find that this is an application of template method pattern in JDK.
0. Unsupported implementation
Before that, it should be noted that there are some special writing methods in abstractcollection, that is, the method is implemented, but the unsupportedoperationexception exception is thrown immediately as soon as it is called by default:
public boolean add(E e) {
throw new UnsupportedOperationException();
}
If you want to use this method, you must rewrite it yourself. This way of writing makes me tangle for a long time. I found a specific statement on the Internet.
Referring to the default implementation of the interface method added in jdk8, I boldly guess that this should be prepared for some classes that implement the collection interface but do not want to implement the add (E) method. Before jdk8, there was no default implementation of the interface. If the abstract class does not provide an implementation, it must implement this method regardless of whether the implementation class needs this method, which obviously does not conform to our original design intention.
1.isEmpty
A very short method is to judge whether the collection is empty by judging whether the container size is 0.
public boolean isEmpty() {
return size() == 0;
}
2.contains/containsAll
Determine whether the element exists.
public boolean contains(Object o) {
Iterator<E> it = iterator();
// 如果要查找的元素是null
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;
}
Containsall() performs traversal judgment based on contains().
public boolean containsAll(Collection<?> c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
3.addAll
The addall () method calls add () in the for loop
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
4.remove/removeAll
The logic of the remove () method is basically the same as that of the contains () method. Because the null judgment is made, the list supports null by default
public boolean remove(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext()) {
if (it.next()==null) {
it.remove();
return true;
}
}
} else {
while (it.hasNext()) {
if (o.equals(it.next())) {
it.remove();
return true;
}
}
}
return false;
}
5.removeAll/retainAll
The logic of removeall() and retainall() are basically the same. They both judge whether an element exists in the collection through the contains() method, and then choose to save or delete it. Because the contains () method only depends on whether it exists and does not care about how many, if there are multiple target elements, they will be deleted or retained.
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
5. ToArray (capacity expansion)
Used to convert a collection to an array. There are two implementations. The commonly used one is the one without parameters.
public Object[] toArray() {
// 创建一个和List相同长度的数字
Object[] r = new Object[size()];
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
// 如果数组长度大于集合长度
if (! it.hasNext())
// 用Arrays.copyOf把剩下的位置用null填充
return Arrays.copyOf(r,i);
r[i] = it.next();
}
// 如果数组长度反而小于集合长度，就扩容数组并且重复上述过程
return it.hasNext() ? finishToArray(r,it) : r;
}
Among them, the finishtoarray (R, it) method involves a capacity expansion process:
// 位运算，扩大当前容量的一半+1
int newCap = cap + (cap >> 1) + 1;
// 如果扩容后的大小比MAX_ARRAY_SIZE还大
if (newCap - MAX_ARRAY_SIZE > 0)
// 使用原容量+1，去判断要直接扩容到MAX_ARRAY_SIZE，Integer.MAX_VALUE还是直接抛OutOfMemoryError异常
newCap = hugeCapacity(cap + 1);
r = Arrays.copyOf(r,newCap);
Max here_ ARRAY_ Size is a constant:
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Here, the size is limited through the hugecapacity() method:
private static int hugeCapacity(int minCapacity) {
// 如果已经大到溢出就抛异常
if (minCapacity < 0)
throw new OutOfMemoryError
("required array size too large");
// 容量+1是否还是大于允许的数组最大大小
return (minCapacity > MAX_ARRAY_SIZE) ?
// 如果是，就把容量直接扩大到Integer.MAX_VALUE
Integer.MAX_VALUE :
// 否则就直接扩容到运行的数组最大大小
MAX_ARRAY_SIZE;
}
6.clear
Iterate and delete all elements.
Iterator<E> it = iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
7.toString
Abstractcollection overrides the toString method, which is why calling toString () of the collection does not print a memory address like an array.
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(' ');
}
}
4、 Summary
Collection
The collection interface class is the parent interface of the three child interfaces of list, queue and set. It inherits the iteratable interface, so all collection implementation classes can be iterated.
The collection provides most of the addition and deletion methods that the implementation class should implement, but does not specify how to use subscripts for operations.
It is worth noting that he redefines the methods of equlas () and hashcode (), so the two methods of the collection implementation class are no longer the same as the object class.
AbstractCollection
Abstractcollection is an abstract class that implements the collection interface. JDK uses the template method pattern here. The implementation class of collection can obtain most of the implemented methods by inheriting abstractcollection.
In abstractcollection, an unsupported implementation is provided for the add () abstract method: that is, the method is implemented, but the call will throw an unsupported operationexception. It is speculated that this is the same as the default implementation of jdk8 interface, so that subclasses can selectively implement the abstract method of the interface. It is not necessary to provide a meaningless empty implementation even if the method is not needed.
Abstractcollection provides methods for adding complex nodes, replacing and deleting singular and complex nodes. In these implementations, because null judgment is made, the default is to support the incoming element to be null, or the collection contains null elements, but the incoming collection is not allowed to be null.
Abstractcollection provides a preliminary implementation of capacity expansion in toarrays() of collection to array: generally, new capacity = old capacity + (old capacity / 2 + 1), if the new capacity is greater than max_ ARRAY_ Size, the old capacity + 1 will be used for judgment. If it has overflowed, the oom overflow will be thrown, which is greater than max_ ARRAY_ Size uses integer MAX_ Value as the new capacity, otherwise Max is used_ ARRY_ SIZE。