图三：存储连续块的object引用的ArrayList
在ArrayList中使用值类型，将额外进行封箱(boxing)和撤箱(unboxing)操作，当你的应用程序是一个很大的ArrayList，并频繁进行读写操作时，会很大程度上影响程序性能。如图3所示，对于引用类型而言，ArrayList和数组的内存分配是相同的。
比较数组而言，ArrayList的自增长并不会导致任何性能的下降。如果你知道存储到ArrayList的元素的准确数量，可以通过ArrayList构造函数初始化容量以关闭其自增长功能。而对于数组，当你不知道具体容量时，不得不在插入的数据元素超过数组长度的时候，手动改变数组的大小。 一个经典的计算机科学问题是：当程序运行时超出了缓存空间，应该分配多少新的空间为最佳。一种方案是是原来分配空间的基础上每次加1。例如数组最初分配了5个元素，那么在插入第6个元素之前，将其长度增加为6。显然，这种方案最大程度上节约了内存空间，但代价太大，因为每插入一个新元素都要进行一次再分配操作。
另一种方案刚好相反，也就是每次分配都在原来大小的基础上增加100倍。如果数组最初分配了5个元素，那么在插入第6个元素之前，数组空间增长为500。显然，该方案大大地减少了再分配操作的次数，但仅当插入极少的数据元素时，就会有上百的元素空间未使用，实在太浪费空间了！
ArrayList的渐近运行时间和标准数组一样。即使对ArrayList的操作是高开销的，尤其是存储值类型，其元素个数和每次操作的代价之间的关系与标准数组相同。 考察数据结构——第二部分：队列、堆栈和哈希表[译]
相关文档
考察数据结构——第一部分:数据结构简介 考察数据结构——第三部分：二叉树和BSTs
原文链接：Part 2: The Queue, Stack, and Hashtable
本文是\考察数据结构\系列文章的第二部分，考察了三种研究得最多的数据结构：队列（Queue)，堆栈（Stack)和哈希表（Hashtable)。正如我们所知，Quenu和Stack其实一种特殊的ArrayList，提供大量不同类型的数据对象的存储，只不过访问这些元素的顺序受到了
限制。Hashtable则提供了一种类数组（array-like)的数据抽象，它具有更灵活的索引访问。数组需要通过序数进行索引，而Hashtable允许通过任何一种对象索引数据项。 目录： 简介
―排队顺序‖的工作进程
―反排队顺序‖——堆栈数据结构 序数索引限制
System.Collections.Hashtable类 结论 简介
在第一部分中，我们了解了什么是数据结构，评估了它们各自的性能，并了解了选择何种数据结构对特定算法的影响。另外我们还了解并分析了数据结构的基础知识，介绍了一种最常用的数据结构：数组。
数组存储了同一类型的数据，并通过序数进行索引。数组实际的值是存储在一段连续的内存空间中，因此读写数组中特定的元素非常迅速。
因其具有的同构性及定长性，.Net Framework基类库提供了ArrayList数据结构，它可以存储不同类型的数据，并且不需要显式地指定长度。前文所述，ArrayList本质上是存储object类型的数组，每次调用Add()方法增加元素，内部的object数组都要检查边界，如果超出，数组会自动以倍数增加其长度。
第二部分，我们将继续考察两种类数组结构：Queue和Stack。和ArrayList相似，他们也是一段相邻的内存块以存储不同类型的元素，然而在访问数据时，会受到一定的限制。
之后，我们还将深入了解Hashtable数据结构。有时侯，我们可以把Hashtable看作杀一种关联数组（associative array)，它同样是存储不同类型元素的集合，但它可通过任意对象（例如string)来进行索引，而非固定的序数。
―排队顺序‖的工作进程
如果你要创建不同的服务，这种服务也就是通过多种资源以响应多种请求的程序；那么当处理这些请求时，如何决定其响应的顺序就成了创建服务的一大难题。通常解决的方案有两种： ―排队顺序‖原则
―基于优先等级‖的处理原则
当你在商店购物、银行取款的时候，你需要排队等待服务。―排队顺序‖原则规定排在前面的比后面的更早享受服务。而―基于优先等级‖原则，则根据其优先等级的高低决定服务顺序。例如在医院的急诊室，生命垂危的病人会比病情轻的更先接受医生的诊断，而不用管是谁先到的。 设想你需要构建一个服务来处理计算机所接受到的请求，由于收到的请求远远超过计算机处理的速度，因此你需要将这些请求按照他们递交的顺序依此放入到缓冲区中。
一种方案是使用ArrayList，通过称为nextJobPos的整型变量来指定将要执行的任务在数组中的位置。当新的工作请求进入，我们就简单使用ArrayList的Add()方法将其添加到ArrayList的末端。当你准备处理缓冲区的任务时，就通过nextJobPos得到该任务在ArrayList的位置值以获取该任务，同时将nextJobPos累加1。下面的程序实现该算法： using System;
using System.Collections; public class JobProcessing {
private static ArrayList jobs = new ArrayList(); private static int nextJobPos = 0;
public static void AddJob(string jobName) {
jobs.Add(jobName); }
public static string GetNextJob()
{
if (nextJobPos > jobs.Count - 1) return \ else {
string jobName = (string) jobs[nextJobPos]; nextJobPos++; return jobName; } }
public static void Main() {
AddJob(\ AddJob(\
Console.WriteLine(GetNextJob()); AddJob(\
Console.WriteLine(GetNextJob()); Console.WriteLine(GetNextJob()); Console.WriteLine(GetNextJob()); Console.WriteLine(GetNextJob()); AddJob(\ AddJob(\
Console.WriteLine(GetNextJob()); } }
输出结果如下： 1 2 3
NO JOBS IN BUFFER NO JOBS IN BUFFER 4
这种方法简单易懂，但效率却可怕得难以接受。因为，即使是任务被添加到buffer中后立即被处理，ArrayList的长度仍然会随着添加到buffer中的任务而不断增加。假设我们从缓冲区添加并移除一个任务需要一秒钟，这意味一秒钟内每调用AddJob()方法，就要调用一次ArrayList的Add()方法。随着Add()方法持续不断的被调用，ArrayList内部数组长度就会根据需求持续不断的成倍增长。五分钟后，ArrayList的内部数组增加到了512个元素的长度，这时缓冲区中却只有不到一个任务而已。照这样的趋势发展，只要程序继续运行，工作任务继续进入，ArrayList的长度自然会继续增长。
出现如此荒谬可笑的结果，原因是已被处理过的旧任务在缓冲区中的空间没有被回收。也即是说，当第一个任务被添加到缓冲区并被处理后，此时ArrayList的第一元素空间应该被再利用。想想上述代码的工作流程，当插入两个工作——AddJob(\和AddJob(\后——ArrayList的
空间如图一所示：
图一：执行前两行代码后的ArrayList