数据结构

数组和链表

数组

数组是内存地址中连在一起的几个内存单元组成必须是连续的地址

这样的话如果用户在数组中添加数据而数组内存区域中没有相连的内存地址就只能复制数组再进行添加将数组移动到一个连续的地址区域中这样效率会非常慢

链表

链表中的元素可存储在内存的任何地方。

链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。

在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2并从中获取元素#3的地址，以此类推，直到访问最后一个元素。需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低。

数组与此不同：你知道其中每个元素的地址。例如，假设有一个数组，它包含五个元素，起始地址为00，那么连续的5个元素地址为

00、01、02、03、04、05

数组的索引从0开始

下面列出了常见的数组和链表操作的运行时间。

在中间插入

假设要在你原先的数组或者是链表中间插入一个值

链表可以直接修改前一个元素的下个内存地址指向这样很容易实现插入操作
数组则必须将后面的元素后移

如果没有足够的空间，可能还得将整个数组复制到其他地方！因此，当需要在中间插入元素
时，链表是更好的选择。

删除

如果你要删除元素，链表也是最好的选择，因为只需要修改前一个元素的地址指向就可以完成修改。而使用数组时，删除元素后，必须将后面的元素都往前移动。

需要指出的是，仅当能够立即访问要删除的元素时，删除操作的运行时间才为O(1).通常我们都记录了链表的第一个元素和最后一个元素，因此删除这些元素时运行时间为O(1).

栈

栈是一种数据呈线性排列的数据结构，不过在这种数据结构中，我们只能访问最新添加的数据。栈就像是一摞书，拿到新书时我们会把他放在书顶，取书也只能从上面去取。

往栈中添加数据叫做入栈(push),往栈中取出数据叫做出栈(pop)

像栈这种最后添加的数据最先被取出，即“后进先出”的结构，我们称为 Last In First Out，简称 LIFO。与链表和数组一样，栈的数据也是线性排列，但在栈中，添加和删除数据的操作只能在一端进行，访问数据也只能访问到顶端的数据。想要访问中间的数据时，就必须通过出栈操作将目标数据移到栈顶才行。 所以栈在访问最新的数据时非常方便

队列queue

与前面提到的数据结构相同，队列中的数据也呈线性排列。虽然与栈有些相似，但队列中添加和删除数据的操作分别是在两端进行的。就和“队列”这个名字一样，把它想象成排成一队的人更容易理解。在队列中，处理总是从第一名开始往后进行，而新来的人只能排在队尾。

像队列这种最先进去的数据最先被取来，即“先进先出”的结构，我们称为 First In First Out，简称 FIFO。
与栈类似，队列中可以操作数据的位置也有一定的限制。在栈中，数据的添加和删除都在同一端进行，而在队列中则分别是在两端进行的。队列也不能直接访问位于中间的数据，必须通过出队操作将目标数据变成首位后才能访问。

哈希表（散列表）

概念

相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

　　我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。

哈希表存储的是键(key)和值(value)组成的数据

为了和哈希表对比我们先使用数组来存储数据来进行比较

此处准备了 6 个箱子（即长度为 6 的数组）来存储数据。假设我们需要查询Ally的性别，由于不知道Ally的数据存储在哪个箱子里，所以只能从头开始查询。这个操作便叫作“线性查找”

这样只能挨个查找数据量越多线性查找的时间就越长由此可知此处不适合用数组进行存储数据。

但使用哈希表便可以解决这个问题。首先准备好数组，这次我们用5个箱子的数组来存储数据。

使用哈希函数（Hash）计算 Joe的键，也就是字符串“Joe”的哈希值。得到的结果为4928

将得到的哈希值除以数组的长度5，求得其余数。这样的求余运算叫作“mod 运算”。此处mod运算的结果为3。因此，我们将Joe的数据存进数组的3号箱子中。重复前面的操作，将其他数据也存进数组中。

哈希冲突

如果两个mod运算后的值相同原来数组该索引上已经有值时就会产生哈希冲突，哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式，

链地址法

将冲突的数据用链表的方式连接(已有数据的后面继续存储新的数据。)

哈希表的查询方法

假如要查询Dan

为了知道Dan存储在哪个箱子里，首先需要算出Dan键的哈希值，然后对其进行mod运算。最后得到的结果为4，于是我们知道了它存储在4号箱中。

查看 4 号箱可知，其中的数据的键与 Dan 一致，于是取出对应的值。由此我们便知道了Dan的性别为男（M）。

如果想要查询Ally的值该怎么办呢？

为了找到它的存储位置，先要算出Ally键的哈希值，再对其进行mod运算。最终得到的结果为3。

然而3号箱中数据的键是Joe而不是Ally。此时便需要对Joe所在的链表进行线性查找。

于是我们找到了键为Ally的数据。取出其对应的值，便知道了 Ally 的性别为女（F）。

在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突，就使用链表进行存储。这样一来，不管数据量为多少，我们都能够灵活应对。如果数组的空间太小，使用哈希表的时候就容易发生冲突，线性查找的使用频率也会更高；反过来，如果数组的空间太大，就会出现很多空箱子，造成内存的浪费。因此，给数组设定合适的空间非常重要。

填装因子

在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速
度与链表一样快，因此它兼具两者的优点！但在最糟情况下，散列表的各种操作的速度都很慢。
因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有：
 较低的填装因子；
 良好的散列函数。

散列表的填装因子很容易计算。

散列表使用数组来存储数据，因此你需要计算数组中被占用的位置数。例如，下述散列表的填装因子为2/5，即0.4。

假设你要在散列表中存储100种商品的价格，而该散列表包含100个位置。那么在最佳情况下，每个商品都将有自己的位置。这个散列表的填装因子为1。如果这个散列表只有50个位置呢？填充因子将为2。不可能让每种商品都有自己的位置，因为没有足够的位置！填装因子大于1意味着商品数量超过了数组的位置数。一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度（resizing）。

当数组容量达到3/4时，就应该调整散列表的长度。

散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型。
你可能很快会发现自己经常在使用它。
 你可以结合散列函数和数组来创建散列表。
 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
 散列表的查找、插入和删除速度都非常快。
 散列表适合用于模拟映射关系。
 一旦填装因子超过0.7，就该调整散列表的长度。
 散列表可用于缓存数据（例如，在Web服务器上）。
 散列表非常适合用于防止重复。

堆

堆是一种图的树形结构，被用于实现“优先队列”（priority queues）。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点”（node），数据就存储在这些结点中。

这就是堆的示例。结点内的数字就是存储的数据。堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。另外，结点的排列顺序为从上到下，同一行里则为从左到右。

在堆中存储数据时必须遵守这样一条规则：子结点必定大于父结点。因此，最小值被存储在顶端的根结点中。往堆中添加数据时，为了遵守这条规则，一般会 把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端。

添加数据

我们试试往堆里添加数据 5

删除数据

从堆中取出数据 1

如果子节点的数小于父节点的要进行替换

这里由于父结点的6大于子结点（右）的5大于子结点（左）的3，所以将左边的子结点与父结点进行交换。重复这个操作直到数据都符合规则，不再需要交换为止。

现在，子结点（右）的 8 大于父结点的 6 大于子结点（左）的 4，需要将左边的子结点与父结点进行交换。

堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为 O(1)。
另外，因为取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为n，根据堆的形状特点可知树的高度为 log2n ，那么重构树的时间复杂度便为 O(logn)。
添加数据也一样。在堆的最后添加数据后，数据会一边比较它与父结点数据的大小，一边往上移动，直到满足堆的条件为止，所以添加数据需要的运行时间与树的高度成正比，也是 O(logn)。

如果需要频繁地从管理的数据中取出最小值，那么使用堆来操作会非常方便

二叉查找树

二叉查找树（又叫作二叉搜索树或二叉排序树）是一种数据结构，采用了图的树形结构，数据存储于二叉树的各个节点中

二叉树的特点

第一个是每个结点的值均大于其左子树上任意一个结点的值。比如结点9大于其左子树上的3和8。
第二个是每个结点的值均小于其右子树上任意一个结点的值。比如结点 15 小于其右子树上的23、17和28。

根据这两个性质可以得到以下结论。首先，二叉查找树的最小结点要从顶端开始，往其左下的末端寻找。此处最小值为3。

反过来，二叉查找树的最大结点要从顶端开始，往其右下的末端寻找。此处最大值为28。

插入较小的数据 1

首先，从二叉查找树的顶端结点开始寻找添加数字的位置。将想要添加的1与该结点中的值进行比较，小于它则往左移，大于它则往右移。

最终位置如下:

添加较大值时的方案一样

删除节点

如果要删除的节点只有一个子节点那么删除后直接将子节点的位置添加上去即可

试试删除节点 9

如果需要删除的结点有两个子结点，那么先删掉目标结点然后在被删除结点的左子树中寻找最大结点

提示: 删除9的时候，我们将“左子树中的最大结点”移动到了删除结点的位置上，但是根据二叉查找树的性质可知，移动“右子树中的最小结点”也没有问题。

我们可以把二叉查找树当作是二分查找算法思想的树形结构体现。因为它具有前面提到的那两个性质，所以在查找数据或寻找适合添加数据的位置时，只要将其和现有的数据比较大小，就可以根据比较结果得知该往哪边移动了。
比较的次数取决于树的高度。所以如果结点数为 n，而且树的形状又较为均衡的话，比较大小和移动的次数最多就是 log2n。因此，时间复杂度为 O(logn)。但是，如果树的形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了 O(n)。

补充说明

有很多以二叉查找树为基础扩展的数据结构，比如“平衡二叉查找树”。这种数据
结构可以修正形状不均衡的树，让其始终保持均衡形态，以提高查找效率。
另外，虽然文中介绍的二叉查找树中一个结点最多有两个子结点，但我们可以把子
结点数扩展为 m（m 为预先设定好的常数）。像这种子结点数可以自由设定，并且形状均
衡的树便是 B 树。