2023年1月10日 22:09 周二转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!
补充索引基础知识(引自b站sgg视频)
#
- 存储引擎，数据的基本单位是页，如果数据很少，只有一页，那就简单，是直接二分查找(不涉及磁盘IO)；如果数据很多，有好几个页，那么需要对页建立一种数据结构，能够最快定位到哪一页，然后减少磁盘IO
索引介绍
#
索引的优缺点
#
优点：
- 使用索引可以大大加快 数据的检索速度（大大减少检索的数据量）, 这也是创建索引的最主要的原因。
- 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
缺点：
- 创建索引和维护索引需要耗费许多时间。当对表中的数据进行增删改的时候，如果数据有索引，那么索引也需要动态的修改，会降低 SQL 执行效率。
- 索引需要使用物理文件存储，也会耗费一定空间
索引一定会提高查询性能吗
- 多数情况下，索引查询都是比全表扫描要快的。但是如果数据库的数据量不大，那么使用索引也不一定能够带来很大提升
索引的底层数据结构
#
Hash表
#
哈希表是键值对的集合，通过键（key）即可快速取出对应的值（value），因此哈希表可以快速检索数据（接近O(1))
为何能够通过key快速取出value呢？原因在于哈希算法（也叫散列算法）。通过哈希算法，我们可以快速找到key对应的index，找到了index也就找到了对应的value
hash = hashfunc(key)
index = hash % array_size
注意，图中keys[天蓝色]是字符串，不是什么莫名其妙的人
哈希算法有个 Hash 冲突 问题，也就是说多个不同的 key 最后得到的 index 相同。通常情况下，我们常用的解决办法是 链地址法。链地址法就是将哈希冲突数据存放在链表中。就比如 JDK1.8 之前 HashMap 就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了减少链表过长的时候搜索时间过长引入了红黑树。
为了减少 Hash 冲突的发生，一个好的哈希函数应该**“均匀地”将数据分布**在整个可能的哈希值集合中
由于Hash索引不支持顺序和范围查询，假如要对表中的数据进行排序或者进行范围查询，那Hash索引就不行了，并且，每次IO只能取一个
例如： SELECT * FROM tb1 WHERE id < 500 ;
...
2023年1月10日 16:48 周二 转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!
图示总结
- MySQL字符编码集有两套UTF-8编码实现：utf-8 和 utf8mb4
而其中，utf-8 不支持存储emoji符号和一些比较复杂的汉字、繁体字，会出错
何为字符集
#
有哪些常见的字符集
#
- 常见的字符集有ASCLL、GB2312、GBK、UTF-8
- 不同的字符集的主要区别在于
- 可以表示的字符范围
- 编码方式
ASCLL
#
ASCII (American Standard Code for Information Interchange，美国信息交换标准代码) 是一套主要用于现代美国英语的字符集（这也是 ASCII 字符集的局限性所在）
为什么 ASCII 字符集没有考虑到中文等其他字符呢？ 因为计算机是美国人发明的，当时，计算机的发展还处于比较雏形的时代，还未在其他国家大规模使用。因此，美国发布 ASCII 字符集的时候没有考虑兼容其他国家的语言
ASCII 字符集至今为止共定义了 128 个字符，其中有 33 个控制字符（比如回车、删除）无法显示
一个 ASCII 码长度是一个字节也就是 8 个 bit，比如“a”对应的 ASCII 码是“01100001”。不过，最高位是 0 仅仅作为校验位，其余 7 位使用 0 和 1 进行组合，所以，ASCII 字符集可以定义 128（2^7）个字符
由于，ASCII 码可以表示的字符实在是太少了。后来，人们对其进行了扩展得到了 ASCII 扩展字符集 。ASCII 扩展字符集使用 8 位（bits）表示一个字符，所以，ASCII 扩展字符集可以定义 256（2^8）个字符
...
2023年1月9日 15:52 周一 转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!
二叉树的分类
#
- **二叉树（Binary tree）**是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构
- 二叉树的分支，通常被称为左子树或右子树，并且，二叉树的分支具有左右次序，不能随意颠倒
- 二叉树的第i层至多拥有2^(i-1) 个节点
深度为k的二叉树至多总共有 2^(k+1) -1 个节点 （深度为k，最多k + 1 层，最多为满二叉树的情况）
至少有2^(k) 个节点，即 深度为k-1的二叉树的最多的节点再加1
（关于节点的深度的定义国内争议比较多，我个人比较认可维基百科对
节点深度的定义open in new window）。
满二叉树
#
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是 满二叉树。也就是说，如果一个二叉树的层数为 K，且结点总数是(2^k) -1 ，则它就是 满二叉树。
...
2023年1月6日 10:46 周五 转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!
什么是堆
#
堆的用途
#
堆的分类
#
- 堆分为最大堆和最小堆，二者的区别在于节点的排序方式
- 最大堆：堆中的每一个节点的值都大于子树中所有节点的值
- 最小堆：堆中的每一个节点的值都小于子树中所有节点的值
- 如图，图1是最大堆，图2是最小堆
堆的存储
#
- 由于完全二叉树的优秀性质，利用数组存储二叉树即节省空间，又方便索引（若根结点的序号为1，那么对于树中任意节点i，其左子节点序号为
2*i，右子节点序号为 2*i+1）。 - 为了方便存储和索引，（二叉）堆可以用完全二叉树的形式进行存储。存储的方式如下图所示
堆的操作
#
堆的更新操作主要包括两种：插入元素和删除堆顶元素
堆是一个公平的公司，有能力的人自然会走到与他能力所匹配的位置
插入元素
#
- 将要插入的元素放到最后
- 从底向上，如果父节点比该元素小，则该节点和父节点交换（其实就是一棵树有3个（最多）节点，与树上最大的节点比较）
直到无法交换（已经与根节点比较过）
删除堆顶元素
#
根据堆的性质可知，最大堆的堆盯元素为所有元素中最大的，最小堆的堆顶元素是所有元素中最小的
当我们需要多次查找最大元素或者最小元素的时候，可以利用堆来实现
删除堆顶元素后，为了保持堆的性质，需要对堆的结构进行调整，我们可以将这个过程称之为堆化
- 自底向上的堆化，上述的插入元素所使用的，就是自顶向上的堆化，元素从最底部向上移动
- 自顶向下的堆化，元素由顶部向下移动。在讲解删除堆顶元素的方法时，我将阐述这两种操作的过程
自底向上堆化
在堆这个公司中，会出现老大离职的现象，老大离职之后，它的位置就空出来了
首先删除堆顶元素，使得数组中下标为1的位置空出
...
2022年12月26日 08:47 周一 转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!
- 图是一种较为复杂的非线性结构
- 线性数据结构的元素满足唯一的线性关系，每个元素（除第一个和最后一个外）只有一个直接前驱和一个直接后继
- 树形数据结构的元素之间有着明显的层级关系
- 图形结构的元素之间的关系是任意的
- 图就是由顶点的有穷非空集合和顶点之间的边组成的集合，通常表示为：G（V，E），其中，G表示一个图，V表示顶点的集合，E表示边的集合
- 下面显示的即图这种数据结构，而且还是一张有向图
图的基本概念
#
顶点
#
- 图中的数据元素，我们称之为顶点，图至少有一个顶点（有穷非空集合）
- 对应到好友关系图，每一个用户就代表一个顶点
- 顶点之间的关系用边表示
- 对应到好友关系图，两个用户是好友的话，那两者之间就存在一条边
- 度表示一个顶点包含多少条边
- 有向图中，分为出度和入度，出度表示从该顶点出去的边的条数，入度表示从进入该顶点的边的条数
- 对应到好友关系图，度就代表了某个人的好友数量
无向图和有向图
#
边表示的是顶点之间的关系，有的关系是双向的，比如同学关系，A是B的同学，那么B也肯定是A的同学，那么在表示A和B的关系时，就不用关注方向，用不带箭头的边表示，这样的图就是无向图。
有的关系是有方向的，比如父子关系，师生关系，微博的关注关系，A是B的爸爸，但B肯定不是A的爸爸，A关注B，B不一定关注A。在这种情况下，我们就用带箭头的边表示二者的关系，这样的图就是有向图。
无权图和带权图
#
对于一个关系，如果我们只关心关系的有无，而不关心关系有多强，那么就可以用无权图表示二者的关系。
对于一个关系，如果我们既关心关系的有无，也关心关系的强度，比如描述地图上两个城市的关系，需要用到距离，那么就用带权图来表示，带权图中的每一条边一个数值表示权值，代表关系的强度。
下图就是一个带权有向图。
图的存储
#
邻接矩阵存储
#
- 邻接矩阵将图用二维矩阵存储，是一种比较直观的表示方式
- 如果第i个顶点和第j个顶点有关系，且关系权值为n，则A[i] [j] = n
- 在无向图中，我们只关心关系的有无，所以当顶点i和顶点j有关系时，A[i] [j]=1 ; 当顶点i和顶点j没有关系时，A[i] [j] = 0 ，如下图所示
无向图的邻接矩阵是一个对称矩阵，因为在无向图中，顶点i和顶点j有关系，则顶点j和顶点i必有关系 - 有向图的邻接矩阵存储
邻接矩阵存储的方式优点是简单直接（直接使用一个二维数组即可），并且在获取两个顶点之间的关系的时候也非常高效*直接获取指定位置的数组元素。但是这种存储方式的确定啊也比较明显即 比较浪费空间
邻接表存储
#
2022年12月20日 13:34 周二 转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!
数组
#
- 数组（Array）是一种常见数据结构，由相同类型的元素（element）组成，并且是使用一块连续的内存来存储
- 直接可以利用元素的**索引（index）**可以计算出该元素对应的存储地址
- 数组的特点是：提供随机访问并且容量有限
假设数组长度为n：
访问：O(1) //访问特定位置的元素
插入：O(n) //最坏的情况插入在数组的首部并需要移动所有元素时
删除：O(n) //最坏的情况发生在删除数组的开头并需要移动第一元素后面所有的元素时
链表
#
链表简介
#
链表（LinkedList）虽然是一种线性表，但是并不会按线性的顺序存储数据，使用的不是连续的内存空间来存储数据
链表的插入和删除操作的复杂度为O(1)，只需要直到目标位置元素的上一个元素即可。但是，在查找一个节点或者访问特定位置的节点的时候复杂度为O(n)
使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理
但链表不会节省空间，相比于数组会占用更多空间，因为链表中每个节点存放的还有指向其他节点的指针。除此之外，链表不具有数组随机读取的优点
链表分类
#
单链表、双向链表、循环链表、双向循环链表
假设链表中有n个元素
访问：O(n) //访问特地给位置的元素
插入删除：O(1) //必须要知道插入元素的位置
单链表
#
- 单链表只有一个方向，结点只有一个后继指针next指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的
- 我们习惯性地把第一个结点叫做头结点，链表通常有一个不保存任何值的head节点（头结点），通过头结点我们可以遍历整个链表，尾结点通常指向null
- 如下图
循环链表
#
- 循环链表是一种特殊的单链表，和单链表不同的是循环链表的尾结点不是指向null，而是指向链表的头结点
- 如图
双向链表
#
- 双向链表包含两个指针，一个prev指向前一个节点，另一个next指向
- 如图
双向循环链表
#
双向循环链表的最后一个节点的next指向head，而head的prev指向最后一个节点，构成一个环
应用场景
#
- 如果需要支持随机访问的话，链表无法做到
- 如果需要存储的数据元素个数不确定，并且需要经常添加和删除数据的话，使用链表比较合适
- 如果需要存储的数据元素的个数确定，并且不需要经常添加和删除数据的话，使用数组比较合适
数组 vs 链表
#
- 数组支持随机访问，链表不支持
- 数组使用的是连续内存空间 对CPU缓存机制友好，链表则相反
- 数组的大小固定，而链表则天然支持动态扩容。如果生命的数组过小，需要另外申请一个更大的内存空间存放数组元素，然后将原数组拷贝进去，这个操作比较耗时
栈简介
#
- 栈（stack）只允许在有序的线性数据集合的一端（称为栈顶top）进行加入数据（push）和移除数据（pop）。因而按照**后进先出（LIFO，Last In First Out）**的原理运作。
- 栈中，push和pop的操作都发生在栈顶
- 栈常用一维数组或链表来实现，用数组实现的叫顺序栈，用链表实现的叫做链式栈
假设堆栈中有n个元素。
访问：O（n）//最坏情况
插入删除：O（1）//顶端插入和删除元素
...
2022年12月20日 11:19 周二 转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!
这部分内容由于涉及太多概念性内容，所以参考了维基百科和百度百科相应的介绍。
什么是数据库，数据库管理系统，数据库系统，数据库管理员
#
- 数据库：数据库（DataBase 简称DB）就是信息的集合或者说数据库管理系统管理的数据的集合。
- 数据库管理系统：数据库管理系统（Database Management System 简称DBMS）是一种操纵和管理数据库的大型软件，通常用于建立、使用和维护 数据库。
- 数据库系统（范围最大）：数据库系统（Data Base System，简称DBS）通常由**软件、数据和数据管理员（DBA）**组成。
- 数据库管理员：数据库管理员（Database Adminitrator，简称DBA）负责全面管理和控制数据库系统 (是一个人)
数据库系统基本构成如下图所示
什么是元组，码，候选码，主码，外码，主属性，非主属性
#
- 元组：元组（tuple）是关系数据库中的基本概念，关系是一张表，表中的每行（即数据库中的每条记录）就是一个元组，每列就是一个属性。在二维表里，元组也成为行
- 码：码就是能唯一标识实体的属性，对应表中的列
- 候选码：若关系中的某一属性或属性组的值能唯一的标识一个元组，而其任何、子集都不能再标识，则称该属性组为候选码。例如：在学生实体中，“学号”是能唯一的区分学生实体的，同时又假设“姓名”、“班级”的属性组合足以区分学生实体，那么**{学号}和{姓名，班级}都是候选码**。
- 主码：主码也叫主键，主码是从候选码中选出来的。一个实体集中只能有一个主码，但可以有多个候选码
- 外码：外码也叫外键。如果一个关系中的一个属性是另外一个关系中的主码则这个属性为外码。
- 主属性 ： 候选码中出现过的属性称为主属性(这里强调单个）。比如关系 工人（工号，身份证号，姓名，性别，部门）. 显然工号和身份证号都能够唯一标示这个关系，所以都是候选码。工号、身份证号这两个属性就是主属性。如果主码是一个属性组，那么属性组中的属性都是主属性。
- 非主属性： 不包含在任何一个候选码中的属性称为非主属性。比如在关系——学生（学号，姓名，年龄，性别，班级）中，主码是“学号”，那么其他的“姓名”、“年龄”、“性别”、“班级”就都可以称为非主属性。
主键和外键有什么区别
#
- 主键(主码) ：主键用于唯一标识一个元组，不能有重复，不允许为空。一个表只能有一个主键。
- 外键(外码) ：外键用来和其他表建立联系用，外键是另一表的主键，外键是可以有重复的，可以是空值。一个表可以有多个外键
为什么不推荐使用外键与级联
#
对于外键和级联，阿里巴巴开发手册这样说道
【强制】不得使用外键与级联，一切外键概念必须在应用层解决。
说明: 以学生和成绩的关系为例，学生表中的 student_id 是主键，那么成绩表中的 student_id 则为外键。如果更新学生表中的 student_id，同时触发成绩表中的 student_id 更新，即为级联更新。
缺点： 外键与级联更新适用于单机低并发，不适合分布式、高并发集群; 级联更新是强阻塞，存在数据库更新风暴的风 险; 外键影响数据库的插入速度
为什么不要使用外键
增加了复杂性
a. 每次做DELETE 或者UPDATE都必须考虑外键约束，会导致开发的时候很痛苦, 测试数据极为不方便; b. 外键的主从关系是定的，假如那天需求有变化，数据库中的这个字段根本不需要和其他表有关联的话就会增加很多麻烦。
增加了额外操作
...
2022年12月19日 16:04 周一 转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!
JDK 命令行工具
#
这些命令在 JDK 安装目录下的 bin 目录下：
jps (JVM Process Status）: 类似 UNIX 的 ps 命令。用于查看所有 Java 进程的启动类、传入参数和 Java 虚拟机参数等信息；jstat（JVM Statistics Monitoring Tool）: 用于收集 HotSpot 虚拟机各方面的运行数据;jinfo (Configuration Info for Java) : Configuration Info for Java,显示虚拟机配置信息;jmap (Memory Map for Java) : 生成堆转储快照;jhat (JVM Heap Dump Browser) : 用于分析 heapdump 文件，它会建立一个 HTTP/HTML 服务器，让用户可以在浏览器上查看分析结果;jstack (Stack Trace for Java) : 生成虚拟机当前时刻的线程快照，线程快照就是当前虚拟机内每一条线程正在执行的方法堆栈的集合。
jps: 查看所有 Java 进程
#
jps(JVM Process Status) 命令类似 UNIX 的 ps 命令。
...
2022年12月19日 15:24 周一 转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!
本文由 JavaGuide 翻译自
https://www.baeldung.com/jvm-parametersopen in new window，并对文章进行了大量的完善补充。翻译不易，如需转载请注明出处，作者：
baeldungopen in new window 。
概述
#
本篇文章中，将掌握最常用的JVM参数配置。下面提到了一些概念，堆、方法区、垃圾回收等。
堆内存相关
#
Java 虚拟机所管理的内存中最大的一块，Java 堆是所有线程共享的一块内存区域，在虚拟机启动时创建。此内存区域的唯一目的就是存放对象实例，几乎 所有的对象实例以及数组都在这里分配内存。
显式指定堆内存-Xms和-Xmx
#
与性能相关的最常见实践之一是根据应用程序要求初始化堆内存。
如果我们需要指定最小和最大堆大小（推荐显示指定大小）：
-Xms<heap size>[unit]
-Xmx<heap size>[unit]
- heap size 表示要初始化内存的具体大小。
- unit 表示要初始化内存的单位。单位为***“ g”*** (GB) 、“ m”（MB）、“ k”（KB）。
举例，为JVM分配最小2GB和最大5GB的堆内存大小
显示新生代内存（Young Generation）
#
2022年12月18日 08:24 周日 转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!
概述
#
- Java中，JVM可以理解的代码就叫做字节码（即扩展名为.class的文件），它不面向任何特定的处理器，只面向虚拟机
- Java语言通过字节码的方式，在一定程度上解决了传统解释型语言执行效率低的问题，同时又保留了解释型语言可移植的特点。所以Java程序运行时效率极高，且由于字节码并不针对一种特定的机器。因此，Java程序无需重新编译便可在多种不通操作系统的计算机运行
- Clojure（Lisp 语言的一种方言）、Groovy、Scala 等语言都是运行在 Java 虚拟机之上。下图展示了不同的语言被不同的编译器编译成
.class文件最终运行在 Java 虚拟机之上。.class文件的二进制格式可以使用
WinHexopen in new window 查看。
.class文件是不同语言在Java虚拟机之间的重要桥梁，同时也是支持Java跨平台很重要的一个原因
Class文件结构总结
#
根据Java虚拟机规范，Class文件通过ClassFile定义，有点类似C语言的结构体
ClassFile的结构如下：
ClassFile {
u4 magic; //Class 文件的标志
u2 minor_version;//Class 的小版本号
u2 major_version;//Class 的大版本号
u2 constant_pool_count;//常量池的数量
cp_info constant_pool[constant_pool_count-1];//常量池
u2 access_flags;//Class 的访问标记
u2 this_class;//当前类
u2 super_class;//父类
u2 interfaces_count;//接口
u2 interfaces[interfaces_count];//一个类可以实现多个接口
u2 fields_count;//Class 文件的字段属性
field_info fields[fields_count];//一个类可以有多个字段
u2 methods_count;//Class 文件的方法数量
method_info methods[methods_count];//一个类可以有个多个方法
u2 attributes_count;//此类的属性表中的属性数
attribute_info attributes[attributes_count];//属性表集合
}
...
深度和高度是对应的；根节点所在层为1层