第七章 集合框架

2.引子

我们过去学的容器比如数组相对简单。(视频下载) (全部书籍)马克-to-win: 如果我们的程序有这样的要求,即只有运行时才能知道对象的类型或数量而且需要我们把这些对象存在某种容器中,这时数组就不胜任了。这时我们就必须用到集合框架。java自带的集合框架可以容纳乃至操纵自己的可变数量的自定义对象。

下图给出了常用的集合框架中的集合类: 


集合框架有两类集合类:
(1) Collection:盛放一组单独的元素,比如,一个List(列表)必须按特定的顺序容纳元素,而一个Set(集)不可包含任何重复的元素。

(2) 映射(Map):一系列“键-值”对。


第一节 集合框架中的各种集合类

1.List接口

List(接口):马克-to-win: 顺序是List最重要的特性;它里面的元素按照规定的顺序排列。List有大量方法,比如方便我们在List中插入和删除元素。


1.1 ArrayList的用法  (视频下载) (全部书籍)

马克-to-win:ArrayList是List接口的众多实现类其中的一个: 可以使我们快速访问元素,马克-to-win:为什么?因为它的内部组成结构就像Array一样,而且提供了可以直接访问第几个元素的方法比如下面例子中的get(index),但往其中插入和删除元素时,速度却稍慢。与LinkedList相比,它的效率要低许多。(因为LinkedList的内部像个Link, 参考数据结构)ArrayList遍历时要用到Iterator(见下)。(新手可忽略)和vector相比: (from java documentation: ArrayList is roughly equivalent to Vector, except that it is unsynchronized.()there is no synchronized keyword in the ArrayList source code.if multithread access ArrayList, you need to use synchroized keyword in your code yourself.).Vector是线程安全的,但多数情况下不使用Vector,因为线程安全需要更多的系统开销。

一个ArrayList的实例:

例:1.1.1

import java.util.ArrayList;

public class TestMark_to_win {
    public static void main(String args[]) {
        ArrayList l = new ArrayList();
        l.add("a");l.add("b");l.add("c");l.add("d");
        System.out.println(l.get(1) + "\n");
        System.out.println(l + "\n");
    }
}

输出结果是:

b

[a, b, c, d]


一个Iterator的实例  (视频下载) (全部书籍)

想遍历ArrayList里面的内容,通常先生成一个“迭代器”(Iterator), 之后利用它里面的iterator()方法,马克-to-win:Iterator就像一面镜子,能照出集合类中的内容。通过遍历,能得到集合类中的内容。

例:1.1.2


import java.util.ArrayList;
import java.util.Iterator;

public class TestMark_to_win {
    public static void main(String args[]) {
        ArrayList l = new ArrayList();
        l.add("a");
        l.add("b");
        l.add("c");
        l.add("d");
        System.out.println(l + "\n");
        Iterator it = l.iterator();
        String lll = "";
        while (it.hasNext()) {
            String kk = (String) it.next();
            lll = lll + kk;
        }
        System.out.println(lll);
    }
}


结果是:

[a, b, c, d]

abcd


一个Collections的例子  (视频下载) (全部书籍)


马克-to-win: 在操纵ArrayList里面的内容时, 通常我们利用Collections。Collections是集合框架中的一个工具类。可用来排序,反转ArrayList里面的内容。

例:1.1.3

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

public class TestMark_to_win {
    public static void main(String args[]) {
        ArrayList l = new ArrayList();
        l.add("a");
        l.add("c");
        l.add("b");
        l.add("d");
        System.out.println(l + "\n");
        Collections.reverse(l);
        System.out.println(l + "\n");
        Collections.sort(l);
        System.out.println(l + "\n");
        Iterator it = l.iterator();
        String lll = "";
        while (it.hasNext()) {
            String kk = (String) it.next();
            lll = lll + kk;
            // if (kk.equals("jkc")) System.out.println("has jkc");
        }
        System.out.println(lll);
        Collections.fill(l, "m");
        System.out.println(l + "\n");
    }
}

结果 is:

[a, c, b, d]

[d, b, c, a]

[a, b, c, d]

abcd
[m, m, m, m]


1.2 LinkedList的用法 (视频下载) (全部书籍)

LinkedList也是List接口的实现类,提供快速的顺序访问性能,同时可以高速地在列表中插 入和删除。但随机访问时,速度却很慢,此时应换用ArrayList。马克-to-win: 前面讲这是由他们的内部结构决定的。linkList也有addFirst(),addLast(),getFirst(),getLast(),removeFirst()以及removeLast()这些方法。

例:1.2.1

import java.util.*;
public class TestMark_to_win {
    public static void main(String args[]) {
        LinkedList link = new LinkedList();
        link.add(new Integer(23));
        link.add(new Integer(24));
        link.add(new Integer(68));
        link.add(new Integer(37));
        System.out.println(link + "\n");
        link.addFirst(new Integer(38));
        System.out.println(link + "\n");
        Iterator it = link.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

结果是:
 [23, 24, 68, 37]

[38, 23, 24, 68, 37]

38
23
24
68
37

2.Set接口

Set是个接口,添加到Set的每个元素都必须是独一无二的;否则Set就不会添加它。马克-to-win:添加到Set里的对象必须定义equals(),从而建立对象的唯一性。一个Set不能保证自己可按任何特定的顺序维持自己的元素。比如像下面的例子:例:2.1.1


2.1 HashSet的用法 (视频下载) (全部书籍)

对象也必须定义hashCode(),比如下面例子2.1.1中的String类中就定义了hashCode方法。 h.add("1");  但随着Set的增大,它的性能不会大打折扣。这是由Hash的低层结构决定的。HashSet不保证输出的顺序。

例:2.1.1

import java.util.*;

public class TestMark_to_win {
    public static void main(String args[]) {
        HashSet h = new HashSet();
        h.add("1");
        h.add("2");
        h.add("3");
        h.add("4");
        System.out.println(h);
    }
}

结果是:

[3, 2, 1, 4]



2.2 TreeSet的用法  (视频下载) (全部书籍)

TreeSet 二叉查找书,所以结果为升序,任何顺序添加打印结果都为升序。 

例:2.2.1

import java.io.*;
import java.util.*;

public class TestMark_to_win {
    public static void main(String args[]) {
        TreeSet t = new TreeSet();
        t.add("2");
        t.add("1");
        t.add("4");
        t.add("3");
/*  because the tree is binary search tree , so the result is iterator
order, so ascending order
*/
        System.out.println(t);
        t.remove("3");
        System.out.println(t);
        t.add("5");
        t.add("4");
        t.add("7");
        System.out.println(t);
    }
}

结果是:

[1, 2, 3, 4]
[1, 2, 4]
[1, 2, 4, 5, 7]


3.其他一些常见的集合类:

3.1 Vector的用法 (视频下载) (全部书籍)

马克-to-win:Vector和ArrayList很类似,前面讲了二者的区别,就在于同步的问题上,Vector的使用是非常简单的:先创建一个,再用addElement()置入对象,以后用elementAt()取得那些对象

例:3.1.1

import java.io.*;
import java.util.*;

public class TestMark_to_win {
    public static void main(String args[]) {
        Vector v = new Vector();
        for (int i = 0; i < 4; i++) {
            v.addElement(new Integer(i));
        }
        Iterator it = v.iterator();
        while (it.hasNext()) {
            System.out.println("" + it.next());
        }
        if (v.contains(new Integer(2))) {
            System.out.println("it has 2");
        }
        Enumeration e = v.elements();
        while (e.hasMoreElements()) {
            System.out.println(e.nextElement());
        }
        v.removeElementAt(2);
        v.addElement("kkk");
        v.addElement(new Double(1.1));
        /*the following statement is a must, because e has ever gone to the end
of the queue.*/
        e = v.elements();
        while (e.hasMoreElements()) {
            System.out.println(e.nextElement());
        }
    }
}

result is:

0
1
2
3
it has 2
0
1
2
3
0
1
3
kkk
1.1


3.2 Stack的用法 (视频下载) (全部书籍)

马克-to-win:Stack称为“后入先出”(LIFO)集合。

例:3.2.1

import java.util.*;
public class TestMark_to_win {
    static String[] months = { "一", "二", "三" };
    public static void main(String[] args) {
        Stack stk = new Stack();
        for (int i = 0; i < months.length; i++)
            stk.push(months[i] );
        System.out.println("stk = " + stk);
        System.out.println("弹出 elements:");
        while (!stk.empty())
            System.out.println(stk.pop());
    }
}

结果:

stk = [一, 二, 三]
弹出 elements:




3.3 Hashtable的用法  (视频下载) (全部书籍)

马克-to-win:假如我们想把张三20岁,李四30岁这样的信息存入一个容器, 将来一查张三多少岁, 立刻能出来, 就用到Hashtable,张三---->20,就是一个键值对。

例:3.3.1

import java.io.*;
import java.util.*;

class TestMark_to_win {
    public static void main(String args[]) {
        Hashtable n = new Hashtable();
        n.put("thre", new Integer(3));
        n.put("for", new Integer(4));
        n.put("two", new Integer(2));
        n.put("one", new Integer(1));
        Integer n0 = (Integer) n.get("twotwo");
        if (n0 != null) {
            System.out.println("won't print = " + n0);
        }

        Integer m = (Integer) n.get("two");
        if (m != null) {
            System.out.println("two = " + m);
        }
        Enumeration e = n.elements();
        while (e.hasMoreElements()) {
            System.out.println(e.nextElement());
        }
        Enumeration ke = n.keys();
        while (ke.hasMoreElements()) {
            System.out.println(ke.nextElement());
        }
    }
}


result is:

two = 2
3
2
1
4
thre
two
one
for

3.4 Arrays的用法  (视频下载) (全部书籍)

马克-to-win:Arrays这个类包含着操纵Array的方法。

例:3.4.1

import java.util.Arrays;
public class TestMark_to_win {
    public static void main(String args[]) {
        int[] a1 = new int[5];
        int[] a2 = new int[5];
        Arrays.fill(a1, 47);
        Arrays.fill(a2, 47);
        for (int i = 0; i < a2.length; i++)
            System.out.print(a2[i]);
        /*public static boolean equals(int[] a1, int[] a2)
判断两个数组是否包含同样多的元素,相同位置元素是否相同*/
        System.out.println(Arrays.equals(a1, a2));
        a2[3] = 11;
        a2[2] = 9;
        System.out.println(Arrays.equals(a1, a2));
        Arrays.sort(a2);
        for (int i = 0; i < a2.length; i++)
            System.out.print(a2[i]);
        System.out.println(Arrays.binarySearch(a2, 11));
    }
}

result is:

4747474747true
false
9114747471

3.5 Comparable的用法  (视频下载) (全部书籍)

马克-to-win:前面讲过进入TreeSet的每个元素是都排了序的,如果被添加的元素是我们自己定义的,就需要告诉TreeSet排序的规则,这个规则就要在Comparable中定义。在下面的例子中, 当我们要往TreeSet中添加我们自己定义的类Worker对象时,就在compareTo中定义排序规则。

例:3.5.1

 

/*why in the past never implements Comparable? becasue Integer claas and
String class both implements this Comparable.
java.lang.Object
java.lang.String
All Implemented Interfaces:
CharSequence, Comparable, Serializable
 */

import java.util.*;
//Comparable接口在java.lang包中定义
//定义的方法:
//int compareTo(Object o);
//实现该接口就可以实现按用户定义的自然顺序排列对象。
/*you must implements Comparable,otherwise, when you add the second element into
 the treeset, it will report error, because it will search for Comparable
 interface. */
class Worker implements Comparable {
    int workNum;
    String name;
    int money;

    public Worker(int workNum, String name, int money) {
        this.workNum = workNum;
        this.name = name;
        this.money = money;
    }



    // 按工资排序
    /*
     * public int compareTo(Object o) Returns: a negative integer, zero, or a
     * positive integer as this object is less than, equal to, or greater than
     * the specified object. it looks like that the one that is in front is
     * small. what if two keys are the same? only print out one item.
     */
    public int compareTo(Object o) {
        Worker e = (Worker) o;
        return money - e.money;//到底谁减谁,讲师如想搞清楚,请听配套视频里的仔细分析。(视频下载)
        // return workNum - e.workNum;

    }

}

public class TestMark_to_win {
    public static void main(String[] args) {
        Worker e1 = new Worker(1, "李1", 5500);
        Worker e2 = new Worker(2, "李2", 6600);
        Worker e3 = new Worker(3, "李2", 4200);
        Worker e4 = new Worker(4, "李4", 2000);

        Collection c = new TreeSet();
       /* but a TreeSet instance performs all key comparisons using its
          compareTo (or compare) method, */
        c.add(e1);
        c.add(e2);
        c.add(e3);
        c.add(e4);

        Iterator i = c.iterator();
        while (i.hasNext()) {
            Worker e = (Worker) i.next();
            System.out.println(e.workNum + " " + e.name + " " + e.money);
        }
    }
}

结果:
4 李4 2000
3 李2 4200
1 李1 5500
2 李2 6600


3.6 Comparator的用法  (视频下载) (全部书籍)

马克-to-win:和Comparable的思路一样,只不过排序规则这次是在Comparator的继承类的compare方法中定义。

例:3.6.1


import java.util.*;

// A reverse comparator for strings.
class MyComp implements Comparator {
    /* Comparator has two methods compare and equals, when your class implements
      Comparator, there is no need to override equals, why? java.lang Class
      Object implement equals method, so its sub-class MyComp does not need to
      implement equals method, while java.lang Class Object does not implements
      compare mathod.     */
    public int compare(Object a, Object b) {
        String aStr, bStr;
        aStr = (String) a;
        bStr = (String) b;
        /* compareTo(String anotherString)Compares two strings
         * lexicographically. The comparison is based on the Unicode value of
         * each character in the strings. The character sequence represented by
         * this String object is compared lexicographically to the character
         * sequence represented by the argument string.

         * The result is a negative integer if this String object
         * lexicographically precedes the argument string.
         */
        /* the following two statements will have the opposite effect. */
        // return bStr.compareTo(aStr);
        return aStr.compareTo(bStr);
    }
}

public class TestMark_to_win {
    public static void main(String args[]) {
        /* Constructs a new, empty set, sorted according to the specified
         * comparator. All elements inserted into the set must be mutually
         * comparable by the specified comparator: comparator.compare(e1, e2)
         */
        TreeSet ts = new TreeSet(new MyComp());
        // Add elements to the tree set
        ts.add("C");
        ts.add("A");
        ts.add("B");
        ts.add("E");
        ts.add("F");
        ts.add("D");
        // Get an iterator
       // Get an iterator
        Iterator i = ts.iterator();
        // Display elements
        while (i.hasNext()) {
            Object element = i.next();
            System.out.print(element + " ");
        }
        System.out.println();
    }
}

 


 

result is:

A B C D E F


3.7 TreeMap的用法  (视频下载) (全部书籍)

马克-to-win:TreeSet是按升序顺序输出的。TreeMap也是按升序输出,但是和它的区别就是TreeSet存储的是单个元素,而TreeMap存储的是一个一个的键值对。

例:3.7.1


import java.util.*;
public class TestMark_to_win {
    public static void main(String args[]) {
        TreeMap tm = new TreeMap();
        tm.put("zs", new Double(1212.34));
        tm.put("lsMark", new Double(3245.22));
        tm.put("ww", new Double(2345.00));
        tm.put("zl", new Double(3323.22));
        /* entrySet取出一个一个的键值对。 */
        Set set = tm.entrySet();
        // Get an iterator
        Iterator i = set.iterator();
        // Display elements according to the order of the key.
        while (i.hasNext()) {
            Map.Entry me = (Map.Entry) i.next();
            System.out.print(me.getKey() + ": ");
            System.out.println(me.getValue());
        }
        System.out.println();
        // Deposit 1000 into John Doe's account
        double balance = ((Double) tm.get("zs")).doubleValue();
        tm.put("zs", new Double(balance + 1000));
        System.out.println("zs's new qian: " + tm.get("zs"));
    }
}

结果是:

lsMark: 3245.22
ww: 2345.0
zl: 3323.22
zs: 1212.34

zs's new qian: 2212.34


3.8 HashMap的用法  (视频下载) (全部书籍)

马克-to-win:HashMap和HashSet很像,只不过它里面存的是一个一个的键值对。

例:3.8.1

import java.util.*;

public class TestMark_to_win {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<String, String>();
        m.put("zs", "333-6666");
        m.put("ls", "111-2222");
        m.put("wwMark", "444-7777");
        Iterator iter = m.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry e = (Map.Entry) iter.next();
            System.out.println(e.getKey() + " " + e.getValue());
        }
    }
}

result is:

ls 111-2222
zs 333-6666
wwMark 444-7777


3.9 Properties的用法  (视频下载) (全部书籍)

马克-to-win:Properties里面存着也是键值对,而且它更方便java对配置文件,字符串的操作,

例:3.9.1


import java.util.*;
public class TestMark_to_win {
    public static void main(String args[]) {
        Properties sala = new Properties();
        Set name;
        String str;
        sala.put("zs", "1111");
        sala.put("ls", "2222");
        sala.put("ww", "3333");
        sala.put("zl", "4444");

        // Show all name and sala in hashtable.
        name = sala.keySet(); // get set-view of keys
        Iterator itr = name.iterator();
        while (itr.hasNext()) {
            str = (String) itr.next();
            System.out.println("The sala of " +
            /* public String getProperty(String key)Searches for the property
             * with the specified key in this property list.*/
            str + " is " + sala.getProperty(str) + ".");
        }
        System.out.println();
        // look for state not in list -- specify default
        /*
         * Searches for the property with the specified key in this property
         * list. The method returns the default value argument if the property
         * is not found.
         */
        str = sala.getProperty("Mark", "Not Found");
        System.out.println("The sal of Mark is " + str + ".");
    }
}

结果:
The sala of ls is 2222.
The sala of zl is 4444.
The sala of zs is 1111.
The sala of ww is 3333.

The sal of Mark is Not Found.



4.补充知识:泛型  (视频下载) (全部书籍)

马克-to-win:从jdk1.5以后,java用<>来限制存入集合容器的对象的类型必须是<>中规定好的。

例:4.1


import java.util.*;

public class TestMark_to_win {
    public static void main(String args[]) {
        /* the following list can only accept Integer type. */
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(3);
        list.add(2);
        list.add(1);
        list.add(2);
        Iterator iter = list.iterator();
        while (iter.hasNext()) {
            System.out.println(iter.next());
        }
        int length = list.size();
        for (int i = 0; i < length; i++) {
            System.out.println(list.get(i));
        }
    }
}

result is:

1
3
2
1
2
1
3
2
1
2


作业:1)往一ArrayList中添加四个元素a,c,b,d, 排序,反转,binarySearch 出c在位置几,填充,从另一个ArrayList拷贝进三个元素来。(提示:int i=Collections.binarySearch(l,"c"); Collection.copy(ld,ls);Collection.fill(l,"kl");
2)往一LinkList中加三个元素一,二,三,练习AddFisrt,remove, get, set,(提示:l.remove("kkl"); l.get(2);l.set(3,"klj");
3) 往一HashSet中加三个元素一,二,三,练习size的使用。(h.size());
4)  往一TreeSet中加八个元素,打印小于5的元素。(t.headSet("5");
5)练习AlgorithmExample,往一LinkList中加三个元素一,二,三,排序后按逆序打印,找出最大的。(Collections.max(l));
6) 练习Stack,Push进4个元素,再弹出且打印出来。
7) 存几人工资在哈希表中,把张三的工资加100再存进去。(put two times is equal to replace)