05-集合框架区别以及性能测试

一、区别

这一块属于面试比较容易遇到的：

针对Collection下的集合的区别

Collection

|- List (接口)顺序是List 最重要的特性他可以保证元素可以按照规定的顺序排列

|- ArrayList 底层是有一个数组实现的允许对元素的快速访问，用来替换原来的Vector 数组的缺点是元素之间不能有间隔，当数组大小不够时，就需要拓展其存储

能力，将现有的数组元素复制到新的存储空间因此在ArrayList中间位置插入数据或者删除数据的时候就涉及到了数组元素的复制、移动等相对消耗性

能的操作，因此通常情况下 ArrayList用来对数据的遍历和查找，不适合插入和删除等操作。

|- LinkedList 用链表结构存储数据，能快速的插入和删除但是不适合数据的遍历也提供了addFirst()，addLast()，getFirst()，getLast()，removeFirst() 以及

removeLast()等方法也可以将LinkedList当作一个规格的队列或者双向队列使用提供push() pop() 方法可当作堆栈使用

|- Vector 底层是数组的实现不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的

　　　　　　　　　　花费，因此，访问它比访问ArrayList慢

-- ListIterator 专门为List结合提供的迭代器利用它可在一个列表里朝两个方向遍历，同时插入和删除位于列表中部的元素（同样地，只建议对LinkedList 这样做）

|- Set (接口) 添加到Set 的每个元素都必须是独一无二的，否则Set 就不会添加重复的元素

|-HashSet 用于除非常小的以外的所有Set 无序的集合

|-ArraySet 由一个数组后推得到的Set。面向非常小的Set 设计，特别是那些需要频繁创建和删除的。对于小Set，与HashSet 相比，ArraySet 创建和反复所需付

　　　　　　　　　　出的代价都要小得多。但随着Set 的增大，它的性能也会大打折扣。

|-TreeSet 由一个“红黑树”后推得到的顺序Set 有序的集合

二、性能测试

工具类：

//: Collection1.java
// Things you can do with all Collections
package c08.newcollections;

import java.util.*;
public class Collection1 {
    // Fill with 'size' elements, start

    // counting at 'start':
    public static Collection fill(Collection c, int start, int size) {
        for (int i = start; i < start + size; i++)
            c.add(Integer.toString(i));
        return c;
    }

    // Default to a "start" of 0:
    public static Collection fill(Collection c, int size) {
        return fill(c, 0, size);
    }

    // Default to 10 elements:
    public static Collection fill(Collection c) {
        return fill(c, 0, 10);
    }

    // Create & upcast to Collection:
    public static Collection newCollection() {
        return fill(new ArrayList());
        // ArrayList is used for simplicity, but it's
        // only seen as a generic Collection
        // everywhere else in the program.
    }

    // Fill a Collection with a range of values:
    public static Collection newCollection(int start, int size) {
        return fill(new ArrayList(), start, size);
    }

    // Moving through a List with an iterator:
    public static void print(Collection c) {
        for (Iterator x = c.iterator(); x.hasNext();)
            System.out.print(x.next() + " ");
        System.out.println();
    }

     
} // /:~

2.1 List 测试

//: ListPerformance.java
// Demonstrates performance differences in Lists
package c08.newcollections;

import java.util.*;

public class ListPerformance {
    private static final int REPS = 100;

    private abstract static class Tester {
        String name;
        int size; // Test quantity

        Tester(String name, int size) {
            this.name = name;
            this.size = size;
        }

        abstract void test(List a);
    }

    private static Tester[] tests = { new Tester("get", 300) {
        void test(List a) {
            for (int i = 0; i < REPS; i++) {  
                for (int j = 0; j < a.size(); j++)
                    a.get(j);
            }
        }
    },

    new Tester("iteration", 300) {
        void test(List a) {
            for (int i = 0; i < REPS; i++) {
                Iterator it = a.iterator();
                while (it.hasNext())
                    it.next();
            }
        }
    }, new Tester("insert", 1000) {
        void test(List a) {
            int half = a.size() / 2;
            String s = "test";
            ListIterator it = a.listIterator(half);
            for (int i = 0; i < size * 10; i++)
                it.add(s);
        }
    }, new Tester("remove", 5000) {
        void test(List a) {
            ListIterator it = a.listIterator(3);
            while (it.hasNext()) {
                it.next();
                it.remove();
            }
        }
    }, };

    public static void test(List a) {
        // A trick to print out the class name:
        System.out.println("Testing " + a.getClass().getName());
        for (int i = 0; i < tests.length; i++) {
            Collection1.fill(a, tests[i].size);
            System.out.print(tests[i].name);
            long t1 = System.currentTimeMillis();
            tests[i].test(a);
            long t2 = System.currentTimeMillis();
            System.out.println(": " + (t2 - t1));
        }
    }

    public static void main(String[] args) {
        test(new ArrayList());
        test(new LinkedList());
    }
} // /:~

执行的结果：

Testing java.util.ArrayList
get: 4
iteration: 5
insert: 9
remove: 91
Testing java.util.LinkedList
get: 13
iteration: 5
insert: 3
remove: 6

2.2 Set测试

//: SetPerformance.java
package c08.newcollections;

import java.util.*;

public class SetPerformance {
    private static final int REPS = 200;

    private abstract static class Tester {
        String name;

        Tester(String name) {
            this.name = name;
        }

        abstract void test(Set s, int size);
    }

    private static Tester[] tests = { new Tester("add") {
        void test(Set s, int size) {
            for (int i = 0; i < REPS; i++) {
                s.clear();
                Collection1.fill(s, size);
            }
        }
    }, new Tester("contains") {
        void test(Set s, int size) {
            for (int i = 0; i < REPS; i++)
                for (int j = 0; j < size; j++)
                    s.contains(Integer.toString(j));
        }
    }, new Tester("iteration") {
        void test(Set s, int size) {
            for (int i = 0; i < REPS * 10; i++) {
                Iterator it = s.iterator();
                while (it.hasNext())
                    it.next();
            }

        }
    }, };

    public static void test(Set s, int size) {
        // A trick to print out the class name:
        System.out.println("Testing " + s.getClass().getName() + " size "
                + size);
        Collection1.fill(s, size);
        for (int i = 0; i < tests.length; i++) {
            System.out.print(tests[i].name);
            long t1 = System.currentTimeMillis();
            tests[i].test(s, size);
            long t2 = System.currentTimeMillis();
            System.out.println(": " + ((double) (t2 - t1) / (double) size));
        }
    }

    public static void main(String[] args) {
        // Small:
        test(new TreeSet(), 10);
        test(new HashSet(), 10);
        // Medium:
        test(new TreeSet(), 100);
        test(new HashSet(), 100);
        // Large:
        test(new HashSet(), 1000);
        test(new TreeSet(), 1000);
    }
} // /:~

执行的结果：

Testing java.util.TreeSet size 10
add: 0.8
contains: 0.2
iteration: 0.8
Testing java.util.HashSet size 10
add: 0.3
contains: 0.1
iteration: 0.7
Testing java.util.TreeSet size 100
add: 0.12
contains: 0.06
iteration: 0.07
Testing java.util.HashSet size 100
add: 0.06
contains: 0.02
iteration: 0.09
Testing java.util.HashSet size 1000
add: 0.031
contains: 0.026
iteration: 0.082
Testing java.util.TreeSet size 1000
add: 0.127
contains: 0.077
iteration: 0.083

contains 随机访问  add  添加数据  方面 TreeSet 不如 HashSet    数据量大的时候优先使用HashSet

2.3 Map测试

//: MapPerformance.java
// Demonstrates performance differences in Maps
package c08.newcollections;

import java.util.*;

public class MapPerformance {
    private static final int REPS = 200;

    public static Map fill(Map m, int size) {
        for (int i = 0; i < size; i++) {
            String x = Integer.toString(i);
            m.put(x, x);
        }
        return m;
    }

    private abstract static class Tester {
        String name;

        Tester(String name) {
            this.name = name;
        }

        abstract void test(Map m, int size);
    }

    private static Tester[] tests = { new Tester("put") {
        void test(Map m, int size) {
            for (int i = 0; i < REPS; i++) {
                m.clear();
                fill(m, size);
            }
        }
    }, new Tester("get") {
        void test(Map m, int size) {
            for (int i = 0; i < REPS; i++)
                for (int j = 0; j < size; j++)
                    m.get(Integer.toString(j));
        }
    }, new Tester("iteration") {
        void test(Map m, int size) {
            for (int i = 0; i < REPS * 10; i++) {
                Iterator it = m.keySet().iterator();
                while (it.hasNext())
                    it.next();
            }
        }
    }, };

    public static void test(Map m, int size) {
        // A trick to print out the class name:
        System.out.println("Testing " + m.getClass().getName() + " size "
                + size);

        fill(m, size);
        for (int i = 0; i < tests.length; i++) {
            System.out.print(tests[i].name);
            long t1 = System.currentTimeMillis();
            tests[i].test(m, size);
            long t2 = System.currentTimeMillis();
            System.out.println(": " + ((double) (t2 - t1) / (double) size));
        }
    }

    public static void main(String[] args) {
        // Small:
        test(new Hashtable(), 10);
        test(new HashMap(), 10);
        test(new TreeMap(), 10);
        // Medium:
        test(new Hashtable(), 100);
        test(new HashMap(), 100);
        test(new TreeMap(), 100);
        // Large:
        test(new HashMap(), 1000);
        test(new Hashtable(), 1000);
        test(new TreeMap(), 1000);
    }
} // /:~

执行结果：

Testing java.util.Hashtable size 10
put: 0.5
get: 0.1
iteration: 0.7
Testing java.util.HashMap size 10
put: 0.3
get: 0.1
iteration: 0.8
Testing java.util.TreeMap size 10
put: 0.6
get: 0.1
iteration: 0.5
Testing java.util.Hashtable size 100
put: 0.03
get: 0.02
iteration: 0.09
Testing java.util.HashMap size 100
put: 0.06
get: 0.02
iteration: 0.09
Testing java.util.TreeMap size 100
put: 0.08
get: 0.05
iteration: 0.07
Testing java.util.HashMap size 1000
put: 0.029
get: 0.027
iteration: 0.079
Testing java.util.Hashtable size 1000
put: 0.031
get: 0.029
iteration: 0.08
Testing java.util.TreeMap size 1000
put: 0.16
get: 0.086
iteration: 0.091

当我们使用Map 时，首要的选择应该是HashMap。只有在极少数情况下才需要考虑其他方法

TreeMap 提供了出色的put()以及遍历时间，但get()的性能并不佳