J2SE----集合框架

    我们都知道，当想要保存一组基本类型数据时，数组是最有效的保存方式，也是推荐使用这种方式的。但是数组是固有大小的，当运行时才知道大小的程序，这种方式使用就受限制了，这就是容器类产生的原因。集合类有几个特点：首先，这种容器是高性能的，对基本数据集合（动态数组、链接表、树和散列表）的实现是高效率的。第二，容器类允许不同类型的类集合以相同的方式和高度互操作方式工作。第三，容器类是容易扩展或修改的。容器类的常用的基本类型有List、Set和Map，这些对象类型也称为集合类，但是在Java中使用了Collection这个名字来指代该类库的一个特殊子集，所以业界使用了范围更广泛的“容器”来称呼。

    Collection：是一个接口，它位于集合框架层次结构的顶层，继承自Iterable接口，说明是可以用Iterator迭代器来访问该集合中的元素的。又有List、Set和Queue接口继承Collection接口，直接实现该接口的是一个叫AbstractCollection的抽象类，该抽象类以最大限度地减少了实现此接口所需的工作。

    List：继承自Collection接口，表示有序的、可包括重复元素的列表。同时拥有Collection内的方法外，还添加了大量的方法，使得可以在List的中间插入和删除元素。实现该接口的基本类有ArrayList和LinkedList. ArrayList：擅长于对元素的随机访问，但是在插入和删除元素时效率较慢。其实，看看ArrayList类实现的源代码就知道，ArrayList是以线性表的数据结构形式存取数据的，初始化的表大小为10，下面就有几个经常用到的核心方法：add（E e）：在当前表的末尾插入元素，如果在前面表不满的情况下，也是很高效的，直接插入到末尾，但是如果在当前表已经满的情况下，就要重新生成一个比当前表大小更大的新表，新表的大小是当前表大小的1.5倍加1，比如当前表长度为20的，新表的大小就为31，还需要把当前表元素复制到新表中去，然后把当前表引用指向新表，最后把数值插入到表末尾，所以这种操作是非常低效的。

    add（int index，E element）：在指定索引位置插入元素，检查表大小和重新追加表大小和上面的add（E e）方式是一样的。最后是要把index以后的元素都是要依次往后移一个大小，然后把元素插入到index位置上去。涉及到表的复制和表内元素的移动，所以效率也是比add（E e）方法还要低。

    remove（int index）：在指定索引位置删除元素，就是把index位置后的所有元素都往前移一个大小，也是涉及到表内元素的移动，效率也是很低的。

    remove（Object o）：删除指定的元素，也就需要查找出该元素在表中出现第一次的位置，查找是用到顺序一个一个进行匹配的方法，找出后就把该元素后面的所有元素往前移一个大小。该方法涉及到顺序查找和表内元素移动，比remove（int index）方法更低效。

    set（int index，E element）：替换表中索引为index的元素值，返回被替换的值，直接用下标索引访问元素，所以效率非常高。

    get（int index）：获取索引为index的元素，直接用下标索引访问，所以效率也是非常高。

    indexOf（Object o）：获取元素的索引号，也就是需要查找，虽然用到了顺序查找法，但效率还是比较高的。

    LinkedList：擅长于对元素的插入和删除操作，但对于随机访问元素比较慢。该类的实现是以双向链表的数据结构为基础的，所以是比较消耗内存的，但它的特定集比ArrayList更大。双向链表，每个节点都有三个域，两个域是存放前后节点的内存地址引用的，一个域是存放数据元素的。在LinkedList类中，有一个叫Entry的内部类，是private的，里面三个属性，分别是element、next和previous，分别对应了双向链表中的三个域，在ArrayList类中每实例化一个Entry就生成一个节点。下面看看它的核心方法：add（E e）：把元素插入到链表末尾，首先要实例化一个节点，新节点previous域存放链表中最后一个节点地址，next域存放链表中第一个节点地址，element域存放元素值，链表中最后一个节点的next域存放新节点的地址，第一个元素的previous域存放新节点的地址，这样这个元素就插入到该链表中去了，没有涉及到复杂的操作，所以是非常高效的。

    add（int index，E element）：在index位置插入元素，这就需要先查找到该位置。查到后，这里就把查到的节点的前一个节点叫为A，实例化新的节点为B，查到index的节点为C.B的next域等于A的next值（也就是C的内存地址），B的previous域等于C的previous值（也就是A的内存地址），B的element域存放元素值，然后把A的next域和C的previous域都等于B的内存地址。这样也就把元素插入到链表的index位置中去了，但涉及到了查询，所以效率虽然高，但也没有add（E e）那么高。

    remove（int index）：删除在index位置的元素，首先也是要找到该位置的节点。然后把该节点的下一个节点（也就是该节点next域的内存地址那个节点）的previous值等于该节点的previous值，该节点的上一个节点（也就是该节点previous域的内存地址那个节点）的next值等于该节点的next值。这样就把该节点从这条链表删除了，过程中虽然涉及到了查找，但没有涉及到像ArrayList类中的remove方法要移动表中元素，所以该方法的效率还是很高的。

    remove（Object o）：删除在链表中第一个元素为o的节点，也是需要查找到该节点，然后就跟remove（int index）思路一样把元素删除，所以效率也是很高的。

    set（int index，E element）：把在链表中第index个元素值改为element，这也需要找到该节点来修改元素值，但涉及到了查找节点，ArrayList中的set方法就不用查找就可以修改，所以相对于ArrayList中的set方法，LinkedList方法set方法效率就没那么高了。

    get（int index）：获取第index位置的元素值，也是要找到该节点，所以就也没ArrayList中的get方法那么高效率了，因为该方法需要查找链表。

    indexOf（Object o）：获取该链表中第一o元素的位置，也是要查找链表，但ArrayList中的indexOf方法也是需要查找的，所以这两个类的indexOf的效率都差不多。

    所以，在编程中，如果要进行大量的随机访问，就使用ArrayList；如果要经常从表中插入或删除元素的就应该使用LinkedList.

    Set：继承自Collection接口，表示无序的，无重复元素的集合。Set中最常使用的是测试归属性，可以很容易测试某个对象是否在某个Set中。所以，查找就成为了Set中最重要的操作，因此通常会选择一个HashSet的实现查找，因为有比较复杂的哈希表支持，它专门对快速查找进行了优化。

    迭代器：迭代器是一种设计模式，在这里是一个对象，它的作用就是遍历并选择列表和操作列表中的对象。迭代器的创佳的代价小，所以通常被称为轻量级对象。迭代器统一了对各种容器的访问方式，很方便。Java中的迭代器有两种，一种是Iterator，另一种是继承了Iterator只能用于各种List访问的ListIterator. Iterator：只能用于单向移动，方法有：iterator（）要求容器返回一个Iterator，Iterator将准备好返回序列的第一元素。next（）获得列表中的下一个元素。hasNext（）检查列表中是否还有元素。remove（）将迭代器新近返回的元素删除。

    ListIterator：只能用于各种的List类的访问，但能用于双向的移动，有一个hasPrevious（）检查时候有前一个元素的，这种操作很像数据库的游标。
    

 import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class ListTest ...{
    public static void main(String [] args)
    ...{
        Collection col = new ArrayList(Arrays.asList(10,20,30));
        List list = new LinkedList();
        list.addAll(col);
        list.add(40);
        list.add(50);
        list.add(60);
        displayIterator(list);
        list.remove(3);
        displayListIterator(list);
    }
    public static void displayIterator(Collection list)
    ...{
        Iterator it = list.iterator();
        Integer i;
        while(it.hasNext())
        ...{
            i = it.next();
            System.out.print(i + " ");
            if(i==50)
            ...{
                it.remove();
            }
        }
        System.out.println();
    }
    public static void displayListIterator(List list)
    ...{
        ListIterator li = list.listIterator();
        /** *//**以下注释代码为死循环，永远输入表中的第一个数据*/
        /** *//**while(li.hasNext())
        {
            System.out.println(li.next());
            System.out.println(li.previous());
        }*/
        while(li.hasNext())
        ...{
            System.out.print(li.next() + " ");
        }
        System.out.println();
        while(li.hasPrevious())
        ...{
            System.out.print(li.previous() + " ");
        }
    }
}

    Map：也是一个映射键/值对的接口，但跟Collection没有任何关系的，也没有继承任何接口，所以不能用Iterator迭代器来访问该集合中的元素。给定一个关键字和一个值，可以这个值到一个Map对象中，存储以后，就可以使用它的关键字来检索它。映射经常使用到的两个基本操作：get()和put()。使用put()方法可以将一个指定了关键字和值的项加入映射。为了得到值，可以通过将关键字作为参数来调用get()方法。

 import java.util.HashMap;
import java.util.Map;

public class TestMap ...{
    public static void main(String [] args)
    ...{
        Map hm = new HashMap();
        hm.put("a1", 1);
        hm.put("b2", 2);
        hm.put("c3", 3);
        hm.put("d4", 4);
        hm.put("e5", 5);
        display(hm);
        System.out.println(hm.containsKey("c3"));
        hm.remove("c3");
        System.out.println(hm.containsValue(3));
        System.out.println(hm.size());
    }
    public static void display(Map m)
    ...{
        for(String s : m.keySet())
        ...{
            System.out.println(s + " : " + m.get(s));
        }
    }
}

【责编:Ken】

--------------------next---------------------