美文网首页
JAVA题库(二)

JAVA题库(二)

作者: Bonjour_蒙 | 来源:发表于2019-03-29 16:45 被阅读0次
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的许多资源就浪费了。

相关文章

网友评论

      本文标题:JAVA题库(二)

      本文链接:https://www.haomeiwen.com/subject/tvlzvqtx.html