Java 集合框架（JCF），java集合框架jcf

Java 集合框架（JCF），java集合框架jcf

根据Java SE源码和《Java核心技术-卷一》（第九版）整理而成

一、Iterator 迭代器

Iterator接口只有三个方法：

public Interface Iterator<E> {
    boolean hashNext();
    E next();
    void remove();
}

如果有了迭代器，就可以对集合采用这些方法进行遍历。一般采用while的形式。从 JavaSE 5.0开始，这种while循环可以采用一种更优雅的方式实现，即for each循环。编译器会将for each循环翻译为带有迭代器的循环。

但是并不是说任何情况下都适合用for each带起迭代器，这边就显示出其remove方法的作用了。

remove方法将会删除上次调用next方法时返回的元素。也就是说，remove方法时和next方法相互依赖的，要删除一个元素，必须先利用调用next将其返回。一个应用场景如下，删除map中value为null的元素，这里如果要用for each并不合适。

Iterator it = map.keySet().iterator();
while (it.hasNext()) {
    long id = (Long) it.next();
    if (map.get(id) == null) {
        it.remove();
    }
}

对于迭代器，下图可以形象的表示。迭代器位于两个元素之间，当调用next方法时，迭代器就会越过下一个元素，并且返回刚刚越过的那个元素的引用。

Iterable接口只提供一个方法，就是返回一个Iterator：

public Interface Iterable<E> {
    Iterator<E> iterator();
}

而Collection接口扩展了Iterable接口，就包含了iterator方法，因此都可以用for each循环遍历。可以这样理解，for each可以与任何实现了Iterable接口的对象一起工作。

二、Collection

是一个公用的接口，其扩展了Iterable接口，有一些通用的方法，List和Set都扩展了改接口。

而类AbstractCollection则实现了该接口的部分通用方法，有需要实现Collection接口的可以继承AbstractCollection类。比如ArrayList和Linked都间接继承了AbstractCollection，当然中间通过了AbstractList类。而HashSet和TreeSet都继承自AbstractSet，AbstractSet也继承自AbstractCollection。

三、List -- LinkedList

1、有一个迭代器，ListIterator，扩展了Iterator接口，添加了add方法。

2、链表不支持随机访问，get方法的效率比较低。

四、List -- ArrayList

1、也实现了List接口，表示动态数组。

2、Vector的所有方法都是同步的，如果不需要同步，建议使用ArrayList。

五、Set -- HashSet

1、依据对象的hashcode来定。

2、一般设置装填因子为75%，如果超过这个数，就会再散列。

3、注意，自己实现的hashcode必须与equals方法兼容，即如果a.equals(b)为true，则a和b应该有相同的hashcode。

4、HashSet依赖于HashMap，其实际上是通过HashMap实现的。

六、Set -- TreeSet

1、利用树结构（红黑树）实现，保证插入的元素有序，但这样也就导致了效率会差一点。

2、默认情况下，TreeSet假定插入的对象实现了Comparable接口，这个接口定义了一个方法。如果要插入自定义对象，就要通过实现Comparable接口自定义排列顺序。

public Interface Comparable<T> {
    int compareTo(T other)
}

3、但是Comparable接口有其局限性，对于一个给定的类，只能实现这个接口一次。如果想要有不同的比较方法，可以实现Comparator接口。

public Interface Comparator<T> {
    int compare(T a, T b);
}

4、从Java SE 6起，TreeSet类实现了NavigableSet接口，这个接口增加了几个便于定位元素以及反向遍历的方法。

5、TreeSet依赖于NavigableMap，其实际是由NavigableMap实现的。

七、Deque

1、双端队列，只支持在头部或者尾部添加或者删除元素，不支持在中间添加元素。

2、Deque在Java SE 6引入，并由ArrayDeque和LinkedList类实现。

八、PriorityQueue

1、优先级队列，采用堆实现。

九、Map

1、键必须唯一，不能对同一个键存放两个值。如果对同一个键调用两次put方法，第二个值将会取代第一个值。

2、映射表（map）包括三个视图Set<K> keySet()，Collection<V> values()，Set<Map.entry<K, V>> entrySet()。注意，keySet既不是HashSet，也不是TreeSet，而是实现了Set接口的某个其他类对象。Set接口扩展了Collection接口，因此可以与使用任何集合一样使用keySet，例如使用for each。

如果要同时查看键和值，可以通过entry来查看。entry接口是map接口内部的接口，其定义如下：

Interface Entry<K, V> {
    K getKey();
    V getValue();
    V setValue(V value);
    boolean equals(Object o);
    int hashCode();
}

这样，就可以利用for each形式，遍历map中的键值对了。

3、通常会用到HashMap和TreeMap两个类。

十、WeakHashMap

1、使用弱引用（weak reference）保存键。

十一、LinkedHashSet和LinkedHashMap

1、都是为了记住插入元素的顺序。

2、链接散列映射表将用访问顺序，而不是插入顺序，对映射条目进行迭代。每次调用put和get方法，收到影响的条目将从当前位置删除，并放到条目链表的尾部。

3、访问顺序对于实现高速缓存的LRU（最近最少使用）原则十分重要。

十二、EnumSet

1、是一个枚举类型元素集的高效实现。

十三、IdentityHashMap

1、标示散列映射表。根据对象的内存地址来计算散列码。对两个对象进行比较时，使用==，而不是equals。也就是说，不同的键对象，即使内容相同，也被视为不同的对象。

2、在实现对象遍历算法（如对象序列化）时，这个类非常有用，可以用来跟踪每个对象的遍历状况。

十四、fail - fast

1、对于并不是线程安全的集合，例如list和set，以及map，当有多个线程同时对其操作时会产生java.util.ConcurrentModificationException