知识总结
2019-12-19 10:21:09 0 举报AI智能生成
java知识点总结
作者其他创作
大纲/内容
数据结构与算法
数据结构
线性结构
数组
数组的基本操作
Insert——在指定索引位置插入一个元素
Get——返回指定索引位置的元素
Delete——删除指定索引位置的元素
Size——得到数组所有元素的数量
数组常见问题
寻找数组中第k大(小)的元素
找到数组中第一个不重复出现的整数
合并两个有序数组
重新排列数组中的正值和负值
链表
链表的基本操作
InsertAtEnd - 在链表的末尾插入指定元素
InsertAtHead - 在链接列表的开头/头部插入指定元素
Delete - 从链接列表中删除指定元素
DeleteAtHead - 删除链接列表的第一个元素
Search - 从链表中返回指定元素
isEmpty - 如果链表为空，则返回true
链表常见问题
反转链表
检测链表中的循环
返回链表倒数第N个节点
删除链表中的重复项
栈
栈的基本操作
Push——在顶部插入一个元素
Pop——返回并移除栈顶元素
isEmpty——如果栈为空，则返回true
Top——返回顶部元素，但并不移除它
栈的常见问题
使用栈计算后缀表达式
对栈的元素进行排序
判断表达式是否括号平衡
消除递归
深度优先搜索
出栈顺序：卡特兰数
队列
队列的基本操作
Enqueue() —— 在队列尾部插入元素
Dequeue() ——移除队列头部的元素
isEmpty()——如果队列为空，则返回true
Top() ——返回队列的第一个元素
关于队列的常见问题
使用队列表示栈
对队列的前k个元素倒序
使用队列生成从1到n的二进制数
字符串
字符串查找
暴力查找
指纹（Rabin-Karp）
KMP
BM
Sunday
Trie树
AC自动机
编码
字符集
ASCII
GBK
ISO
Unicode
编码
UFT-8
Base64
哈希表
哈希函数构造方法
哈希冲突解决方法
非线性结构
树
基础知识
结点：指树中的一个元素；
结点的度：指结点拥有的子树的个数，二叉树的度不大于2；
树的度：指树中的最大结点度数；
叶子：度为0的结点，也称为终端结点；
高度：叶子节点的高度为1，根节点高度最高；
层：根在第一层，以此类推；
二叉树性质
1：二叉树的第i层上至多有2^(i-1)个结点
2：深度为k的二叉树，至多有2^k-1个结点
二叉树的遍历
1：先序遍历：根->左子树->右子树（先序）
2：中序遍历：左子树->根->右子树（中序）
3：后序遍历：左子树->右子树->根（后序）
完全二叉树
定义：如果二叉树的深度为k，则除第k层外其余所有层节点的度都为2，且叶子节点从左到右依次存在
性质
1：结点 i 的子结点为2*i 和 2*i+1(前提是都小于总结点数)
2：结点 i 的父结点为 i/2
满二叉树：叶子节点一定要在最后一层，并且所有非叶子节点都存在左孩子和右孩子
二叉搜索树
概念
二叉查找树（Binary Search Tree）也称有序二叉树（Ordered Binary Tree）、排序二叉树（Sorted Binary Tree）。
二叉查找树是java的 TreeSet 和 TreeMap 类实现的基础。
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。
特点
若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意结点的左、右子树也分别为二叉查找树。
没有键值相等的结点（no duplicate nodes）。
平衡二叉树
概念
AVL树又称为高度平衡的二叉搜索树。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。
性质
左子树和右子树的高度之差的绝对值不超过1
树中的每个左子树和右子树都是AVL树
一棵AVL树有N个节点，其高度可以保持在lgN，插入/删除/查找的时间复杂度也是lgN。
234树
概念
2-3-4树是平衡树，但不是二叉树，因为它可以有多个节点值，也可以有多个节点。它可以实现完美平衡
节点种类
2-node: 一个key值，两个儿子节点。
3-node: 两个key值，三个儿子节点。
4-node: 三个key值，四个儿子节点。
子树种类
2-node: 左子树比key小，右子树比key大。
3-node：左子树比第一个key小；中间子树比比第一个key大，比第二个key小；右子树比第二个key大。
4-node：左子树比第一个key小；第二子树比比第一个key大，比第二个key小；第三子树比第二个key大，比第三个key小；右子树比第三个key大。
红黑树
概念
一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。
规则
每个节点不是红色就是黑色的；
根节点总是黑色的；
如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。
B树
B-树
规则
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的
子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
特点
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；
B+树
规则
1.其定义基本与B-树同，除了：
2.非叶子结点的子树指针与关键字个数相同；
3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
5.为所有叶子结点增加一个链指针；
6.所有关键字都在叶子结点出现；
特点
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统；
B*树
是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针
LSM树
把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。
LSM树与B树相比，牺牲了部分的读性能，大幅提高写性能。
图
图的表示
邻接表
邻接矩阵
最短路径
Dijistra
Floyd
最小生成树
Kruskal
Prime
最大流
拓扑排序
并查集
算法
排序
基于比较
冒泡排序
选择排序
插入排序
希尔排序
归并排序
快速排序
堆排序
基于计数
计数排序
基数排序
桶排序
查找
二分查找
基本二分查找
变型
递归
回溯
动态规划
DFS/BFS
海量数据处理
基础知识
解决时间复杂度
解决空间复杂度
数学与数理逻辑
位运算
rand7
蓄水池抽样
洗牌
胡牌
抢红包
智力题
操作系统
进程管理
特征
动态性
并发性
独立性
结构性
进程与线程的区别
线程：调度的基本单位
进程：拥有资源的基本单位
状态
新建
就绪
运行
阻塞
终止
PCB(进程管理块)
进程标识符
处理机状态
进程调度信息
进程控制信息
通信
低级PV
共享存储
消息传递
管道通信
调度
死锁
必要条件
互斥条件
不剥夺条件
请求和保持条件
环路等待条件
预防：破坏四个条件
死锁避免：银行家算法
死锁检测和解除
文件管理
文件结构
逻辑结构
无结构
有结构
顺序文件
索引文件
索引顺序文件
散列文件
物理结构
顺序结构
链接结构
隐式链接
显示链接
FAT表
索引结构
存储空间管理
空闲表法
空闲链表法
位示图
磁盘管理
调度算法
FCFS
SSTF
SCAN
C-SCAN
内存管理
程序编译、链接
静态
装入动态
运行动态
装入
绝对装入
重定位装入
动态运行时(重定位寄存器)
连续分配
单一连续
固定分区
动态分区
首次适应
最佳适应
最坏适应
临近适应
非连续分配
页式
段式
段页
虚拟内存
请求分页
缺页中断
页面置换算法
OPT
LRU
CLOCK
FIFO
页面分配策略
驻留集大小
调入页面的时机
从何处调入页面
Linux
目录结构
常用命令
权限
文件
进程
网络
shell
计算机网络
基础
通信方式
C/S
P2P
电路交换与分组交换
时延：排队时延+处理时延+传输时延+传播时延
体系结构
OSI(七层)
五层协议
TCP/IP
体系结构
物理层
传输方式
单工通信
半双工通信
双工通信
带通调制：数字信号转换为模拟信号
数据链路层
基本问题
封装成帧
透明传输
差错检测
信道分类
广播信道
点对点信道
信道复用
频分复用
时分复用
统计时分复用
波分复用
码分复用
CSMA/CD
PPP协议
MAC地址
局域网、以太网、虚拟局域网
交换机
网络层
IP数据包
IP地址编址方式
ARP协议
ICMP协议
Ping
Traceroute
VPN
NAT网络地址转换
路由器
传输层
UDP
TCP
首部
三次握手
四次挥手
可靠传输
滑动窗口
流量控制
拥塞控制
慢开始
拥塞避免
快重传
快恢复
应用层
DNS域名系统
FTP文件传输协议
DHCP动态主机配置协议
TELNET远程登录协议
电子邮件协议
POP3
IMAP
HTTP
URI:URI=URL+URN
http方法
GET
POST
PUT
HEAD
PATCH
DELETE
OPTIONS
CONNECT
TRACE
状态码
1XX：信息性状态码
2XX:成功状态码
3XX:重定向状态码
4XX:客户端错误状态码
5XX:服务端状态码
cookie与session
缓存
连接管理
长连接
短连接
流水线
http2
二进制分帧
服务端推送
https
加密
认证
完整性保护
GET与POST的区别
作用
参数
安全
幂等性
缓存
XmlHttpRequest
数据库
数据库原理
ACID
原子性
一致性
隔离性
持久性
隔离级别
读未提交
读已提交
可重复度
串行化
并发一致性问题
丢失修改
脏读
不可重复读
幻读
封锁
封锁粒度
表级锁
行级锁
封锁类型
共享锁
排它锁
悲观锁
乐观锁
三级封锁协议
一级封锁协议
二级封锁协议
三级封锁协议
两段锁协议
扩展阶段
收缩阶段
显式/隐式锁定
MVVC
版本号
隐藏的列
undo日志
next-key locks
Record Locks
Gap Locks
Next-key Locks
死锁
产生原因
解决方法
范式
第一范式
第二范式
第三范式
巴斯-科德范式(BCNF)
第四范式
第五范式(完美范式)
反范式
SQL
查询
分组查询
连接查询
同表
自连接
多表
内连接
等值连接
不等值连接
自然连接
外连接
左连接
右连接
全连接
交叉连接
子查询
视图
触发器
存储过程
MySQL
InnoDB与MyISAM
区别
存储结构
存储空间
可移植性、备份及恢复
事务支持
AUTO_INCREMENT
表锁
全文索引
表主键
具体行数
CURD操作
外键
选用
索引优化
索引分类
数据结构角度
B+树索引
hash索引
FULLTEXT索引（现在MyISAM和InnoDB引擎都支持了）
R-Tree索引（用于对GIS数据类型创建SPATIAL索引）
物理存储角度
聚集索引（clustered index）
非聚集索引（non-clustered index）
逻辑角度
主键索引：主键索引是一种特殊的唯一索引，不允许有空值
普通索引或者单列索引
多列索引（复合索引）：复合索引指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。使用复合索引时遵循最左前缀集合
唯一索引或者非唯一索引
空间索引：空间索引是对空间数据类型的字段建立的索引，MYSQL中的空间数据类型有4种，分别是GEOMETRY、POINT、LINESTRING、POLYGON。
建索引的原则
① 最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整；
② =和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式；
③ 尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0，那可能有人会问，这个比例有什么经验值吗？使用场景不同，这个值也很难确定，一般需要join的字段我们都要求是0.1以上，即平均1条扫描10条记录；
④ 索引列不能参与计算，保持列“干净”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’);
⑤ 尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可。
查询优化
Explain
优化思路
优化数据访问
减少请求的数量
减少服务端扫描的行数
重构查询方式
切分大查询
分解大连接查询
水平切分与垂直切分
原理
水平切分
垂直切分
存在的问题
存在分布式事务的问题。
存在跨节点Join的问题。
存在跨节点合并排序、分页的问题。
存在多数据源管理的问题。
主从复制
原理
分类
基于 SQL 语句的复制(statement-based replication, SBR)
基于行的复制(row-based replication, RBR)
混合模式复制(mixed-based replication, MBR)
日志
重做日志（redo log）
回滚日志（undo log）
二进制日志（binlog）
错误日志（errorlog）
慢查询日志（slow query log）
一般查询日志（general log）
中继日志（relay log）
面向对象与设计模式
UML
面向对象设计原则
开闭原则(OCP)
单一职责原则(SRP)
里式替换原则(LSP)
依赖倒置原则(DIP)
接口隔离原则(ISP)
合成复用原则(CRP)
迪米特法则(LoD)
对象间的关系
泛化
继承
实现
关联
组合(大雁-翅膀)
聚合(雁群-大雁)
依赖
UML图
用例视图
用例图
设计视图
类图
对象图
进程视图
序列图
协作图
状态图
活动图
实现视图
构件图
拓扑视图
部署图
设计模式
创建型
单例模式
工厂模式
简单工厂
工厂方法
抽象工厂
建造者模式
原型模式
结构型
适配器模式
桥接模式
组合模式
装饰者模式
外观模式
享元模式
代理模式
行为型
责任链模式
命令模式
策略模式
解释器模式
迭代模式
备忘录模式
状态模式
模板方法模式
中介者模式
观察者模式
访问者模式
Java与框架
JAVA
基础
数据类型
运算符
流程控制
面向对象
三大特性
接口与抽象类
内部类
注解
泛型
核心
JCF
JVM
JUC
类库
字符串
时间
I/O
网络
正则
数据库
新特性
Spring
MVC
IOC
AOP
事务
MyBatis
原理
插件
Hibernate
原理
缓存
关系映射
API
分布式与系统设计
分布式架构原理
分布式架构要点
CAP
BASE
分布式一致性协议
2PC/3PC
Paxos
Raft
Zab
分布式通信
RPC
webService
RMI
thrift
Netty
分布式缓存
缓存位置
CDN
LRU
缓存问题
缓存穿透
缓存雪崩
缓存一致性
一致性hash
分布式数据库中间件
mycat
zebra
分布式实战
分布式全局ID
分布式seesion与SSO登录
分布式事务
分布式锁
分布式任务调度
高并发下的服务降级、限流
负载均衡算法
(加权)轮询
(加权)最少连接
随机
原地址hash
系统设计
秒杀系统
WEB页面请求
二维码登录
tinyURL
KV存储
搜索引擎
微服务
微服务架构
SpringBoot
SpringCloud
dubbo
ServiceMesh
NACOS
NoSQL与大数据
NoSQL
Redis
Hbase
大数据
基本概念
解决问题
采集
存储
计算
查询
挖掘
大数据4V特性
数量（Volume），即数据巨大，从TB级别跃升到PB级别
多样性（Variety），即数据类型繁多，不仅包括传统的格式化数据，还包括来自互联网的网络日志、视频、图片、地理位置信息等
速度（Velocity），即处理速度快
真实性（Veracity），即追求高质量的数据。
Hadoop
HDFS
架构
文件读取和写入流程
高可用
YARN
MapReduce
Spark
RDD
Flink
OLAP
Hive
Kylin
ElasticSearch
工程化
Git
Maven
docker
tomcat
jetty
0 条评论
下一页
