内存管理
内存管理有哪几种方式?
常见的内存管理方式:
块式管理:把主存分为一大块一大块的,当所需的程序片段不在主存时就分配一块主存空间,把程序片段载入主存,就算所需的程序片段只有几个字节也只能把这一块分配给它。这样会造成很大的浪费,平均浪费了50%的内存空间,但是易于管理。
页式管理:用户程序的地址空间被划分成若干个固定大小的区域,这个区域被称为“页”,相应地,内存空间也被划分为若干个物理块,页和块的大小相等。可将用户程序的任一页放在内存的任一块中,从而实现了离散分配。这种方式的优点是页的大小是固定的,因此便于管理;缺点是页长与程序的逻辑大小没有任何关系。这就导致在某个时刻一个程序只有一部分在主存中,而另一部分则在辅存中。这不利于编程时的独立性,并给换入换出处理、存储保存和存储共享等操作造成麻烦。
段式管理:段是按照程序的自然分界划分的并且长度可以动态改变的区域。使用这种方式,程序员可以把子程序、操作数和不同类型的数据和函数划分到不同的段中。这种方式将用户程序地址空间分成若干个大小不等的段,每段可以定义一组相对完整的逻辑信息。存储分配时,以段为单位,段与段在内存中可以不相连,也实现了离 ...
排序算法(内部)
插入排序算法插入排序算法是所有排序方法中最简单的一种算法,其主要的实现思想是将数据按照一定的顺序一个一个地插入到有序的表中,最终得到的序列就是已经排序好的数据。
注意:很多初学者所说的插入排序,实际上指的就是直接插入排序算法,插入排序算法还包括: 折半插入排序算法、2-路插入排序算法、表插入排序算法和希尔排序算法等。
插入排序算法-直接插入
直接插入排序算法是插入排序算法中的一种,采用的方法是:在添加新的记录时,使用顺序查找的方式找到其要插入的位置,然后将新记录插入。
具体实现:
见代码。
直接插入排序算法本身比较简洁,容易实现,该算法的时间复杂度为:O(n^2)
插入排序算法-希尔排序
希尔排序算法,又称“缩小增量排序”,也是插入排序算法的一种,但是同前面几种排序算法比较来看,希尔排序在时间效率上有很大的改进。
在使用直接插入排序算法时,如果表中的记录只有个别的是无序的,多数保持有序,这种情况下算法的效率也会比较高;除此之外,如果需要排序的记录总量很少,该算法的效率同样会很高。希尔排序就是从这两点出发对算法进行改进得到的排序算法。
希尔排序的具体实现思路是:先将整个记录表分割成若干部 ...
HTTP篇
HTTPHTTP(HyperText Transfer Protocol)即超文本传输协议,是一种获取网络资源的应用层协议,它是互联网数据通信的基础,由请求和响应构成。
URI和URLURI
URI(Uniform Resource Identifier)即统一资源标识符,用于标识某个互联网资源,由熟悉的URL和URN构成
URL(Uniform Resource Locator)即统一资源定位符,俗称网址。应用程序通过URL才能定位到资源所处的位置,URL相当于一个人的住址
URN(Uniform Resource Name)即统一资源名称,是URI过去的名字,用于在特定的命名空间中标识资源,URN相当于一个人的身份
URL语法
URL有两种表现方式:绝对和相对。
HTTP协议HTTP协议有三个特征,如下:
持久连接
管道化
状态管理
HTTP报文HTTP报文就是HTTP协议通信的内容,HTTP报文是一种简单的格式化数据块,由带语义的纯文本组成,所以能很方便地进行读或写。
报文语法
报文分为两类:请求报文和响应报文
请求报文由五部分组成:请求方法、请求URL、HTT ...
创建型模式
单例模式 Singleton目的在应用程序调用的时候,只能获得一个对象实例。
应用场景
数据库连接
日志 (多种不同用途的日志也可能会成为多例模式)
UML图
特点
单例类不能直接实例化创建,而是只能由类本身实例化。因此,要获得这样的限制效果,构造函数必须标记为private,从而防止类被实例化。
需要一个私有静态成员变量来保存类实例。
公开一个能访问到实例的公开静态方法。
在PHP中,为了防止他人对单例类实例克隆,通常还为其提供一个空的私有__clone()方法。
简单工厂模式 SimpleFactory目的简单工厂模式是一个精简版的工厂模式。它与静态工厂模式最大的区别是它不是「静态」的。因为非静态,所以你可以拥有多个不同参数的工厂,你可以为其创建子类。甚至可以模拟(Mock)他,这对编写可测试的代码来讲至关重要。这也是它比静态工厂模式受欢迎的原因!
UML图
工厂方法模式 Factory目的对比简单工厂模式的优点是,您可以将其子类用不同的方法来创建一个对象。举一个简单的例子,这个抽象类可能只是一个接口。这种模式是「真正」的设计模式, 因为他实现了 S.O.L.I.D 原则中「D ...
高并发处理方案
web资源防盗链盗链是什么?为什么要防?在自己页面上显示一些不是自己服务器上的资源(如HTML/CSS/JS/图片/音频/视频等)的现象。
由于别人盗链你的资源会加重你的服务器的负担,所以我们需要防止,
防盗链是什么?如何防盗链?防止别人通过一些技术手段绕过本站的资源展示页,盗用本站资源,让绕开本站资源展示页的资源链接失效,这样可以大大减轻服务器的压力。
有以下两种方式:
Referer(容易伪造Referer,安全性低)
加密签名(安全性高)
防盗链的工作原理通过Referer,服务器可以检测到访问目标资源的来源网站,如果是资源文件,则可以追踪到显示它的网页地址。一旦检测到来源网站不是本网站,则进行阻止。
通过签名,根据计算签名的方式,判断请求是否合法,如果合法就显示,否则返回错误信息。
Referer实现以NGINX为例,前提是加载ngx_http_referer_module模块:
注意:使用none是因为如果浏览器直接访问资源,Referer是为空的,所以这种方式不能彻底阻挡住盗链。
加密签名以NGINX为例,前提是加 ...
线性表
线性表什么是线性表将具有“一对一”关系的数据“线性”地存储到物理空间中,这种存储结构就称为线性表。
使用线性表存储的数据,如同数组中存储数据那样,要求数据类型必须一致。
存储结构和链式存储结构
线性表存储结构可以分为顺序存储结构和链式存储结构。
前驱和后继
数据结构中,一组数据的每个个体被称为“数据元素”(简称“元素”)。
某一元素的左侧相邻元素称为“直接前驱”,位于此元素左侧的所有元素统称为“前驱元素”;某一元素的右侧相邻元素称为“直接后继”,位于此元素右侧的所有元素统称为“后继元素”。
顺序表顺序表存储数据时,会提前申请一整块足够大小的物理空间,然后将数据一次性存储起来,存储时做到数据元素之间不留一丝缝隙。
顺序表存储数据使用的是数组。
顺序表的初始化
见代码。
顺序表的基本操作
见代码。
链表(单向链表)与顺序表不同,链表不限制数据的物理存储状态,换句话说,使用链表存储的数据元素,其物理存储位置是随机的。
数据元素随机存储,并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。
链表的结点
链表中每个数据的存储都由以下两部分组成:
数据元素本身,其所在的区域称为数据域
指 ...
认证
单点登录(SSO)什么是单点登录
单点登录的英文名叫做:Single Sign On(简称 SSO)。在以前的时候,一般我们就单系统,所有的功能都在同一个系统上。
后来,我们为了合理利用资源和降低耦合性,于是把单系统拆分成多个子系统。
比如阿里系的淘宝和天猫,很明显地我们可以知道这是两个系统,但是你在使用的时候,登录了天猫,淘宝也会自动登录。简单来说,单点登录就是在多个系统中,用户只需一次登录,各个系统即可感知该用户已经登录。
回顾单系统登录
在我初学 Java Web 的时候,登录和注册是我做得最多的一个功能了(初学 Servlet 的时候做过、学SpringMVC 的时候做过、跟着做项目的时候做过…),反正我也数不清我做了多少次登录和注册的功能了…这里简单讲述一下我们初学时是怎么做登录功能的。
众所周知,HTTP 是无状态的协议,这意味着服务器无法确认用户的信息。于是,W3C 就提出了:给每一个用户都发一个通行证,无论谁访问的时候都需要携带通行证,这样服务器就可以从通行证上确认用户的信息。通行证就是 Cookie。如果说 Cookie 是检查用户身上的“通行证”来确认用户的身份,那 ...
web安全
SQL注入什么是SQL注入
SQL注入,就是通过注入SQL命令来进行攻击,更确切地说是攻击者把SQL命令插入到web表单或者请求参数的查询字符串里面提交给服务器,从而让服务器执行恶意的SQL命令。
产生的原因
SQL注入是通过让服务器执行了恶意的SQL命令从而进行攻击的,那么主要问题就在于服务器是如何生成SQL语句的。绝大多数有SQL注入漏洞的web系统,在生成SQL语句的时候,采用的是拼接字符串的方式,并且没有对要组装成SQL语句的参数进行过滤和转义。
举例
下面以一个用户登录的场景来讲解:
前端登录页面:
1234567891011121314<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <title>SQL injection test</title></head><body><form action="index.php" meth ...
加解密
加密/解密对称加密算法DES
DES是1977年美国联邦信息处理标准中采用的一种对称密码。
DES是一种将64位比特明文加密成64比特密文的对称算法。
现在DES已经可以被暴力破解了。1999年RSA公司举办的破译DES比赛,破译耗时仅仅是22小时15分钟。
3DES
三重DES是为了增加DES的强度,将DES重复三次所得到的的一种密码算法。
三重DES处理速度不高,除了特别重视向下兼容的情况外,很少被使用。
AES
AES是取代其前任的标准DES而成为新标准的一种对称加密算法。
AES是美国NIST组织的竞选活动中选出来的,参加这个竞选是有条件的:被选中的AES算法必须无条件地免费提供给全世界使用。
AES的选拔过程对全世界是公开的,评选是由全世界的密码学家共同完成的,其中也包括AES的参赛者,一旦找到弱点就会被淘汰,所以通过全世界的密码学家共同的破译未能找到弱点,AES是一种密码强度很棒的算法。
加密步骤
解密步骤
非对称加密算法RSA算法
RSA密码算法,不需要XOR操作,没有什么多轮循环,简单明了。
RSA的破解,就是破解私钥中的D,但是随着 ...
编解码
编码/解码概念字符:是各种文字和符号的总称,包括各个国家的文字、符号、图形符号和数字等。
字符集:是一个系统支持的所有抽象字符的集合。
字符编码:是把字符集中的字符编码成特定的二进制数,以便在计算机中存储,每个字符集中的字符对应唯一的一个二进制数。
编码方式:一个字符的Unicode编码是确定的。但是在实际传输中,不同系统平台的设计不一致,对Unicode的实现方式有所不同。Unicode的实现方式称为Unicode转换格式(Unicode Transformation Format,简称UTF)。UTF-8、UTF-16、UTF-32都是将字符转换为二进制数字的编码方式。
编码人类先有了自己的语言,交流了若干个世纪,然后出现了计算机。可惜计算机只认0和1,人类只能认文字,双方都不能妥协,那就必须要有一个从文字到0、1的映射了。从文字到0、1的映射称为编码,反过来从0、1到文字叫解码。
计算机里只有0和1,怎么来表示“Hello World”呢(假如我们在美国),那就需要将字母数字及标点符号编一个号。一个字节可以表示256个数字,表示字母数字标点足够了,所以用一个字节就可以对 ...
进程与线程
进程和线程有什么区别?进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,它是系统进行资源分配的基本单位(最小单位)、是系统调度的独立单位。
线程是进程的一个实体,是系统调度的基本单位(最小单位)。线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器、一组寄存器和栈),但是它可以与同属于一个进程的其他线程共享进程所拥有的全部资源。在没有实现线程的操作系统中,进程既是资源分配的基本单位,又是系统调用的基本单位,它是系统中并发执行的单元;而在实现了线程的操作系统中,进程是资源分配的基本单位,而线程是系统调度的基本单位,是系统中并发执行的单元。
引入线程主要有以下四个方面的优点:
易于调度
提供并发性。通过线程可以方便有效地实现并发
开销小。创建线程比创建进程要快,所需要的开销也更小
有利于发挥多处理器的功能。通过创建多线程,每个线程可以在一个处理器上运行,从而实现应用程序的并行,使每个处理器都得到充分的运行。
尽管进程和线程很相似,但两者也存在着很大的不同,区别如下:
一个线程必定属于也只能属于一个进程;而一个进程可以拥有多个线程且至少拥有一 ...
查找算法
什么是查找表查找表是由同一类型的数据元素构成的集合。
一般对于查找表有以下操作:
在查找表中查找某个具体的数据元素
在查找表中插入数据元素
在查找表中删除数据元素
…
静态查找表和动态查找表
在查找表中只做查找操作,而不改动表中数据元素,称此类查找表为静态查找表;
在查找表中做查找操作的同时进行插入数据或者删除数据的操作,称此类表为动态查找表。
关键字
在查找表中查找某个特定元素时,前提是需要知道这个元素的一些属性。例如,每个人上学的时候都会有自己唯一的学号,因为你的姓名、年龄都有可能和其他人是重复的,唯独学号不会重复。而学生具有的这些属性(学号、姓名、年龄等)都可以称为关键字。关键字又细分为主关键字和次关键字。若某个关键字可以唯一地识别一个数据元素时,称这个关键字为主关键字,例如学生的学号就具有唯一性;反之,像学生姓名、年龄这类的关键字,由于不具有唯一性,称为次关键字。
如何进行查找?
不同的查找表,其使用的查找方法是不同的。例如每个人都有属于自己的朋友圈,都有自己的电话簿,电话簿中数据的排序方式是多种多样的,有的是按照姓名的首字母进行排序,这种情况在查找时,就可以根据被 ...
基础篇
TCP/IP网络模型协议协议可简单理解为计算机之间的一种约定,好比人与人之间对话所使用的语言。
在 OSI7层 模型中,发送方从第7层的应用层到第1层的物理层,由上至下按顺序传输数据,而接收方则从第1层到第7层,由下至上接收数据,如下图所示:
层数
功能
应用层
为应用程序提供服务并管理应用程序之间的通信,常用的协议有SMTP、FTP、HTTP等
表示层
负责数据的格式转换、加密与解密、压缩与解压
会话层
负责建立、管理和断开通信连接,实现数据同步
传输层
为数据提供可靠的或不可靠的端到端传输,同时处理传输错误、控制流量,例如TCP/UDP协议
网络层
负责地址管理、路由选择和拥塞控制,例如IP协议
数据链路层
将数据分割成帧,并负责MAC寻址、差错检验和信息纠正,例如以太网
物理层
管理最基础的传送通道,建立物理连接,并提供物理链路所需的机械、电气、功能和过程等特性
TCP/IPTCP/IP是互联网服务的协议族,它是网络通信协议的统称,由IP、TCP、HTTP和FTP等协议组成。TCP/IP将 ...
基础
设计模式六大原则最终目的:高内聚、低耦合
开放封闭原则:一个软件实体,如类、模块和函数应该对扩展开放,对修改关闭
里氏替换原则:所有引用基类的地方,必须能透明地使用其子类的对象
依赖倒置原则:高层模块不应该依赖低层模块,二者都应该依赖其抽象;抽象不应该依赖细节;细节应该依赖抽象
单一职责原则:一个类只负责一项职责
接口隔离原则:客户端不应该依赖它不需要的接口;一个类对另一个类的依赖应该建立在最小的接口上
迪米特原则:一个对象应该对其他的对象保持最小的了解
数据结构概述
什么是数据结构数据结构,直白地理解,就是研究数据的存储方式。
数据存储只有一个目的,就是方便后期对数据的再利用。
综合来看,数据结构是一门学科,它教会我们“如何存储具有复杂关系的数据更有助于后期对数据的再利用”。
数据结构有哪些数据结构大致包含以下几种存储结构:
线性表:包括顺序表、链表、栈和队列
树结构:包括普通树、二叉树、二叉查找树、平衡二叉树、B-Tree、B+Tree 等
图结构:包括无向图、有向图、完全图、连通图 、稀疏图、稠密图等
时间复杂度和空间复杂度算法,即解决问题的方法。同一个问题,使用不同的算法,虽然得到相同的结果,但是耗费的时间和资源是不同的。
算法 VS 程序
算法是解决某个问题的方式、思路;程序是在心中有算法的前提下编写出来的可以运行的代码。
好算法的标准
首先它必须能够解决这个问题(称为准确性),其次,通过这个算法编写的程序要求在任何情况下不能崩溃(称为健壮性)。
若准确性和健壮性都满足,就要考虑最重要的一点:通过算法编写的程序,运行的效率怎么样。
运行的效率体现在两方面:
算法的运行时间(称为时间复杂度)
运行算法所需的内存空间大小(称为空间 ...