抉择实施方案

从早些时候的那幅示意图可以看出，实际上只有三个荟萃组件：Map，List和Set。并且每个接口只有两种或三种实施方案。若需利用由一个特定的接口提供的成果，如何才气抉择到底采纳哪一种方案呢？
为领略这个问题，必需认识到每种差异的实施方案都有本身的特点、利益和缺点。好比在那张示意图中，可以看到Hashtable，Vector和Stack的“特点”是它们都属于“传统”类，所以不会滋扰原有的代码。但在另一方面，应只管制止为新的（Java 1.2）代码利用它们。
其他荟萃间的差别凡是都可归纳为它们详细是由什么“后推”的。换言之，取决于物理意义上用于实施方针接口的数据布局是什么。譬喻，ArrayList，LinkedList以及Vector（大抵等价于ArrayList）都实现了List接口，所以无论选用哪一个，我们的措施城市获得雷同的功效。然而，ArrayList（以及Vector）是由一个数组后推获得的；而LinkedList是按照通例的双重链接列表方法实现的，因为每个单独的工具都包括了数据以及指向列表内前后元素的句柄。正是由于这个原因，如果想在一个列表中部举办大量插入和删除操纵，那么LinkedList无疑是最得当的选择（LinkedList尚有一些特另外成果，成立于AbstractSequentialList中）。若非如此，就情愿选择ArrayList，它的速度大概要快一些。
作为另一个例子，Set既可作为一个ArraySet实现，亦可作为HashSet实现。ArraySet是由一个ArrayList后推获得的，设计成只支持少量元素，出格适合要求建设和删除大量Set工具的场所利用。然而，一旦需要在本身的Set中容纳大量元素，ArraySet的机能就会大打折扣。写一个需要Set的措施时，应默认选择HashSet。并且只有在某些非凡环境下（对机能的晋升有急切的需求），才应切换到ArraySet。

1. 抉择利用何种List
为体会各类List实施方案间的差别，最轻便的要领就是举办一次机能考试。下述代码的浸染是成立一个内部基本类，将其作为一个测试床利用。然后为每次考试都建设一个匿名内部类。每个这样的内部类都由一个test()要领挪用。操作这种要领，可以利便添加和删除测试项目。
 

//: 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());
  }
} ///:~

内部类Tester是一个抽象类，用于为特定的测试提供一个基本类。它包括了一个要在测试开始时打印的字串、一个用于计较测试次数或元素数量的size参数、用于初始化字段的一个构建器以及一个抽象要领test()。test()做的是最实际的测试事情。各类范例的测试都会合到一个处所：tests数组。我们用担任于Tester的差异匿名内部类来初始化该数组。为添加或删除一个测试项目，只需在数组里简朴地添加或移去一个内部类界说即可，其他所有事情都是自动举办的。
首先用元素填充通报给test()的List，然后对tests数组中的测试计时。由于测试用呆板的差异，功效虽然也会有所区别。这个措施的宗旨是展现出差异荟萃范例的相对机能较量。下面是某一次运行获得的功效：

范例 获取 重复 插入 删除
ArrayList 110 270 1920 4780
LinkedList 1870 7580 170 110

可以看出，在ArrayList中举办随时机见（即get()）以及轮回重复是最划得来的；但对付LinkedList却是一个不小的开销。但另一方面，在列表中部举办插入和删除操纵对付LinkedList来说却比ArrayList划算得多。我们最好的做法也许是先选择一个ArrayList作为本身的默认起点。今后若发明由于大量的插入和删除造成了机能的低落，再思量换成LinkedList不迟。

2. 抉择利用何种Set
可在ArraySet以及HashSet间作出选择，详细取决于Set的巨细（假如需要从一个Set中得到一个顺序列表，请用TreeSet；注释⑧）。下面这个测试措施将有助于各人作出这方面的决议：
 

//: 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);
  }
} ///:~

#p#分页标题#e#

⑧：TreeSet在本书写作时尚未成为一个正式的特性，但在这个例子中可以很轻松地为其添加一个测试。

最后对ArraySet的测试只有500个元素，而不是1000个，因为它太慢了。

范例 测试巨细 添加 包括 重复
 

#p#分页标题#e#

举办add()以及contains()操纵时，HashSet显然要比ArraySet精彩得多，并且机能明明与元素的多寡干系不大。一般编写措施的时候，险些永远用不着利用ArraySet。

3. 抉择利用何种Map
选择差异的Map实施方案时，留意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.entries().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);
  }
} ///:~

由于Map的巨细是最严重的问题，所以措施的计时测试按Map的巨细（或容量）来支解时间，以便获得令人信服的测试功效。下面列出一系列功效（在你的呆板上大概差异）：

范例 测试巨细 置入 取出 重复
 

#p#分页标题#e#

纵然巨细为10，ArrayMap的机能也要比HashMap差——除重复轮回时以外。而在利用Map时，重复的浸染凡是并不重要（get()凡是是我们时间花得最多的处所）。TreeMap提供了精彩的put()以及重复时间，但get()的机能并不佳。可是，我们为什么仍然需要利用TreeMap呢？这样一来，我们可以不把它作为Map利用，而作为建设顺序列表的一种途径。树的本质在于它老是顺序分列的，不必出格举办排序（它的排序方法顿时就要讲到）。一旦填充了一个TreeMap，就可以挪用keySet()来得到键的一个Set“情形”。然后用toArray()发生包括了那些键的一个数组。随后，可用static要领Array.binarySearch()快速查找排好序的数组中的内容。虽然，也许只有在HashMap的行为不行接管的时候，才需要回收这种做法。因为HashMap的设计宗旨就是举办快速的检索操纵。最后，当我们利用Map时，首要的选择应该是HashMap。只有在少少数环境下才需要思量其他要领。
另外，在上面那张内外，有另一本机能问题没有反应出来。下述措施用于测试差异范例Map的建设速度：
 

//: MapCreation.java
// Demonstrates time differences in Map creation
package c08.newcollections;
import java.util.*;

public class MapCreation {
  public static void main(String[] args) {
    final long REPS = 100000;
    long t1 = System.currentTimeMillis();
    System.out.print("Hashtable");
    for(long i = 0; i < REPS; i++)
      new Hashtable();
    long t2 = System.currentTimeMillis();
    System.out.println(": " + (t2 - t1));
    t1 = System.currentTimeMillis();
    System.out.print("TreeMap");
    for(long i = 0; i < REPS; i++)
      new TreeMap();
    t2 = System.currentTimeMillis();
    System.out.println(": " + (t2 - t1));
    t1 = System.currentTimeMillis();
    System.out.print("HashMap");
    for(long i = 0; i < REPS; i++)
      new HashMap();
    t2 = System.currentTimeMillis();
    System.out.println(": " + (t2 - t1));
  }
} ///:~

#p#分页标题#e#

在写这个措施期间，TreeMap的建设速度比其他两种范例明明快得多（但你应亲自实验一下，因为听说新版本大概会改进ArrayMap的机能）。思量到这方面的原因，同时由于前述TreeMap精彩的put()机能，所以假如需要建设大量Map，并且只有在今后才需要涉及大量检索操纵，那么最佳的计策就是：建设和填充TreeMap；今后检索量增大的时候，再将重要的TreeMap转换成HashMap——利用HashMap(Map)构建器。同样地，只有在事实证明晰实存在机能瓶颈后，才应体贴这些方面的问题——先用起来，再按照需要加速速度。