常用数据结构的时间复杂度
DataStructurAddFindDltGtByIndxArray(T[])O(n)O(n)O(n)O(1)Linkdlist(LinkdListT)O(1)O(n)O(n)O(n)Rsizablarraylist(ListT)O(1)O(n)O(n)O(1)Stack(StackT)O(1)-O(1)-Quu(QuuT)O(1)-O(1)-Hashtabl(DictionaryK,T)O(1)O(1)O(1)-Tr-basddictionary(SortdDictionaryK,T)O(logn)O(logn)O(logn)-Hashtablbasdst(HashStT)O(1)O(1)O(1)-Trbasdst(SortdStT)O(logn)O(logn)O(logn)-如何选择数据结构
Array(T[])
当元素的数量是固定的，并且需要使用下标时。
Linkdlist(LinkdListT)
当元素需要能够在列表的两端添加时。否则使用ListT。
Rsizablarraylist(ListT)
当元素的数量不是固定的，并且需要使用下标时。
Stack(StackT)
当需要实现LIFO（LastInFirstOut）时。
Quu(QuuT)
当需要实现FIFO（FirstInFirstOut）时。
Hashtabl(DictionaryK,T)
当需要使用键值对（Ky-Valu）来快速添加和查找，并且元素没有特定的顺序时。
Tr-basddictionary(SortdDictionaryK,T)
当需要使用价值对（Ky-Valu）来快速添加和查找，并且元素根据Ky来排序时。
Hashtablbasdst(HashStT)
当需要保存一组唯一的值，并且元素没有特定顺序时。
Trbasdst(SortdStT)
当需要保存一组唯一的值，并且元素需要排序时。
Array在计算机程序设计中，数组（Array）是最简单的而且应用最广泛的数据结构之一。在任何编程语言中，数组都有一些共性：
数组中的内容是使用连续的内存（ContiguousMmory）来存储的。
数组中的所有元素必须是相同的类型，或者类型的衍生类型。因此数组又被认为是同质数据结构（HomgnousDataStructurs）。
数组的元素可以直接被访问。比如你需要访问数组的第i个元素，则可以直接使用arrayNam[i]来访问。
对于数组的常规操作包括：
分配空间（Allocation）
数据访问（Accssing）
在C#中，可以通过如下的方式声明数组变量。
intallocationSiz=10;bool[]boolanArray=nwbool[allocationSiz];FilInfo[]filInfoArray=nwFilInfo[allocationSiz];
上面的代码将在CLR托管堆中分配一块连续的内存空间，用以容纳数量为allocationSiz，类型为arrayTyp的数组元素。如果arrayTyp为值类型，则将会有allocationSiz个未封箱（unboxd）的arrayTyp值被创建。如果arrayTyp为引用类型，则将会有allocationSiz个arrayTyp类型的引用被创建。
如果我们为FilInfo[]数组中的一些位置赋上值，则引用关系为下图所示。
.NET中的数组都支持对元素的直接读写操作。语法如下：
1//读数组元素boolb=boolanArray[7];34//写数组元素5boolanArray[0]=fals;访问一个数组元素的时间复杂度为O(1)，因此对数组的访问时间是恒定的。也就是说，与数组中包含的元素数量没有直接关系，访问一个元素的时间是相同的。
ArrayList由于数组是固定长度的，并且数组中只能存储同一种类型或类型的衍生类型。这在使用中会受到一些限制。.NET提供了一种数据结构ArrayList来解决这些问题。
1ArrayListcountDown=nwArrayList();countDown.Add(3);3countDown.Add();4countDown.Add(1);5countDown.Add(blastoff!);6countDown.Add(nwArrayList());ArrayList是长度可变的数组，并且它可以存储不同类型的元素。
但这些灵活性是以牺牲性能为代价的。在上面Array的描述中，我们知道Array在存储值类型时是采用未装箱（unboxd）的方式。由于ArrayList的Add方法接受objct类型的参数，导致如果添加值类型的值会发生装箱（boxing）操作。这在频繁读写ArrayList时会产生额外的开销，导致性能下降。
ListT当.NET中引入泛型功能后，上面ArrayList所带来的性能代价可以使用泛型来消除。.NET提供了新的数组类型ListT。
泛型允许开发人员在创建数据结构时推迟数据类型的选择，直到使用时才确定选择哪种类型。泛型（Gnrics）的主要优点包括：
类型安全（TypSafty）：使用泛型定义的类型，在使用时仅能使用指定的类型或类型的衍生类型。
性能（Prformanc）：泛型移除了运行时类型检测，消除了装箱和拆箱的开销。
可重用（Rusability）：泛型打破了数据结构与存储数据类型之间的紧耦合。这提高了数据结构的可重用性。
ListT等同于同质的一维数组（Homognousslf-rdimnsioningarray）。它像Array一样可以快速的读取元素，还可以保持长度可变的灵活性。
1//创建int类型列表ListintmyFavoritIntgrs=nwListint();34//创建string类型列表5ListstringfrindsNams=nwListstring();ListT内部同样使用Array来实现，但它隐藏了这些实现的复杂性。当创建ListT时无需指定初始长度，当添加元素到ListT中时，也无需关心数组大小的调整（rsiz）问题。
1ListintpowrsOf=nwListint();3powrsOf.Add(1);4powrsOf.Add();56powrsOf[1]=10;78intsum=powrsOf[1]+powrsOf[];ListT的渐进运行时（AsymptoticRunningTim）复杂度与Array是相同的。
LinkdListT在链表（LinkdList）中，每一个元素都指向下一个元素，以此来形成了一个链（chain）。
在创建一个链表时，我们仅需持有头节点had的引用，这样通过逐个遍历下一个节点nxt即可找到所有的节点。
链表与数组有着同样的线性运行时间O(n)。例如在上图中，如果我们要查找Sam节点，则必须从头节点Scott开始查找，逐个遍历下一个节点直到找到Sam。
同样，从链表中删除一个节点的渐进时间也是线性的O(n)。因为在删除之前我们仍然需要从had开始遍历以找到需要被删除的节点。而删除操作本身则变得简单，即让被删除节点的左节点的nxt指针指向其右节点。下图展示了如何删除一个节点。
向链表中插入一个新的节点的渐进时间取决于链表是否是有序的。如果链表不需要保持顺序，则插入操作就是常量时间O(1)，可以在链表的头部或尾部添加新的节点。而如果需要保持链表的顺序结构，则需要查找到新节点被插入的位置，这使得需要从链表的头部had开始逐个遍历，结果就是操作变成了O(n)。下图展示了插入节点的示例。
链表与数组的不同之处在于，数组的中的内容在内存中时连续排列的，可以通过下标来访问，而链表中内容的顺序则是由各对象的指针所决定，这就决定了其内容的排列不一定是连续的，所以不能通过下标来访问。如果需要更快速的查找操作，使用数组可能是更好的选择。
使用链表的最主要的优势就是，向链表中插入或删除节点无需调整结构的容量。而相反，对于数组来说容量始终是固定的，如果需要存放更多的数据，则需要调整数组的容量，这就会发生新建数组、数据拷贝等一系列复杂且影响效率的操作。即使是ListT类，虽然其隐藏了容量调整的复杂性，但仍然难逃性能损耗的惩罚。
链表的另一个优点就是特别适合以排序的顺序动态的添加新元素。如果要在数组的中间的某个位置添加新元素，不仅要移动所有其余的元素，甚至还有可能需要重新调整容量。
所以总结来说，数组适合数据的数量是有上限的情况，而链表适合元素数量不固定的情况。
在.NET中已经内置了LinkdListT类，该类实现了双向链表（doubly-linkdlist）功能，也就是节点同时持有其左右节点的引用。而对于删除操作，如果使用Rmov(T)，则运算复杂度为O(n)，其中n为链表的长度。而如果使用Rmov(LinkdListNodT)，则运算复杂度为O(1)。
QuuT当我们需要使用先进先出顺序（FIFO）的数据结构时，.NET为我们提供了QuuT。QuuT类提供了Enquu和Dquu方法来实现对QuuT的存取。
QuuT内部建立了一个存放T对象的环形数组，并通过had和tail变量来指向该数组的头和尾。
默认情况下，QuuT的初始化容量是3，也可以通过构造函数指定容量。
Enquu方法会判断QuuT中是否有足够容量存放新元素。如果有，则直接添加元素，并使索引tail递增。在这里的tail使用求模操作以保证tail不会超过数组长度。如果容量不够，则QuuT根据特定的增长因子扩充数组容量。
默认情况下，增长因子（growthfactor）的值为.0，所以内部数组的长度会增加一倍。也可以通过构造函数中指定增长因子。QuuT的容量也可以通过TrimExcss方法来减少。
Dquu方法根据had索引返回当前元素，之后将had索引指向null，再递增had的值。
StackT当需要使用后进先出顺序（LIFO）的数据结构时，.NET为我们提供了StackT。StackT类提供了Push和Pop方法来实现对StackT的存取。
StackT中存储的元素可以通过一个垂直的集合来形象的表示。当新的元素压入栈中（Push）时，新元素被放到所有其他元素的顶端。当需要弹出栈（Pop）时，元素则被从顶端移除。
StackT的默认容量是10。和QuuT类似，StackT的初始容量也可以在构造函数中指定。StackT的容量可以根据实际的使用自动的扩展，并且可以通过TrimExcss方法来减少容量。
如果StackT中元素的数量Count小于其容量，则Push操作的复杂度为O(1)。如果容量需要被扩展，则Push操作的复杂度变为O(n)。Pop操作的复杂度始终为O(1)。
Hashtabl现在假设我们要使用员工的社保号作为唯一标识进行存储。社保号的格式为DDD-DD-DDDD（D的范围为数字0-9）。
如果使用Array存储员工信息，要查询社保号为--的员工，则将会尝试遍历数组的所有位置，即执行渐进时间为O(n)的查询操作。好一些的办法是将社保号排序，以使查询渐进时间降低到O(log(n))。但理想情况下，我们更希望查询渐进时间为O(1)。
一种方案是建立一个大数组，范围从-00-0到-99-9。
这种方案的缺点是浪费空间。如果我们仅需要存储1个员工的信息，那么仅利用了0.1%的空间。
第二种方案就是用哈希函数（HashFunction）压缩序列。
我们选择使用社保号的后四位作为索引，以减少区间的跨度。这样范围将从0到9。
在数学上，将这种从9位数转换为4位数的方式称为哈希转换（Hashing）。可以将一个数组的索引空间（indxrsspac）压缩至相应的哈希表（HashTabl）。
在上面的例子中，哈希函数的输入为9位数的社保号，输出结果为后4位。
H(x)=lastfourdigitsofx上图中也说明在哈希函数计算中常见的一种行为：哈希冲突（HashCollisions）。即有可能两个社保号的后4位均为0。
当要添加新元素到Hashtabl中时，哈希冲突是导致操作被破坏的一个因素。如果没有冲突发生，则元素被成功插入。如果发生了冲突，则需要判断冲突的原因。因此，哈希冲突提高了操作的代价，Hashtabl的设计目标就是要尽可能减低冲突的发生。
处理哈希冲突的方式有两种：避免和解决，即冲突避免机制（CollisionAvoidanc）和冲突解决机制（CollisionRsolution）。
避免哈希冲突的一个方法就是选择合适的哈希函数。哈希函数中的冲突发生的几率与数据的分布有关。例如，如果社保号的后4位是随即分布的，则使用后4位数字比较合适。但如果后4位是以员工的出生年份来分配的，则显然出生年份不是均匀分布的，则选择后4位会造成大量的冲突。我们将这种选择合适的哈希函数的方法称为冲突避免机制（CollisionAvoidanc）。
在处理冲突时，有很多策略可以实施，这些策略称为冲突解决机制（CollisionRsolution）。其中一种方法就是将要插入的元素放到另外一个块空间中，因为相同的哈希位置已经被占用。
通常采用的冲突解决策略为开放寻址法（OpnAddrssing），所有的元素仍然都存放在哈希表内的数组中。
开放寻址法的最简单的一种实现就是线性探查（LinarProbing），步骤如下：
当插入新的元素时，使用哈希函数在哈希表中定位元素位置；
检查哈希表中该位置是否已经存在元素。如果该位置内容为空，则插入并返回，否则转向步骤3。
如果该位置为i，则检查i+1是否为空，如果已被占用，则检查i+，依此类推，直到找到一个内容为空的位置。
现在如果我们要将五个员工的信息插入到哈希表中：
Alic(-33-)
Bob(-44-)
Cal(-55-)
Danny(-00-)
Edward(-00-)
则插入后的哈希表可能如下：
元素的插入过程：
Alic的社保号被哈希为，因此存放在位置。
Bob的社保号被哈希为，但由于位置处已经存放Alic的信息，则检查下一个位置，为空，则Bob的信息就被放到。
Cal的社保号被哈希为，位置为空，所以Cal就放到处。
Danny的社保号被哈希为，已被占用，则检查位置是否为空，为空，所以Danny就被放到。
Edward的社保号被哈希为，已被占用，检查，也被占用，再检查，直到检查到时，该位置为空，于是Edward被放到了位置。
线性探查（LinarProbing）方式虽然简单，但并不是解决冲突的最好的策略，因为它会导致同类哈希的聚集（PrimaryClustring）。这导致搜索哈希表时，冲突依然存在。例如上面例子中的哈希表，如果我们要访问Edward的信息，因为Edward的社保号-00-哈希为，然而我们在位置找到的是Bob，所以再搜索，找到的却是Danny，以此类推直到找到Edward。
一种改进的方式为二次探查（QuadraticProbing），即每次检查位置空间的步长为平方倍数。也就是说，如果位置s被占用，则首先检查s+1处，然后检查s-1，s+，s-，s+3依此类推，而不是象线性探查那样以s+1，s+...方式增长。尽管如此，二次探查同样也会导致同类哈希聚集问题（ScondaryClustring）。
.NET中的Hashtabl类的实现，要求添加元素时不仅要提供元素（Itm），还要为该元素提供一个键（Ky）。例如，Ky为员工社保号，Itm为员工信息对象。可以通过Ky作为索引来查找Itm。
1Hashtablmploys=nwHashtabl();3//AddsomvalustothHashtabl,indxdbyastringky4mploys.Add(--,Scott);5mploys.Add(-33-4,Sam);6mploys.Add(-44-55,Jisun);78//Accssaparticularky9if(mploys.ContainsKy(--))10{11stringmpNam=(string)mploys[--];1Consol.WritLin(Employ--snamis:+mpNam);13}14ls15Consol.WritLin(Employ--isnotinthhashtabl...);Hashtabl类中的哈希函数比前面介绍的社保号的实现要更为复杂。哈希函数必须返回一个序数（OrdinalValu）。对于社保号的例子，通过截取后四位就可以实现。但实际上Hashtabl类可以接受任意类型的值作为Ky，这都要归功于GtHashCod方法，一个定义在Systm.Objct中的方法。GtHashCod的默认实现将返回一个唯一的整数，并且保证在对象的生命周期内保持不变。
Hashtabl类中的哈希函数定义如下：
H(ky)=[GtHash(ky)+1+(((GtHash(ky)5)+1)%(hashsiz–1))]%hashsiz这里的GtHash(ky)默认是调用ky的GtHashCod方法以获取返回的哈希值。hashsiz指的是哈希表的长度。因为要进行求模，所以最后的结果H(ky)的范围在0至hashsiz-1之间。
当在哈希表中添加或获取一个元素时，会发生哈希冲突。前面我们简单地介绍了两种冲突解决策略：
线性探查（LinarProbing）
二次探查（QuadraticProbing）
在Hashtabl类中则使用的是一种完全不同的技术，称为二度哈希（rhashing）（有些资料中也将其称为双重哈希（doublhashing））。
二度哈希的工作原理如下：
有一个包含一组哈希函数H1...Hn的集合。当需要从哈希表中添加或获取元素时，首先使用哈希函数H1。如果导致冲突，则尝试使用H，以此类推，直到Hn。所有的哈希函数都与H1十分相似，不同的是它们选用的乘法因子（multiplicativfactor）。
通常，哈希函数Hk的定义如下：
Hk(ky)=[GtHash(ky)+k*(1+(((GtHash(ky)5)+1)%(hashsiz–1)))]%hashsiz当使用二度哈希时，重要的是在执行了hashsiz次探查后，哈希表中的每一个位置都有且只有一次被访问到。也就是说，对于给定的ky，对哈希表中的同一位置不会同时使用Hi和Hj。在Hashtabl类中使用二度哈希公式，其始终保持(1+(((GtHash(ky)5)+1)%(hashsiz–1))与hashsiz互为素数（两数互为素数表示两者没有共同的质因子）。
二度哈希使用了Θ(m)种探查序列，而线性探查（LinarProbing）和二次探查（QuadraticProbing）使用了Θ(m)种探查序列，故二度哈希提供了更好的避免冲突的策略。
Hashtabl类中包含一个私有成员变量loadFactor，loadFactor指定了哈希表中元素数量与位置（slot）数量之间的最大比例。例如：如果loadFactor等于0.5，则说明哈希表中只有一半的空间存放了元素值，其余一半都为空。
哈希表的构造函数允许用户指定loadFactor值，定义范围为0.1到1.0。然而，不管你提供的值是多少，范围都不会超过7%。即使你传递的值为1.0，Hashtabl类的loadFactor值还是0.7。微软认为loadFactor的最佳值为0.7，这平衡了速度与空间。因此虽然默认的loadFactor为1.0，但系统内部却自动地将其改变为0.7。所以，建议你使用缺省值1.0（但实际上是0.7）。
向Hashtabl中添加新元素时，需要检查以保证元素与空间大小的比例不会超过最大比例。如果超过了，哈希表空间将被扩充。步骤如下：
哈希表的位置空间几乎被翻倍。准确地说，位置空间值从当前的素数值增加到下一个最大的素数值。
因为二度哈希时，哈希表中的所有元素值将依赖于哈希表的位置空间值，所以表中所有值也需要重新二度哈希。
由此看出，对哈希表的扩充将是以性能损耗为代价。因此，我们应该预先估计哈希表中最有可能容纳的元素数量，在初始化哈希表时给予合适的值进行构造，以避免不必要的扩充。
DictionaryK,THashtabl类是一个类型松耦合的数据结构，开发人员可以指定任意的类型作为Ky或Itm。当.NET引入泛型支持后，类型安全的DictionaryK,T类出现。DictionaryK,T使用强类型来限制Ky和Itm，当创建DictionaryK,T实例时，必须指定Ky和Itm的类型。
DictionarykyTyp,valuTypvariablNam=nwDictionarykyTyp,valuTyp();如果继续使用上面描述的社保号和员工的示例，我们可以创建一个DictionaryK,T的实例：
Dictionaryint,EmploymployData=nwDictionaryint,Employ();这样我们就可以添加和删除员工信息了。
1//AddsommploysmployData.Add()=nwEmploy(ScottMitchll);3mployData.Add()=nwEmploy(JisunL);45//SifmploywithSSN13-45-workshr6if(mployData.ContainsKy(5))DictionaryK,T与Hashtabl的不同之处还不止一处。除了支持强类型外，DictionaryK,T还采用了不同的冲突解决策略（CollisionRsolutionStratgy），这种技术称为链接技术（chaining）。
前面使用的探查技术（probing），如果发生冲突，则将尝试列表中的下一个位置。如果使用二度哈希（rhashing），则将导致所有的哈希被重新计算。而链接技术（chaining）将采用额外的数据结构来处理冲突。DictionaryK,T中的每个位置（slot）都映射到了一个链表。当冲突发生时，冲突的元素将被添加到桶（buckt）列表中。
下面的示意图中描述了DictionaryK,T中的每个桶（buckt）都包含了一个链表以存储相同哈希的元素。
上图中，该Dictionary包含了8个桶，也就是自顶向下的黄色背景的位置。一定数量的Employ对象已经被添加至Dictionary中。如果一个新的Employ要被添加至Dictionary中，将会被添加至其Ky的哈希所对应的桶中。如果在相同位置已经有一个Employ存在了，则将会将新元素添加到列表的前面。
向Dictionary中添加元素的操作涉及到哈希计算和链表操作，但其仍为常量，渐进时间为O(1)。
对Dictionary进行查询和删除操作时，其平均时间取决于Dictionary中元素的数量和桶（buckt）的数量。具体的说就是运行时间为O(n/m)，这里n为元素的总数量，m是桶的数量。但Dictionary几乎总是被实现为n=O(m)，也就是说，元素的总数绝不会超过桶的总数，所以O(n/m)也变成了常量O(1)。
参考资料
AnExtnsivExaminationofDataStructursUsingC#.0:Part1:AnIntroductiontoDataStructurs
AnExtnsivExaminationofDataStructursUsingC#.0:Part:ThQuu,Stack,andHashtabl
考察数据结构——第一部分：数据结构简介[译]
考察数据结构——第二部分：队列、堆栈和哈希表[译]
本篇文章《常用数据结构及复杂度》由DnnisGao发表自博客园
关于1CTO1CTO是中国互联网第一技术社交与学习平台。为CTO、技术总监，技术专家，架构师、技术经理，高级研发工程师、PM等提供学习成长，教育培训，工作机会、人脉影响力等高价值的在线教育和社交网站。