游戏开发面试题7

ArrayList数据结构的底层是什么样的？

ArrayList底层是基于数组实现的。它通过动态地扩容或者缩小数组的大小来实现。当容量不够时，它会新建一个更大的数组，然后将原来的数据复制过来，最后再将新数据添加进去。

ArrayList扩容的机制是：当添加第一个元素时，ArrayList的容量为10；每次添加新的元素时，如果超过了容量，就会将原来的容量加倍，即原来的容量*2，如果原来的容量是0，则新的容量为1。

ArrayList扩容机制的优缺点：

优点：

ArrayList扩容机制简单易懂，易于实现。
扩容后的容量一定大于原来的容量，可以减少在添加新元素时的数组拷贝次数，提高添加元素的效率。

缺点：

ArrayList扩容机制导致内存的浪费，容易造成内存空间的浪费。
当容量较大时，每次扩容需要消耗大量的内存和CPU资源，会影响性能，因此在使用ArrayList时，需要合理设置初始容量。

ArrayList不是线程安全的

ArrayList 内部实现是基于数组，当多线程同时访问同一个ArrayList是可能出现数据不一致的情况，比如，当一个线程正在读取ArrayList的数据，而另外一个线程正在向ArrayList中添加/删除数据，可能会使ArrayList中的数据发生变化，这样一来，读取ArrayList数据的线程就可能读取到不正确的数据，从而导致程序出错。

解决ArrayList线程不安全的常用方法有：

使用Vector代替ArrayList：Vector是同步的，所有的方法都是由synchronized修饰的，因此它是线程安全的；
将ArrayList包装成线程安全的：使用Collections.synchronizedList(list)方法，将ArrayList转换成线程安全的；
使用CopyOnWriteArrayList：它是一个线程安全的高效的集合，它的写操作是通过复制底层数组的方式实现的，这种实现方式的开销在可以接受的范围内，它适用于读多写少的并发场景；
使用锁来实现线程安全：可以使用ReentrantLock等锁机制实现线程安全的ArrayList。

栈、堆区别

栈是一种特殊的线性表，其特点是数据只能在一端进行插入和删除操作，先进后出，后进先出的原则。它是一种存储结构，可以用来存储函数的参数值、局部变量等。
堆是一种特殊的树形结构，其特点是所有节点的值都大于或等于其子节点的值，其根节点的值最大或最小。堆是一种动态的存储结构，可以用来存储大量的数据，如排序、搜索等。

协程底层

协程的本质是一个轻量级的线程，每个协程都有一个栈，用来存储函数及其参数、局部变量等，协程可以被挂起、恢复、切换，这是实现协程的基础。

C#GC（垃圾回收）原理

引用计数：当某个对象被引用时，将其引用计数加1，当引用失效时，将其引用计数减1。如果某个对象的引用计数变为0，则该对象将被垃圾回收器回收。
标记-清除：垃圾回收器在运行的时候，根据引用关系遍历对象，将可以访问的对象标记为“存活”，将不可访问的对象标记为“死亡”，然后清除所有标记为“死亡”的对象。
复制算法：垃圾回收器将可用内存分为两块，每次只使用其中一块，当空间不足时，将存活的对象复制到另一块空间，然后再把已复制的对象从原来的空间清除掉。
标记-整理算法：垃圾回收器在运行的时候，会首先标记出所有存活的对象，然后将所有存活的对象向一端移动，把未使用的空间碎片清除掉。

状态同步与帧同步的区别

状态同步是指在每个控制周期中，将多机系统中的每台机器的状态（如位置、速度、加速度等）传输给其他机器，使得每台机器都保持同步。状态同步可以实现多机协同控制的实时性，但是由于每个控制周期中都需要传输大量的数据，它的精度可能比较低。

帧同步是指在每个控制周期中，将多机系统中的每台机器的控制命令传输给其他机器，使得每台机器都保持同步。帧同步可以实现多机协同控制的精度，但是由于每个控制周期中只传输少量的控制命令，它的实时性可能比较低。

常见的设计模式

单例模式（Singleton Pattern）

工厂模式（Factory Pattern）

组合模式（Composite Pattern）

代理模式（Proxy Pattern）

链表、二叉树、哈希表的特点

1. 链表：

是一种线性表结构，其特点是每个结点都有一个指针指向下一个结点，从而形成一个链表；
无论插入或删除结点，都只需要改变指针的指向，时间复杂度为O(1)；
查找一个结点的时间复杂度为O(n)，需要从头结点开始按顺序查找；
链表不需要考虑空间的分配问题，一般采用动态分配内存，可以实现灵活的内存管理。

2. 二叉树：

二叉树是一种树结构，每个结点最多只有两个孩子；
二叉树的查找、插入和删除操作的时间复杂度分别为O(log2n)、O(log2n)和O(log2n)；
由于二叉树的每个结点不是被连续的存储，而是按层次被分散存储，且每个结点只能有两个孩子，所以可以更有效地利用存储空间。

3. 哈希表：

哈希表是一种数据结构，将关键字映射到表中一个位置来访问记录，以加快查找速度；
哈希表的查找时间复杂度为O(1)，插入和删除时间复杂度为O(n)；
哈希表的实现需要额外的空间，以存储哈希表本身，并且需要解决哈希冲突的问题。

HashMap 底层原理

HashMap 底层采用数组+链表（红黑树）实现，它根据键的 hashCode 值存储数据，根据哈希码能够计算出数据在数组中的位置(哈希冲突)，用链表（红黑树）来存储冲突的数据。HashMap 在 Java 8 中，当链表长度超过阈值（默认为 8）时，会转化为红黑树，提高查询效率。当容量不够时会自动扩容，默认的负载因子是 0.75，扩容的方式是容量的 2 倍

如何判断链表有环

利用一个哈希表，遍历链表中的每个节点，将节点的地址存入哈希表中，如果哈希表中已经存在当前节点，则说明链表有环；
定义两个指针，一个慢指针一次走一步，一个快指针一次走两步，如果快指针遇到慢指针，说明链表有环。

栈和队列的使用场景？

浏览器的前进后退功能：浏览器访问过的网页可以通过栈的数据结构来实现前进和后退功能。

tcp粘包问题有没有了解

TCP粘包问题是指由于TCP协议在传输数据时没有对数据进行分片处理，导致接收端收到的数据量大于发送端发送的数据量。

解决TCP粘包问题的方式有：

在发送端添加分隔符：在发送端添加一个分隔符，接收端收到分隔符后，就可以根据分隔符来进行数据的拆分。
在发送端添加报头：发送端在发送数据前添加报头，报头中包含有当前数据的长度信息，接收端根据报头中的长度信息来进行数据的拆分。
在发送端添加缓冲区：发送端在发送数据前，先将数据放入缓冲区中，每次只发送缓冲区中的一部分数据，接收端收到数据后，根据数据的总长度判断数据是否发送完毕。

如何使用UDP实现一个简单的TCP

首先，UDP数据报可以帮助实现TCP/IP协议中的三次握手过程。在第一次握手中，一个客户端发送一个UDP数据报，其中包含一个握手请求。当服务器收到这个报文，就会回复一个确认报文，表示服务器已经收到客户端的握手请求，并准备好提供服务。在第二次握手中，客户端会再次发送一个UDP数据报，这次的报文中包含了一些有用的信息，比如客户端的IP地址、端口号等，以便服务器可以识别客户端。在第三次握手中，服务器会发送一个UDP数据报，表示连接已经建立，客户端可以开始发送数据了。