Java集合类源码翻阅笔记（一）
java.util.Iterator
public interface Iterator<E>接口类型；
An iterator over a collection说明它是在collection之上的；
Iterator takes the place of Enumeration in the Java collections framework说明在java中用它来替代枚举类型，但它与枚举有两点不同：1.Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics意思是它的元素可删除；2.Method names have been improved不太明白这个的意思；
boolean hasNext()
@return <tt>true</tt> if the iterator has more elements；
E next()
@return the next element in the iteration
@exception NoSuchElementException iteration has no more elements；
void remove()
Removes from the underlying collection the last element returned by the iterator (optional operation). This method can be called only once per call to <tt>next</tt>. The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method
* @exception UnsupportedOperationException if the <tt>remove</tt>
* operation is not supported by this Iterator.
* @exception IllegalStateException if the <tt>next</tt> method has not
* yet been called, or the <tt>remove</tt> method has already
* been called after the last call to the <tt>next</tt> * method.
这个方法要求每执行一次next再执行一次remove
java.util.Iterable
public interface Iterable<T>接口类型
Implementing this interface allows an object to be the target of the "foreach" statement
Iterator<T> iterator()
@return an Iterator
Returns an iterator over a set of elements of type T
java.util.Collection
public interface Collection<E> extends Iterable<E>接口类型
The root interface in the <i>collection hierarchy</i>是集合类的根节点接口；它没有直接实现类，只有子接口Set和List；实现它的类有两个构造器：a void (no arguments) constructor和a constructor with a single argument of type <tt>Collection</tt>；throw <tt>UnsupportedOperationException</tt> if this collection does not support the operation调用不支持的方法抛这个异常；如何调用无效方法则不一定会不会抛这个异常；Attempting to add an ineligible element throws an unchecked exception, typically <tt>NullPointerException</tt> or <tt>ClassCastException</tt>
以下均是Query Operations：
int size()
@return the number of elements in this collection如果这个值大于Integer.MAX_VALUE，则返回Integer.MAX_VALUE的值
boolean isEmpty()
@return <tt>true</tt> if this collection contains no elements判断集合是否为空，是则返回true
boolean contains(Object o)
满足表达式(o==null ? e==null : o.equals(e))，其中e为collection中的某一元素
* @param o element whose presence in this collection is to be tested
* @return <tt>true</tt> if this collection contains the specified
* element
* @throws ClassCastException if the type of the specified element
* is incompatible with this collection (optional)
* @throws NullPointerException if the specified element is null and this
* collection does not permit null elements (optional)
Iterator<E> iterator()
@return an <tt>Iterator</tt> over the elements in this collection不保证返回元素的顺序
Object[] toArray()
@return an array containing all of the elements in this collection返回顺序与它的Iterator一致，返回的是一个新的数组，可任意修改，这个方法是Array和Conllection API之间的桥梁
<T> T[] toArray(T[] a)
* @param a the array into which the elements of this collection are to be
* stored, if it is big enough; otherwise, a new array of the same
* runtime type is allocated for this purpose.
* @return an array containing all of the elements in this collection
* @throws ArrayStoreException if the runtime type of the specified array
* is not a supertype of the runtime type of every element in
* this collection
* @throws NullPointerException if the specified array is null
以下均是Modification Operations：
boolean add(E e)
* @param e element whose presence in this collection is to be ensured
* @return <tt>true</tt> if this collection changed as a result of the
* call
* @throws UnsupportedOperationException if the <tt>add</tt> operation
* is not supported by this collection
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this collection
* @throws NullPointerException if the specified element is null and this
* collection does not permit null elements
* @throws IllegalArgumentException if some property of the element
* prevents it from being added to this collection
* @throws IllegalStateException if the element cannot be added at this
* time due to insertion restrictions
boolean remove(Object o)
* @param o element to be removed from this collection, if present
* @return <tt>true</tt> if an element was removed as a result of this call
* @throws ClassCastException if the type of the specified element
* is incompatible with this collection (optional)
* @throws NullPointerException if the specified element is null and this
* collection does not permit null elements (optional)
* @throws UnsupportedOperationException if the <tt>remove</tt> operation
* is not supported by this collection
以下均是Bulk Operations：
boolean containsAll(Collection<?> c)
* @param c collection to be checked for containment in this collection
* @return <tt>true</tt> if this collection contains all of the elements
* in the specified collection
* @throws ClassCastException if the types of one or more elements
* in the specified collection are incompatible with this
* collection (optional)
* @throws NullPointerException if the specified collection contains one
* or more null elements and this collection does not permit null
* elements (optional), or if the specified collection is null
* @see #contains(Object)
boolean addAll(Collection<? extends E> c)
* @param c collection containing elements to be added to this collection
* @return <tt>true</tt> if this collection changed as a result of the call
* @throws UnsupportedOperationException if the <tt>addAll</tt> operation
* is not supported by this collection
* @throws ClassCastException if the class of an element of the specified
* collection prevents it from being added to this collection
* @throws NullPointerException if the specified collection contains a
* null element and this collection does not permit null elements,
* or if the specified collection is null
* @throws IllegalArgumentException if some property of an element of the
* specified collection prevents it from being added to this
* collection
* @throws IllegalStateException if not all the elements can be added at
* this time due to insertion restrictions
* @see #add(Object)
boolean removeAll(Collection<?> c)
* @param c collection containing elements to be removed from this collection
* @return <tt>true</tt> if this collection changed as a result of the
* call
* @throws UnsupportedOperationException if the <tt>removeAll</tt> method
* is not supported by this collection
* @throws ClassCastException if the types of one or more elements
* in this collection are incompatible with the specified
* collection (optional)
* @throws NullPointerException if this collection contains one or more
* null elements and the specified collection does not support
* null elements (optional), or if the specified collection is null
* @see #remove(Object)
* @see #contains(Object)
boolean retainAll(Collection<?> c)
* @param c collection containing elements to be retained in this collection
* @return <tt>true</tt> if this collection changed as a result of the call
* @throws UnsupportedOperationException if the <tt>retainAll</tt> operation
* is not supported by this collection
* @throws ClassCastException if the types of one or more elements
* in this collection are incompatible with the specified
* collection (optional)
* @throws NullPointerException if this collection contains one or more
* null elements and the specified collection does not permit null
* elements (optional), or if the specified collection is null
* @see #remove(Object)
* @see #contains(Object)
void clear()
* @throws UnsupportedOperationException if the <tt>clear</tt> operation
* is not supported by this collection
以下均是Comparison and hashing：
boolean equals(Object o)
* @param o object to be compared for equality with this collection
* @return <tt>true</tt> if the specified object is equal to this
* collection
*
* @see Object#equals(Object)
* @see Set#equals(Object)
* @see List#equals(Object)
int hashCode()
* @return the hash code value for this collection
*
* @see Object#hashCode()
* @see Object#equals(Object)
java.util.AbstractCollection
public abstract class AbstractCollection<E> implements Collection<E>实现collection接口的抽象类
扩展此类，并提供iterator和size方法的实现，则可以获得一个不可修改的collection；如果还实现了add和remove方法，则可以获得一个可修改的collection；根据Collection接口的建议要实现一个void和Collection构造器；子类可以重写已实现的方法
唯一的构造器：
protected AbstractCollection() {}
以下均是Query Operations：
public abstract Iterator<E> iterator()
由继承的子类实现
public abstract int size()
由继承的子类实现
public boolean isEmpty() { return size() == 0; }
这个表达式为true，说明collection为空
public boolean contains(Object o) { Iterator<E> e = iterator(); if (o==null) { while (e.hasNext()) if (e.next()==null) return true; } else { while (e.hasNext()) if (o.equals(e.next())) return true; } return false; }
先判断o是否为null，再找collection里有没有null，再找collection里和o相同的项
public Object[] toArray() { // Estimate size of array; be prepared to see more or fewer elements Object[] r = new Object[size()]; Iterator<E> it = iterator(); for (int i = 0; i < r.length; i++) { if (! it.hasNext()) // fewer elements than expected return Arrays.copyOf(r, i); r[i] = it.next(); } return it.hasNext() ? finishToArray(r, it) : r; }
如果迭代过程中collection发生变化，返回数据的长度总是等于迭代器返回的数目
public <T> T[] toArray(T[] a) { // Estimate size of array; be prepared to see more or fewer elements int size = size(); T[] r = a.length >= size ? a : (T[])java.lang.reflect.Array .newInstance(a.getClass().getComponentType(), size); Iterator<E> it = iterator(); for (int i = 0; i < r.length; i++) { if (! it.hasNext()) { // fewer elements than expected if (a != r) return Arrays.copyOf(r, i); r[i] = null; // null-terminate return r; } r[i] = (T)it.next(); } return it.hasNext() ? finishToArray(r, it) : r; }
如果a大于collection长度，则就返回a，否则返回一个新建数组；
如果a大于collection长度，则用null填补剩余的数组值；
private static <T> T[] finishToArray(T[] r, Iterator<?> it) { int i = r.length; while (it.hasNext()) { int cap = r.length; if (i == cap) { int newCap = ((cap / 2) + 1) * 3; if (newCap <= cap) { // integer overflow if (cap == Integer.MAX_VALUE) throw new OutOfMemoryError ("Required array size too large"); newCap = Integer.MAX_VALUE; } r = Arrays.copyOf(r, newCap); } r[i++] = (T)it.next(); } // trim if overallocated return (i == r.length) ? r : Arrays.copyOf(r, i); }
是个静态函数
如果迭代器返回的数目比期望的多，这个函数可以重新规划数组长度，规则是：大约扩大1.5倍，可见newCap一般是比cap大的，如果出现newCap <= cap的情况，表明发生integer overflow了，就是整型溢出
以下均是Modification Operations：
public boolean add(E e) { throw new UnsupportedOperationException(); }
总是抛这个异常
public boolean remove(Object o) { Iterator<E> e = iterator(); if (o==null) { while (e.hasNext()) { if (e.next()==null) { e.remove(); return true; } } } else { while (e.hasNext()) { if (o.equals(e.next())) { e.remove(); return true; } } } return false; }
分null和非null两种情况，因为null的Object不能用equals方法
以下均是Bulk Operations：
public boolean containsAll(Collection<?> c) { Iterator<?> e = c.iterator(); while (e.hasNext()) if (!contains(e.next())) return false; return true; }
循环调用contains方法
public boolean addAll(Collection<? extends E> c) { boolean modified = false; Iterator<? extends E> e = c.iterator(); while (e.hasNext()) { if (add(e.next())) modified = true; } return modified; }
如果不重写add方法，总是会抛UnsupportedOperationException异常
public boolean removeAll(Collection<?> c) { boolean modified = false; Iterator<?> e = iterator(); while (e.hasNext()) { if (c.contains(e.next())) { e.remove(); modified = true; } } return modified; }
删除的是e中与c相同的项，保留与c不同的项
public boolean retainAll(Collection<?> c) { boolean modified = false; Iterator<E> e = iterator(); while (e.hasNext()) { if (!c.contains(e.next())) { e.remove(); modified = true; } } return modified; }
删除的是e中与c不同的项，保留与c相同的项
public void clear() { Iterator<E> e = iterator(); while (e.hasNext()) { e.next(); e.remove(); } }
删除全部项
以下均是String conversion：
public String toString() { Iterator<E> i = iterator(); if (! i.hasNext()) return "[]"; StringBuilder sb = new StringBuilder(); sb.append('['); for (;;) { E e = i.next(); sb.append(e == this ? "(this Collection)" : e); if (! i.hasNext()) return sb.append(']').toString(); sb.append(", "); } }
输出形式类似为：["1","2","3"]