本周老师主要讲了java中常见的数据结构、计算机网络、NIO、数据库

Java 中常见的数据结构



1、数据结构有什么作用？

当使用 Java 里面的容器类时，你有没有想过，怎么 ArrayList 就像一个无限扩充的数组，也好像链表之类的。很好使用，这就是数据结构的用处，只不过你在不知不觉中使用了。

数据结构内容比较多，细细的讲解也是相对费功夫的，不可能达到一蹴而就。我就将常见的数据结构：堆栈、队列、数组、链表和红黑树 给大家介绍一下，作为数据结构的入门，了解一下它们的特点即可。

2、常见的数据结构

数据存储的常用结构有：栈、队列、数组、链表和红黑树。

栈

栈：stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。

简单的说：采用该结构的集合，对元素的存取有如下的特点:

先进后出（存进去的元素，要在后它后面的元素依次取出后，才能取出该元素）。

栈的入口、出口的都是栈的顶端位置。

需要注意的 2 个名词

• 压栈：就是存元素。即，把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置。

• 弹栈：就是取元素。即，把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置。

队列

队列：queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。

简单的说，采用该结构的集合，对元素的存取有如下的特点：

先进先出（存进去的元素，要在后它前面的元素依次取出后，才能取出该元素）。

队列的入口、出口各占一侧。

栈和队列的结构图:

数组

数组:Array,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。

简单的说,采用该结构的集合，对元素的存取有如下的特点：

查找元素快：通过索引，可以快速访问指定位置的元素

增删元素慢

指定索引位置增加元素：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根据索引，复制到新数组对应索引的位置。

指定索引位置删除元素：需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位置，原数组中指定索引位置元素不复制到新数组中。

数组的结构示意图：

链表

链表:linked list,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时i动态生成。

每个结点包括两个部分：

一个是存储数据元素的数据域，

一个是存储下一个结点地址的指针域。

链表结构有单向链表与双向链表。

采用该结构的集合，对元素的存取有如下的特点：

多个结点之间，通过地址进行连接。

查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素。



• 增加元素：只需要修改连接下个元素的地址即可。

• 删除元素：只需要修改连接下个元素的地址即可。

红黑树

二叉树：binary tree ,是每个结点不超过2的有序树（tree） 。

简单的理解，就是一种类似于树的结构，只不过每个结点上都最多只能有两个子结点。

二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”。

结构示意图：

二叉树的一种比较有意思的叫做红黑树，红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。

红黑树的约束:

节点可以是红色的或者黑色的

根节点是黑色的

叶子节点(特指空节点)是黑色的

每个红色节点的子节点都是黑色的

任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同



红黑树的特点:

速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍。



计算机网络基础知识总结

1.网络层次划分



为了使不同计算机厂家生产的计算机能相互通信，在更大范围内建立计算机网络，国际标准化组织（ISO）在1978年提出了“开放系统互联参考模型”，即著名的OSI/RM模型（Open System Interconnection/Reference Model）。它将计算机网络体系结构的通信协议划分为七层，自下而上依次为：物理层（Physics Layer）、数据链路层（Data Link Layer）、网络层（Network Layer）、传输层（Transport Layer）、会话层（Session Layer）、表示层（Presentation Layer）、应用层（Application Layer）。

出了标准的OSI七层模型以外，常见的网络层次划分还有TCP/IP四层协议以及TCP/IP五层协议，他们之间的对应关系如下图所示：



2.OSI七层网络模型



TCP/IP协议是互联网的基础协议，没有它就根本不可能上网，任何和互联网有关的操作都离不开TCP/IP协议。不管是OSI七层模型还是TCP/IP的四层、五层模型，每一层中都有自己的专属协议，完成自己相应的工作以及与上下层级之间进行沟通。由于OSI七层模型为网络的标准层次划分，所以我以OSI七层模型为例从上向下进行一一介绍



1）应用层



应用层是操作系统或网络应用程序提供访问网络服务的接口。



2）表示层



表示层对上层数据或信息进行变换，保证一个主机应用层信息可以被另一个主机的应用程序理解。表示层的数据转换包括数据的加密、压缩、格式转换等。



3）会话层



会话层管理主机之间的会话进程，负责建立、管理、终止进程之间的会话。会话层还利用在数据中插入校验点来实现数据的同步。



会话层、表示层、应用层重点：



数据传输基本单位为报文

包含的主要协议：FTP（文件传输协议）、Telnet（远程登陆协议）、DNS（域名解析协议）、SMTP（邮件传送协议）、POP3协议（邮局协议）、HTTP协议（Hyper Text Transfer Protocol）

4）传输层



第一个端到端（主机到主机）的层次。传输层负责将上层数据分段并提供端到端的、可靠的或不可靠的传输。此外，传输层还要处理端到端的差错控制和流量控制问题。



传输层的任务是根据通信子网的特性，利用最佳的网络资源，为两个端系统的会话层之间提供建立、维护和取消传输连接的功能，负责端到端的可靠数据传输。在这一层，信息传送的协议数据单元称为段或报文。



网络层只是根据网络地址将源结点发出的数据包传送到目的结点，而传输层则负责将数据可靠地传送到相应地端口



有关传输层的重点：



包含的主要协议：TCP协议（Transmission Control Protocol，传输控制协议）、UDP协议（User Datagram Protocol，用户数据报协议）

重要设备：网关

5）网络层



网络层的目的是实现两端系统之间的数据透明传送，具体功能包括寻址和路由选择、连接的建立、保持和终止等。它提供的服务使传输层不需要了解网络中的数据传输和交换技术。用少量的词来记忆网络层，那就是“路径选择，路由及逻辑寻址”。



网络层涉及众多的协议，其中包括最重要的协议，也是TCP/IP的核心协议——IP协议。IP协议仅仅提供不可靠、无连接的传送服务。IP协议的主要功能有：无连接数据报传输、数据报路由选择和差错控制。与IP协议配套使用实现其功能的还有地址解析协议ARP、逆地址解析协议RARP、因特网报文协议ICMP、因特网组管理协议IGMP。



有关网络层的重点：



网络层负责对子网间地数据包进行路由选择。此外，网络层还可以实现拥塞控制、网际互联等功能

基本数据单位为IP数据报

包含的主要协议：

Internet Protocol（因特网互联协议）

Internet Control Message Protocol（因特网控制报文协议）

Address Resolution Protocol（地址解析协议）

Reverse Address Resolution Protocol（逆地址解析协议）

重要地设备：路由器

6）数据链路层



数据链路层在物理层提供的服务的基础上再向网络层提供服务，最基本的服务是将原子网络层来的数据可靠地传输到相邻结点的目标机网络层，为达到这一目的，数据链路必须具备一系列相应的功能，主要有：如何将数组合成数据块，在数据链路层中这种数据块为帧（frame），帧是数据链路层的传送单位；如何控制帧再物理信道上的传输，包括如何处理传输差错，如何调节发送速率以使与接收方相匹配；以及在两个网络实体之间提供数据链路通路的建立、维持和释放的管理。数据链路层在不可靠的物理介质上提供可靠的传输。该层的作用包括：物理地址寻址、数据成帧、流量控制、数据检错、重发等。



有关数据链路层的重点：



数据链路层为网络层提供可靠的数据传输

基本数据单位为帧

主要的协议：以太网协议

两个重要设备名称：网桥和交换机

7）物理层



激活、维持、关闭通信端点之间的机械特性、电气特性、功能特性以及过程特性。该层为上层协议提供了一个传数据的可靠物理媒体。简单的说，物理层确保原始的数据可在各种物理媒体上传输。物理层记住两个重要的设备名称，中继器（Repeater，也叫放大器）和集线器



3.IP地址



1）网络地址



IP地址由网络号（包括子网号）和主机号组成，网络地址的主机号全为0，网络地址代表着整个网络。



2）广播地址



广播地址通常称为直接广播地址，是为了区分受限广播地址。

广播地址与网络地址的主机号正好相反，广播地址中，主机号为全1。当向某个网络的广播地址发送消息时，该网络内的所有主机都能收到该广播消息。



3）组播地址



D类地址就是组播地址



A类地址以0开头，第一个字节作为网络号，地址范围为：0.0.0.0~127.255.255.255

B类地址以10开头，前两个字节作为网络号，地址范围是：127.0.0.0~191.255.255.255

C类地址以110开头，前三个字节作为网络号，地址范围是：192.0.0.0~223.255.255.255

D类地址以1110开头，地址范围是224.0.0.0~239.255.255.255，D类地址作为组播地址（一对多的通信）

E类地址以1111开头，地址范围是240.0.0.0~255.255.255.255，E类地址为保留地址，供以后使用

注：只有A、B、C由网络号和主机号之分，D、E没有划分网络号和主机号



4）255.255.255.255



该IP地址指的是受限的广播地址。受限广播地址与一般广播地址（直接广播地址）的区别在于，首先广播地址只能用于本地网络，路由器不会转发以受限广播地址为目的的地址的分组；一般广播地址既可以在本地广播，也可跨网段广播。例如：主机192.168.1.1/30直接广播数据包后，另一个网段192.168.1.15/30也能直接收到该数据包；若发送受限广播数据包则不能收到



注：一般的广播地址（直接广播地址）能够通过某些路由器（当然不是所有的路由器），而受限的广播地址则不能通过路由器



5）0.0.0.0



常用于寻找自己的IP地址，例如在RARP，BOOTP和DHCP协议中，若某个位置IP地址的无盘机想要知道自己的IP地址，他就以255.255.255.255为目的地址，像本地范围（具体而言是被各个路由器屏蔽的范围内）的服务器发送IP请求分组



6）回环地址



127.0.0.0/8被用作回环地址，会换地址表示本机的地址，常用于对本机的测试，用得最多的是127.0.0.1



7）A、B、C类私有地址



私有地址（Private Address）也叫专用地址，他们不会在全球使用，只具有本地意义

A类私有地址：10.0.0.0/8，范围是：10.0.0.0~10.255.255.255

B类私有地址：172.16.0.0/12，范围是：172.16.0.0~172.31.255.255

C类私有地址：192.168.0.0/16，范围是：192.168.0.0~192.168.255.255



4.子网掩码及网络划分



随着互联网应用的不断扩大，原先的IPv4的弊端也逐渐暴露出来，即网络号站位太多，而主机号位太少，所以其能提供的主机地址也越来越稀缺，目前除了使用NAT在企业内部利用保留地址自行分配以外，通常都对一个高类别的IP地址进行再划分，以形成多个子网，提供给不同规模的用户群使用

为了再网络分段情况下有效利用IP地址，通过对主机号的高位部分作为子网号，从通常的网络位界限中扩展或压缩子网掩码，用来创建某类地址的更多子网。但创建更多的子网时，在每个子网上的可用主机地址数目会比原先减少。



什么是子网掩码？



子网掩码是标志两个IP地址是否属于一个子网的，也是32位二进制地址，其每一个1代表该位是网络位，0代表主机位。它和IP地址一样也是使用点式十进制来表示的。如果两个IP地址在子网掩码的按位与计算所得结果相同，即表明它们共属于同一个子网中。



注：在计算子网掩码时，要注意IP地址中的保留地址，即"0"地址和广播地址，他们是指主机地址或网络全为"0"或"1"时的IP地址，他们代表着本网络地址和广播地址，一般是不能被计算在内的。



子网掩码的计算



对于无须再划分成子网的IP地址来说，其子网掩码非常简单，即按照其定义即可写出：如某B类IP地址位10.12.3.0，则该IP地址的子网掩码255.255.0.0；如果它是一个C类地址，则其子网掩码为255.255.255.0。其他类推。下面关键要介绍的是一个IP地址，还需要将其高位主机再作为划分出的子网网络号，剩下的是每个子网的主机号，这时该如何进行每个子网的掩码计算



1）利用子网数来计算



求子网掩码前必须先搞清楚要划分的子网数目，以及每个子网内的所需主机数



（1）将子网数转化为二进制表示：如欲将B类IP地址168.195.0.0划分成27个子网：27=11011;



（2）取得该二进制的位数，为N：该二进制为5位数，N=5



（3）取得该IP地址的类子网掩码，将其主机地址部分的前N位置1即得出该IP地址划分子网的子网掩码



该B类地址的子网掩码255.255.0.0的主机地址前5位置1，得到255.255.248.0.



2）利用主机数来计算



如欲将B类IP地址168.195.0.0划分成若干子网，每个子网内由主机700台：



（1）将主机数转化为二进制表示：700=1010111100;



（2）如果主机数小于或等于254，则取得该主机的二进制位数，为N。如果大于254，也就是说主机地址将占据不止8位，该二进制为十位数，N=10



（3）使用255.255.255.255来将该类IP地址的主机地址位数全部置1，然后从后向前将N位全部置0，即为子网掩码值。将该B类地址的子网掩码255.255.0.0的主机地址全部置1，得到255.255.255.255，然后再从后向前将十位置0，即为：11111111.11111111.11111100.00000000，即255.255.252.0.这就是将划分成主机为700台B类IP地址168.195.0.0的子网掩码。

0684



现在使用NIO的场景越来越多，很多网上的技术框架或多或少的使用NIO技术，譬如Tomcat，Jetty。学习和掌握NIO技术已经不是一个JAVA攻城狮的加分技能，而是一个必备技能。在前面2篇文章《什么是Zero-Copy?》和《NIO相关基础篇》中我们学习了NIO的相关理论知识，而在本篇中我们一起来学习一下Java NIO的实战知识。全文较长，建议先马后看（记得关注不迷路）。



一、概述



NIO主要有三大核心部分：Channel(通道)，Buffer(缓冲区), Selector。传统IO基于字节流和字符流进行操作，而NIO基于Channel和Buffer(缓冲区)进行操作，数据总是从通道读取到缓冲区中，或者从缓冲区写入到通道中。Selector(选择区)用于监听多个通道的事件（比如：连接打开，数据到达）。因此，单个线程可以监听多个数据通道。



NIO和传统IO（一下简称IO）之间第一个最大的区别是，IO是面向流的，NIO是面向缓冲区的。 Java IO面向流意味着每次从流中读一个或多个字节，直至读取所有字节，它们没有被缓存在任何地方。此外，它不能前后移动流中的数据。如果需要前后移动从流中读取的数据，需要先将它缓存到一个缓冲区。NIO的缓冲导向方法略有不同。数据读取到一个它稍后处理的缓冲区，需要时可在缓冲区中前后移动。这就增加了处理过程中的灵活性。但是，还需要检查是否该缓冲区中包含所有您需要处理的数据。而且，需确保当更多的数据读入缓冲区时，不要覆盖缓冲区里尚未处理的数据。



IO的各种流是阻塞的。这意味着，当一个线程调用read() 或 write()时，该线程被阻塞，直到有一些数据被读取，或数据完全写入。该线程在此期间不能再干任何事情了。 NIO的非阻塞模式，使一个线程从某通道发送请求读取数据，但是它仅能得到目前可用的数据，如果目前没有数据可用时，就什么都不会获取。而不是保持线程阻塞，所以直至数据变得可以读取之前，该线程可以继续做其他的事情。 非阻塞写也是如此。一个线程请求写入一些数据到某通道，但不需要等待它完全写入，这个线程同时可以去做别的事情。 线程通常将非阻塞IO的空闲时间用于在其它通道上执行IO操作，所以一个单独的线程现在可以管理多个输入和输出通道（channel）。



Channel



首先说一下Channel，国内大多翻译成“通道”。Channel和IO中的Stream(流)是差不多一个等级的。只不过Stream是单向的，譬如：InputStream, OutputStream.而Channel是双向的，既可以用来进行读操作，又可以用来进行写操作。

NIO中的Channel的主要实现有：



• FileChannel

• DatagramChannel

• SocketChannel

• ServerSocketChannel



这里看名字就可以猜出个所以然来：分别可以对应文件IO、UDP和TCP（Server和Client）。下面演示的案例基本上就是围绕这4个类型的Channel进行陈述的。



Buffer



NIO中的关键Buffer实现有：ByteBuffer, CharBuffer, DoubleBuffer, FloatBuffer, IntBuffer, LongBuffer, ShortBuffer，分别对应基本数据类型: byte, char, double, float, int, long, short。当然NIO中还有MappedByteBuffer, HeapByteBuffer, DirectByteBuffer等这里先不进行陈述。



Selector



Selector运行单线程处理多个Channel，如果你的应用打开了多个通道，但每个连接的流量都很低，使用Selector就会很方便。例如在一个聊天服务器中。要使用Selector, 得向Selector注册Channel，然后调用它的select()方法。这个方法会一直阻塞到某个注册的通道有事件就绪。一旦这个方法返回，线程就可以处理这些事件，事件的例子有如新的连接进来、数据接收等。