容器深入研究（9）：选择接口的不同实现（上）

秒速五厘米 2023-07-25 06:17 6阅读 0赞

现在已经知道了，尽管实际上只有四种容器：Map、List、Set和Queue，但是每种接口都有不止一个实现版本。如果需要使用某种接口的功能，应该如何选择使用哪一个实现呢？

每种不同的实现各自的特征、优点和缺点。例如，从容器分类图中可以看出，Hashtable、Vector和Stack的“特征”是，它们是过去遗留下来的类，目的只是为了支持老的程序（最好不要在新的程序中使用它们）。

在java类库中不同的类型的Queue只在它们接受和产生数值的方式上有所差异（你将在并发章节中看到其重要性）。

容器之间的区别通常归结为由什么在背后“支持”它们。也就是说，所使用的接口是由什么样的数据结构实现的。例如，因为ArrayList和LinkedList都实现了List接口，所以无论选择哪一个，基本的List操作都是相同的。然而，ArrayList底层是由数组支持；而LinkedList是由双向链表实现的，其中的每个对象包含数据的同时还包含指向链表中前一个和后一个元素的引用。因此，如果要经常在表中插入和删除元素，LinkedList就比较合适（LinkedList还有建立在AbstractSequentialList基础上的其他功能）；否则，应该使用速度更快的ArrayList。

再举一个例子，Set可被实现为TreeSet、HashSet或LinkedHashSet。每一种都有不同的行为；HashSet是最常用的，查询速度最快；LinkedHashSet保持元素插入的次序；TreeSet基于TreeMap，生成一个总是处于排序状态的Set。你可以根据所需的行为来选择不同的接口实现。

有时某个特定容器的不同实现会拥有一些共同的操作，但是这些操作的性能却并不相同。在这种情况下，你可以基于使用某个特定操作的频率，以及你需要的执行速度来在它们中间进行选择。对于类似的情况，一种查看容器实现之间差异的方式是使用性能测试。

### 一、性能测试框架 ###

为了防止代码重复以及为了提供测试的一致性，我将测试过程的基本功能放置到了一个测试框架中。下面的代码建立了一个基类，从中可以创建一个匿名内部类列表，其中每个匿名内部类都用于每种不同的测试，它们每个都被当做测试过程的一部分而被调用。这种方式使得你可以很方便的添加或移除新的测试种类。

这是模版方法设计模式的另一个示例。尽管你遵循了典型的模版方法模式，覆盖了每个特定测试的Test.test()方法，但是在本例中，其核心代码（不会发生变化）在一个单独的Tester类中。待测容器类型是泛型参数C：

public abstract class Test<C> {
    	String name;
    
    	public Test(String name) {
    		this.name = name;
    	}
    
    	abstract int test(C container, TestParam tp);
    }

每个Test对象都存储了该测试的名字。当你调用test()方法时，必须给出待测容器，以及“信使”或“数据传输对象”，它们保存有用于该特定测试的各种参数。这些参数包括size，它表示在容器中的元素数量；以及loops，它用来控制该测试迭代的次数。这些参数在每个测试中都有可能会用到，也有可能会用不到。

每个容器都要经历一系列对test()的调用，每个都带有不同的TestParam，因此TestParam还包含静态的array()方法，使得创建TestParam对象数组变得更容易。array()的第一个版本接受的是可变参数列表，其中包括可互换的size和loops的值；而第二个版本接受相同类型的列表，但是它的值都在String中——通过这种方式，它可以用来解析命令行参数：

public class TestParam {
    	public final int size;
    	public final int loops;
    
    	public TestParam(int size, int loops) {
    		this.size = size;
    		this.loops = loops;
    	}
    
    	public static TestParam[] array(int... values) {
    		int size = values.length / 2;
    		TestParam[] result = new TestParam[size];
    		int n = 0;
    		for (int i = 0; i < size; i++) {
    			result[i] = new TestParam(values[n++], values[n++]);
    		}
    		return result;
    	}
    
    	public static TestParam[] array(String[] values) {
    		int[] vals = new int[values.length];
    		for (int i = 0; i < vals.length; i++) {
    			vals[i] = Integer.decode(values[i]);
    		}
    		return array(vals);
    	}
    }

为了使用这个框架，你需要将待测容器以及Test对象传递给Tester.run()方法（这些都是重载的泛型便利方法，它们可以减少在使用它们时所必需的类型检查）。Tester.run()方法调用适当的重载构造器，然后调用timedTest()，它会执行针对该容器的列表中的每一个测试。timedTest()会使用paramList中的每个TestParam对象进行重复测试。因为paramList是从静态的defaultParams数组中初始化出来的。因此你可以通过重新赋值defaultParams，来修改用于所有测试的paramList，或者可以通过传递针对某个测试的定制的paramList，来修改用于该测试的paramList：

import java.util.List;
    
    public class Tester<C> {
    	public static int fieldWidth = 0;
    	public static TestParam[] defaultParams = TestParam.array(10, 5000, 100, 5000, 1000, 5000, 10000, 500);
    
    	protected C initialize(int size) {
    		return container;
    	}
    
    	protected C container;
    
    	private String headline = "";
    	private List<Test<C>> tests;
    
    	private static String stringField() {
    		return "%" + fieldWidth + "s";
    	}
    
    	private static String numberField() {
    		return "%" + fieldWidth + "d";
    	}
    
    	private static int sizeWidth = 5;
    	private static String sizeField = "%" + sizeWidth + "s";
    	private TestParam[] paramList = defaultParams;
    
    	public Tester(C container, List<Test<C>> tests) {
    		this.container = container;
    		this.tests = tests;
    		if (container != null) {
    			headline = container.getClass().getSimpleName();
    		}
    	}
    
    	public Tester(C container, List<Test<C>> tests, TestParam[] paramList) {
    		this(container, tests);
    		this.paramList = paramList;
    	}
    
    	public void setHeadline(String newHeadline) {
    		headline = newHeadline;
    	}
    
    	public static <C> void run(C cntnr, List<Test<C>> tests) {
    		new Tester<C>(cntnr, tests).timedTest();
    	}
    
    	public static <C> void run(C cntnr, List<Test<C>> tests, TestParam[] paramList) {
    		new Tester<C>(cntnr, tests, paramList).timedTest();
    	}
    
    	private void displayHeader() {
    		int width = fieldWidth * tests.size() + sizeWidth;
    		int dashLength = width - headline.length() - 1;
    		StringBuilder head = new StringBuilder(width);
    		for (int i = 0; i < dashLength / 2; i++) {
    			head.append('-');
    		}
    		head.append(' ');
    		head.append(headline);
    		head.append(' ');
    		for (int i = 0; i < dashLength / 2; i++) {
    			head.append('-');
    		}
    		System.out.println(head);
    		System.out.format(sizeField, "size");
    		for (Test test : tests) {
    			System.out.format(stringField(), test.name);
    		}
    		System.out.println();
    	}
    
    	public void timedTest() {
    		displayHeader();
    		for (TestParam param : paramList) {
    			System.out.format(sizeField, param.size);
    			for (Test<C> test : tests) {
    				C kontainer = initialize(param.size);
    				long start = System.nanoTime();
    				int reps = test.test(kontainer, param);
    				long duration = System.nanoTime() - start;
    				long timePerRep = duration / reps;
    				System.out.format(numberField(), timePerRep);
    			}
    			System.out.println();
    		}
    	}
    }

stringField()和numberField()方法会产生用于输出结果的格式化字符串，格式化的标准宽度可以通过修改静态的fieldWidth的值进行调整。displayHeader()方法为每个测试格式化和打印头信息。

如果你需要执行特殊的初始化，那么可以覆盖initialize()方法，这将产生具有恰当尺寸的容器对象——你可以修改现有的容器对象，或者创建新的容器对象。在test()方法中可以看到，其结果被捕获在一个被称为kontainer的局部引用中，这使得你可以将所存储的成员container替换为完全不同的被初始化的容器。

每个Test.test()方法的返回值都必须是该测试执行的操作的数量，这些测试都会计算其所有操作所需的纳秒级。你应该意识到，通常System.nanoTime()所产生的值的粒度都会大于1（这个粒度会随机器和操作系统的不同而不同），因此，在结果中可能会存在某些时间点上的重合。

执行的结果可能会随机器的不同而不同，这些测试只是想要比较不同容器的性能。

### 二、对List的选择 ###

下面是对List操作中最本质部分的性能测试。为了进行比较，它还展示了Queue中最重要的操作。该程序创建了两个分离的用于测试每一种容器类的测试列表。在本例中，Queue操作只应用到LinkedList上：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.ListIterator;
    import java.util.Random;
    import java.util.Vector;
    
    import com.buba.util.CountingGenerator;
    import com.buba.util.CountingIntegerList;
    import com.buba.util.Generated;
    
    public class ListPerformance {
    	static Random r = new Random();
    	static int reps = 1000;
    	static List<Test<List<Integer>>> tests = new ArrayList<>();
    	static List<Test<LinkedList<Integer>>> qTests = new LinkedList<>();
    	static {
    		tests.add(new Test<List<Integer>>("add") {
    			@Override
    			int test(List<Integer> container, TestParam tp) {
    				int loops = tp.loops;
    				int listSize = tp.size;
    				for (int i = 0; i < loops; i++) {
    					container.clear();
    					for (int j = 0; j < listSize; j++) {
    						container.add(j);
    					}
    				}
    				return loops * listSize;
    			}
    		});
    
    		tests.add(new Test<List<Integer>>("get") {
    			@Override
    			int test(List<Integer> container, TestParam tp) {
    				int loops = tp.loops * reps;
    				int listSize = container.size();
    				for (int i = 0; i < loops; i++) {
    					container.get(r.nextInt(listSize));
    				}
    				return loops;
    			}
    		});
    
    		tests.add(new Test<List<Integer>>("set") {
    			@Override
    			int test(List<Integer> container, TestParam tp) {
    				int loops = tp.loops * reps;
    				int listSize = container.size();
    				for (int i = 0; i < loops; i++) {
    					container.set(r.nextInt(listSize), 47);
    				}
    				return loops;
    			}
    		});
    
    		tests.add(new Test<List<Integer>>("iteradd") {
    			@Override
    			int test(List<Integer> container, TestParam tp) {
    				final int LOOPS = 100000;
    				int half = container.size() / 2;
    				ListIterator<Integer> it = container.listIterator(half);
    				for (int i = 0; i < LOOPS; i++) {
    					it.add(47);
    				}
    				return LOOPS;
    			}
    		});
    
    		tests.add(new Test<List<Integer>>("insert") {
    			@Override
    			int test(List<Integer> container, TestParam tp) {
    				int loops = tp.loops;
    				for (int i = 0; i < loops; i++) {
    					container.add(5, 47);
    				}
    				return loops;
    			}
    		});
    
    		tests.add(new Test<List<Integer>>("remove") {
    			@Override
    			int test(List<Integer> container, TestParam tp) {
    				int loops = tp.loops;
    				int size = tp.size;
    				for (int i = 0; i < loops; i++) {
    					container.clear();
    					container.addAll(new CountingIntegerList(size));
    					while (container.size() > 5)
    						container.remove(5);
    				}
    				return loops * size;
    			}
    		});
    
    		qTests.add(new Test<LinkedList<Integer>>("addFirst") {
    			@Override
    			int test(LinkedList<Integer> container, TestParam tp) {
    				int loops = tp.loops;
    				int size = tp.size;
    				for (int i = 0; i < loops; i++) {
    					container.clear();
    					for (int j = 0; j < size; j++) {
    						container.addFirst(47);
    					}
    				}
    				return loops * size;
    			}
    		});
    
    		qTests.add(new Test<LinkedList<Integer>>("addLast") {
    			@Override
    			int test(LinkedList<Integer> container, TestParam tp) {
    				int loops = tp.loops;
    				int size = tp.size;
    				for (int i = 0; i < loops; i++) {
    					container.clear();
    					for (int j = 0; j < size; j++) {
    						container.addLast(47);
    					}
    				}
    				return loops * size;
    			}
    		});
    
    		qTests.add(new Test<LinkedList<Integer>>("rmFirst") {
    			@Override
    			int test(LinkedList<Integer> container, TestParam tp) {
    				int loops = tp.loops;
    				int size = tp.size;
    				for (int i = 0; i < loops; i++) {
    					container.clear();
    					container.addAll(new CountingIntegerList(size));
    					while (container.size() > 0)
    						container.removeFirst();
    				}
    				return loops * size;
    			}
    		});
    
    		qTests.add(new Test<LinkedList<Integer>>("rmLast") {
    			@Override
    			int test(LinkedList<Integer> container, TestParam tp) {
    				int loops = tp.loops;
    				int size = tp.size;
    				for (int i = 0; i < loops; i++) {
    					container.clear();
    					container.addAll(new CountingIntegerList(size));
    					while (container.size() > 0)
    						container.removeLast();
    				}
    				return loops * size;
    			}
    		});
    	}
    
    	static class ListTester extends Tester<List<Integer>> {
    
    		public ListTester(List<Integer> container, List<Test<List<Integer>>> tests) {
    			super(container, tests);
    		}
    
    		@Override
    		protected List<Integer> initialize(int size) {
    			container.clear();
    			container.addAll(new CountingIntegerList(size));
    			return container;
    		}
    
    		public static void run(List<Integer> list, List<Test<List<Integer>>> tests) {
    			new ListTester(list, tests).timedTest();
    		}
    	}
    
    	public static void main(String[] args) {
    		if (args.length > 0) {
    			Tester.defaultParams = TestParam.array(args);
    		}
    		Tester<List<Integer>> arrayTest = new Tester<List<Integer>>(null, tests.subList(1, 3)) {
    			@Override
    			protected List<Integer> initialize(int size) {
    				Integer[] ia = Generated.array(Integer.class, new CountingGenerator.Integer(), size);
    				return Arrays.asList(ia);
    			}
    		};
    		Tester.fieldWidth = 12;
    		arrayTest.setHeadline("Array as List");
    		arrayTest.timedTest();
    		Tester.defaultParams = TestParam.array(10, 5000, 100, 5000, 1000, 1000, 10000, 200);
    		if (args.length > 0)
    			Tester.defaultParams = TestParam.array(args);
    		ListTester.run(new ArrayList<Integer>(), tests);
    		ListTester.run(new LinkedList<Integer>(), tests);
    		ListTester.run(new Vector<Integer>(), tests);
    		Tester<LinkedList<Integer>> qTest = new Tester<>(new LinkedList<Integer>(), qTests);
    		qTest.setHeadline("Queue tests");
    		qTest.timedTest();
    	}
    }

每个测试都需要仔细的思考，以确保可以产生有意义的结果。例如，add测试首先清除List，然后重新填充它到指定的列表尺寸。因此，clear()的调用也就成了该测试的一部分，并且可能会对执行时间产生影响，尤其是对小型的测试。尽管这里的结果看起来相当合理，但是你可以设想重写测试框架，使得在计时循环之外有一个对准备方法的调用（在本例中将包括clear()调用）。

注意，对于每个测试，都必须准确的计算将要发生的操作的数量以及从test()中返回的值，因此计时是正确的。

get和set测试都使用了随机数生成器来执行对List的随机访问。在输出中，你可以看到，对于背后有数组支撑的List和ArrayList，无论列表的大小如何，这些访问都很快速和一致；而对于LinkedList，访问时间对于较大的列表将明显增加。很显然，如果你需要执行大量的随机访问，链接链表不会是一种好的选择。

iteradd测试使用迭代器在列表中间插入新的元素。对于ArrayList，当列表变大时，其开销将变得很高昂，但是对于LinkedList，相对来说比较低廉，并且不随列表尺寸而发生变化。这是因为ArrayList在插入时，必须创建空间将它的所有引用向前移动，这会随ArrayList的尺寸增加而产生高昂的代价。LinkedList只需链接新的元素，而不必修改列表中剩余的元素，因此你可以认为无论列表尺寸如何变化，其代价大致相同。

insert和remove测试都使用了索引位置5作为插入或移除点，而没有选择List两端的元素。LinkedList对List的端点会进行特殊处理——这使得在将LinkedList用作Queue时，速度可以得到提高。但是，如果你在列表的中间增加或移除元素，其中会包含随机访问的代价，我们已经看到了，这在不同的List实现中变化很大。当执行在位置5的插入和移除时，随机访问的代价应该可以被忽略，但是我们将看不到对LinkedList端点所做的任何特殊优化操作。从输出中可以看出，在LinkedList中的插入和移除代价相当低廉，并且不会随着列表尺寸发生变化，但是对于ArrayList，插入操作代价特别高昂，并且其代价将随列表尺寸的增加而增加。

从Queue测试中，你可以看到LinkedList可以多么快速地从列表的端点插入和移除元素，这正是对Queue行为所做的优化。

通常，你可以只调用Tester.run()，传递容器和tests列表。但是，这里我们必须覆盖initialize()方法，使得List在每次测试之前，都会被清空并重新填充，否则在不同的测试过程中，对于List尺寸的控制将丧失。ListTester继承自Tester，并使用CountingIntegerList执行这种初始化。run()便捷方法也被覆盖了。

我们还想将数组访问与容器访问进行比较（主要是与ArrayList比较）。在main()的第一个测试中，使用匿名内部类创建了一个特殊的Test对象。initialize()方法被覆盖为在每次被调用时都创建一个新对象（此时会忽略container对象，因此对于这个Tester构造器来说，null就是传递进来的container参数）。这个新对象是使用Generated.array()和Arrays.asList()创建的。在本例中，只有两个测试可以执行，因为你不能在使用背后有数组支撑的List时，插入或移除元素，因此List.subList()方法方法被用来在tests列表中选取想要执行的测试。

对于随机访问的get()和set()操作，背后有数组支撑的List只比ArrayList稍快一点，但是对于LinkedList，相同的操作会变得异常引人注目的高昂，因为它本来就不是针对随机访问操作而设计的。

应该避免使用Vector，它只存在于支持遗留代码的类库中（在此程序中它能正常的工作的唯一原因，只是因为为了向前兼容，它被适配成了List）。

最佳的做法可能是将ArrayList作为默认的首选，只有你需要使用额外的功能，或者当前程序的性能因为经常从表中间进行插入和删除而变差的时候，才去选择LinkedList。如果使用的是固定数量的元素，那么既可以选择使用背后有数组支撑的List（就像Arrays.asList()产生的列表），也可以选择真正的数组。

CopyOnWriteArrayList是List的一个特殊实现，专门用于并发编程，我们将在并发章节中讨论它。

**如果本文对您有很大的帮助，还请点赞关注一下。**