} } }

    Java回顾之凑集

    添加时间:2013-5-9 点击量:

      第一篇:Java回顾之I/O


      第二篇:Java回顾之收集通信


      第三篇:Java回顾之多线程


      第四篇:Java回顾之多线程同步



      在这篇文章里,我们存眷Java中的凑集(Collection)。凑集是编程说话中根蒂根基的一项目组,Java自JDK早期,就引入了Java Collection Framework。设计JCF的那小我,后来还写了一本书,叫《Effective Java》。


      Java中的凑集首要集中在2项目组,一项目组是java.util包中,一项目组是java.util.concurrent中,后者是在前者的根蒂根基上,定义了一些实现了同步功能的凑集。


      这篇文章首要存眷java.util下的各类凑集对象。Java中的凑集对象可以粗略的分为3类:List、Set和Map。对应的UML图如下(包含了java.util下大项目组的凑集对象):



      (这张图经过缩放已经变形,完全清楚疆土片请拜见:http://files.cnblogs.com/wing011203/java_collection_structure.zip,解紧缩后就可以看到未经缩放的版本。)


      Collection概述


      Java凑集中的List和Set都从Collection出来,它是一个进修凑集很不错的进口,它包含了凑集中凡是须要有的操纵:



    • 添加元素:add/addAll

    • 清空凑集:clear

    • 删除元素:remove/removeAll

    • 断定凑集中是否包含某元素:contains/containsAll

    • 断定凑集是否为空:isEmpty

    • 策画凑集中元素的个数:size

    • 将凑集转换为数组:toArray

    • 获取迭代器:iterator


      我们来看一个简单的例子,下面的代返回一个凑集,凑集中的元素是随机生成的整数:



     1 private static Collection initCollection()
    
    2 {
    3 Collection<Integer> collection = new ArrayList<Integer>();
    4 Random r = new Random();
    5 forint i = 0 ; i < 5; i++
    6 {
    7 collection.add(new Integer(r.nextInt(100)));
    8 }
    9
    10 return collection;
    11 }


      在对凑集进行操纵的过程中,遍历是一个经常应用的操纵,我们可以应用两种体式格式对凑集进行遍历:


      1) 应用迭代器对凑集进行遍历。正如上方描述Collection接口时所说,所有凑集都邑有一个迭代器,我们可以用它来遍历凑集。



    1 private static void accessCollectionByIterator(Collection<Integer> collection)
    
    2 {
    3 Iterator<Integer> iterator = collection.iterator();
    4 System.out.println(The value in the list:);
    5 while(iterator.hasNext())
    6 {
    7 System.out.println(iterator.next());
    8 }
    9 }


      2)应用foreach遍历凑集。



    1 private static void accessCollectionByFor(Collection<Integer> collection)
    
    2 {
    3 System.out.println(The value in the list:);
    4 for(Integer value : collection)
    5 {
    6 System.out.println(value);
    7 }
    8 }


      List


      Java中的List是对数组的有效扩大,它是如许一种布局,若是不应用泛型,它可以容纳任何类型的元素,若是应用泛型,那么它只能容纳泛型指定的类型的元素。和数组比拟,List的容量是可以动态扩大的。


      List中的元素是可以反复的,里面的元素是“有序”的,这里的“有序”,并不是排序的意思,而是说我们可以对某个元素在凑集中的地位进行指定。


      List中常用的凑集对象包含:ArrayList、Vector和LinkedList,此中前两者是基于数组来进行存储,后者是基于链表进行存储。此中Vector是线程安然的,其余两个不是线程安然的。


      List中是可以包含null的,即使是应用了泛型。


      ArrayList可能是我们日常平凡用到的最多的凑集对象了,在上述的示例代码中,我们也是应用它来实例化一个Collection对象,在此不再赘述。


      Vector


      Vector的示例如下,起首我们看如何生成和输出Vector:



     1 private static void vectorTest1()
    
    2 {
    3 List<Integer> list = new Vector<Integer>();
    4 forint i = 0 ; i < 5; i++
    5 {
    6 list.add(new Integer(100));
    7 }
    8 list.add(null);
    9 System.out.println(size of vector is + list.size());
    10 System.out.println(list);
    11 }


      它的元素中,既包含了反复元素,也包含了null,输出成果如下:



    size of vector is 6
    
    [
    100, 100, 100, 100, 100, null]


      下面的示例,演示了Vector中的一些常用办法:



     1 private static void vectorTest2()
    
    2 {
    3 Vector<Integer> list = new Vector<Integer>();
    4 Random r = new Random();
    5 forint i = 0 ; i < 10; i++
    6 {
    7 list.add(new Integer(r.nextInt(100)));
    8 }
    9 System.out.println(size of vector is + list.size());
    10 System.out.println(list);
    11 System.out.println(list.firstElement());
    12 System.out.println(list.lastElement());
    13 System.out.println(list.subList(3, 8));
    14 List<Integer> temp = new ArrayList<Integer>();
    15 forint i = 4; i < 7; i++
    16 {
    17 temp.add(list.get(i));
    18 }
    19 list.retainAll(temp);
    20 System.out.println(size of vector is + list.size());
    21 System.out.println(list);
    22 }


      它的输出成果如下:



    size of vector is 10
    
    [
    39, 41, 20, 9, 29, 32, 54, 12, 94, 82]
    39
    82
    [
    9, 29, 32, 54, 12]
    size of vector is
    3
    [
    29, 32, 54]


      LinkedList


      LinkedList应用链表来存储数据,它的示例代码如下:


    LinkedList示例

     1 private static void linkedListTest1()
    
    2 {
    3 LinkedList<Integer> list = new LinkedList<Integer>();
    4 Random r = new Random();
    5 forint i = 0 ; i < 10; i++
    6 {
    7 list.add(new Integer(r.nextInt(100)));
    8 }
    9 list.add(null);
    10 System.out.println(size of linked list is + list.size());
    11 System.out.println(list);
    12 System.out.println(list.element());
    13 System.out.println(list.getFirst());
    14 System.out.println(list.getLast());
    15 System.out.println(list.peek());
    16 System.out.println(list.peekFirst());
    17 System.out.println(list.peekLast());
    18 System.out.println(list.poll());
    19 System.out.println(list.pollFirst());
    20 System.out.println(list.pollLast());
    21 System.out.println(list.pop());
    22 list.push(new Integer(100));
    23 System.out.println(size of linked list is + list.size());
    24 System.out.println(list);
    25 }



      这里列出了LinkedList常用的各个办法,从办法名可以看出,LinkedList也可以用来实现栈和队列。


      输出成果如下:



    size of linked list is 11
    
    [
    17, 21, 5, 84, 19, 57, 68, 26, 27, 47, null]
    17
    17
    null
    17
    17
    null
    17
    21
    null
    5
    size of linked list is
    8
    [
    100, 84, 19, 57, 68, 26, 27, 47]


      Set


      Set 和List类似,都是用来存储单个元素,单个元素的数量不断定。但Set不克不及包含反复元素,若是向Set中插入两个雷同元素,那么后一个元素不会入。


      Set可以大致分为两类:不排序Set和排序Set,不排序Set包含HashSet和LinkedHashSet,排序Set首要指TreeSet。此中HashSet和LinkedHashSet可以包含null。


      HashSet


      HashSet是由Hash表支撑的一种凑集,它不是线程安然的。


      我们来看下面的示例,它和Vector的第一个示例根蒂根基上是雷同的:



     1 private static void hashSetTest1()
    
    2 {
    3 Set<Integer> set = new HashSet<Integer>();
    4
    5 forint i = 0; i < 3; i++
    6 {
    7 set.add(new Integer(100));
    8 }
    9 set.add(null);
    10
    11 System.out.println(size of set is + set.size());
    12 System.out.println(set);
    13 }


      这里,HashSet中既包含了反复元素,又包含了null,和Vector不合,这里的输出成果如下:



    size of set is 2
    
    [
    null, 100]


      对于HashSet是如何断定两个元素是否是反复的,我们可以深切查核一下。Object中也定义了equals办法,对于HashSet中的元素,它是按照equals办法来断定元素是否相等的,为了证实这一点,我们可以定义个“不正常”的类型:


    定义MyInteger对象

    class MyInteger
    
    {
    private Integer value;

    public MyInteger(Integer value)
    {
    this.value = value;
    }

    public String toString()
    {
    return String.valueOf(value);
    }

    public int hashCode()
    {
    return 1;
    }

    public boolean equals(Object obj)
    {
    return true;
    }
    }



      可以看到,对于MyInteger来说,对于随便率性两个实例,我们都认为它是不相等的。


      下面是对应的测试办法:



     1 private static void hashSetTest2()
    
    2 {
    3 Set<MyInteger> set = new HashSet<MyInteger>();
    4
    5 forint i = 0; i < 3; i++
    6 {
    7 set.add(new MyInteger(100));
    8 }
    9
    10 System.out.println(size of set is + set.size());
    11 System.out.println(set);
    12 }


      它的输出成果如下:



    size of set is 3
    
    [
    100, 100, 100]


      可以看到,如今HashSet里有“反复”元素了,但对于MyInteger来说,它们不是“雷同”的。


      TreeSet


      TreeSet是支撑排序的一种Set,它的父接口是SortedSet。


      我们起首来看一下TreeSet都有哪些根蒂根基操纵:



     1 private static void treeSetTest1()
    
    2 {
    3 TreeSet<Integer> set = new TreeSet<Integer>();
    4
    5 Random r = new Random();
    6 forint i = 0 ; i < 5; i++
    7 {
    8 set.add(new Integer(r.nextInt(100)));
    9 }
    10
    11 System.out.println(set);
    12 System.out.println(set.first());
    13 System.out.println(set.last());
    14 System.out.println(set.descendingSet());
    15 System.out.println(set.headSet(new Integer(50)));
    16 System.out.println(set.tailSet(new Integer(50)));
    17 System.out.println(set.subSet(30, 60));
    18 System.out.println(set.floor(50));
    19 System.out.println(set.ceiling(50));
    20 }


      它的输出成果如下:



    [8, 42, 48, 49, 53]
    
    8
    53
    [
    53, 49, 48, 42, 8]
    [
    8, 42, 48, 49]
    [
    53]
    [
    42, 48, 49, 53]
    49
    53


      TreeSet中的元素,一般都实现了Comparable接口,默认景象下,对于Integer来说,SortedList是采取升序来存储的,我们也可以自定义Compare体式格式,例如以降序的体式格式来存储。


      下面,我们起首从头定义Integer:


    定义MyInteger2对象

     1 class MyInteger2 implements Comparable
    
    2 {
    3 public int value;
    4
    5 public MyInteger2(int value)
    6 {
    7 this.value = value;
    8 }
    9
    10 public int compareTo(Object arg0)
    11 {
    12 MyInteger2 temp = (MyInteger2)arg0;
    13 if (temp == nullreturn -1;
    14 if (temp.value > this.value)
    15 {
    16 return 1;
    17 }
    18 else if (temp.value < this.value)
    19 {
    20 return -1;
    21 }
    22 return 0;
    23 }
    24
    25 public boolean equals(Object obj)
    26 {
    27 return compareTo(obj) == 0;
    28 }
    29
    30 public String toString()
    31 {
    32 return String.valueOf(value);
    33 }
    34 }



      下面是测试代码:



     1 private static void treeSetTest2()
    
    2 {
    3 TreeSet<Integer> set1 = new TreeSet<Integer>();
    4 TreeSet<MyInteger2> set2 = new TreeSet<MyInteger2>();
    5 Random r = new Random();
    6 forint i = 0 ; i < 5; i++
    7 {
    8 int value = r.nextInt(100);
    9 set1.add(new Integer(value));
    10 set2.add(new MyInteger2(value));
    11 }
    12 System.out.println(Set1 as below:);
    13 System.out.println(set1);
    14 System.out.println(Set2 as below:);
    15 System.out.println(set2);
    16 }


      代码的运行成果如我们所预期的那样,如下所示:



    Set1 as below:
    
    [
    13, 41, 42, 45, 61]
    Set2 as below:
    [
    61, 45, 42, 41, 13]


      Map


      Map中存储的是“键值对”,和Set类似,Java中的Map也有两种:排序的和不排序的,不排序的包含HashMap、Hashtable和LinkedHashMap,排序的包含TreeMap。


      非排序Map


      HashMap和Hashtable都是采取Hash表的体式格式进行存储,HashMap不是线程安然的,Hashtable是线程安然的,我们可以把HashMap看做是“简化”版的Hashtable。


      HashMap是可以存储null的,无论是对Key还是对Value。Hashtable是不成以存储null的。


      无论HashMap还是Hashtable,我们调查它的机关函数,就会发明它可以有两个参数:initialCapacity和loadFactor,默认景象下,initialCapacity便是16,loadFactor便是0.75。这和Hash表中可以存放的元素数量有关系,当元素数量跨越initialCapacityloadFactor时,会触发rehash办法,对hash表进行扩容。若是我们须要向此中插入过多元素,须要恰当调剂这两个参数。


      我们起首来看HashMap的示例:



     1 private static void hashMapTest1()
    
    2 {
    3 Map<Integer,String> map = new HashMap<Integer, String>();
    4
    5 map.put(new Integer(1), a);
    6 map.put(new Integer(2), b);
    7 map.put(new Integer(3), c);
    8
    9 System.out.println(map);
    10 System.out.println(map.entrySet());
    11 System.out.println(map.keySet());
    12 System.out.println(map.values());
    13 }


      这会输出HashMap里的元素信息,如下所示。



    {1=a, 2=b, 3=c}
    
    [
    1=a, 2=b, 3=c]
    [
    1, 2, 3]
    [a, b, c]


      下面的示例是对null的演示:



     1 private static void hashMapTest2()
    
    2 {
    3 Map<Integer,String> map = new HashMap<Integer, String>();
    4
    5 map.put(nullnull);
    6 map.put(nullnull);
    7 map.put(new Integer(4), null);
    8 map.put(new Integer(5), null);
    9
    10 System.out.println(map);
    11 System.out.println(map.entrySet());
    12 System.out.println(map.keySet());
    13 System.out.println(map.values());
    14 }


      履行成果如下:



    {null=null, 4=null, 5=null}
    
    [
    null=null, 4=null, 5=null]
    [
    null, 4, 5]
    [
    nullnullnull]


      接下来我们演示Hashtable,和上述两个示例根蒂根基上完全一样(代码不再展开):


    Hashtable示例

     1 private static void hashTableTest1()
    
    2 {
    3 Map<Integer,String> table = new Hashtable<Integer, String>();
    4
    5 table.put(new Integer(1), a);
    6 table.put(new Integer(2), b);
    7 table.put(new Integer(3), c);
    8
    9 System.out.println(table);
    10 System.out.println(table.entrySet());
    11 System.out.println(table.keySet());
    12 System.out.println(table.values());
    13 }
    14
    15 private static void hashTableTest2()
    16 {
    17 Map<Integer,String> table = new Hashtable<Integer, String>();
    18
    19 table.put(nullnull);
    20 table.put(nullnull);
    21 table.put(new Integer(4), null);
    22 table.put(new Integer(5), null);
    23
    24 System.out.println(table);
    25 System.out.println(table.entrySet());
    26 System.out.println(table.keySet());
    27 System.out.println(table.values());
    28 }



      履行成果如下:



    {3=c, 2=b, 1=a}
    
    [
    3=c, 2=b, 1=a]
    [
    3, 2, 1]
    [c, b, a]
    Exception in thread
    main java.lang.NullPointerException
    at java.util.Hashtable.put(Unknown Source)
    at sample.collections.MapSample.hashTableTest2(MapSample.java:
    61
    at sample.collections.MapSample.main(MapSample.java:
    11)


      可以很清楚的看到,试图将null插入到hashtable中时,报出了空指针异常。


      排序Map


      排序Map主如果指TreeMap,它对元素增、删、查操纵时的时候错杂度都是O(log(n))。它不是线程安然的。


      它的特点和TreeSet很是像,这里不再赘述。

    分享到: