# 技术概念

# Flag

  • 代码不是靠死记硬背,而是不停的写、不停的思考,在反复的练习中熟练掌握的。
  • 编程需要学习记住的是:不同的场景中一些实现方式的原理机制、思维方式,如:设计模式、排序算法、数据结构等,而不是具体的代码。
  • 千万不要尝试用记忆力去替代自己的理解力!

RESTful是一种架构风格,其核心是面向资源,更简单;而WebService底层SOAP协议,主要核心是面向活动;两个都是通过web请求调用接口

逃逸分析(Escape Analysis)

是编译器用来决定程序中值的位置的过程。编译器执行静态代码分析,以确定一个构造体的实例化值是否会逃逸到堆

逃逸是指在某个方法之内创建的对象,除了在方法体之内被引用之外,还在方法体之外被其它变量引用到; 这样带来的后果是在该方法执行完毕之后,该方法中创建的对象将无法被GC回收,由于其被其它变量引用。 正常的方法调用中,方法体中创建的对象将在执行完毕之后,将回收其中创建的对象;故由于无法回收,即成为逃逸。

# 编程范式

编程范型、编程范式或程序设计法(Programming Paradigm)是某种编程语言典型的编程风格或者说是编程方式

范类:强类型/弱类型,动态语言/静态语言,编译/解释

  • 过程化(命令式)编程
  • 事件驱动编程
  • 面向对象编程
  • 链式编程
  • 函数式编程
  • 并发编程
  • 约束编程
  • 数据流编程(Dataflow programming)
  • 声明性编程
  • 分布式的编程
  • 泛型编程
  • 逻辑编程
  • 元编程
  • 响应式/反应式编程(Reactive programming)
  • 面向方面/面向切面编程(AOP)
  • 过程式编程

# 设计模式及原则

# 数据结构与算法

# 算法复杂度

O(1)O(n)O(logn)O(nlogn) 可表示时间复杂度,也可以表示空间复杂度

O加上()里面是一个函数f()O(f()),函数指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。

如果ax=Na>0,且a≠1),那么数x叫做以a为底N的对数,记作x=logaN,读作以a为底N的对数,其中a叫做对数的底数,N叫做真数。

类型 意义 举例
O(1) 最低复杂度,常量值也就是耗时/ 耗空间与输入数据大小无关,无论输入数据增大多少倍,耗时/耗空间都不变 哈希算法就是典型的O(1)时间复杂度,无论数据规模多大,都可以在一次计算后找到目标 (不考虑冲突的话)
O(n) 数据量增大几倍,耗时也增大几倍 遍历算法
O(n^2) 对n个数排序,需要扫描 n x n 次 冒泡排序
O(logn) 当数据增大n倍时,耗时增大logn 倍(这里的log是以2为底的,比 如,当数据增大256倍时,耗时只增大8倍, 二分查找就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标
O(nlogn) 就是n乘以logn,当数据增大256倍 时,耗时增大256*8=2048倍。这个复杂度高于线性低于平方。 归并排 序就是O(nlogn)的时间复杂度
数据结构 查找(平均) 查找(最坏) 插入(平均) 插入(最坏) 删除(平均) 删除(最坏) 遍历
数组 O(N) O(N) O(N) O(N) O(N) O(N)
有序数组 O(logN) O(n) O(N) O(N) O(N) O(N) O(N)
链表 O(N) O(N) O(1) O(1) O(1) O(1)
有序链表 O(N) O(N) O(N) O(N) O(1) O(1) O(N)
二叉查找树 O(logN) O(N) O(logN) O(N) O(logN) O(N) O(N)
红黑树 O(logN) O(logN) O(logN) O(logN) O(logN) O(logN) O(N)
平衡树 O(logN) O(logN) O(logN) O(logN) O(logN) O(logN) O(N)
二叉堆 优先队列 O(1) O(1) O(logN) O(logN) O(logN) O(logN) O(N)
哈希表 O(1) O(1) O(1) O(1) O(1) O(1) O(N)

# 数据传输模型

该模型用于帮助人们解决应用程序与服务器传递数据的问题

  • HTTP接口:基于HTTP协议的开发接口,如HTTP POST/GET
  • SOAP接口:是一种轻量的、简单的、基于XML(标准通用标记语言下的一个子集)的协议,它被设计成在WEB上交换结构化的和固化的信息。
  • Restful接口:一种接口规范,符合这套规范编写的接口就是restful 接口
  • Webservice接口:一种跨编程语言和跨操作系统平台的远程调用技术。SOAP/Restful都属于WebService接口。主要是系统间的调用。
  • RPC协议:远程过程调用,它是一种通过网络从远程计算机程序上跨语言跨平台的请求服务。主要是分布式式系统中应用。

# 网络通信协议

应用层

  • HTTP(Hypertext Transfer Protocol)超文本传输协议,显示网页
  • DNS(Domain Name System)
  • FTP(File Transfer Protocol)
  • SFTP(SSH File Transfer Protocol)和FTP不一样
  • SCP(Secure copy)基于SSH
  • SSH (Secure Shell)
  • SMTP(Simple Mail Transfer Protocol)
  • SNMP(simple Network Management Protocol)
  • Socket 是应用层与TCP/IP协议族通信的中间软件抽象层,它是一组接口。
    • 在设计模式中,Socket其实就是一个门面模式,它把复杂的TCP/IP协议族隐藏在Socket接口后面

通信层

网络层

  • IP(Internet Protocol)
  • ICMP(Internet Control Message Protocol,主要用于路由发送错误报告)
  • IGMP

链接层

  • MAC(media access control)
  • ARP
  • RARP

# HTTP

Content-Type只会存在于POSTPATCHPUT等有请求数据实体时指定数据类型和数据字符集编码, 而GETDELETEHEADOPTIONSTRACE等没有请求数据实体

Content-Length则视Content-Type而定,如text/htmltext/javascript等请求数据没有Content-Length

POSTPATCHPUT等请求有请求数据实体的数据为表单参数, GETDELETEHEADOPTIONSTRACE等没有请求数据实体的查询参数拼接在URL?后面

# 迭代循环遍历递归

  • 循环(loop),指的是在满足条件的情况下,重复执行同一段代码。比如,while语句。
    • 循环则即能对应集合,列表,数组等,也能对执行代码进行操作。
  • 遍历(traversal),指的是按照一定的规则访问树形结构中的每个节点,而且每个节点都只访问一次。
    • 遍历同迭代一样,也不能对执行代码进行遍历。
  • 迭代(iterate),指的是按照某种顺序逐个访问列表中的每一项。比如,for语句。
    • 迭代只能对应集合,列表,数组等。不能对执行代码进行迭代。
    • 环结构,从初始状态开始,每次迭代都遍历这个环,并更新状态,多次迭代直到到达结束状态
  • 递归(recursion),指的是一个函数不断调用自身的行为。比如,以编程方式输出著名的斐波纳契数列。
    • 线性递归(单向递归)和尾递归(tail recursion)。单向递归 → 尾递归 → 迭代
    • 树结构,从字面可以其理解为重复“递推”和“回归”的过程,当“递推”到达底部时就会开始“回归”,其过程相当于树的深度优先遍历

理论上递归和迭代时间复杂度方面是一样的,但实际应用中(函数调用和函数调用堆栈的开销)递归比迭代效率要低。

将递归方案转换为迭代的方案我们通常只需要两步即可:

  1. 我们在函数中使用堆或队列数据结构,以取代系统调用栈的作用。在每一次递归出现时,我们简单地将参数作为一个新元素压入到我们创建的数据结构中,来代替递归调用。
  2. 另外,我们在之前创建的数据结构上做一个循环操作。递归的调用链就被迭代的循环操作替代了。

# directory和folder区别

  • directory 目录,简称 dir
  • folder 文件夹

两者一般情况下是可以相互通用的,都表示文件夹的意思;但是细细纠来,还是有区别的:

Hi, please go to D:\files\images\directory, and then double click and open folder "travelImg".

  • 看完上面那句话,相信大家有点知道意思了:

directory 也是一个folder,但是我们在说一个directory的时候,通常指它含有路径的意思在里面;

folder 一般情况,是说某一个文件夹,通常不包含路径的意思,比如:双击这个文件夹,在里面找找看。

# 多线程

并发、并行、同步、异步、多线程、协程的区别

对操作系统来说,线程是最小的执行单元,进程是最小的资源管理单元。无论进程还是线程,都是由操作系统所管理的。

协程(Coroutine)编译器级的,进程(Process)和线程(Thread)操作系统级的,Process -> Thread -> Coroutine

  • 并发

同一时间段有几个程序都处于已经启动到运行完毕之间,并且这几个程序都在同一个处理机上运行,并发的两种关系是同步和互斥;

  • 互斥

进程之间访问临界资源时相互排斥的现象;

  • 同步

进程之间存在依赖关系,一个进程结束的输出作为另一个进程的输入。具有同步关系的一组并发进程之间发送的信息称为消息或者事件;

  • 并行

单处理器中进程被交替执行,表现出一种并发的外部特征;在多处理器中,进程可以交替执行,还能重叠执行, 实现并行处理,并行就是同事发生的多个并发事件,具有并发的含义,但并发不一定是并行,也就是说事件之间不一定要同一时刻发生;

  • 多线程

多线程是进程中并发运行的一段代码,能够实现线程之间的切换执行;

  • 异步

和同步相对,同步是顺序执行,而异步是彼此独立,在等待某个事件的过程中继续做自己的事,不要等待这一事件完成后再工作。 线程是实现异步的一个方式,异步是让调用方法的主线程不需要同步等待另一个线程的完成,从而让主线程干其他事情。

  • 异步和多线程

不是同等关系,异步是目的,多线程只是实现异步的一个手段,实现异步可以采用多线程技术或者交给其他进程来处理

  • 协程

coroutine协程详解 (opens new window)

协程 (opens new window)

协程,又称微线程,纤程。协程(Coroutine)是一种轻量级的用户态线程,实现的是非抢占式的调度,即由当前协程切换到其他协程由当前协程来控制。 协程本身可以做在用户态,每个协程的体积比线程要小得多,因此一个进程可以容纳数量相当可观的协程

  • 信号量

进程间通信之-信号量semaphore (opens new window)

信号量的使用主要是用来保护共享资源,使得资源在一个时刻只有一个进程(线程)所拥有。

信号量的值为正的时候,说明它空闲。所测试的线程可以锁定而使用它。若为0,说明它被占用,测试的线程要进入睡眠队列中,等待被唤醒。

上下文切换

什么是进程、线程、协程 (opens new window)

进程的切换者是操作系统,切换时机是根据操作系统自己的切换策略,用户是无感知的。 进程的切换内容包括页全局目录、内核栈、硬件上下文,切换内容保存在内存中。进程切换过程是由“用户态到内核态到用户态”的方式,切换效率低。

线程的切换者是操作系统,切换时机是根据操作系统自己的切换策略,用户无感知。 线程的切换内容包括内核栈和硬件上下文。线程切换内容保存在内核栈中。线程切换过程是由“用户态到内核态到用户态”, 切换效率中等。

协程的切换者是用户(编程者或应用程序),切换时机是用户自己的程序所决定的。 协程的切换内容是硬件上下文,切换内存保存在用户自己的变量(用户栈或堆)中。协程的切换过程只有用户态,即没有陷入内核态,因此切换效率高。

多线程并不一定是要在多核处理器才支持的,就算是单核也是可以支持多线程的。

CPU 通过给每个线程分配一定的时间片,由于时间非常短通常是几十毫秒,所以 CPU 可以不停的切换线程执行任务从而达到了多线程的效果。

但是由于在线程切换的时候需要保存本次执行的信息,在该线程被 CPU 剥夺时间片后又再次运行恢复上次所保存的信息的过程就称为上下文切换。

  • 上下文切换是非常耗效率的。通常有以下解决方案:
  1. 采用无锁编程,比如将数据按照 Hash(id) 进行取模分段,每个线程处理各自分段的数据,从而避免使用锁。
  2. 采用 CAS(compare and swap) 算法,如 Atomic 包就是采用 CAS 算法。
  3. 合理的创建线程,避免创建了一些线程但其中大部分都是处于 waiting 状态,因为每当从 waiting 状态切换到 running 状态都是一次上下文切换。

# 线程数量控制

  • IO密集型

线程数 = CPU核心数/(1-阻塞系数)

Blocking Coefficient(阻塞系数)(一般为0.8~0.9之间) = 阻塞时间/(阻塞时间+使用CPU的时间)

  • 计算密集型

CPU有超线程:线程数 = CPU内核线程数*2

CPU无超线程:线程数 = CPU核数+1

# 缓存

  • 缓存穿透

在高并发下,查询一个不存在的值时,缓存不会被命中,导致大量请求直接落到数据库上,如活动系统里面查询一个不存在的活动。

  • 缓存击穿

在高并发下,对一个特定的值进行查询,但是这个时候缓存正好过期了,缓存没有命中,导致大量请求直接落到数据库上,如活动系统里面查询活动信息,但是在活动进行过程中活动缓存突然过期了。

  • 缓存雪崩

在高并发下,大量的缓存key在同一时间失效,导致大量的请求落到数据库上,如活动系统里面同时进行着非常多的活动,但是在某个时间点所有的活动缓存全部过期。

  • 缓存命中率

命中:直接从缓存中读取到想要的数据。

不命中:缓存中没有想要的数据,还需要到数据库进行一次查询才能读取到想要的数据。

  • 缓存丢失

常见解决方案

  • 直接缓存NULL值(时间不能过长,防止影响正常值)
  • 过滤器(如白名单,符合某种规则等)
  • 限流
  • 缓存预热
  • 分级缓存
  • 缓存永远不过期

常见算法

  1. Least Frequently Used (LFU)
  2. Least Recently Used (LRU)
  3. Least Recently Used2 (LRU2)
  4. Two Queue (2Q)

# 锁和事务

单进程的系统中,存在多线程同时操作一个公共变量,此时需要加锁对变量进行同步操作,保证多线程的操作线性执行消除并发修改。 解决的是单进程中的多线程并发问题。

分布式锁

只要的应用场景是在集群模式的多个相同服务,可能会部署在不同机器上,解决进程间安全问题,防止多进程同时操作一个变量或者数据库。 解决的是多进程的并发问题。

事务

解决一个会话过程中,上下文的修改对所有数据库表的操作要么全部成功,要不全部失败。所以应用在service层。 解决的是一个会话中的操作的数据一致性。

分布式事务

解决一个联动操作,比如一个商品的买卖分为:(1)添加商品到购物车,(2)修改商品库存-1; 此时购物车服务和商品库存服务可能部署在两台电脑,这时候需要保证对两个服务的操作都全部成功或者全部回退。 解决的是组合服务的数据操作的一致性问题。

# HTTP授权认证

Basic Auth:这种认证直接顺应HTTP协议的无状态性,每次执行业务的时候,将username与password参数发送给服务器进行验证

Session:是指在客户端Cookie中存储一个Session Id。请求时携带Session Id,服务器从Session数据存储中找到对应的Session。 Native App一般是不直接支持Cookie机制

JWT是一种认证协议

JWT(Json web token)提供了一种用于发布接入令牌(Access Token),并对发布的签名接入令牌进行验证的方法。 令牌(Token)本身包含了一系列声明,应用程序可以根据这些声明限制用户对资源的访问。

应用场景:JWT是用在前后端分离, 需要简单的对后台API进行保护时使用.(前后端分离无session, 频繁传用户密码不安全)

# SSO

单点登录(Single sign-on)是在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统。

CAS

中央认证服务(Central Authentication Service),一个基于Kerberos票据方式实现SSO单点登录的集中认证服务协议

三个角色:用户/客户端(Browser),应用服务(CAS Client),单点登录服务器(CAS Server)

OAuth2

OAuth2是一种授权框架,提供了一套详细的授权机制(指导)。用户或应用可以通过公开的或私有的设置,授权第三方应用访问特定资源。

应用场景:OAuth2用在使用第三方账号登录的情况(比如使用weibo, qq, github登录某个app)

  • OAuth2是一个相对复杂的协议, 有4种授权模式:
  1. 授权码模式(authorization code)
  2. 密码模式(resource owner password credentials)
  3. 客户端模式(client credentials)
  4. 简化模式(implicit)

# 加密哈希

  • 编码算法 Base64
  • 哈希算法(摘要)
  • BouncyCastle
  • Hmac算法
  • 对称加密算法
    • 分组加密算法:AES (Advanced Encryption Standard)、DES(Data Encryption Standard)、TwoFish、3DES(Triple DES)、Blowfish
    • 流式加密算法:Salsa20、ChaCha20、RC4、ORYX、SEAL
  • 口令加密算法
  • 密钥交换算法
  • 非对称加密算法 RSA、DSA、ECC、DH、ElGamal
  • 签名算法
  • 数字证书

哈希(散列)函数-数据消息摘要算法

  • RC4, MD4, MD5, SHA-0, SHA-1, DES, 2DES 等(不推荐)
  • SHA-2(SHA-256, SHA-384, SHA-512)、SHA-3、Blake2、RipeMD128、RipeMD160、RipeMD256、RipeMD320Hex、RipeMD320、HmacRipeMD128
  • 密码哈希函数(Password Hash):PBKDF2, Bcrypt, Scrypt, Argon2
  • HMAC(Hash-based Message Authentication Code)散列消息认证码,结合一个加密密钥,通过特别计算方式之后产生的消息认证码(MAC)

应对普通哈希容易被破解的策略

  • 加盐(salt)

加盐就是对目标字段哈希前,拼接上另一个字段(salt)。注:盐值加到字段之前较为普遍。加盐对防彩虹表很有效。

  • 慢哈希
  • Base64

Base64是一种能将任意Binary资料用64种字元组合成字串的方法,而Binary资料和字串资料彼此之间可以互相转换。 在实际应用中,Base64除了能将Binary资料可视化之外,也常用来表示字串加密过后的内容

证书格式

  • .DER/.CER(X.509) 文件是二进制格式,只保存证书,不保存私钥,Java 和 Windows 服务器偏向于使用这种编码格式
  • .PEM(Privacy Enhanced Mail) 一般是文本格式,可保存证书,可保存私钥,常用于 Apache 和 Nginx 服务器
    • 一般为文本格式,以 -----BEGIN... 开头,以 -----END... 结尾,中间的内容是 BASE64 编码。
    • 这种格式可以保存证书和私钥,有时也把PEM 格式的私钥的后缀改为 .key 以区别证书与私钥
  • .CRT(Certificate) 可以是二进制格式,可以是文本格式,与 .DER 格式相同,不保存私钥。
  • .PFX/.P12(Predecessor of PKCS#12) 二进制格式,同时包含证书和私钥,一般有密码保护。
  • .JKS(Java Key Storage) 二进制格式,同时包含证书和私钥,一般有密码保护,JAVA 专属格式,一般用于 Tomcat 服务器

# CICD

  • CI全名Continuous Integration 持续集成概念
  • CD全名是Continuous Deployment,是持续部署
  • CD Continuous delivery,交持续交付

CI/CD优点是,重复的工作用自动化来代替、减少时间成本、版本发布时间减短了。 当开发每天会提交多次代码到主干上,会做一些重复性的动作时,就可以用持续集成环境来操作。