Java Collection源码分析(JDk corretto 11)

Collection 系列源码分析 (JDK Amazon corretto 11)

Collection接口

//public interface Iterator<E> {} 支持遍历
public interface Collection<E> extends Iterable<E> {//主要抽象方法int size();boolean isEmpty();boolean contains(Object o);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);void clear();//...
}

Iterable接口

Iterable<E> 接口
public interface Iterable<T> {Iterator<T> iterator();default void forEach(Consumer<? super T> action) {Objects.requireNonNull(action);for (T t : this) {action.accept(t);}}default Spliterator<T> spliterator() {return Spliterators.spliteratorUnknownSize(iterator(), 0);}
}
Iterator<E> 接口
public interface Iterator<E> {boolean hasNext();E next();default void remove() {throw new UnsupportedOperationException("remove");}default void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);while (hasNext())action.accept(next());}
}//遍历Collection的三种方式
1.传统for循环
2.java forEach写法
3.通过 继承Iterable接口的容器集合方法 iterator()方法返回迭代对象Iterator<E>,通过hasNext()和next()进行迭代

子接口 Queue

public interface Queue<E> extends Collection<E> {//就只有这6个抽象方法//增boolean add(E e);boolean offer(E e);//删E remove();E poll();//返回队首元素E element();E peek();
}
// poll()  peek()队列为空时返回null， remove() element() 抛出异常

Queue的子接口 Deque双端队列

public interface Deque<E> extends Queue<E> {void addFirst(E e);void addLast(E e);boolean offerFirst(E e);boolean offerLast(E e);E removeFirst();E removeLast();E pollFirst();E pollLast();E getFirst();E getLast();E peekFirst();E peekLast();boolean removeFirstOccurrence(Object o);boolean removeLastOccurrence(Object o);void push(E e);E pop();boolean remove(Object o); // 等价boolean removeFirstOccurrence(Object o);
}

子接口List

public interface List<E> extends Collection<E> {// default jdk8出现 可以在接口中定义默认方法与静态方法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);}}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);//List Iterators    ListIterator<E>继承Iterator<E> 功能更加强大ListIterator<E> listIterator(); //完整的List迭代ListIterator<E> listIterator(int index);//返回特定位置的迭代器，可以向前和向后遍历//返回子ListList<E> subList(int fromIndex, int toIndex);//迷惑操作  重载了12个of方法 前11个参数个数从0到10,第12个使用了可变长参数  static <E> List<E> of() {return ImmutableCollections.emptyList();}static <E> List<E> of(E e1) {return new ImmutableCollections.List12<>(e1);}static <E> List<E> of(E e1, E e2) {return new ImmutableCollections.List12<>(e1, e2);}// 省略@SafeVarargs@SuppressWarnings("varargs")static <E> List<E> of(E... elements) {switch (elements.length) { // implicit null check of elementscase 0:return ImmutableCollections.emptyList();case 1:return new ImmutableCollections.List12<>(elements[0]);case 2:return new ImmutableCollections.List12<>(elements[0], elements[1]);default:return new ImmutableCollections.ListN<>(elements);}}
}

ArrayList 实现类

/*
扩容机制
默认情况下，新的容量会是原容量的1.5倍。 新容量=旧容量右移一位（相当于除于2）在加上旧容量ArrayList 的底层是用动态数组来实现的。我们初始化一个空的ArrayList 集合还没有添加元素时，其实它是个空数组，只有当我们添加第一个元素时，内部会调用扩容方法并返回最小容量10，也就是说ArrayList 初始化容量为10。 当前数组长度小于最小容量的长度时（前期容量是10，当添加第11个元素时就就扩容），便开始可以扩容了，ArrayList 扩容的真正计算是在一个grow()里面，新数组大小是旧数组的1.5倍，如果扩容后的新数组大小还是小于最小容量，那新数组的大小就是最小容量的大小，后面会调用一个Arrays.copyof方法，这个方法是真正实现扩容的步骤。*/public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{//6个属性//序列化idprivate static final long serialVersionUID = 8683452581122892189L;/*** Default initial capacity. 默认容量大小为10*/private static final int DEFAULT_CAPACITY = 10;/*** Shared empty array instance used for empty instances.在传入初始容量的构造函数中如果给的初始化容量为0使用这个数组*/private static final Object[] EMPTY_ELEMENTDATA = {};/*** Shared empty array instance used for default sized empty instances. We* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when* first element is added.*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** The array buffer into which the elements of the ArrayList are stored.* The capacity of the ArrayList is the length of this array buffer. Any* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA* will be expanded to DEFAULT_CAPACITY when the first element is added.具体的存储通过数组进行*/transient Object[] elementData; // non-private to simplify nested class access/*** The size of the ArrayList (the number of elements it contains).* 元素的数量 通过属性来确定* @serial*/private int size;//构造方法//1.空的构造public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}//2.给定容量public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {// 用到了6个属性之一this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}//3.通过其他集合创建ArrayListpublic ArrayList(Collection<? extends E> c) { // Collection<? extends E> ?为泛型中的通配符Object[] a = c.toArray();if ((size = a.length) != 0) {//类名.class获取这个类的Class对象。只是三种方式之一if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData = EMPTY_ELEMENTDATA;}}// Integer.MAX_VALUE=0x7fffffff    4字节  1位符号位为0，然后全是1private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//将容量缩减到数组元素数目大小public void trimToSize() {modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}//扩容用的方法private Object[] grow(int minCapacity) {return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));}private Object[] grow() {return grow(size + 1);}private int newCapacity(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity <= 0) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)return Math.max(DEFAULT_CAPACITY, minCapacity);if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return minCapacity;}return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity: hugeCapacity(minCapacity);}private void add(E e, Object[] elementData, int s) {if (s == elementData.length)elementData = grow();elementData[s] = e;size = s + 1;}public boolean add(E e) {modCount++;add(e, elementData, size);return true;}//...其他后续再看吧
}

ArrayList实现了Serializable接口:

序列化与反序列化(后续解决)

获取Calss对象的方式 主要有三种：

• 通过Class.forName(“类的全名称”)获取
• 通过已经实例化的对象获取，getClass()方法获取
• 通过类名.class获取

Arrays工具类

public class Arrays {// <<为左移  1左移13位private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;//copyOf 最终还是调用System.arraycopy，见下文public static <T> T[] copyOf(T[] original, int newLength) {return (T[]) copyOf(original, newLength, original.getClass());}
}

System类

public final class System {@HotSpotIntrinsicCandidatepublic static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);
}

LinkedList实现类

//实现List<E> 和 Deque<E> 所以LinkedList是双向链表
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{transient int size = 0;/*** Pointer to first node.*/transient Node<E> first;/*** Pointer to last node.*/transient Node<E> last;//Node<E> 是一个内部类，双向链表结构主要由Node来维护private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}/*** Links e as first element.将新元素链接到表头*/private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;}/*** Links e as last element.将新元素链接到表尾*/void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}/*** Inserts element e before non-null Node succ.链接到某个非空节点前面*/void linkBefore(E e, Node<E> succ) {// assert succ != null;final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;}/*** Unlinks non-null first node f.*/private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}/*** Unlinks non-null last node l.*/private E unlinkLast(Node<E> l) {// assert l == last && l != null;final E element = l.item;final Node<E> prev = l.prev;l.item = null;l.prev = null; // help GClast = prev;if (prev == null)first = null;elseprev.next = null;size--;modCount++;return element;}/*** Unlinks non-null node x.*/E unlink(Node<E> x) {// assert x != null;final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;}/*后面这6个方法都是对上面方法的封装*/public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;}public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);}public void addFirst(E e) {linkFirst(e);}public void addLast(E e) {linkLast(e);}
}

transient关键字

Java语言的关键字，变量修饰符，如果用transient声明一个实例变量，当对象存储时，它的值不需要维持。换句话来说就是，用transient关键字标记的成员变量不参与序列化过程

Vector实现类

//底层和ArrayList差不多都是基于数组实现
public class Vector<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{protected Object[] elementData;protected int elementCount;protected int capacityIncrement;/** use serialVersionUID from JDK 1.0.2 for interoperability */private static final long serialVersionUID = -2767605614048989439L;//4个构造方法public Vector(int initialCapacity, int capacityIncrement) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);this.elementData = new Object[initialCapacity];this.capacityIncrement = capacityIncrement;}public Vector(int initialCapacity) {this(initialCapacity, 0);}public Vector() {this(10);}public Vector(Collection<? extends E> c) {Object[] a = c.toArray();elementCount = a.length;if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, elementCount, Object[].class);}}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;public int indexOf(Object o) {return indexOf(o, 0);}public synchronized int indexOf(Object o, int index) {if (o == null) {for (int i = index ; i < elementCount ; i++)if (elementData[i]==null)return i;} else {for (int i = index ; i < elementCount ; i++)if (o.equals(elementData[i]))return i;}return -1;}public synchronized int lastIndexOf(Object o) {return lastIndexOf(o, elementCount-1);}public synchronized int lastIndexOf(Object o, int index) {if (index >= elementCount)throw new IndexOutOfBoundsException(index + " >= "+ elementCount);if (o == null) {for (int i = index; i >= 0; i--)if (elementData[i]==null)return i;} else {for (int i = index; i >= 0; i--)if (o.equals(elementData[i]))return i;}return -1;}public synchronized E elementAt(int index) {if (index >= elementCount) {throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);}return elementData(index);}public synchronized E firstElement() {if (elementCount == 0) {throw new NoSuchElementException();}return elementData(0);}public synchronized E lastElement() {if (elementCount == 0) {throw new NoSuchElementException();}return elementData(elementCount - 1);}public synchronized void setElementAt(E obj, int index) {if (index >= elementCount) {throw new ArrayIndexOutOfBoundsException(index + " >= " +elementCount);}elementData[index] = obj;}public synchronized void removeElementAt(int index) {if (index >= elementCount) {throw new ArrayIndexOutOfBoundsException(index + " >= " +elementCount);}else if (index < 0) {throw new ArrayIndexOutOfBoundsException(index);}int j = elementCount - index - 1;if (j > 0) {System.arraycopy(elementData, index + 1, elementData, index, j);}modCount++;elementCount--;elementData[elementCount] = null; /* to let gc do its work */}public synchronized void insertElementAt(E obj, int index) {if (index > elementCount) {throw new ArrayIndexOutOfBoundsException(index+ " > " + elementCount);}modCount++;final int s = elementCount;Object[] elementData = this.elementData;if (s == elementData.length)elementData = grow();System.arraycopy(elementData, index,elementData, index + 1,s - index);elementData[index] = obj;elementCount = s + 1;}public synchronized void addElement(E obj) {modCount++;add(obj, elementData, elementCount);}public synchronized boolean removeElement(Object obj) {modCount++;int i = indexOf(obj);if (i >= 0) {removeElementAt(i);return true;}return false;}public synchronized void removeAllElements() {final Object[] es = elementData;for (int to = elementCount, i = elementCount = 0; i < to; i++)es[i] = null;modCount++;}public synchronized E set(int index, E element) {}public synchronized boolean add(E e) {}public boolean remove(Object o) {return removeElement(o);}public void add(int index, E element) {insertElementAt(element, index);}public synchronized E remove(int index) {}public void clear() {removeAllElements();}
}

Stack

public
class Stack<E> extends Vector<E> {public Stack() {}public E push(E item) {addElement(item);return item;}public synchronized E pop() {E       obj;int     len = size();obj = peek();removeElementAt(len - 1);return obj;}public synchronized E peek() {int     len = size();if (len == 0)throw new EmptyStackException();return elementAt(len - 1);}public boolean empty() {return size() == 0;}public synchronized int search(Object o) {int i = lastIndexOf(o);if (i >= 0) {return size() - i;}return -1;}
}

ListIterator接口

// ListIterator<E> 功能更加强大
// 对于有n的元素的列表 共有n+1个游标位置public interface ListIterator<E> extends Iterator<E> {boolean hasNext();//判断游标后有没有元素E next();//返回游标后的元素，并后移boolean hasPrevious();//判断游标前有没有元素E previous();//返回游标前的元素，并前移int nextIndex();//返回游标后边元素的索引位置int previousIndex();//返回游标前面元素的位置，初始时为 -1/*删除迭代器最后一次操作的元素，注意事项和 set 一样。*/void remove();/*更新迭代器最后一次操作的元素为 E，也就是更新最后一次调用 next() 或者 previous() 返回的元素。    注意，当没有迭代，也就是没有调用 next() 或者 previous() 直接调用 set 时会报 java.lang.IllegalStateException 错;*/void set(E e);void add(E e);//在游标 前面 插入一个元素。注意，是前面！！
}

子接口Set

public interface Set<E> extends Collection<E> {//没看出有什么新的东西
}

HashSet

//底层使用HashMap实现
public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable
{static final long serialVersionUID = -5024744406713321676L;//HashMap实现private transient HashMap<E,Object> map;// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();
}