Java Collection Frameworks 学习

 

 

Java 集合总结

<!--[if !supportLists]-->1.       <!--[endif]-->Collection – Super class of List, Set

一般的容器的子类通过实行其中一子接口（List， Set）， 有两个构造函数：

<!--[if !supportLists]-->a.        <!--[endif]-->无参数

<!--[if !supportLists]-->b.       <!--[endif]-->一个集合作为参数的构造函数

 

<!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"> <v:stroke joinstyle="miter" /> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0" /> <v:f eqn="sum @0 1 0" /> <v:f eqn="sum 0 0 @1" /> <v:f eqn="prod @2 1 2" /> <v:f eqn="prod @3 21600 pixelWidth" /> <v:f eqn="prod @3 21600 pixelHeight" /> <v:f eqn="sum @0 0 1" /> <v:f eqn="prod @6 1 2" /> <v:f eqn="prod @7 21600 pixelWidth" /> <v:f eqn="sum @8 21600 0" /> <v:f eqn="prod @7 21600 pixelHeight" /> <v:f eqn="sum @10 21600 0" /> </v:formulas> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect" /> <o:lock v:ext="edit" aspectratio="t" /> </v:shapetype><v:shape id="_x0000_i1058" type="#_x0000_t75" alt="Two interface trees, one starting with Collection and including Set, SortedSet, List, and Queue, and the other starting with Map and including SortedMap." style='width:328.5pt;height:96.75pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="file:///C:\Users\bli3\AppData\Local\Temp\msohtmlclip1\01\clip_image001.gif" o:title="Two interface trees, one starting with Collection and including Set, SortedSet, List, and Queue, and the other starting with Map and including SortedMap" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]-->

                Collection implements Interable<E>

public interface Collection<E> extends Iterable<E> {

    // Basic operations

    int size();

    boolean isEmpty();

    boolean contains(Object element);

    boolean add(E element);         //optional

    boolean remove(Object element); //optional

    Iterator<E> iterator();

 

    // Bulk operations

    boolean containsAll(Collection<?> c);

    boolean addAll(Collection<? extends E> c); //optional

    boolean removeAll(Collection<?> c);        //optional

    boolean retainAll(Collection<?> c);        //optional

    void clear();                              //optional

 

    // Array operations

    Object[] toArray();

    <T> T[] toArray(T[] a);  // T -àRuntime type

}

 

Traversing Collections

<!--[if !supportLists]-->A.       <!--[endif]-->For each　－元素被访问的顺序与集合的类型有关

<!--[if !supportLists]-->B.       <!--[endif]-->Iterator --- 和Enumeration类似

         public interface Iterator<E> {

                       boolean hasNext();

              next();

              void remove(); //optional

               }

注意：remov依赖next方法，remove方法只能删除next()刚刚越过的元素。Eg> 

Remove();remove()， IllegalStatementException 抛出

 

Use Iterator instead of the for-each construct when you need to:

• Remove the current element. The for-each construct hides the iterator, so you cannot call remove. Therefore, the for-each construct is not usable for filtering.
• Iterate over multiple collections in parallel.

三点非常重要对于掌握集合：

     Interface

     Implementation

     Algorithm

<!--[if !supportLists]-->2.       <!--[endif]-->List  --  an ordered collection (sometimes called a sequence). Lists can contain duplicate elements.

按找索引访问，且索引始于0.

Method only for List

E get(int index); 

E set(int index, E element);

void add(int index, E element);

ListIterator<E> listIterator();

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

int indexOf(Object o);

int lastIndexOf(Object o)

 

对于List有个特殊的迭代器ListIterator

     Set(E);nextIndex();next();HasNext()

     Add(E);previousIndex();Privious(); HasPrevious();

主要的类：

<!--[if !supportLists]-->a.       <!--[endif]-->ArrayList –动态增长和缩减的索引序列 （从数组中间删除一个元素，导致后面元素都要向前移动 – 必须付出足够的代价）

 

<!--[if !supportLists]-->1） <!--[endif]-->Add方法只依赖于迭代器的位置而 remove迭代器的状态（HasNext）

<!--[if !supportLists]-->2） <!--[endif]--> 

<!--[if gte vml 1]><v:shape id="Picture_x0020_4" o:spid="_x0000_i1057" type="#_x0000_t75" alt="http://langyu.iteye.com/upload/picture/pic/34615/cd6f2ffb-82ec-3082-adfe-afa1b3606308.jpg" style='width:342.75pt;height:175.5pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="file:///C:\Users\bli3\AppData\Local\Temp\msohtmlclip1\01\clip_image002.jpg" o:title="cd6f2ffb-82ec-3082-adfe-afa1b3606308" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]-->

 

3） ArrayList维护着一个对象数组。如果调用new ArrayList()后，它会默认初始一个size=10的数组。 
４）每次add操作都要检查数组容量，如果不够，重新设置一个初始容量1.5倍大小的新数组，然后再把每个元素copy过去。 
5）  在数组中间插入或删除，都要移动后面的所有元素。（使用System.arraycopy()）

 

<!--[if !supportLists]-->b.      <!--[endif]-->LinkedList –可以在任何位置进行高效地插入和删除的有序序列

 

1） 链表只负责跟踪对列表的结构性修改：add() and Remove(),

Set操作不视为结构性修改，它只对现节点的内容进行修改。

2）在LinkedList还是有get（int Index），不错已经多get方法做了优化，如果索引大于size()/2就从列表外端开始搜索元素。

 

LinkedList的实现是一个双向链表。每个节点除含有元素外，还包含向前，向后的指针。 
新建一个LinkedList，生成一个头节点（header，就是一个头指针），它的元素为null。 
<!--[if gte vml 1]><v:shape id="_x0000_i1056" type="#_x0000_t75" alt="http://langyu.iteye.com/upload/picture/pic/34629/0d81a644-d01e-3d73-a61e-d755ebec5d70.jpg" style='width:287.25pt;height:246.75pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="file:///C:\Users\bli3\AppData\Local\Temp\msohtmlclip1\01\clip_image004.jpg" o:title="0d81a644-d01e-3d73-a61e-d755ebec5d70" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]--> 
它自包含，next和previous指针都指向自己。 
执行add(Object obj)方法后，会生成一个新节点 
<!--[if gte vml 1]><v:shape id="_x0000_i1055" type="#_x0000_t75" alt="http://langyu.iteye.com/upload/picture/pic/34625/91330575-4e1d-37c3-a3a5-ebe8f4a486a2.jpg" style='width:473.25pt;height:309pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="file:///C:\Users\bli3\AppData\Local\Temp\msohtmlclip1\01\clip_image005.jpg" o:title="91330575-4e1d-37c3-a3a5-ebe8f4a486a2" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]--> 
Header节点的next指向链表的第一个节点，previous指向链表的最后一个节点，在这里都是first。 
再增加一个对象，它的形状像下面这样。 
<!--[if gte vml 1]><v:shape id="_x0000_i1054" type="#_x0000_t75" alt="http://langyu.iteye.com/upload/picture/pic/34627/ad40ad46-8b65-3950-9a9c-4454f08d9f4c.jpg" style='width:525pt;height:249.75pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="file:///C:\Users\bli3\AppData\Local\Temp\msohtmlclip1\01\clip_image006.jpg" o:title="ad40ad46-8b65-3950-9a9c-4454f08d9f4c" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]--> 
现在是一个标准的双向链表形状。每个节点都有自己的next和previous指针。 
1)  增加节点，只会对链表的指针进行操作，速度快 
2)  LinkedList实现了Deque，所以它有双向队列的特征，在链表两端可增删数据 
3) 使用index查找对象时，会以index和size/2比较，从前或从后向中间搜索 

4) ListIterator可向前或向后迭代 

比较ArrayList和LinkedList的结构，就可以得出： 
1． ArrayList的remove和add(index, Object)操作代价高，需要移动后面的每个元素。 
2． LinkedList的get(index)操作代价高，它要先循环遍历list，找到Object 

 

 

<!--[if !supportLists]-->3.       <!--[endif]-->Set

特点： 1. Sets contain no pair of elements, e1, and e2, such that e1.equals(e2)

                2. At most one null element

                3. it makes no guarantees as to the iteration order of the set. that is to say, it does not guarantee that the order will remain constant over time.

                4. This is best done at creation time, to prevent accidental  unsynchronized access to the map:  Map m = Collections.synchronizedMap(new HashMap(...))

 

注意：Great care must be exercised if mutable objects are used as set

elements. The behavior of a set is not specified if the value of an object　　　is changed in a manner that affects equals comparisons while the　object is an element in the set.  A special case of this prohibition is　that it is not permissible for a set to contain itself as an element.

              

it would be wrong to write a program that depended on this

    exception for its correctness: the fail-fast behavior of iterators

 * should be used only to detect bugs.

 

1).HashSet 

HashSet使用HashMap来保持元素。Key = 元素，value是一个公有的对象，对每个元素都一样，在HashMap里面key是惟一的，当然很适合于构造set集合。等同于用HashMap包装了次，显示Set自己的特性。 

 

1.    HashSet概述：

HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。

 

2.    HashSet的实现：

对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet 的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成， HashSet的源代码如下：

public class HashSet<E>

    extends AbstractSet<E>

    implements Set<E>, Cloneable, java.io.Serializable

{

    static final long serialVersionUID = -5024744406713321676L;

 

    // 底层使用HashMap来保存HashSet中所有元素。

    private transient HashMap<E,Object> map;

   

    // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。

    private static final Object PRESENT = new Object();

 

    /**

     * 默认的无参构造器，构造一个空的HashSet。

     *

     * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。

     */

    public HashSet() {

            map = new HashMap<E,Object>();

    }

 

    /**

     * 构造一个包含指定collection中的元素的新set。

     *

     * 实际底层使用默认的加载因子0.75和足以包含指定

     * collection中所有元素的初始容量来创建一个HashMap。

     * @param c 其中的元素将存放在此set中的collection。

     */

    public HashSet(Collection<? extends E> c) {

            map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));

            addAll(c);

    }

 

    /**

     * 以指定的initialCapacity和loadFactor构造一个空的HashSet。

     *

     * 实际底层以相应的参数构造一个空的HashMap。

     * @param initialCapacity 初始容量。

     * @param loadFactor 加载因子。

     */

    public HashSet(int initialCapacity, float loadFactor) {

            map = new HashMap<E,Object>(initialCapacity, loadFactor);

    }

 

    /**

     * 以指定的initialCapacity构造一个空的HashSet。

     *

     * 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。

     * @param initialCapacity 初始容量。

     */

    public HashSet(int initialCapacity) {

            map = new HashMap<E,Object>(initialCapacity);

    }

 

    /**

     * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。

     * 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。

     *

     * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。

     * @param initialCapacity 初始容量。

     * @param loadFactor 加载因子。

     * @param dummy 标记。

     */

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {

            map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);

    }

 

    /**

     * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。

     *

     * 底层实际调用底层HashMap的keySet来返回所有的key。

     * 可见HashSet中的元素，只是存放在了底层HashMap的key上，

     * value使用一个static final的Object对象标识。

     * @return 对此set中元素进行迭代的Iterator。

     */

    public Iterator<E> iterator() {

            return map.keySet().iterator();

    }

 

    /**

     * 返回此set中的元素的数量（set的容量）。

     *

     * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。

     * @return 此set中的元素的数量（set的容量）。