面经1

[数据结构
一、数组和链表
1、存储空间上：数组在内存中是连续的，从栈中分配空间；链表是可以不连续的，从堆中分配空间。
2、在查询，访问方式上：数组可以随机访问其中的元素，查找速度相对较快，链表则必须是顺序访问，不能随机访问。
3、空间的使用上：链表对内存空间的利用率较高，可扩展性高；数组则不能，数组的空间大小是固定的，不适合动态存储，不方便动态添加。
4、添加或删除元素时，数组比链表慢，因为数组要移动大量的元素，而链表只需修改指针即可。
二、堆和栈的区别：
1、申请方式：stack由系统自动分配。 堆;需要程序员自己申请，并指明大小。
2、申请效率的比较：栈:由系统自动分配，速度较快。
堆:是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.
3、申请大小的限制：栈顶的地址和栈的最大容量是系统预先规定好的，在WINDOWS下，栈的大小是2M，超出剩余空间会溢出。
堆的大小受限于计算机系统中有效的虚拟内存。
4、数据结构区别：堆可以被看成是一棵树，如：堆排序。栈：一种先进后出的数据结构。
5、缓存方式区别：栈使用的是一级缓存，它们通常都是被调用时处于存储空间中，调用完毕立即释放。
堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定。
三、快排：
通常我们将数组的第一个元素定义为比较元素，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
数据库
一、索引优化
a对较小的数据列使用索引,这样会使索引文件更小,同时内存中也可以装载更多的索引键。
b对where,on,group by,order by中出现的列使用索引
c.并不是所有索引对查询都有效，当索引列有大量数据重复时,查询可能不会去利用索引。
d.索引并不是越多越好。提高查询效率，但同时也降低了insert及update的效率，因为可能会重建索引。
e.应尽量避免在where子句中使用!=或<>操作符或使用or来连接条件，否则引擎放弃使用索引而进行全表扫描。
f.Where后的查询字段尽量减少使用函数或者表达式操作，因为会造成索引失效。
G.尽量的扩展索引，不要新建索引。
二、数据库优化
三、索引的最左优先原则
四、数据库左连、右连和内连
左联：首先取出a表中所有数据,然后再加上与a,b匹配的的数据
内联：两个表a,b相连接,要取出id相同的字段
右联：指的是首先取出b表中所有数据,然后再加上与a,b匹配的的数据
五、存储引擎以及他们之间的区别
InnoDB：提供了良好的事务处理、崩溃修复能力和并发控制。为了维护数据完整性，InnoDB还支持外键完整性约束。
支持自动增加列AUTO_INCREMENT（自动增长列）属性。InnoDB提供行级锁，大幅度提高了多用户并发操作的性能。
缺点是读写效率较差，占用的数据空间相对较大。使用场景，如：银行（对事务的完整性要求比较高），售票（要求实现并发控制）。
MyISAM：使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。
拥有较高的插入、查询速度，但不支持事物。基于MyISAM存储引擎的表支持3种不同的存储格式。包括静态型、动态型和压缩型。其中，静态型是MyISAM的默认存储格式，它的字段是固定长度的；动态型包含变长字段，记录的长度不是固定的；压缩型需要用到myisampack工具，占用的磁盘空间较小。
六、B+
B+树是在B树的基础上改造，它的数据都在叶子节点，同时，叶子节点之间还加了指针形成链表.
B+树所有的数据都在叶子节点，不用跨层，同时有链表结构，只需要找到首尾，通过链表就能把所有数据查询出来.
七、数据库索引有哪些类型
八、范式、第三范式
九、全文索引跟其他索引的区别，怎么实现的
十、查重复‘字段’，统计重复次数：
SELECT [字段],COUNT(0) AS重复次数FROM [表名] GROUP BY [字段] HAVING COUNT([字段]) > 1 order by重复次数
十一、查找薪资第二高：select (select DISTINCT Salary from Employee ORDER BY Salary DESC limit 1 offset 1) as Second；
十二、一个文件夹目录，获取该目录下以’ppt‘结尾的文件：find dir -name ".txt"
查找目录：find /（查找范围）-name '查找关键字' -type d
查找文件：find /（查找范围）-name查找关键字-print
十三、inux里source、sh、bash、./有什么区别
1、source：source a.sh，在当前shell内去读取、执行a.sh，而a.sh不需要有"执行权限"
2、sh/bash:打开一个subshell去读取、执行a.sh，而a.sh不需要有"执行权限".通常在subshell里运行的脚本里设置变量，不会影响到父shell的。
3、 打开一个subshell去读取、执行a.sh，但a.sh需要有"执行权限",可以用chmod +x添加执行权限.
十四、LInux的同步和异步锁
十五、grep进行文件内容匹配工作是用到的参数主zha要有两个，分别是
1.取出两个文件中的相同部分内容“-wf”参数.
2.取出两个文件中的不同部分内容“-wvf”参数
计算机网络
1、SSL怎么加密的？
非对称加密算法：RSA，DSA/DSS
对称加密算法：AES，RC4，3DES
HASH算法：MD5，SHA1，SHA256
其中非对称加密算法用于在握手过程中加密生成的密码，对称加密算法用于对真正传输的数据进行加密，而HASH算法用于验证数据的完整性。由于浏览器生成的密码是整个数据加密的关键，因此在传输的时候使用了非对称加密算法对其加密。
非对称加密算**生成公钥和私钥，公钥只能用于加密数据，因此可以随意传输，而网站的私钥用于对数据进行解密，所以网站都会非常小心的保管自己的私钥，防止泄漏。
2、HTTPS的具体流程
1、浏览器将自己支持的一套加密规则发送给网站。
2、网站从中选出一组加密算法与HASH算法，并将自己的身份信息以证书的形式发回给浏览器。证书里面包含了网站地址，加密公钥，以及证书的颁发机构等信息。
3、获得网站证书之后浏览器要做以下工作：a)验证证书的合法性b)如果证书受信任，或者是用户接受了不受信的证书，浏览器会生成一串随机数的密码，并用证书中提供的公钥加密。c)使用约定好的HASH计算握手消息，并使用生成的随机数对消息进行加密，最后将之前生成的所有信息发送给网站。
4、网站接收浏览器发来的数据之后要做以下的操作：a)使用自己的私钥将信息解密取出密码，使用密码解密浏览器发来的握手消息，并验证HASH是否与浏览器发来的一致。b)使用密码加密一段握手消息，发送给浏览器。
5、浏览器解密并计算握手消息的HASH，如果与服务端发来的HASH一致，此时握手过程结束，之后所有的通信数据将由之前浏览器生成的随机密码并利用对称加密算法进行加密。
三次握手：
1）发送端首先发送一个带有SYN标志地数据包给接收方。
2）接收方接收后，回传一个带有SYN/ACK标志的数据包传递确认信息，表示我收到了。
3）最后，发送方再回传一个带有ACK标志的数据包，代表我知道了，表示’握手‘结束。
四次挥手：
1）第一次挥手：Client发送一个FIN，用来关闭Client到Server的数据传送，Client进入FIN_WAIT_1状态。
2）第二次挥手：Server收到FIN后，发送一个ACK给Client，确认序号为收到序号+1（与SYN相同，一个FIN占用一个序号），Server进入CLOSE_WAIT状态。
3）第三次挥手：Server发送一个FIN，用来关闭Server到Client的数据传送，Server进入LAST_ACK状态。
4）第四次挥手：Client收到FIN后，Client进入TIME_WAIT状态，接着发送一个ACK给Server，确认序号为收到序号+1，Server进入CLOSED状态，完成四次挥手。
为什么是四次？当被动方收到主动方的FIN报文通知时，它仅仅表示主动方没有数据再发送给被动方了。但未必被动方所有的数据都完整的发送给了主动方，所以被动方不会马上关闭SOCKET,它可能还需要发送一些数据给主动方后，再发送FIN报文给主动方，告诉主动方同意关闭连接，所以这里的ACK报文和FIN报文多数情况下都是分开发送的。
TCP与UDP区别总结：
1、TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接
2、TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付.
3、TCP面向字节流，TCP把数据看成一连串无结构的字节流;UDP是面向报文的
UDP没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）
4、每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信
5、TCP首部开销20字节;UDP的首部开销小，只有8个字节
6、TCP的逻辑通信信道是全双工的可靠信道，UDP则是不可靠信道
DHCP（动态主机配置协议）是一个局域网的网络协议。指的是由服务器控制一段lP地址范围，客户机登录服务器时就可以自动获得服务器分配的lP地址和子网掩码。采用udp传输。
1、DHCP Client以广播的方式发出DHCP Discover报文。
2、所有的DHCP Server都能够接收到DHCP Client发送的DHCP Discover报文，所有的DHCP Server都会给出响应，向DHCP Client发送一个DHCP Offer报文。
3、DHCP Client只能处理其中的一个DHCP Offer报文。
4、DHCP Server收到DHCP Request报文后，判断选项字段中的IP地址是否与自己的地址相同。如果相同，DHCP Server就会向DHCP Client响应一个DHCP ACK报文
5、DHCP Client接收到DHCP ACK报文后，检查DHCP Server分配的IP地址是否能够使用
6、DHCP Client在成功获取IP地址后，随时可以通过发送DHCP Release报文释放自己的IP地址，DHCP Server收到DHCP Release报文后，会回收相应的IP地址并重新分配。