Unity游戏开发客户端面经——数据结构（初级）_unity 数据结构

前言：记录了总6w字的面经知识点，文章中的知识点若想深入了解，可以点击链接学习。由于文本太多，按类型分开。这一篇是数据结构常问问题总结，有帮助的可以收藏。

---

1.栈和堆的区别：

1. GC方面：栈保持着先进后出的原则，是一片连续的内存域，有系统自动分配和维护，产生的垃圾系统自动释放。而堆是无序的，他是一片不连续的内存域，用户自己来控制和释放，如果用户自己不释放的话，当内存达到一定的特定值时，通过垃圾回收器(GC)来回收。
2. 存储方面：栈通常保存着我们代码执行的步骤，如方法变量等等。而堆上存放的则多是对象，数据等。我们可以把栈想象成一个接着一个叠放在一起的盒子(越高内存地址越低)。当我们使用的时候，每次从最顶部取走一个盒子，当一个方法（或类型）被调用完成的时候，就从栈顶取走接着下一个。堆则不然，像是一个仓库，储存着我们使用的各种对象等信息，跟栈不同的是他们被调用完毕不会立即被清理掉。
3. 缓存方面：栈使用的是一级缓存，他们通常都是被调用时处于存储空间中，调用完毕立即释放;堆是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收)。所以调用这些对象的速度要相对来得低一些。
4. 存储方面：栈(Stack)是一种先进后出的数据结构，在内存中，变量会被分配在栈上来进行操作。堆(heap)是用于为引用类型的实例(对象),分配空间的内存区域，在堆上创建一个对象，会将对象的地址传给栈上的变量(反过来叫变量指向此对象，或者变量引用此对象)-----也就是栈上的变量指向了堆上地址为XXX的实例(对象)。

2.栈溢出一般是由什么原因导致的

1. 无限递归。函数递归调用时，系统要在栈中不断保存函数调用时的现场和产生的变量，如果递归调用太深，就会造成栈溢出，这时递归无法返回。再有，当函数调用层次过深时也可能导致栈无法容纳这些调用的返回地址而造成栈溢出。
2. 无限循环。
3. 大量局部变量分配。

3.Stack栈和Queue队列

    相同点：

1. 都是线性结构。
2. 插入操作都是限定在表尾进行。
3. 都可以通过顺序结构和链式结构实现。
4. 插入与删除的时间复杂度都是O（1），在空间复杂度上两者也一样。
5. 多链栈和多链队列的管理模式可以相同。
6. 底层都是由泛型数组实现。

    不同点：

1. 栈先进后出，队列先进先出：删除数据元素的位置不同，栈的删除操作在表尾进行，队列的删除操作在表头进行。
2. 顺序栈能够实现多栈空间共享，而顺序队列不能。
3. 应用场景不同

常见栈的应用场景包括

1. 括号问题的求解，
2. 深度优先搜索遍历等；
3. 函数调用和递归实现，
4. 表达式的转换和求值

常见的队列的应用场景包括

1. 计算机系统中各种资源的管理，
2. 消息缓冲器的管理
3. 广度优先搜索遍历等

4.链表

        单双向链表的区别：

        指向不同：单向链表只有一个指向下一结点的指针，双向链表除了有一个指向下一结点的指针外，还有一个指向前一结点的指针。

        功能不同：单向链表只能next ，双向链表可以return。

        单双向不同：单链表只能单向读取，双向链表可以双向遍历。

        单向链表优缺点：

         优点：单向链表增加删除节点简单。遍历时候不会死循环；

         缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。

        双向链表优缺点：

        优点：可以找到前驱和后继，可进可退；

        缺点：增加删除节点复杂，多需要分配一个指针存储空间。

        

                        s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;

        例题：遍历一遍找到链表倒数第 k 个元素

        由于单链表只能从头到尾依次访问链表的各个节点，所以如果要找链表的倒数第 k 个元素，也只能从头到尾遍历查找。在查找过程中，设置两个指针，让其中一个指针比另一个指针先移动 k 步，然后两个指针同时往前移动。循环到先行的指针值为 NULL 时，另一个指针所指的位置就是要找的位置。

5.链表与数组的对比

        1.数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取，时间复杂度O(1)。

        2.链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素。

        从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反，如果需要经常插入和删除元素就需要用链表数据结构了。

6.二叉树

        计算深度（高度）

        二叉树的高度是二叉树结点层次的最大值，也就是其左右子树的最大高度+1。当树为空时，高度为0；否则为其左右子树最大高度+1。

        遍历:（看根节点的位置）

        前序遍历：（根左右）先访问根节点，再访问左节点，再访问右节点。

        中序遍历，（左根右）先访问左节点，再访问根节点，再访问右节点。

        后序遍历，（左右根）先访问左节点，再访问右节点，再访问根节点。

 　这一点上没有什么本质上的优缺点，要看实际需求决定采用何种遍历方式

　采用递归方式和非递归方式。前者优点是直观，编写起来简单，缺点是但其开销也比较大。非递归形式开销小，但编写复杂。

        根据中序遍历与后续遍历求前序遍历（还原树）

        详细请看：

        力扣

        针对选择题：

        无脑秒解！已知先/后序遍历与中序遍历，求后/先序遍历。_哔哩哔哩_bilibili

        先序遍历与中序遍历　或者　后续遍历与中序遍历  可确定一条树。

    原因：

        先序和后序可以告诉我们根节点，只不过先序遍历的根节点从前往后，后序遍历的根节点从后往前，也正是因为先序遍历和后序遍历都只能告诉我们根节点这个信息，所以他们两个在一起是没办法得到足够信息去构建二叉树的。我们知道根节点之后，可以拿这个根节点在中序遍历的数据中，以该节点为中心，节点左面为该节点的左子树，节点右面为该节点的右子树。很明显上述的规律有递归的特性。

        详细请看：

哪两种遍历方式可以唯一确定一棵二叉树,结合力扣105题_有裂痕的石头的博客-CSDN博客_唯一确定二叉树的遍历方法

        拓展小知识

                完全二叉树：

        完全二叉树是一种特殊的二叉树，满足以下要求：

        1.所有叶子节点都出现在 k 或者 k-1 层，而且从 1 到 k-1 层必须达到最大节点数；

        2.第 k 层可以不是满的，但是第 k 层的所有节点必须集中在最左边。 需要注意的是不要把完全二叉树和“满二叉树”搞混了，完全二叉树不要求所有树都有左右子树，但它要求：

        任何一个节点不能只有右子树没有左子树

        叶子节点出现在最后一层或者倒数第二层，不能再往上。

        用一张图对比下“完全二叉树”和“满二叉树”：

                

                        

                 平衡二叉树：

        平衡二叉树的提出就是为了保证树不至于太倾斜，尽量保证两边平衡。因此它的定义如下：

        1.平衡二叉树要么是一棵空树

        2.要么保证左右子树的高度之差不大于 1

        3.子树也必须是一颗平衡二叉树

                节点

        根节点：树的最顶端的节点。（根节点只有一个）

        子节点：除根节点之外，并且本身下面还连接有节点的节点。

        叶子节点：自己下面不再连接有节点的节点（即末端），称为叶子节 点（又称为终端结点）度为0。

                经典例题：

        1.在完全二叉树中，节点数为n，叶子节点数为m。两者关系为  n = m*2-1；m =（n+1）/2。

        2.一棵树度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1，则这棵树的叶子节点个数为多少？

        解：因为任一棵树中，结点总数 = 度数*该度数对应的结点数 + 1，所以：

        总结点数 = 1 * 4+2 * 2+3 * 1+4 * 1 + 1=16

        叶子结点数=16-4-2-1-1（总节点数－度不为0的个数）=8

        则：叶子结点=8

7.List底层实现

        插入，扩容，删除，收缩。

        底层的变化：实际是一个动态扩容的泛型数组，插入的时候：若容量不够，内存扩两倍（不是Count，容量默认值为4：4--8--16...），原数组内容copy新数组里，旧数组回收。

        直接定义预估大小，避免频繁扩容，产生GC；

        排序：快排（分治思想） nlongn

        详细请看：【C#】浅析C# List实现原理 - 知乎

8.字典

        1.介绍

1. Dictionary表示键和值的集合。
2. Dictionary<object, object>是一个泛型。
3. 他本身有集合的功能有时候可以把它看成数组。
4. 他的结构是这样的：Dictionary<[key], [value]>。
5. 他的特点是存入对象是需要与[key]值一一对应的存入该泛型，任何键都是唯一。
6. 通过某一个一定的[key]去找到对应的值。查找元素的时间复杂度为O(1)。

       

       增删查改时间复杂度

        Dictionary字典类是hash表，Add操作是O(1)。

        其Containskey方法是O(1)，原因是通过hash来查找元素而不是遍历元素。

        ContainsValue方法的时间复杂度是O(N)，原因是内部通过遍历key来查找value，而不是通过hash来查找。

        ltem[Key]属性根据key来检索value，其时间复杂度也是O(1)。

        基本都是O（1）

        2.底层实现原理

        Dictionary在构造的时候做了以下几件事：

        1.初始化一个桶数组this.buckets = new int[prime]

        2.初始化一个this.entries = new Entry<TKey, TValue>[prime]

        Bucket和entries的容量都为大于字典容量的一个最小的质数

        其中this.buckets主要用来进行Hash碰撞

        this.entries用来存储字典的内容，并且标识下一个元素的位置。

        详细过程

        1.哈希表法：将不定长的二进制数据集映射到一个较短的二进制数据集，一个Key通过HashFunc得到HashCode。

        2.Hash桶算法：对HashCode进行分段显示，常用方法对HashCode直接取余。

        3.拉链法：分段则会导致key对应的哈希桶相同，拉链法的基本思想就像对冲突的元素，建立一个单链表，头指针存储在对应哈希桶的位置。反之就是通过hash桶对应后，遍历单链表，获取value值。

        详细请看：带你看懂Dictionary的内部实现 - 独上高楼 - 博客园

        3.提高性能

        哈希冲突的发生，往往会降低字典和集合的操作速度。因此，为了保证高效性，字典和集合的哈希表，通常会保证其至少留有1/3的剩余空间。随着元素的不断插入，当剩余空间小于1/3时，会重新获取更大的内存空间，扩充哈希表。不过，这种情况表中所有的元素位置都会被重新排放，会导致速度缓慢，但是发生情况较少。

        TryGetValue与Contains如何取舍

        因为当Dictionary的value是复杂对象的时候，TryGetValue会将value转换为Object在转换为对应的类型，这个装箱拆箱的过程对复杂对象耗时很高。

        当字典的value是复杂对象的时候，建议大家不要使用TryGetValue。

         4.扩容

         Dictionary 的内部构造和运作机制。他是由数组构成，并且由哈希函数完成地址构建，由拉链法冲突解决方式来解决冲突。new 时尽量确定大致数量会更加高效。

        从内存操作上看，大小以3->7->17->37->….的速度，每次增加到2倍原容量的最小质数的容量，删除时，并不缩减内存。

        详细地址：

https://blog.csdn.net/qq_41044598/article/details/126067510?ops_request_misc=&request_id=&biz_id=102&utm_term=字典如何扩容&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~sobaiduweb~default-3-126067510.nonecase&spm=1018.2226.3001.4450

        

        常见的哈希算法：

        Hash桶算法：首先将key通过hash函数生成hashcode,然后与hash桶的数量进行取余，结果用于确定将该值存放在哪个桶。

        平方取中法：取keyword平方后的中间几位作为散列地址。

        随机数法：选择—随机函数，取keyword的随机值作为散列地址，通经常使用于keyword长度。

        解决hash碰撞：

        拉链法（开散列）：发生哈希冲突的位置，生成—个链表，用来存储hash冲突的元素。

        开放定址法(闭散列)：发生哈希冲突位置开始，依次向后探测，直到找到下一个空位置为止。

        再哈希法。

        5.现在Dictionary容量是4个元素,现在要插入1个新的元素进去，此时底层会发生什么？

        1.容量扩容。

        2.拷贝+ GC。

        3. hash找buckets索引。

        4.将新数据挂在该buckets索引处的单链表中。

        6.为什么Dictionary 查找效率是O（1）

        通过元素的key值进行取余操作，找的对应的哈希桶，判定哈希桶对应的哈希表的头节点是不是该元素，若不是进行next操作，对哈希表进行遍历，这两个过程都是常数级别的操作。所以是O（1）。

        7 hash冲突解决（开放定址法、再哈希法、拉链法）

        散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度。

        哈希表的长度一般是定长的，在存储数据之前我们应该知道我们存储的数据规模是多大，应该尽可能地避免频繁地让哈希表扩容。但是如果设计的太大，那么就会浪费空间，因为我们跟不用不到那么大的空间来存储我们当前的数据规模；如果设计的太小，那么就会很容易发生哈希冲突，体现不出哈希表的效率。所以，我们设计的哈希表的大小，必须要做到尽可能地减小哈希冲突，并且也要尽可能地不浪费空间，选择合适的哈希表的大小是提升哈希表性能的关键。

        一个数除以一个素数的时候，会产生最分散的余数。由于我们通常使用表的大小对哈希函数的结果进行模运算，如果表的大小是一个素数，那么这样我们就会尽可能地产生分散的哈希值。

        拉链法与开放地址法相比的缺点：

        拉链法的优点

        与开放定址法相比，拉链法有如下几个优点：

        ①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；

        ②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；

        ③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；

        ④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

        拉链法的缺点

　        拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

        详细请看：数据结构与算法：hash冲突解决 - 知乎

散列冲突处理：链地址法与开放地址法_a092cc的博客-CSDN博客_开放定址法和链地址法的平均查找长度

数据结构与算法 — 认识哈希表、地址的冲突、链地址法、开放地址法、哈希化的效率_吃不到棒棒糖的小熊的博客-CSDN博客_开放地址法 链地址法

9. 关于List与字典的遍历与查询效率

        List的底层，是一个泛型数组，连续且紧密的顺序存储，一般数据存储在缓存中。而字典是离散（散列）分布，由数组和哈希表共同组成，遍历的时候，会伴有换页的操作，且数组都存储在内存中。而读写速度是：缓存>内存>硬盘。因此List更适合遍历。

        字典的查询效率是通过元素的key值进行取余操作，找的对应的哈希桶，判定哈希桶对应的哈希表的头节点是不是该元素，若不是进行next操作，对哈希表进行遍历，这两个过程都是常数级别的操作。所以是O（1）。而List的查询效率是先遍历，找到对应的值，因此是O（n）。所以字典更适合查询。

---

        希望此篇文章可以帮助到更多的同学，此外对现在面临校招的大三大四的同学，以及热爱游戏或者即将面临找工作的朋友，可以点击下方链接，来解决游戏职业道路的种种困惑，并且还可以学习理论知识的同时，拓宽游戏制作的实践技能~

游戏行业大揭秘https://scrm.vipskill.com/CMS/prod/5726/54/home.html?mantisSiteId=175&track_id=__TRACKID__