前言

整理了一下记录在手机中的技术知识点，包含JAVA、MYSQL、数据结构等，自用笔记，放博客上备份以备不时之需，如若有人发现错误还请指出。

由于太长，分成两篇记录,笔记二地址： 自自技术笔记（二）

红黑树笔记

红黑树

红黑树其实就是平衡二叉树，该规则可保证每个节点都是平衡的，不会出现单个节点过长的情况

红黑树的作用，红黑树是一种平衡二叉树，不会退化为链表，多用于搜索查找，时间复杂度logn,也就是树的深度，倍数增长，红黑树是局部平衡二叉树

普通二叉树的局限性是子节点都比父节点小因此全排在右，会退化成链表

红黑树4个性质

• 1.节点是红色或者黑色
• 2.红色节点不会连在一起（子父节点不能同为红色）
• 3.根节点都是黑色
• 4.空的叶子节点都是黑色（既无子节点）

红黑树有三种变化规则
1.红变黑 2.黑变红 3.旋转

红黑树的操作规则

• 0.所有变换后的节点不可违背红黑树的基本性质，既当插入节点后规则不符合红黑树基本性质时依次尝试，变色、左旋、右旋
• 1.所有插入的节点默认为红色
• 2.变换颜色条件，当子节点和父节点以及父节点的兄弟节点都是红色时需要变换颜色，颜色变换规则为将父节点以及父节点的兄弟节点变换成红色，将祖节点变换为红色
• 3.左旋条件，当前节点的父节点是红色，叔叔节点是黑色，且当前节点是父节点的右子树时，旋转父节点和祖节点
• 4.右旋条件，当前父节点是红色，叔叔节点是黑色，且当前节点是左子树时右旋转，与左旋不同的是右旋转操作是旋转祖节点和祖父节点

右旋有3步

• 1.把父节点变为黑色
• 2.把祖节点变为红色
• 3.把以祖节点为旋转点旋转（不同于左旋以父节点为旋转点）

mysql笔记

Mysql的五种索引

• 1.主键索引 （不可以有空，唯一的）
• 2.普通索引
• 3.唯一索引 （可以有空）
• 4.联合索引
• 5.全文索引 （对文本内容分词搜索）
• 6.哈西索引 （myISAM和InnoDB不支持）

联合索引按照最左匹配原则

Mysql聚簇(cu)索引
聚簇索引是一种数据存储方式，innoDB使用b+tree存储索引和数据行，当有聚簇索引时，数据是存储在索引的叶子节点中，一张表只能有一个聚簇索引，聚簇索引一般是自增的id主键

索引的条件顺序可以打乱，mysql优化器会自动调整顺序

聚合索引是物理地址连续存放的索引

索引场景

• 1.使用条件1和3，条件1会使用索引，条件3不会使用索引
• 2.between 属于范围查询，因此不走索引
• 3.in不会使用索引 ，可使用not exists，in属于范围查询
• 4.mysql like 百分号在后会走索引

mysql四个隔离级别

• 未提交读(未提交事务数据可读)
• 已提交读（只可看见已提交事务数据）
• 可重复读（默认） (事务A在读到一条数据之后，此时事务B对该数据进行了修改并提交，那么事务A再读该数据，读到的还是原来的内容)
• 可序列化(队列有序)

幻读，多个人员同时修改一个数据时，后操作的人员将就旧数据修改后覆盖了先操作人员修改的数据称之为幻读

mysql锁
mysql行锁 走索引 for update 不走索引则表锁
for update为排他锁 不可读 lock in share.mode为共享锁其他事务可读

msql binary log原理
binlog保存数据为事务日志和二进制日志，二进制日志索引文件后缀为.index，二进制日志文件为.00000*，记录了所有的ddl dml操作

其内容分别为事务提交前数据和事务提交后数据，binlog除了可以用来回滚事务外还可以做主从同步，读写分离

Mysql优化

• 1.合理的表设计
• 2.水平垂直分割表
• 3.读写分离
• 4.查看慢查询sql show variables like “long_query_time”
• 5.适当添加索引
• 6.定时整理碎片数据
• 7.复杂操作可以使用存储过程

msql主从复制原理

通过binlog异步同步数据，为保证复制准确，mysql在master.info和relay-log.info中保存了同步日志，主从同步有两个线程
1.io线程，监听主库数据是否发生改变，当发生修改时，将异步复制到从库中的relay log中
2. sql线程，从中继日志中读取主库修改的数据同步到从库中来完成数据同步操作。

三种复制方式
二进制binlog的格式有三种：
statement：基于sql的binlog，每条修改数据的sql都会保存到binlog里。
row：基于行级别，记录每一行数据的变化，也就是将每一行数据的变化都记录到binlog里，记录非常详细。
mixed：混合statement和row模式。
阿里的canal框架也可以实现主从复制

Msql分库分表后按时间查询思路
垂直拆分，新建一张数据索引表，保存了主表id和该表的时间数据，查询时先按时间来索引表查id，再根据id查关联数据，如果索引表也变得非常庞大，可以单开一个库按月分表，查询时先按月份找到表，再按时间从表中筛选，最后根据id查到想要的数据

Mysql保证持久化
Undo log记录修改前的数据，用于回滚
Redo log记录事物提交修改后的数据，用于数据恢复

Mysql优化笔记
查看开关
show variables like “%slow_query_log%”
打开开关，1秒超时
set global slow_query_log = on;
set global long_query_time = 1;
查看慢sql条数
show status like “%slow_queries%”
慢sql日志文件在 /data/mysql/localhost-slow.log

Spring事务传播级别

• PROPAGATION_REQUIRED:支持当前事务，假设当前没有事务。就新建一个事务。
• ROPAGATION_SUPPORTS:支持当前事务，假设当前没有事务，就以非事务方式运行。
• ROPAGATION_MANDATORY:支持当前事务，假设当前没有事务，就抛出异常。
• PROPAGATION_REQUIRES_NEW:新建事务，假设当前存在事务。把当前事务挂起。
• PROPAGATION_NOT_SUPPORTED:以非事务方式运行操作。假设当前存在事务，就把当前事务挂起。
• PROPAGATION_NEVER:以非事务方式运行，假设当前存在事务，则抛出异常。
• ROPAGATION_NESTED:如果当前存在事务，则在嵌套事务内执行。如果当前没有事务，则进行与PROPAGATION_REQUIRED类似的操作。

spring生命周期关键点:

执行initantiationAwareBeanPostProcessor的postProcessPropertyValue方法后开始 执行bean构造器 - 为bean注入属性 - beanAware的setBeanName setBeanFactoru - 调用 bean init-method 销毁时执行destory 并调用配置的destroy-method

分布式锁笔记
分布式锁有如下几种
1.使用redis做分布式锁
2.使用mysql索引锁
3.使用乐观锁
Redis锁的加锁和解锁需要两步操作，为保证原子性，需要用lua脚本一次执行，一般使用公平锁，加速队列，避免出现大量线程竞争不到锁而超时的问题

当redis为分布式环境时需要使用redlock算法，避免重复获取锁
Redlock基本原理如下
1.快速失败时间，客户端使用相同key和随机数尝试获取锁时，为每个锁设置快速失败时间
2.计算获取锁的时间，判断获取锁消耗时间小于锁的存活时间，且一半以上的master节点获得锁才算锁定成功
3.获取成功的锁不足一半以上时需要释放所有节点锁
4.加锁失败时如释放锁时出现问题需要等待所有锁自动失效
5.获取锁成功后，执行任务的时间窗口是锁的存活时间减去锁的消耗时间

JVM相关

jvm类的加载方式

• 1.本地class
• 2.网络加载 java.net.URIClassLoader可以加载url指定类
• 3.jar zip等压缩文件，自动解析
• 4.从java源代码文件动态编译为class

类加载生命周期
加载～验证～准备～解析～初始化～使用～卸载

jvm三种预定义类型类加载器

• 1.启动类加载器bootstrap 本地代码实现的类加载器，负责两java home/lib下的类库加载到内存中，开发者无法直接使用
• 2.标准扩展类加载器Extension 负责将java home/lib/ext.或者系统变量java.ext.dir指定为的的类库加载到内存中，开发者可以直接使用
• 3.系统类加载器system 负责classpath中指定类库的加载，开发者可直接使用
• 4.自定义类加载器:java.lang.ClassLoader

类加载双亲委派机制

在某个特定的类加载器接到加载请求时先将加载任务委托给父类，依次递归，如果父类不能完成才自己去加载，类加载器均继承自ClassLoader抽象类。

jvm内存模型

JVM内存空间分为五部分，分别是：方法区、堆、Java虚拟机栈、本地方法栈、程序计数器，方法区主要用来存放类信息、类的静态变量、常量、运行时常量池等，方法区的大小是可以动态扩展的，

堆主要存放的是数组、类的实例对象、字符串常量池等。Java虚拟机栈是描述JAVA方法运行过程的内存模型，Java虚拟机栈会为每一个即将执行的方法创建一个叫做“栈帧”的区域，该区域用来存储该方法运行时需要的一些信息，

包括：局部变量表、操作数栈、动态链接、方法返回地址等。比如我们方法执行过程中需要创建变量时，就会将局部变量插入到局部变量表中，局部变量的运算、传递等在操作数栈中进行，

当方法执行结束后，这个方法对应的栈帧将出栈，并释放内存空间。栈中会发生的两种异常，StackOverFlowError和OutOfMemoryError,StackOverFlowError表示当前线程申请的栈超过了事先定好的栈的最大深度，

但内存空间可能还有很多。 而OutOfMemoryError是指当线程申请栈时发现栈已经满了，而且内存也全都用光了。

本地方法栈结构上和Java虚拟机栈一样，只不过Java虚拟机栈是运行Java方法的区域，而本地方法栈是运行本地方法的内存模型。运行本地方法时也会创建栈帧，

同样栈帧里也有局部变量表、操作数栈、动态链接和方法返回地址等，在本地方法执行结束后栈帧也会出栈并释放内存资源，也会发生OutOfMemoryError。

最后是程序计数器，程序计数器是一个比较小的内存空间，用来记录当前线程正在执行的那一条字节码指令的地址。如果当前线程正在执行的是本地方法，那么此时程序计数器为空。

程序计数器有两个作用：

• 1、字节码解释器通过改变程序计数器来一次读取指令，从而实现代码的流程控制，比如我们常见的顺序、循环、选择、异常处理等。

• 2、在多线程的情况下，程序计数器用来记录当前线程执行的位置，

当线程切换回来的时候仍然可以知道该线程上次执行到了哪里。而且程序计数器是唯一一个不会出现OutOfMeroryError的内存区域。

方法区和堆都是线程共享的，在JVM启动时创建，在JVM停止时销毁，而Java虚拟机栈、本地方法栈、程序计数器是线程私有的，随线程的创建而创建，随线程的结束而死亡。

JVM三大性能调优参数：-Xms –Xmx –Xss

-Xms –Xmx是对堆的性能调优参数，一般两个设置是一样的，如果不一样，当Heap不够用，会发生内存抖动。一般都调大这两个参数，并且两个大小一样。

-Xss是对每一个线程栈的性能调优参数,影响堆栈调用的深度

Jvm回收判断

1.引用计数法，缺点是当循环引用时会内存溢出

2.可达性分析法，存储了对象的引用链接，并向下搜索，当一个对象到root节点没有任何引用链接时，则证明此对象是可以被回收的。以下对象会被认为是root对象：

• 栈内存中引用的对象
• 方法区中静态引用和常量引用指向的对象
• 被启动类（bootstrap加载器）加载的类和创建的对象
• Native方法中JNI引用的对象。

Jvm 3个回收算法

• 1.标记清除
• 2.复制算法
• 3.标记复制算法，(整合1和2)

Jvm调优工具

• 1.jconsole，jdk1.5自带，用于对JVM中内存，线程和类等的监控，是一个基于JMX（java management extensions）的GUI性能监测工具

• 2.VisualVM，可监控cpu、内存、类、线程，新生代，老年代等内存变化

• 3.Mat eclipse的一个第三方调优工具，它可以帮助我们查找内存泄漏和减少内存消耗。使用内存分析工具从众多的对象中进行分析，快速的计算出在内存中对象的占用大小

JAVA多线程笔记

join的作用
join的作用是等待调用该方法的线程结束后才往下执行，如主线程调用t1.join（） 那么t1 执行完后才继续执行后面代码

java线程锁

• 1.Synchronized，它就是一个：非公平，悲观，独享，互斥，可重入的重量级锁
• 2.ReentrantLock，它是一个：默认非公平但可实现公平的，悲观，独享，互斥，可重入，重量级锁，
• reentrantlock可设置超时，不会死锁，可中断
• 3.ReentrantReadWriteLocK，它是一个，默认非公平但可实现公平的，悲观，写独享，读共享，读写，可重入，重量级锁。

以下是各种概念上锁的分类
1.悲观锁，乐观锁
2.独占锁，互斥锁
3.可重入，不可重入
4.重量级，轻量级
5.公平锁，非公平锁

各种杂项锁的概念分类
自旋锁 ，自旋锁的其他种类，阻塞锁，可重入锁 ，读写锁，互斥锁，悲观锁，乐观锁，公平锁，偏向锁， 对象锁，线程锁，锁粗化，锁消除，轻量级锁，重量级锁， 信号量，独享锁，共享锁，分段锁

java实现线程的几种方式

• 1.thread
• 2.runnable
• 3.线程池
• 4.timer
• 5.FutureTask 带返回结果的线程

4种线程池

• 1.newCachedThreadPool可缓存线程池，无限制扩展，无可回收时创建新的线程
• 2.newFixedThreadPool 固定数量大小的线程池，当任务超过线程数量时加入队列等待
• 3.newSingleThreadExecutor单线程化线程池，将所有线程按指定顺序如先进先出，先进后出的顺序执行
• 4.newScheduleThreadPool 定长的线程池，支持定时周期性的任务执行

线程池的4种拒绝策略

• 1.discardPolicy 直接丢弃
• 2.discardOldestPolicy丢弃队列中最老的任务
• 3.abortPolicy抛异常
• 4.callerRunsPolicy将任务分给调用线程来执行,但调用者线程性能会下降

默认策略抛异常

线程池的4种队列:

• 1.ArrayBlockingQuene 数组结构，有序，先进先出（FIFO）
• 2.LinkedBlickingQuene 链表结构，先进先出，吞吐量高于数组结构
• 3.SynchronousQuene无缓冲队列，当第一个任务添加进该队列后会一直处于阻塞状态，直到有线程将调用take方法取走元素，该队列不保存元素，添加进来的元素会直接被消费方取走
  支持公平，非公平策略，非公平策略有可能取不到元素
• 4.priorityBlockingQuene具有优先级的无阻塞队列，可自定义竞争算法

join 让父线程等待子线程结束后才运行，join可指定等待时间

java IO流
1.字节流 不缓存到缓冲区，主要操作类inputStream outputStream
2.字符流 会缓存到缓冲区，当输出内容到文件时即使不flush文件中也依旧有内容，且一个字符占两个字节，默认编码unicode 主要操作类为 Reader Writer

线程池原理
workset线程集合加队列
配置说明:
keepAlivetime排队时长，该参数只在当然线程求大于corePoolSize时有用

maxinumPoolSize最大线程执行数量，超过核心线程会自动创建非核心线程，前提是不超过maxinumPoolSize

线程池总体流程:
当用户提交线程时创建新线程执行直到线程数量等于corePoolSize，多出来的任务则加入队列，当队列满了且当前线程数小于maxinumPoolSize时创建新的线程执行任务，当队列满了且线程池执行数量超过设定上限则执行配置的拒绝策略。