第八周作业

关注
发布于: 2020 年 07 月 28 日
﻿
作业一：以下两题，至少完成一道
1、有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
﻿
Set keySet = new HashSet();
while(true) {
if(m==null && n==null) {
return null;
}
﻿
if(m!=null && (m= m -> next) != null) {
if(ketSet.contains(m)) {
return m;
}
keySet.add(m);
}
﻿
if(n!=null && (n= n -> next) != null) {
if(ketSet.contains(n)) {
return n;
}
keySet.add(n);
}
}
﻿
时间复杂度是length(m+n)，空间复杂度是length(m+n)
﻿
2、请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。
﻿
作业二：根据当周学习情况，完成一篇学习总结
﻿
时间复杂度与空间复杂度
NP问题、P、NP-hard、NP完全问题
﻿
数组：内存连续、数据类型相同、随机快速读写、根据数组下标访问数据时间复杂度为O(1)
链表：可以使用零散的内存空间存储数据，查找复杂度是O(N),增删数据性能好
数组链表结合，可以实现快速查找和快速增删
hash表：hash表key冲突，使用链表存储数据
﻿
栈：后进先出
队列：先进先出
用队列搜索好友关系中最有钱的人、用队列搜索最短路径
﻿
树：二叉排序树、不平衡的二叉(排序)树、平衡二叉(排序)树、红黑(排序)树
红黑树VS平衡二叉树：大量增删情况下，红黑树性能更高，查找效率稍微差一些
跳表
﻿
常用算法：穷举算法、递归算法、贪心算法、迪杰斯特拉算法(改进贪心算法)、动态规划、遗传算法
﻿
OSI七层模型：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层
TCP/IP四层模型：网络访问层、网络互联层、传输层、应用层
﻿
网络数据包格式：链路层协议头(mac地址) -> IP协议头(IP) -> TCP协议头(端口) -> HTTP协议头(方法、path)
﻿
TCP协议：面向连接的、可靠的、基于字节流的传输层协议
使用序号，对收到的TCP报文进行排序和检测重复的数据
无错传输：使用校验和检测报文段的错误
使用确认和计时器来检测和纠正丢包或者延时
流量控制，避免主机分组发送过快而使接收方来不及完全收下
拥塞控制，发送方根据网络承载情况控制分组的发送量，以获得高性能同时避免拥塞崩溃
丢失包的重传
﻿
TCP3次握手：
1、App先发送SYN=1,Seq=X的报文，表示请求建立连接，X是一个随机数；
2、服务器收到这个报文后，应答SYN=1,ACK=X+1,Seq=Y的报文，表示同意建立连接；
3、App收到这个报文后，检查ACK的值为自己发送的Seq值+1，确认建立连接，并发送ACK=Y+1的报文给服务器；服务器收到这个报文后检查ACK值为自己发送Seq值+1，确认建立连接。至此，App和服务器建立起TCP连接，就可以进行数据传输了
﻿
TCP关闭连接4次挥手：
1、客户端向服务端发送一个FIN，请求关闭数据传输。
2、当服务器接收到客户端的FIN时，向客户端发送一个ACK，其中ACK的值等于FIN+Seq。
3、然后服务器向客户端发送一个FIN，告诉客户端应用程序关闭。
4、当客户端收到服务端的FIN时，回复一个ACK给服务器端。其中ACK的值等于FIN+Seq。
﻿
HTPP的七种方法和五种状态
﻿
HTTP协议版本：
HTTP/1.0,客户端请求到资源后会关闭连接，频繁三次握手、四次挥手很耗性能
HTTP/1.1，默认启用长连接模式，客户端可以使用一个长连接顺序发送多个请求。引入了管道机制，客户端可以不用等上一个请求的响应结果就可以发送下一个请求，但是服务端也是按照客户端发送顺序进行响应的，可以理解为半双工模式
HTTP/2.0,依然遵循请求响应模式，但客户端发送多个请求和服务端给出多个响应的顺序不受限制，这样既避免了队头阻塞，又能更快获取响应
﻿
客户端与服务端通过socket进行通信，一个连接一个socket，一个socket可以采用一个线程或者线程池进行业务处理
﻿
BIO: 进行I/O操作时，用户线程会一致阻塞，知道读操作或写操作完成
NIO(非阻塞IO)：I/O操作立即返回，发起线程不会阻塞等待
系统IO复用方式：select、poll、epoll
epoll性能最好，poll其次
﻿
数据库preppareStatement预编译，提前生产查询计划，性能更好，还能防止sql注入
数据库连接池：初始化的时候建立一些数据库连接放在连接池里，处理sql的时候就不需要花时间建立连接了
数据库语法分析器、语义分析与优化器、执行计划
B-树与B+树
聚簇索引
添加索引可以优化查询性能，但是也不要盲目添加索引，添加索引的alter会消耗较长的时间，阻塞DML
数据库事务：原子性、隔离性、持久性、一致性
﻿