Unity面试易考题 - 框架概念||Unity面试易考题 - 数据结构_unity面试的框架

Unity面试易考题 - 框架概念 

MVC框架
MVC是一种将代码的功能进行划分的设计框架，主要原理是将游戏数据、用户界面以及业务逻辑分离，以使代码可扩展性、可复用性、可维护性、灵活性加强，降低耦合性。

Model - 数据层    数据管理

View - 视图层    视图交互

Controller - 控制层     业务逻辑

大概流程：

 M -> Add数据更新事件 M -> Send数据更新改事件

 V -> Add数据更改事件 V -> Send视图交互事件

 C -> Add视图交互事件 C -> Send数据更改事件

ECS框架
Entity 实体

Component 组件

System 系统

实体与组件是一对多的关系，实体拥有怎样的功能，完全是取决于其拥有哪些组件，可以通过动态添加或删除组件，可以在游戏运行时改变实体的行为。

组件为通用型组件，任何实体一旦挂载该组件，即可拥有该组件的功能。

系统是来处理拥有一个或多个相同组件的实体集合的工具

https://gameinstitute.qq.com/community/detail/114516

ECS提高Cache命中率的原理：

ECS里面储存数据会根据Entity拥有的Component来决定Archetype，Archetype代表这一类型的Entity所拥有的所有Component，同一个Archetype的数据会存储在8k为单位的chunk里面，一般L1缓存是16k以上，也就是说可以放2个chunk或更多，Archetype在内存里的排布是连续的，ComponentSytem处理对应需要有相对组件的时候他会把这些进入L1的chunk都直接通过偏移字节来进行读写，直到需要的chunk超出了L1，而常用的面向对象是用指针的方式的，他在内存中的排布并不是连续的，会导致在内存里乱飞，出现cache miss的问题，ECS则是通过struct的sequencial layout连续的排布，所以它不会有缓存丢失。 

Unity面试易考题 - 数据结构

数组
用连续的存储空间存储相同类型数据的线性数据结构

适用于对存储空间要求不大，很少增加和删除的情况

优点：

按照索引查询元素速度快

按照索引遍历数组方便

缺点：

数组的大小固定后无法扩容

数组只能存储一种类型的数据

不便进行数据的插入、删除

栈
只能通过访问它的顶端，来实现数据存储和检索的一种线性数据结构。

存储数据按先进后出原则进行。

栈的存储结构

避免栈溢出可用链表存储栈中数据

栈空间容量可以动态扩容

需要预先定义或申请栈的存储空间

栈空间容量有限

数据入栈需要判断是否栈满，栈满则抛出异常

顺序栈一般通过数组实现，不建议动态扩容，会产生深度拷贝

顺序存储

链式存储

队列
队列是一种先进先出的线性数据结构

只允许在队列的队首(front)pop数据，队列的队尾(rear)push数据

队列的存储结构

队列为空的判断条件是头指针和尾指针的值相同，且均指向头结点

链表存储队列数据，可动态扩容，避免队列溢出

顺序队列假想成一个环状结构，称之为循环队列

可以循环利用数组空间

队满弹出队首，可用于缓存之类的结构

需要预先定义或申请队列的存储空间

队列空间容量有限，队尾指针达到其上限时，队满

利用一组地址连续的存储单元存放队列中的数据

元素入队只修改队尾指针，元素出队只修改队首指针

顺序存储

循环存储

链表存储

两个栈实现队列

- 入队列：直接压入栈1即可

- 出队列：如果栈2不为空，把栈2中的栈顶数据直接弹出；否则，把栈1的所有数据全部弹出压入栈2中，再弹出栈2的栈顶数据

链表
物理存储单元中非连续、非顺序的存储结构

既可以表示线性结构，也可以用于表示非线性结构

通过链表中的指针链接次序实现链表数据存储

链表类型

单向链表

循环链表

双向循环链表

树
基本概念
树是一种非线性的有序数据结构

每个节点有零个或多个子节点

没有父节点的节点称为根节点

每一个非根节点有且只有一个父节点

除了根节点外，每个子结点可以分为多个不相交的子树

树(Tree)是n ( n ≥ 0) 个节点的有限集合，n = 0 时称为空树

任意一颗非空树中，有且只有一个特定的称为根(root)的节点

根节点：一棵树最上面的节点父节点、子节点：如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子节点叶子节点：没有任何子节点的节点兄弟节点：具有相同父节点的节点互称为兄弟节点节点度：节点拥有的子树数树的深度：从根节点开始（其深度为0）自顶向下逐层累加树的高度：从叶子节点开始（其高度为0）自底向上逐层累加

对于树中相同深度的每个节点来说，它们的高度不一定相同，这取决于每个节点下叶子节点的深度

二叉树
二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”

二叉树常被用于实现二叉查找树和二叉堆 

二叉树分类
满二叉树

所有的分支节点都有左节点和右节点，并且叶节点都集中在二叉树的最下一层

满二叉树的特点：   1 . 叶子节点都在最下层   2 . 深度 = 最大层数  3 . 叶子节点树 = Math.Pow(2, 层数 - 1) || （总节点数+1）/2  4 . 第i层的节点数 = Math.Pow(2, i - 1)   5 . 总节点数 =  Math.Pow(2, 层数) - 1，且总结点数一定为奇数

完全二叉树

除最后一层外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点

平衡二叉树

左右两个子树的高度差的绝对值不超过 1

红黑树

每个节点都带颜色的树，节点颜色或是红色或是黑色

红黑树是一种查找树

从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍

堆
堆是一种特殊的树形数据结构，每个结点都有一个值。通常堆的数据结构，是指二叉堆。特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆 

图 

图是由一组顶点和一组能够将两个顶点相连的边组成的

路径、环

路径是由边顺序连接的一系列顶点，路径或者环的长度为其中所包含的边数

简单路径是一条没有重复顶点的路径

环是一条至少含有一条边且起点和终点相同的路径

简单环是一条不含有重复顶点和边的环（除了起点和终点必须相同之外）

连通图

从任意一个顶点都存在一条路径到达另一个任意顶点

散列表(哈希表) 

冲突处理

建立一个特殊存储空间，专门存放冲突的数据

适用于数据和冲突较少的情况

开放定制法

链地址法

公共溢出区法

再散列法

准备若干个hash函数，如果使用第一个hash函数发生了冲突，那么就使用下一个

扩容

如果需要频繁添加数据，最好提前开好空间