音视频开发与计算机基础面试实战

题目1.丢包恢复算法怎么实现的？丢包是由于网络不好导致的,还是确实丢包了,丢包率怎么反馈给发送端的？
题目2.回音消除的实现原理？
题目3.Opus，G.711音频编解码的实现原理？OPus的好处，最低带宽是多少？
题目4.音视频数据传输怎么判断延迟发生在哪个阶段？
题目5.带宽估计和带宽反馈是怎么做的？

计算机基础：
题目1.Hash表的实现原理？
要想找到一个不同的 key 对应的散列值都不一样的散列函数,几乎是不可能的。而且数组空间有限也会增加散列冲突的概率。

如何解决散列冲突？

1.开放寻址法

当我们往散列表中插入数据时，如果相应的位置已经被占用，就从当前位置依次往后查找，直到找到空位置位置

查找时，通过散列函数先找出要找元素的key对应的散列值，通过散列值下标找出对应位置的元素，看看是不是和我们要找的元素相等，不相等的话，依次循环去找，如果找到空闲位置还没找到，说明要找的元素不在散列表中

散列表的删除时不能单纯把元素设置为空，不然存在散列表的元素也可能找到空值停止查找，查找不到，删除元素时要在对应的位置标记deleted,查找时遇到deleted继续查找.

线性探测存在的问题：当空闲位置越来越少时，插入元素，查找元素，删除元素可能时间复杂度为O(n).要遍历整个散列表.

2.链表法

当插入元素的时候，我们根据散列函数，求得一个散列值，插入到对应槽的链表中即可，插入的时间复杂度0(1).删除和查找的平均时间复杂度是O(n/m),一共n个元素，m个槽

装载因子：已经插入的元素个数/散列表的总长度
一般装载因子达到0.8时就可以考虑2倍扩容了，新的装载因子就变成了0.4，当删除的元素过多时，装载因子很小又对空间的使用敏感时，也可考虑动态缩容
动态扩容时要重新计算每个元素的散列值
为了解决一次扩容消耗资源过多，可以把扩容穿插到每次插入中，每次往新申请空间插入新元素时，都将老散列表元素插入新散列表中，这样没有了集中一次数据迁移，插入就会很快
这时需要查找元素时，就先从新的散列表中查，再去老的散列表中查

基于链表散列冲突比较适合处理大对象，大的数据量，插入时再创建，比起开放寻址它支持更多的优化策略，比如用红黑树代替链表。当链表的长度过长时，就用红黑树代替链表的数据结构实现增删改查的功能，红黑树少于一定的节点时，又可以转换为链表

哈希算法的定义和原理:将任意长度的二进制值串映射为固定长度的二进制值串.
哈希算法有两点非常重要:
1.很难根据哈希值推导出原始数据内容
2.散列冲突的概率要很小

唯一标示:通过哈希算法对文件做一个信息摘要
校验数据的完整性和正确性
安全加密
散列函数，更关注生成的散列值是否平均

题目3.Tcp的滑动窗口会变化吗？
发送端的TCP滑动窗口大小就是：已发送未确认部分+未发送准备发送部分
接收端的TCP滑动窗口大小是：最大的缓存量 - 已确认还没被应用层读取的部分
比如数据包7,8,9到了，但是6还没有到，那7,8,9只能缓存着，不能ACK,
超时时间要大于RTT,每一次超时重传要把下一次超时重传的时间设置为2倍，2次超时说明网络状况不好，不宜频繁反复发送。
快速重传机制：比如6,8,9已经接收了，就是7没来那肯定是丢了，于是发生3个6的ACK,要求下一个是7，客户端收到3个6的ACK,就知道7丢了，不等超时，马上重发。
如果接收方缓冲满了，处理不过来了，就把发送端的窗口设置为0，暂停发送。接收端不处理已确认数据，窗口就会变小，直到为0.

题目4.如何减少系统的内存碎片？
题目5.IPV6的适配？

IPv6.001.png

DNS64:把传统服务器返回的IPV4通过映射转换成看着像IPV6的地址，最简单的转换:64:ff9b::IPV4 =IPV6
NAT64:帮助IPV6 Packet接入IPV4的公网中，IPV4公网环境只认IPV4地址，拥有IPV4,IPV6网卡，让IPV6-IPV4进行映射.

题目6.Mac地址和Ip地址的关系？
在同一个局域网，知道了IP，不知道MAC怎么办？
发送一个广播，告诉自己的IP,MAC，然后问某个IP,你的MAC是啥？
找到MAC后也会进行ARP缓存，过一段时间去更新缓存。
交换机会把包含MAC1的数据包发给所有的口，然后找到对应口的MAC地址后进行缓存，这就是转发表

题目7.Hash表解决的索引冲突的方法,除了下标++,循环查找空位置存储数据还有其他算法吗？Hash表满时扩容需要重新申请内存一块更大的内存空间吗？
题目8.谈谈你对http协议的理解？

http报文：

1.请求行:URL,方法
1.1GET方法：获取服务器的一些资源，一个页面
1.2.POST，在正文中主动告诉服务器一些信息,而非获取.我是谁？我支付多少？我要买什么？
1.3 PUT,指向资源位置上传最新内容，往往用来修改一个资源
1.4 DELETE,往往用来删除一个资源

2.首部字段,包含一些key value 值
Accept-Charest ：可接受的字符集
Content-Type : JSON
Cache-control控制缓存的，有一些商品的图片，详情信息是基本不变的，而库存，价格可能是会改变的，使用Max-age控制是否需要请求最新的数据,还是使用缓存数据，来减少服务器的压力

http:http请求当然要先建立TCP连接，建立连接以后http1.1默认开启了keep-Alive,建立的TCP连接，就可以多次请求复用

题目9.怎么做图片、数组、字符串的无差别存储，key怎么确定，怎么删除数据，如何保证取出的数组顺序
题目10.动态库和静态库的区别有哪些

题目11.HTTPS传输数据的过程, https的验证证书怎么做的, 描述一下https的握手过程
Https验证证书怎么做的？
怎么确认公钥的证书是对的，CA也需要更牛的CA给它签名，拿到更牛的CA公钥看能不能解开签名，就像你不相信区公安局可以打电话向市公安局去确认，从而保证非对称加密模式的正常运转。

Https的安全策略？
对称加密效率高，但是解决不了密钥传输问题；非对称加密可以解决这个问题，但是效率不高。
非对称加密需要通过证书和权威机构来验证公钥的合法性。
HTTPS 是综合了对称加密和非对称加密算法的 HTTP协议。既保证传输安全，也保证传输效率。

https的握手过程：
1.服务器生成公钥，私钥，把自己的公钥通过权威认证机构生成证书
2.客户端请求服务器证书(证书包含的信息有颁发机构,所有者，有效期，公钥)，进行验证
3.验证通过后生成随机数，利用公钥加密随机数，服务器利用私钥进行解密，解密出的随机数作为对称加密的密钥
4.服务器，客户端通过对称加密密钥进行数据传输

题目12.你使用过quic吗？

TCP为了保证可靠性，使用序号和应答机制，来解决顺序问题和丢包问题。

一旦超时就会重发这个序号包，至于怎么才算超时，用自适应重传算法？超时通过采样往返的RTT不断调整的。

quic是递增的，任何一个序列号的包只发送一次，下次就要+1了，这次发送100没有返回，下次就是101，返回的ACK100就是对第一个包的响应，返回的ACK 101 就是对第2个包的响应，计算RTT（Round Trip Time）.

怎么知道两个包的内容一样呢？发送的数据流里面有一个偏移量offset,通过offset查看数据发送到哪里了，offset的包没来就要重发，来了就拼接。

QUIC 的流量控制也是通过 window_update，来告诉对端它可以接受的字节数。

在 TCP 协议中，接收端的窗口的起始点是下一个要接收并且ACK 的包，即便后来的包都到了，放在缓存里面，窗口也不能右移，因为 TCP 的 ACK 机制是基于序列号的累计应答，一旦 ACK 了一个系列号，就说明前面的都到了，所以只要前面的没到，后面的到了也不能 ACK，就会导致后面的到了，也有可能超时重传，浪费带宽。