# 技术概念

类型	意义	举例
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)

https://github.com/labuladong/fucking-algorithm (opens new window)

排序、双指针、查找、分治、动态规划、递归、回溯、贪心、位运算、DFS、BFS、图

# 数据传输模型

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

JMS Java消息服务(Java Message Service) (opens new window)

Web Service 模型
- SOAP(Simple Object Access Protocol，即简单对象访问协议) (opens new window) 模型（面向消息）
- RPC 模型（面向方法）
  - XML-RPC (opens new window)
  - JSON-RPC (opens new window)
  - SOAP + WSDL [SOAP 本质上是 XML-RPC 的升级版]
- REST Web Service
- RESTful Web Service
WEB API
- REST(Representational State Transfer) 模型（面向资源）
  - REST API
  - RestFul API
  - GraphQL
SOA（面向服务的架构）

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

# 网络通信协议

应用层

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

通信层

TCP（Transmission Control Protocol）三次握手传输协议
- 详解TCP连接的“三次握手”与“四次挥手” (opens new window)
UDP（User Datagram Protocol）用户数据报协议
TCP、Socket、WebSocket、HTTP (opens new window)
网络编程 socket详解 TCP socket和UDP socket (opens new window)
【Socket学习】1. TCP与UDP (opens new window)
socket通信 tcp协议和udp协议 C++ (opens new window)
UDP 和 TCP 的 socket 分别一般用在什么地方？ (opens new window)
https://wicg.github.io/direct-sockets (opens new window)
https://github.com/NetAsmCom/Socketify (opens new window)

网络层

IP（Internet Protocol）
ICMP（Internet Control Message Protocol，主要用于路由发送错误报告）
IGMP

链接层

MAC（media access control）
ARP
RARP

# HTTP

Content-Type只会存在于POST、PATCH、PUT等有请求数据实体时指定数据类型和数据字符集编码，而GET、DELETE、HEAD、OPTIONS、TRACE等没有请求数据实体

Content-Length则视Content-Type而定，如text/html、text/javascript等请求数据没有Content-Length

POST、PATCH、PUT等请求有请求数据实体的数据为表单参数， GET、DELETE、HEAD、OPTIONS、TRACE等没有请求数据实体的查询参数拼接在URL?后面

# 迭代循环遍历递归

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

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

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

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

# 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 一般情况，是说某一个文件夹，通常不包含路径的意思，比如：双击这个文件夹，在里面找找看。

# 进程/线程/纤程/协程

DRF-SC：无数据竞争的程序以顺序一致的方式执行

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

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

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

并发

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

互斥

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

同步

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

并行

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

多线程

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

异步

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

异步和多线程

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

协程coroutine

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

信号量

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

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

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

上下文切换

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

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

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

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

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

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

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

上下文切换是非常耗效率的。通常有以下解决方案:

采用无锁编程，比如将数据按照 Hash(id) 进行取模分段，每个线程处理各自分段的数据，从而避免使用锁。
采用 CAS(compare and swap) 算法，如 Atomic 包就是采用 CAS 算法。
合理的创建线程，避免创建了一些线程但其中大部分都是处于 waiting 状态，因为每当从 waiting 状态切换到 running 状态都是一次上下文切换。

# 线程数量控制

别再纠结线程池大小/线程数量了，没有固定公式的 (opens new window)

IO密集型

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

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

计算密集型

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

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

# 缓存

缓存穿透、缓存击穿和缓存雪崩实践 (opens new window)

缓存穿透

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

缓存击穿

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

缓存雪崩

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

缓存命中率

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

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

缓存丢失

常见解决方案

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

常见算法

Least Frequently Used (LFU)
Least Recently Used (LRU)
Least Recently Used2 (LRU2)
Two Queue (2Q)

# 锁和事务

锁

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

分布式锁

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

事务

事物概念 (opens new window)

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

分布式事务

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

# HTTP授权认证

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

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

JWT是一种认证协议

https://github.com/auth0 (opens new window)
- https://jwt.io (opens new window)

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

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

# 加密哈希

同态加密（HE） https://github.com/homenc/HElib (opens new window)
https://github.com/google/fully-homomorphic-encryption (opens new window)

Java开发中的加密、解密、签名、验签，密钥，证书 (opens new window)

加密算法

使用密钥加密数据转换成指定格式的数据，可通过密钥转换还原数据

BouncyCastle
Hmac算法
对称加密算法
- 分组加密算法：AES （Advanced Encryption Standard）、DES（Data Encryption Standard）、TwoFish、3DES（Triple DES）、Blowfish
- 流式加密算法：Salsa20、ChaCha20、RC4、ORYX、SEAL、Rabbit
口令加密算法
密钥交换算法 DHE、ECDHE
非对称加密算法 RSA、DSA(Digital Signature Algorithm)、ECDSA、ECC(Elliptic Curves Cryptography)、DH、ElGamal
- 加解密篇 - 非对称加密算法 (RSA、DSA、ECC、DH) (opens new window)
签名算法
数字证书

编码算法

把数据转换成指定格式的数据，可解码，一般用于处理特殊字符

Base64
quoted-printable Percent-encoding (opens new window)
Content-Transfer-Encoding (opens new window)
Unicode编码(\u开头)
URL编码(%开头)
Gzip压缩
UTF16编码(\x开头)
十六进制编码
HTML深度编码

哈希（散列）函数-数据消息摘要算法

生成数据的唯一密文，不可逆

密码哈希（Password Hash） (opens new window)

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）
- 从零入门HMAC-SHA256 (opens new window)

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

加盐（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/CD？ (opens new window)

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

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

# 定时任务

分布式定时任务解决方案

分时方案：严格划分时间片，交替运行计划任务，当主系统宕机后，备用系统仍然工作，但处理初期被拉长
HA（High Availability）高可用方案：正常情况下主系统工作，备用系统守候，心跳检测发现主系统出现故障备用系统启动
多路心跳方案：
- 采用多路心跳，做服务级，进程级的，IP和端口级别的心跳检测，正常情况是主系统工作，备用系统守候
- 心跳检测主系统出现故障，备用系统启动，当再次检测到主系统工作，则将执行权交回主系统
任务抢占方案：
- A，B两台服务器同时工作，启动需要存在一前一后，谁先启动谁率先加锁，其他服务器只能等待
- 他们同时对互斥锁进行监控，一旦发现锁被释放，其他服务那个先抢到，那个运行，运行前加排他锁。
任务轮询或任务轮询+抢占排队方案：
- 每个服务器首次启动时加入队列；
- 每次任务运行首先判断自己是否是当前可运行任务，如果是便运行；
- 如果不是当前运行的任务，检查自己是否在队列中，如果在，便推出，如果不在队列中，便键入队列

← 其他编程语言编程规范 →