忘了什么原因突然想看下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 Operationsint size();boolean isEmpty();boolean contains(Object o);Iterator<E> iterator();Object[] toArray();<T> T[] toArray(T[] a);// Modification Operationsboolean add(E e);boolean remove(Object o);// Bulk Operationsboolean containsAll(Collection<?> c);boolean addAll(Collection<? extends E> c);boolean removeAll(Collection<?> c);boolean retainAll(Collection<?> c);void clear();// Comparison and hashingboolean 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 OperationsE get(int index);E set(int index, E element);void add(int index, E element);E remove(int index);// Search Operationsint indexOf(Object o);int lastIndexOf(Object o);// List IteratorsListIterator<E> listIterator();ListIterator<E> listIterator(int index);// ViewList<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
写的不错,好