java集合框架类源代码阅读体会

忘了什么原因突然想看下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永远不相等。 

Java代码  

// 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中较小的一个做迭代，优化了性能。 
Java代码  

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特定的方法。 
Java代码  

// 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中充满了类似于 
Java代码  

   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的分开处理。 

Java代码  

   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的代码最难读懂。 
Java代码  

    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基本就不能使用了。 
Java代码  

@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方法来改变值。 
红黑树的插入以前一直没有看，现在一看果然精彩。 
注意红黑树删除元素时的特殊处理。 
Java代码  

// 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。

总结

以上是生活随笔为你收集整理的java集合框架类源代码阅读体会的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。