关于数据结构

什么是数据结构？

简单地说，数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。首先我们需要理解各种数据结构，才能在处理实际问题时选取最合适的数据结构。

我理解的数据结构

在我看来，数据结构大体上分三种，线性结构、层级结构和键值结构，线性结构中又分内存地址连着的和不连着的，连着的分别是数组，栈、以及队列，不连着的是链表，层级结构有树和堆，而键值结构就是我们经常使用的散列表

为什么我们需要数据结构？

数据是计算机科学当中最关键的实体，而数据结构则可以将数据以某种组织形式存储，因此，数据结构的价值不言而喻。

无论你以何种方式解决何种问题，你都需要处理数据——无论是涉及员工薪水、股票价格、购物清单，还是只是简单的电话簿问题。

数据需要根据不同的场景，按照特定的格式进行存储。有很多数据结构能够满足以不同格式存储数据的需求。

常见的数据结构

首先列出一些最常见的数据结构，我们将逐一说明：

数组 栈 队列 链表 树 字典树（这是一种高效的树形结构，但值得单独说明） 散列表（哈希表）

数组

数组是最简单、也是使用最广泛的数据结构。栈、队列等其他数据结构均由数组演变而来。下图是一个包含元素（1，2，3和4）的简单数组，数组长度为4。

每个数据元素都关联一个正数值，我们称之为索引，它表明数组中每个元素所在的位置。大部分语言将初始索引定义为零。

以下是数组的两种类型：

一维数组（如上所示） 多维数组（数组的数组）

数组的基本操作

Insert——在指定索引位置插入一个元素 Get——返回指定索引位置的元素 Delete——删除指定索引位置的元素 Size——得到数组所有元素的数量

面试中关于数组的常见问题

寻找数组中第二小的元素 找到数组中第一个不重复出现的整数 合并两个有序数组 重新排列数组中的正值和负值

栈

著名的撤销操作几乎遍布任意一个应用。但你有没有思考过它是如何工作的呢？这个问题的解决思路是按照将最后的状态排列在先的顺序，在内存中存储历史工作状态（当然，它会受限于一定的数量）。这没办法用数组实现。但有了栈，这就变得非常方便了。

可以把栈想象成一列垂直堆放的书。为了拿到中间的书，你需要移除放置在这上面的所有书。这就是LIFO（后进先出）的工作原理。

下图是包含三个数据元素（1，2和3）的栈，其中顶部的3将被最先移除：

栈的基本操作

Push——在顶部插入一个元素 Pop——返回并移除栈顶元素 isEmpty——如果栈为空，则返回true Top——返回顶部元素，但并不移除它

面试中关于栈的常见问题

使用栈计算后缀表达式 对栈的元素进行排序 判断表达式是否括号平衡

应用场景：逆序输出，语法检查，进制转换

在我们日常编程中，括号都是成对出现的，比如“()”“[]”“{}”“<>”这些成对出现的符号

那么具体处理的方法就是:凡是遇到括号的前半部分，即把这个元素入栈，凡是遇到括号的后半部分就比对栈顶元素是否该元素相匹配，如果匹配，则前半部分出栈，否则就是匹配出错

将十进制的数转换为2-9的任意进制的数

我们都知道，通过求余法，可以将十进制数转换为其他进制，比如要转为八进制，将十进制数除以8，记录余数，然后继续将商除以8，一直到商等于0为止，最后将余数倒着写数来就可以了。

比如100的八进制，100首先除以8商12余4,4首先进栈，然后12除以8商1余4，第二个余数4进栈，接着1除以8，商0余1，第三个余数1进栈，最后将三个余数出栈，就得到了100的八进制数144,

堆和栈区别

堆是满足一定限制的树型结构（比如父亲节点的权值要大于儿子节点的权值，左儿子又要大于右儿子）。

栈是元素有先进后出顺序的线性结构。可以考虑叠盘子，只能从最上面拿盘子，也只能往最上面放盘子。那这个盘子序列、包括上面两条规则就构成了一个栈。

栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。

堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。

堆和栈是两种东西，堆栈连起来读其实是栈。

队列

与栈相似，队列是另一种顺序存储元素的线性数据结构。栈与队列的最大差别在于栈是LIFO（后进先出），而队列是FIFO，即先进先出。

一个完美的队列现实例子：售票亭排队队伍。如果有新人加入，他需要到队尾去排队，而非队首——排在前面的人会先拿到票，然后离开队伍。

下图是包含四个元素（1，2，3和4）的队列，其中在顶部的1将被最先移除：

移除先入队的元素、插入新元素

队列的基本操作

Enqueue()——在队列尾部插入元素 Dequeue()——移除队列头部的元素 isEmpty()——如果队列为空，则返回true Top()——返回队列的第一个元素

面试中关于队列的常见问题

使用队列表示栈 对队列的前k个元素倒序 使用队列生成从1到n的二进制数

两个栈实现一个队列

入队：元素进栈A

出队：先判断栈B是否为空，为空则将栈A中的元素 pop 出来并 push 进栈B，再栈B出栈，如不为空则栈B直接出栈

class Queue:
    def __init__(self):
        self.stockA=[]
        self.stockB=[]
    def push(self, node):
        self.stockA.append(node)
    def pop(self):
        if self.stockB==[]:
            if self.stockA==[]:
                return None
            else:
                for i in range(len(self.stockA)):
                    self.stockB.append(self.stockA.pop())
        return self.stockB.pop()

链表

链表是另一个重要的线性数据结构，乍一看可能有点像数组，但在内存分配、内部结构以及数据插入和删除的基本操作方面均有所不同。

链表就像一个节点链，其中每个节点包含着数据和指向后续节点的指针。 链表还包含一个头指针，它指向链表的第一个元素，但当列表为空时，它指向null或无具体内容。

链表一般用于实现文件系统、哈希表和邻接表。

这是链表内部结构的展示：

链表包括以下类型：

单链表（单向） 双向链表（双向）

链表的基本操作：

InsertAtEnd - 在链表的末尾插入指定元素 InsertAtHead - 在链接列表的开头/头部插入指定元素 Delete - 从链接列表中删除指定元素 DeleteAtHead - 删除链接列表的第一个元素 Search - 从链表中返回指定元素 isEmpty - 如果链表为空，则返回true

面试中关于链表的常见问题

反转链表 检测链表中的循环 返回链表倒数第N个节点 删除链表中的重复项

树（重点）

树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。 树类似于图，但区分树和图的重要特征是树中不存在环路。

树形结构被广泛应用于人工智能和复杂算法，它可以提供解决问题的有效存储机制。

这是一个简单树的示意图，以及树数据结构中使用的基本术语：

Root - 根节点

Parent - 父节点

Child - 子节点

Leaf - 叶子节点

Sibling - 兄弟节点

类型

二叉树

二叉查找树的特点就是左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大。

基于二叉查找树的这种特点，在查找某个节点的时候，可以采取类似于二分查找的思想，快速找到某个节点。n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 O(logN)。之所以说是正常情况下，是因为二叉查找树有可能出现一种极端的情况。

二叉查找树有可能退化为一条链表，这样的二叉查找树的查找时间复杂度顿时变成了 O(n)。由此必须防止这种情况发生，为了解决这个问题，于是引申出了平衡二叉树。

平衡二叉树

平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构。

非叶子节点只能允许最多两个子节点存在。 每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如hash值)。

平衡二叉树的查询性能和树的层级(高度h)成反比，h值越小查询越快。

为了保证树的结构左右两端数据大致平衡。降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如Treap、红黑树。使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1，通过这样避免树形结构由于删除增加变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找：

红黑树

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

特点：

每个节点或者是黑色，或者是红色。 根节点是黑色。 每个叶子节点(NIL)是黑色。 如果一个节点是红色的，则它的子节点必须是黑色的。 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树是一种平衡树，复杂的定义和规则都是为了保证树的平衡性。说白了就是防止平衡二叉树做倾斜动作

B树(B-tree)

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个)，数据库索引技术里大量使用B树和B+树的数据结构。

排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则。

B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理(磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来)把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。

B+树（B+tree）

B+树是B树的一个升级版，B+树更充分的利用了节点的空间

B+跟B树不同。B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加。

（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样。

（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。

B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快。

（2）B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定。

（3）B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。

（4）B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树对每一层进行遍历，这有利于数据库做全表扫描。

（5）B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

具体查找过程

那么，假设数据库中有1-7条数据，一次查询，B+tree到底怎么帮我们快速检索到数据呢？

1,2,3,4,5,6,7

如果要查找数据4，那么首先会把B+tree的根节点加载到内存，此时发生一次咬包子(IO读操作)，在内存中用二分查找确定4在3和5之间，通过根节点所存储的指针加载叶子节点(3,4)到内存中，发生第二次咬包子，结束查询，总计两次。如果不使用索引，我们需要咬四口包子才能把4咬出来。而在生产环境中，2阶的B+树可以表示上百万的数据，如果上百万的数据查找只需要两次IO读操作，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO读取，那么总共需要百万次的IO，显然成本是巨大的。

同时，我们知道IO次数读写取决于B+树的层级，也就是高度h，假设当前数据表的数据为N，每个存储容器的数据项的数量是m，则有h=㏒(m+1)N，当数据量N一定的情况下，m越大，h越小；而m = 存储容器的大小 / 数据项的大小，存储容器的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么B+树要求把真实的数据放到叶子节点而不是非叶子节点，一旦放到非叶子节点，存储容器的数据项会大幅度下降，导致树的层数增高。当数据项等于1时将会退化成线性表，又变成了顺序查找，所以这也是为啥索引用B+tree，而不用B-tree，根本原因就是叶子节点存储数据高度就会减小，而高度减小才能帮我们更快的吃到馅儿。

说白了就是B-tree也能实现索引，也能让我们更快的访问数据，但是B-tree每个节点上都带着一点儿馅儿，而这个馅儿占据了本来油皮的空间，所以为了扩容，只能增加B-tree的高度进行扩容，随着馅儿越来越多，导致B-tree的高度也越来越高，高度越高，我们咬包子的次数也越来越频繁，读写效率则越来越慢。

思维方式

从平衡二叉树、B树、B+树、总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度。

树遍历方式

区别

1） 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。

2） 深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下：

先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。 先序遍历可以想象成，节点从树根开始绕着整棵树的外围转一圈，经过结点的顺序就是先序遍历的顺序

中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。 中序遍历可以想象成，按树画好的左右位置投影下来就可以了

后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。　　

后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的。还记得我们先序遍历绕圈的路线么？就是围着树的外围绕一圈，如果发现一剪刀就能剪下的一颗葡萄（注意必须是一颗葡萄），就把它剪下来，组成的就是后序遍历了。　

3）深度优先搜素算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。

广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。

通常 深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。

所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。 　

广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。

但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些

字典树（Trie）

字典树，也称为“前缀树”，是一种特殊的树状数据结构，对于解决字符串相关问题非常有效。它能够提供快速检索，主要用于搜索字典中的单词，在搜索引擎中自动提供建议，甚至被用于IP的路由。

这些单词以顶部到底部的方式存储，其中绿色节点“p”，“s”和“r”分别表示“top”，“thus”和“theirs”的底部。

面试中关于字典树的常见问题

计算字典树中的总单词数 打印存储在字典树中的所有单词 使用字典树对数组的元素进行排序 使用字典树从字典中形成单词 构建T9字典（字典树+ DFS ）

哈希

哈希（hash）也翻译作散列。Hash算法，是将一个不定长的输入，通过散列函数变换成一个定长的输出，即散列值。

这种散列变换是一种单向运算，具有不可逆性即不能根据散列值还原出输入信息，因此严格意义上讲Hash算法是一种消息摘要算法，不是一种加密算法。常见的hash算法有：SM3、MD5、SHA-1等 。

在不同的应用场景下，hash函数的选择也会有所侧重。比如在管理数据结构时，主要要考虑运算的快速性，并且要保证hash均匀分布；而应用在密码学中就要优先考虑抗碰撞性，避免出现两段不同明文hash值相同的情况发生。

在密码学领域的应用

在密码学中，Hash算法的作用主要是用于消息摘要和签名，换句话说，它主要用于对整个消息的完整性进行校验。比如一些登陆网站并不会直接明文存储用户密码，存储的是经过hash处理的密码的摘要（hash值），当用户登录时只需要对比输入明文的摘要与数据库存储的摘要是否相同；即使黑客入侵或者维护人员访问数据库也无法获取用户的密码明文，大大提高了安全性。

在数据结构中的应用

使用Hash算法的数据结构叫做哈希表，也叫散列表，主要是为了提高查询的效率。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数就是hash函数，存放记录的数组叫做哈希表。在数据结构中应用时，有时需要较高的运算速度而弱化考虑抗碰撞性，可以使用自己构建的哈希函数。

哈希算法可以自定义，通常可利用除留余数、移位、循环哈希、平方取中等方法。下面这个例子就是我自己定义的一个哈希函数，运用了取模运算和异或运算。

Python 的不可变对象才有 hash 值，可变对象没有 hash 值，我们称它为 不可哈希，如列表。因此，hash() 可以应用于数字、字符串和元祖，不能直接应用于 list、set、dictionary。

集合（set）的元素、字典（dict）的 key 必须是可哈希的，它保证了在同一个解释器进程里相同字符串 hash 一致

单向加密

不可逆加密，根据密文无法解析出原文，适用于数据校验的场景，例如登录密码。常用的单向加密有MD5、SHA、HMAC。

MD5（Message Algorithm（消息摘要算法第五版），最常用的单向加密算法，可将原文加密为固定长度的密文，压缩性高，安全系数不高。通常将MD5产生的字节数组在进行一次BASE64编码，以提高算法深度。

SHA(Secure Hash Algorithm，安全散列算法），数字签名等密码学应用中重要的工具，被广泛地应用于电子商务等信息安全领域。虽然SHA与MD5通过碰撞法都被破解了，但是SHA仍然是公认的安全加密算法，较之MD5更为安全。

HMAC(Hash Message Authentication Code，散列消息鉴别码，基于密钥的Hash算法的认证协议。消息鉴别码实现鉴别的原理是，用公开函数和密钥产生一个固定长度的值作为认证标识，用这个标识鉴别消息的完整性。使用一个密钥生成一个固定大小的小数据块，即MAC，并将其加入到消息中，然后传输。接收方利用与发送方共享的密钥进行鉴别认证等。

双向加密

可逆加密，根据密文可解析出原文，适用于数据传输的场景，例如支付。常用的双向加密算法有RSA、AES、DES等等。双向加密又分对称加密和非对称加密。对称加密又叫单密钥加密，是通过单个密钥进行加解密的算法；非对称加密是用公钥和私钥来加解密的算法，私钥可以用来解密公钥加密的密文，公钥无法揭秘私钥加密的密文。

常用的双向对称加密有：DES,IDEA,3DES 。

常见的非对称加密算法有：RSA、ECC（移动设备用）、Diffie-Hellman、El Gamal、DSA（数字签名用）

哈希表

哈希法（Hashing）是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引（称为“键（key）”）中的过程。因此，对象以键值对的形式存储，这些键值对的集合被称为“字典”。可以使用键搜索每个对象。基于哈希法有很多不同的数据结构，但最常用的数据结构是哈希表。

哈希表通常使用数组实现。

数组 链表 区别

数组与链表的区别

（1）存储空间上 链表存放的内存空间可以是连续的，也可以是不连续的，数组则是连续的一段内存空间。一般情况下存放相同多的数据时，数组占用较小的内存，而链表还需要存放其前驱和后继的空间。

（2）长度的可变性 链表的长度是按实际需要可以伸缩的，而数组的长度是在定义时要给定的，如果存放的数据个数超过了数组的初始大小，则会出现溢出现象。

（3）查找效率： 按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均需要O(n)；

按值查找时，若数组无序，数组和链表时间复杂度均为O(n)，但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)；

（4）插入删除时： 数组平均需要移动n/2个元素，而链表只需修改指针即可；

（5）空间分配方面： (静态)数组从栈中分配空间, 对于程序员(某些编程语言如java对于堆内存的管理也交由程序自动控制，但性能肯定有差异)方便快速,但是自由度小。

链表从堆中分配空间, 自由度大但是申请管理比较麻烦。

那么有没有一种数据结构可以结合该两者的优点呢？那就是哈希表。

哈希表将需要查找的key值，通过hash函数的计算，换算为数组的位置值。这样在查找时就可以直接定位数据的位置。它结合了数组的快速查询的优点又能融合链表方便快捷的增加删除元素的优势

总结下！

数组------查找快，修改慢！

链表------查找慢，修改快！

哈希表：是数组和链表的结合体。

Python复合数据类型底层

list 列表

底层由线性表实现，列表中元素 保存的不是具体的数据的内存地址，而是 指针(就是指向元素的内存地址的指针)

简而言之：列表 存储的是指针 就是指向内存的头信息和元素 分开放 所以可以动态的扩容 也可以 多种数据结构的数据

列表的扩容：首先会申请8个元素的内存空间大小，然后如果满了，扩容4倍，直至数量达到了50000个，就扩容2倍的连续储存空间。

dict 字典 enumerate zip hash()

底层 哈希表(散列表 实现

其实字典是由一个关联数组或者哈希数组， 数组的索引是 将 键通过哈希算法得到的整型数字 对数组长度取余 取余的结果就是下标 索引 根据索引区查找内存地址

dict元素修改更新 判断的依据就是 索引对应的表的内存空间的键值对和要修改的键值对是否一致

哈希碰撞 公开寻址

set 集合 值为空的字典

判断两个元素是否一致 依据就是 hash值 是否一致

frozenset 冰冻集合 不可变的数据类型 是能做 交差并补 操作

tuple 元组

元组是长度不可变的数组， 列表则是可变的数组