java集合框架类源代码阅读体会(Java Collections Framework)

忘了什么原因突然想看下JCF，于是就有了这个阅读体会。
java版本基于sun jdk1.6.0_18


1 通用接口




public interface Iterable<T>
public interface Iterator<E>
一个典型的iterator模式的应用。
注意注释中提到的Iterator和enumerations一个不同点是方法名的提高，命名还是很重要的。

public interface Collection<E>
extends Iterable<E>

比较有意思。
线程策略由实现类决定。
注意contains并不是一定要使用equals，而是把自由给了实现类。
很多可选操作。
如果要继承equals方法需要特别小心，默认的约定是List和Set永远不相等。

// Query Operations
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);

// Modification Operations
boolean add(E e);
boolean remove(Object o);

// Bulk Operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();

// Comparison and hashing
boolean equals(Object o);
int hashCode();

public abstract class AbstractCollection<E>
implements Collection<E>

注意对整数加法溢出的处理。
用简单的算法实现给出了Collection的基本实现。
最大限度的简化了子类的编写，同时不限制子类效率更高的写法。

public interface Queue<E>
extends Collection<E>

public interface Deque<E>
extends Queue<E>

Comparator
注意consistent with equals的意义，即
c.compare(e1, e2)==0 <=> e1.equals(e2)
这里可以重温一下equals和hashcode的关系。
Comparable



2 Set
public interface Set<E>
extends Collection<E>
为了方便copy了Collection<E>所有的方法。
明确了Set作为对数学上Set的建模。
对方法做了更为详尽的注释。如add不能加入重复元素。
明确了Set的equals和hashCode的契约。
equals,只有Set和Set才可能相等，size相同，元素相等。
hashCode,每一个元素hashCode的和，保持了Object的equals和hashCode的惯用法。

public abstract class AbstractSet<E>
extends AbstractCollection<E>
implements Set<E>
Set的骨架类。
简单实现了equals和hashCode。
removeAll考虑了使用2个Set中较小的一个做迭代，优化了性能。

    public boolean removeAll(Collection<?> c) {
        boolean modified = false;

        if (size() > c.size()) {
            for (Iterator<?> i = c.iterator(); i.hasNext(); )
                modified |= remove(i.next());
        } else {
            for (Iterator<?> i = iterator(); i.hasNext(); ) {
                if (c.contains(i.next())) {
                    i.remove();
                    modified = true;
                }
            }
        }
        return modified;
    }

public class HashSet<E>   
extends AbstractSet<E>   
implements Set<E>, Cloneable, java.io.Serializable
由HashMap作为存储。用key来存储元素，用一个哑元作为所有key对应的value。
iterator是fail fast的，但是这是一个best effect行为，程序的正确性不应该依赖该异常。
注意IO序列化的一个自定义实现。writeObject和readObject。
小技巧：
HashSet(int initialCapacity, float loadFactor, boolean dummy)
dummy在这里的作用只是为了和其他的构造函数相区别。
主要是和public HashSet(int initialCapacity, float loadFactor)区别。


public class LinkedHashSet<E>   
extends HashSet<E>   
implements Set<E>, Cloneable, java.io.Serializable
使用了LinkedHashMap保持了元素的插入顺序。

public interface SortedSet<E>
extends Set<E>

public interface NavigableSet<E>
extends SortedSet<E>
public class TreeSet<E>
extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable

和HashSet，LinkedHashSet一样，都是代理到对应的Map来实现。

3 List



public interface List<E>
extends Collection<E>
为了方便copy了Collection<E>所有的方法。
List是有序队列。
增加了很多List特定的方法。

// Positional Access Operations
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);

// Search Operations
int indexOf(Object o);
int lastIndexOf(Object o);

// List Iterators
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);

// View
List<E> subList(int fromIndex, int toIndex);

public interface ListIterator<E>
extends Iterator<E>
基于游标的一个列表的Iterator。
可以前后移动，可以增加，删除，设置元素。

public abstract class AbstractList<E>
extends AbstractCollection<E>
implements List<E>
随机访问List的骨架类。
modCount这个字段标识了List结构性被改动的次数，而且子类继承的时候，该字段是一个可选的字段。
该类中的Itr，ListItr内部类的实现还是很值得一看一学的。
同样，SubList的实现也是比较简洁的。
RandomAccessSubList。


public interface RandomAccess
这个是一个list的marker interface。
列表相关的算法由于列表的实现不同性能差异太大。


public abstract class AbstractSequentialList<E>
extends AbstractList<E>
链表型列表的骨架类。

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
对System.arraycopy方法的大量使用。
为了少做一点检查，提高性能，使用fastRemove。
一般我们都是使用List接口来使用List，直接使用ArrayList可以更好的控制List。当然，没有特殊需求还是使用List比较方便。
ArrayList中提供了trimToSize，ensureCapacity来对其内部数据结构做一些控制。


public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
使用了哑元的双向链表。
Clear时，删除原有所有元素的引用。
private Entry<E> entry(int index)时不是单向遍历，而是判断正向和逆向哪个方向路径更短，然后决定使用哪个方向查找。
ListItr.remove() 注意List的ListIterator是双向的，删除的时候要判断前一个动作是什么。



4 Map




public interface Map<K,V>
interface Entry<K,V>

public abstract class AbstractMap<K,V>
implements Map<K,V>
map的骨架类。
大量实现是基于entrySet。
JCF中充满了类似于

    public V get(Object key) {
	Iterator<Entry<K,V>> i = entrySet().iterator();
	if (key==null) {
	    while (i.hasNext()) {
		Entry<K,V> e = i.next();
		if (e.getKey()==null)
		    return e.getValue();
	    }
	} else {
	    while (i.hasNext()) {
		Entry<K,V> e = i.next();
		if (key.equals(e.getKey()))
		    return e.getValue();
	    }
	}
	return null;
    }

的代码，提高性能，避免在每个循环体中比较。

public static class SimpleEntry<K,V>
implements Entry<K,V>, java.io.Serializable
public static class SimpleImmutableEntry<K,V>
implements Entry<K,V>, java.io.Serializable





public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
关于capacity, load factor, rehash之间的关系。
HashMap不是线程安全的。大部分JCF的类都不是线程安全的。
Capacity必须是2的幂。默认16。Loadfactor默认0.75。
Map初始化的一个钩子函数，方便子类实现。
对于null的特殊处理，所有key为null的都放在index为0的位置。
内部类，wrapper用的出神入化。
用链表法解决hash冲突。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
implements Map<K,V>
可以是插入顺序，也可以是access order。
使用双链表保持顺序。

public interface SortedMap<K,V>
extends Map<K,V>

public interface NavigableMap<K,V>
extends SortedMap<K,V>






public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
底层使用红黑树。
为了性能，在get时对自然序和comparator的分开处理。

    final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
	Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }


    final Entry<K,V> getEntryUsingComparator(Object key) {
	K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

果然还是TreeMap的代码最难读懂。

    final Entry<K,V> getCeilingEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
//进入到左子树，说明该子树的root比key大。
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else if (cmp > 0) {
                if (p.right != null) {
                    p = p.right;
                } else {
//如果是左子树进来的，查找该左子树的root。如果不是，结果是null。
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else
                return p;
        }
        return null;
    }

TreeMap可以插入为null的key，但是插入后，该TreeMap基本就不能使用了。

	@Test(expected = NullPointerException.class)
	public void testAddNullToTreeMap() {
		TreeMap<String, String> tm = new TreeMap<String, String>();
		tm.put(null, "test");
		tm.get("key");
	}

View返回的都是快照（SimpleImmutableEntry），无法setValue，但是可以使用map的put方法来改变值。
红黑树的插入以前一直没有看，现在一看果然精彩。
注意红黑树删除元素时的特殊处理。

                // deleted entries are replaced by their successors
                if (lastReturned.left != null && lastReturned.right != null)
                    next = lastReturned;

最后的构建红黑树也比较有意思，如果一个完全二叉树，最后一层不满的话，则全部为RED。

小结
1 漂亮的注释：JCF的注释的确是比较漂亮的，简单清晰。唯一的不足就是为了保持每个方法注释的完整性，导致有很多重复的注释。当然，对于使用方法有需要才去看注释的程序员来说，这样更方便一点，但是对于完整阅读代码的人来说，貌似有点多余。
2 勿以善小而不为：当看到Iterator的类说明中有改善命名一条时，真的有点感动。
3 大师级的设计和代码复用技术。这个没有什么好说的，喜爱代码的人是在看艺术品。
4 框架代码对性能的有限度强调：在可以提高性能的地方提高性能，但是并不阻止其他人实现子类时提供性能更好的方法。同时，代码并没有因为对一些性能问题的特殊处理而变得丑陋。
5 关于类线程安全性的注释：一般代码哪里看的到这个。
6 几个骨架类的设计和实现都很简洁有力，仅仅使用几个基本方法，就可以实现接口的所有功能。
7 modCount思想。fail-fast的实现机制。
8 平时还是要打好基础，数据结构和算法中对红黑数的插入和删除以前没有怎么看过，只知道概念和用途，直接导致看到TreeMap的时候比较费力。
9 一行行读代码未必是一个好办法，对于JCF的接口和类的体系还是比较熟悉的，因此没有什么问题，但是Map的Iterator和View的继承体系以前没有接触过，看完过自己觉得没有清晰的把握设计思路，动手画画图，真是有如泰山登顶，一览天下的感觉，神清气爽啊。
10 优秀的源代码还是应该早读的，有点后悔为什么拖到现在才开始看JCF，以前干嘛去了。
11 强烈推荐大家都看看JCF。

评论

1 楼 luweiwei 2011-12-14  

写的不错，好