一、区别
这一块属于面试比较容易遇到的 ：
针对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 Collectionspackage 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 Listspackage 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.ArrayListget: 4iteration: 5insert: 9remove: 91Testing java.util.LinkedListget: 13iteration: 5insert: 3remove: 6
2.2 Set测试
//: SetPerformance.javapackage 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 10add: 0.8contains: 0.2iteration: 0.8Testing java.util.HashSet size 10add: 0.3contains: 0.1iteration: 0.7Testing java.util.TreeSet size 100add: 0.12contains: 0.06iteration: 0.07Testing java.util.HashSet size 100add: 0.06contains: 0.02iteration: 0.09Testing java.util.HashSet size 1000add: 0.031contains: 0.026iteration: 0.082Testing java.util.TreeSet size 1000add: 0.127contains: 0.077iteration: 0.083
contains 随机访问 add 添加数据 方面 TreeSet 不如 HashSet 数据量大的时候优先使用HashSet
2.3 Map测试
//: MapPerformance.java// Demonstrates performance differences in Mapspackage 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 10put: 0.5get: 0.1iteration: 0.7Testing java.util.HashMap size 10put: 0.3get: 0.1iteration: 0.8Testing java.util.TreeMap size 10put: 0.6get: 0.1iteration: 0.5Testing java.util.Hashtable size 100put: 0.03get: 0.02iteration: 0.09Testing java.util.HashMap size 100put: 0.06get: 0.02iteration: 0.09Testing java.util.TreeMap size 100put: 0.08get: 0.05iteration: 0.07Testing java.util.HashMap size 1000put: 0.029get: 0.027iteration: 0.079Testing java.util.Hashtable size 1000put: 0.031get: 0.029iteration: 0.08Testing java.util.TreeMap size 1000put: 0.16get: 0.086iteration: 0.091
当我们使用Map 时，首要的选择应该是HashMap。只有在极少数情况下才需要考虑其他方法
TreeMap 提供了出色的put()以及遍历时间，但get()的性能并不佳