1.实现一个保证迭代顺序的HashMap。
答:Java里面有个容器LinkedHashMap, 它能实现按照插入的顺序输出结果。
它的原理也是维护一张表,但它是链表,并且hashmap中维护指向链表的指针,这样可以快速定位链表中的元素进行删除。
它的时间复杂度也是O(n), 空间上要比上面少些
2.说一说排序算法,稳定性,复杂度。
排序算法比较表格
排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 是否稳定 |
---|---|---|---|---|
冒泡排序 | O(n2)O(n2) | O(n2)O(n2) | O(1)O(1) | 是 |
选择排序 | O(n2)O(n2) | O(n2)O(n2) | O(1)O(1) | 不是 |
直接插入排序 | O(n2)O(n2) | O(n2)O(n2) | O(1)O(1) | 是 |
归并排序 | O(nlogn)O(nlogn) | O(nlogn)O(nlogn) | O(n)O(n) | 是 |
快速排序 | O(nlogn)O(nlogn) | O(n2)O(n2) | O(logn)O(logn) | 不是 |
堆排序 | O(nlogn)O(nlogn) | O(nlogn)O(nlogn) | O(1)O(1) | 不是 |
希尔排序 | O(nlogn)O(nlogn) | O(ns)O(ns) | O(1)O(1) | 不是 |
计数排序 | O(n+k)O(n+k) | O(n+k)O(n+k) | O(n+k)O(n+k) | 是 |
基数排序 | O(N∗M)O(N∗M) | O(N∗M)O(N∗M) | O(M)O(M) | 是 |
原理理解
1 冒泡排序
2 选择排序
3 插入排序
4 归并排序
5 快速排序
6 堆排序
image
注意!!!数组从1开始,1~n
7 希尔排序
8 桶排序(基数排序和基数排序的思想)
[图片上传中...(image-19ec86-1553847936802-7)]
9 计数排序
图解
10 基数排序
image对a[n]按照个位0~9进行桶排序:
image
对b[n]进行累加得到c[n],用于b[n]中重复元素计数
!!!b[n]中的元素为temp中的位置!!!跳跃的用++补上:
image
temp数组为排序后的数组,写回a[n]。temp为按顺序倒出桶中的数据(联合b[n],c[n],a[n]得到),重复元素按顺序输出:
image
3.TCP如何保证可靠传输?三次握手过程?
答:TCP发送的报文段是交给IP层传送的,但IP层只能提供尽最大努力交付的服务,也就是说,TCP下面的网络所提供的是不可靠的传输。因此,TCP采用了一些适当的措施来提供可靠的传输,使得两个传输层直接的通信变得可靠。
TCP为了提供可靠传输:
(1)首先,采用三次握手来建立TCP连接,四次握手来释放TCP连接,从而保证建立的传输信道是可靠的。
(2)其次,TCP采用了连续ARQ协议(回退N,Go-back-N;超时自动重传)来保证数据传输的正确性,使用滑动窗口协议来保证接收方能够及时处理所接收到的数据,进行流量控制。
(3)最后,TCP使用慢开始、拥塞避免、快重传和快恢复来进行拥塞控制,避免网络拥塞。
三次握手:
TCP需要三次握手才能建立连接,整个过程如下图所示:
假设A运行的是TCP客户端进程,而B运行的是TCP服务端进程。最开始的时候两端的TCP进程都处于ClOSED(关闭)状态。
这时候,A主动打开连接,而B被动打开连接,B在打开连接之后进入LISTEN(收听)状态。
(1)第一次握手
A的TCP客户进程向B发出建立连接请求报文段,其中SYN(同步位)=1,ACK(确认位)=0,seq(序号)=x。
TCP规定,当报文段的SYN=1且ACK=0时,表明这是一个请求建立连接的;SYN报文段(SYN=1的报文段)不能携带数据,但是要消耗掉一个序号。
在A发送完毕之后,A的TCP客户端进程进入SYN-SENT(同步已发送)状态。
(2)第二次握手
B在收到连接请求报文段之后,如果同意建立连接,则向A发送确认报文段。其中SYN=1,ACK=1,ack(确认号)=x+1,同时设置自己的初始序号seq=y。
TCP规定,当报文段的SYN=1且ACK=1时,表明这是一个同一建立连接响应报文段;这个报文段也不能携带数据,同样需要消耗掉一个序号。
在B发送完毕之后,B的TCP服务端进程进入SYN-RCVD(同步收到)状态。
(3)第三次握手
A在收到B的确认报文段之后,还需要向B给出确认报文段。其中ACK=1,seq=x+1,ack=y+1。
TCP规定,这个ACK报文段可以携带数据;如果不携带数据则不消耗序号,即A下一个数据报文段的序号仍然是seq=x+1。
在A发送完毕之后,A的TCP客户端进程进入ESTABLISHED(已建立连接)状态;B在接收到A的确认报文段之后,B的服务端进程也进入ESTABLISHED(已建立连接)状态。
二、三次握手的原因
为什么A还需要发送一次确认,进行第三次握手呢?主要是为了防止已失效的请求连接报文段突然又传送到了B,因而产生错误。
原因如下:
先假如出现了一种异常情况,即A发出的第一个连接请求报文段因为在某些网络节点上滞留了。由于超时重传,于是A又向B发起请求并成功建立了连接,在传输完数据之后,AB同之间释放了连接。
而在A和B已经释放连接之后,那个在网络上滞留的报文段又达到了B。这时候,B接收到报文以为是A发起的新的一次建立连接的请求,于是就向A发出确认建立连接报文段。而A此时并没有发起建立连接的请求,于是不予理睬。但是B以为新的连接已经建立,一直等待A发送数据,于是B的许多资源就浪费了。
网友评论