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的许多资源就浪费了。