计算机网络传输层
传输层介于应用层与网络层之间,是计算机网络最为基本的一层,该层的协议为应用进程提供端到端的通信服务。其提供面向连接的数据流支持、可靠性、流量控制、多路复用等服务。
此层还包含了两个重要的传输层服务:TCP 和 UDP 。
由于传输层的下一层,网络层的 IP 服务是不做任何保证的,是一个不可靠服务,因此传输层就必须做一定的保障服务。
多路复用与多路分解
多路复用(Multiplexing)和多路分解(Demultiplexing),将网络层提供的主机到主机的交付服务延伸到了为运行在主机上的应用程序提供进程到进程的交付服务。
多路分解:将运输层报文段中的数据交付到正确的套接字。
多路复用:将源主机不同套接字中的数据块封装首部信息,并生成报文段传递到网络的一系列过程。
无连接的复用与分解(面向UDP)
利用端口号创建 Socket
DatagramSocket mySocket1 = new DatagramSocket(99111);
UDP 的 Socket 用二元组表示
(目的 IP,目的端口号)
主机收到 UDP 段后
检查段中的 ...
计算机网络应用层
所谓应用层,便是指生活中一些基础的应用所处的层次,也就是我们日常所能够看到的,诸如 Web 网页,电子邮件等这些基础的应用所使用的协议。
本篇内容,主要说说最为重要、最为基础的 HTTP 协议。
HTTP协议
我们所浏览的 Web 网页,其主要是基于 HTTP 协议所搭建的。
HTTP 协议,英文全称为 Hyper Text Transfer Protocol (超文本传输协议),其是一种双端协议,也就是说,这个协议是有两个版本的,一个是服务端的协议一个是客户端的协议。
正如 Computer Networking, A Top-Down Approach 中所说的那样:HTTP defines how Web clients request Web pages from Web servers and how servers transfer Web pages to clients. HTTP 定义了 Web 客户端如何从 Web 服务器请求网页以及 Web 服务器如何向 Web 客户端传输结果。
HTTP报文格式
HTTP 规范包含了对HTTP报文格式的定义,正 ...
计算机网络概述
所谓二十一世纪是生物的世纪,在生物的曙光还未照亮之际,我们的生活却实实在在地被计算机所改变,被计算机网络所改变。
计算机网络,现今,通过光纤将许许多多计算机组在一起,以联通你和世界;通过互联网协议,使数据可以“安全稳定”地传输、解析,将一条条信息送到你眼前。
OSI服务参考模型
OSI参考模型是一种计算机网络的理论模型,其按照功能将计算机网络自上而下分为了 7 层:
应用层:主要是一些服务/协议,用于完成某项特殊功能
文件传输协议:FTP
电子邮件协议:SMTP
表示层:用于处理两个系统之间交换信息的语法与语义问题
信息的加密与解密
信息的压缩与解压
会话层:用于会话控制
建立、维护会话
传输层:负责源-目的(端到端)(进程间)完整的报文传输
分段与重组
连接、流量、差错控制等
网络层:控制子网运行,将网络地址翻译为物理地址
逻辑编址
分组传输,路由选择等
数据链路层:负责节点到节点的数据传输
物理寻址
连接、流量、差错控制等
物理层:指定物理底层的标准
接口标准:形状、电压等
编 ...
二分查找细则
关于二分查找
二分查找或许是很多人学习的第一个算法,其简洁明快,但是在实际应用中,你却会看到许多种写法的二分查找,而这些写法,仅是细节处的区别。
这些不同写法的二分查找,究竟哪一个才是正确的?还是,无论怎么写,达到目的便可以称之为二分查找?
常规写法一
1234567891011121314public static int bSearch(int[] arr, int start, int end, int key){ while (start <= end){ // 防止溢位 int mid = start + (end - start)/2; if (arr[mid] == key) return mid; if (arr[mid] > key) end = mid - 1; else start = mid + 1; } return -1;}
这种写法便是我所学习的,或许也是大多数 ...
花里胡哨的位运算
位运算,虽然说是一种十分精妙的算法技巧,但是除了花里胡哨好像并不能大幅提升时间复杂度。虽说如此,但不得不说,位运算的诸多技巧还是非常有趣的!
初识位运算
初次见到位运算的应用,那是在一个夏天的下午,有同学在班群问:“如何写交换函数?”不久,有人贴了这么段代码:
12345void swap(int* a, int* b) { *a ^= *b; *b ^= *a; *a ^= *b;}
我一脸懵,这都行?这是怎么交换的?异或还能这么使?记得那天我在草稿纸上花了半天,才搞懂了个大概:
我们以 3 和 6 为例:
1234初始状态时: a = 3 = 011 b = 6 = 110第一句执行: a = 101 b = 110第二句执行: a = 101 b = 011 = 3第三局执行: a = 110 = 6 b = 011 = 3
确实交换过来了,但为啥呢?但其实,我们可以将 ...
素数筛
素数是一种作业或竞赛中较易考察的知识点,但好像在实际开发中用的不多【素数好像更多地用在网安领域】。总归,求取 a~b 之间的素数还是一种比较基本的算法技巧。
新手求素数
想当年,我刚学C语言的时候,便是这么写的,也就是直接暴力枚举:
1234567891011121314int count;int prime[MAX_N]; void getPrime(int a, int b) { count = 0; int j; for (int i = a; i <= b; ++i) { for (j = 2; j < i; ++j) { if (i % j == 0) break; } if (j == i) prime[count++] = i; }}
那时的我也还想到了比如 2*3=6 和 3*2=6 是等价的,所以判断素数的终止条件可以再压缩,也就是:
1for (j = 2; j < ...
Java集合概述
Java 集合是一种非常常用的容器,就像数组那样,是为了储存各种各样的数据类型或者数据结构而设计的。其包含了各种已经封装好的数据结构,比如栈,队列,封装好的“数组”等等。
Collection 接口
Collection 接口是最为基本的集合接口,也是相对比较高级的接口,其下又实现了一些子接口。
Set 子接口
Set 子接口最显著的特征就是置入其中的数据是“无序”且不可重复的。这种无序指的是其中存储的数据可能并不是按照你输入的顺序存储的,而是以其独有的方式进行排列的。而 Set 中的一些数据结构,是直接利用了 Map 中的数据结构实现的。
HashSet 类
HashSet 虽然是基于 HashMap 实现的,但其最底层所应用的便是我们数据结构中所学习的哈希表,有也就是说其底层实际上是利用哈希函数存储的,而这样的存储方式,也使得其查找,插入,删除等操作的时间复杂度可以降为 \(\Theta (1)\) 。
常见操作的示例代码如下:
123456789101112131415public static void main(String[] args) { ...
堆的应用
书接上文,上篇博客中我说明了堆的定义,那么这一篇就谈谈堆的用法。由于堆快速的增删特性,所以往往有以下重要用途:
实现优先队列,用于启发式搜索等内容。
一般用于贪心算法中辅助的数据结构。
堆的使用
堆固然好用,但是也要清楚如何使用。
快速手写堆
库固然好用,但是某些情况下你却可能不得不手写堆,那么这时候掌握快速手写堆的技巧便显得尤为重要。
数组是“万能的”,所以一般仅需要一个数组,便能够表示一个堆。众所周知,我们的堆是使用完全二叉树表示的,如下所示:
最小堆.png
我们可以发现,可以将二叉树依次对应到数组中:
数组下标
0
1
2
3
4
数组的值
2
5
4
7
8
可以发现,某个节点的根,实际上就是该节点下标的一半【这也是上个博客实现堆的时候使用的具体原理】。
知道了数组与完全二叉树的对应关系,那么便有可以自己实现最小堆,代码1如下:
12345678910111213141516171819202122232425262728293031323334353637383940 ...
堆
引例:在搜索算法实现中,会遇到这样一个问题——我们并不希望按照入队的先后顺序出队,而是希望每次出队的都是队列中最大或最小的元素。
而要实现这样的方式,我们可以假设一种队列,取出元素的顺序以大小为准,我们往往将这样的队列称之为优先队列。
优先队列(Priority Queue):特殊的“队列”,依照元素的优先权(关键字)大小取出数据,而不是元素进入队列的先后顺序。
选择合适的数据结构
既然已经有了这样一个设想,那我们应该采用何种方式来实现呢?
使用数组或者链表
我们首先会想到以前学过的基本内容,以数组,链表等方式来储存,为了方便判断各种储存方法的优劣,我们将几种方法的时间复杂度进行比较。
普通数组
插入:我们只需要将普通数组的尾部即可 —— 时间复杂度 O(1)
删除:需要从数组中查找最大或最小的元素,进行一次遍历即可 —— 时间复杂度为 O(n)
链表
插入:元素总是插在链表的头部(头插法) —— 时间复杂度 O(1)
删除:同样需要遍历查找查找最大或最小元素 —— 时间复杂度 O(1)
有序数组:即在插入时就按照一定顺序插入
...
博客重新配置
之前用的 yilia 主题的作者跑路了,好久都没更新了,这导致我以前好不容易搞好的博客开始出现了一些有的没的小问题:标签搜索时有时无,赞赏二维码被压缩至一侧等等。但由于种种原因,也一直懒得再搞一个新主题,昨晚突然心血来潮,找了找新一点的主题,最终相中了 icarus。
icarus 是那种很干净的主题,虽然简洁度比着 yilia 差了一些,但也多了不少内容,加了许些动画。
主题安装
根据 gitbub 上的说明,切换到主目录下执行下面命令即可。
1git clone https://github.com/ppoffice/hexo-theme-icarus.git themes/icarus
完成后,更改了 _config.yml 文件,将主题换了过来,并 hexo g。正在我拿起手机准备等待其配置的时候,不幸的故事发生了,是的,报错了:
1fs.SyncWriteStream is deprecated.
就这么一句报错,我搜了一个晚上,经过数次尝试后未果。
第二天起了个大早——十点多就起了,我改变了我的思路,因为 ...