JAVA题库(二)

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,099评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,828评论 3 387
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,540评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,848评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,971评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,132评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,193评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,934评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,376评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,687评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,846评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,537评论 4 335
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,175评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,887评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,134评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,674评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,741评论 2 351