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 elementsObject[] r = new Object[size()]; Iterator<E> it = iterator();for (int i = 0; i < r.length; i++) { if (! it.hasNext())// fewer elements than expectedreturn 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 expectedif (a != r) return Arrays.copyOf(r, i);r[i] = null; // null-terminatereturn 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"]
