面试集锦

• https://blog.csdn.net/sinat_27143551/article/details/80216842
• https://www.cnblogs.com/li1992/articles/9217391.html
• 第一范式： 要求数据库中的每个字段都是不可再分的（原子性），比如地址这个字段可以拆分成省份、城市等字段，不满足第一范式
• 第二范式：
  • 满足第一范式
  • 所有的非主属性都必须 完全依赖（如果主键是两个字段，必须依赖这两个字段，不能部分依赖） 于主键
• 第三范式：
  • 满足第二范式（即是同时满足第一范式和第二范式）
  • 属性不依赖于其他非主属性
  • 例如：存在一个部门信息表，其中每个部门有部门编号（dept_id）、部门名称、部门简介等信息。那么在员工信息表中列出部门编号后就不能再将部门名称、部门简介等与部门有关的信息再加入员工信息表中。如果不存在部门信息表，则根据第三范式（3NF）也应该构建它，否则就会有大量的数据冗余。

mysql性能优化（索引，分库分表，升级硬盘SSD，主从部署，读写分离）

硬件优化

• 升级内存，带宽等
• 提升读写速度

索引优化

• https://chenjiabing666.github.io/2018/09/07/mysql%E7%B4%A2%E5%BC%95%E4%BC%98%E5%8C%96%E8%AF%A6%E8%A7%A3/

全值匹配

最佳左前缀，并且不能组合索引的中间字段

不要在索引列上做任何的操作（函数，计算等）

使用覆盖索引，少使用select *

mysql在使用不等于(!=或者<>)的时候无法使用导致全表扫描

在使用or的时候，前后两个都是索引的时候才会生效

is null和is not null 导致索引失效

like使用%开头的将会导致索引失效

字符串不加单引号导致索引失效

索引的优缺点

• 优点：
  • 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
  • 大大加快查询的速度
• 缺点：
  • 创建索引和维护索引要耗费时间，这种时间随着数据 量的增加而增加。
  • 索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
  • 当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

开启查询缓存

分库分表

• https://chenjiabing666.github.io/2018/10/07/Mycat/

• Mycat和sharding-jdbc

• 水平拆分和垂直拆分

重构查询方式

• 一个复杂查询能够解决就不要使用多个简单的查询
• 切分查询，将一个大的查询方式切分成多个小的查询，比如删除数据，可以尽可能的多次删除
• 分解关联查询：将关联查询分解成多个子查询，利用查询缓存

使用冗余的字段避免多表联合查询

禁用外键关联

事务的ACID

• 原子性： 一个事务中的所有操作要么同时完成要么同时失败
• 一致性： 无论事务是否执行成功，必须保证一个一致性的标准，比如转账，必须保证转账前后的总金额不变
• 隔离性： 事务与事务之间互不影响
• 持久性： 事务执行完成之后数据将会持久的保存到数据库中

事务的隔离级别

• READ UNCOMMITTED（未提交读） ：在READ UNCOMMITTED级别，事务中的修改，即使没有提交，对其他事务也都是可见的。事务可以读取未提交的数据，这也被称为 脏读 （Dirty Read）。这个级别会导致很多问题，从性能上来说，READ UNCOMMITTED不会比其他的级别好太多，但却缺乏其他级别的很多好处，除非真的有非常必要的理由，在实际应用中一般很少使用。
• READ COMMITTED（提交读） ：大多数数据库系统的默认隔离级别都是READ COMMITTED（但 MySQL 不是）。READ COMMITTED满足前面提到的隔离性的 简单定义：一个事务开始时，只能“看见”已经提交的事务所做的修改。换句话说，一个事务从开始直到提交之前，所做的任何修改对其他事务都是不可见的。这个级别有时候也叫做不可重复读（nonrepeatable read），因为两次执行同样的查询，可能会得到不一样的结果。
• REPEATABLE READ（可重复读） ：REPEATABLE READ解决了脏读的问题。该级别保证了在同一个事务中多次读取同样记录的结果是一致的。但是理论上，可重复读隔离级别还是无法解决另外一个 幻读 （Phantom Read）的问题。所谓幻读，指的是当某个事务在读取某个范围内的记录时，另外一个事务又在该范围内插入了新的记录，当之前的事务再次读取该范围的记录时，会产生幻行（Phantom Row）。InnoDB和XtraDB存储引擎通过多版本并发控制（MVCC，Multiversion Concurrency Control）解决了幻读的问题。本章稍后会做进一步的讨论。 可重复读是MySQL的默认事务隔离级别。
• SERIALIZABLE（可串行化） ：SERIALIZABLE是最高的隔离级别。它通过强制事务串行执行，避免了前面说的幻读的问题。简单来说，SERIALIZABLE会在读取的每一行数据上都加锁，所以可能导致大量的超时和锁争用的问题。实际应用中也很少用到这个隔离级别，只有在非常需要确保数据的一致性而且可以接受没有并发的情况下，才考虑采用该级别。

视图

• https://chenjiabing666.github.io/2018/03/28/SQL%E6%93%8D%E4%BD%9C%E5%85%AD/#%E8%A7%86%E5%9B%BE
• 一张虚拟的表，create view name as …..
• 简化查询，隐藏敏感信息

Mysql中的锁

• https://chenjiabing666.github.io/2018/06/26/MySQL%E4%B8%AD%E7%9A%84%E9%94%81/

Mysql中的explain的各个属性

• https://blog.csdn.net/qq_36120342/article/details/85333749

算法

算法的稳定性

• https://www.cnblogs.com/zhaoshuai1215/p/3448154.html
• 两个相同的数，经过一趟 排序 前后的位置保持不变就是稳定排序，反之不稳定

排序算法的稳定性

• https://www.cnblogs.com/xiaochun126/p/5086037.html
• https://blog.csdn.net/stand1210/article/details/52403569

• https://www.cnblogs.com/zhaoshuai1215/p/3448154.html

• 不稳定的算法

  • 选择排序：O(nlogn)
  • 快速排序：平均时间复杂度为O(nlogn)，最坏的情况时间复杂度为O(n^2）
    • 最坏的情况：已经排好序或者倒序的
  • 希尔排序：希尔排序的时间复杂度与增量(即，步长gap)的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)，而Hibbard增量的希尔排序的时间复杂度为O(N3/2)。
  • 堆排序：O(nlogn)
• 稳定的算法：
  • 冒泡排序：O(n^2)
  • 归并排序：O(nlogn)
  • 插入排序：O(n^2)

排序算法

public static void main(String[] args)throws CloneNotSupportedException {
		int[] arrays= {1,3,2,7,5};
		insertSort(arrays);
		for (Integer a : arrays) {
			System.out.print(a+"\t");
		}
	}

	/**
	 * 冒泡排序
	 * @param arrays
	 */
	public static void bubbleSort(int[] arrays){
		// 外层循环
		for (int i = 0; i < arrays.length - 1; i++) {
			for (int j = arrays.length - 1; j > i; j--) {
				if (arrays[j] < arrays[j - 1]) {
					int c = arrays[j];
					arrays[j] = arrays[j - 1];
					arrays[j - 1] = c;
				}
			}
		}
	}
	
	
	/**
	 * 选择排序
	 * 1、先假设第一个元素是最小的，依次和后面的元素比较，第一轮之后，第一个元素就是最小的，依次经过n轮之后，前n个元素是有序的（由小到大排序）
	 * @param arrays
	 */
	public static void changeSort(int[] arrays){
		for (int i = 0; i < arrays.length-1; i++) {
			int minIndex=i;  //假设第一个元素是最小的
			for(int j=i+1;j<arrays.length;j++) {
				if (arrays[minIndex]>arrays[j]) {
					minIndex=j;
				}
			}
			
			//经过一轮之后，minIndex的值改变了，那么表示出之前定的最小值改变了，此时就需要交换
			if (minIndex!=i) { 
				int c = arrays[minIndex];
				arrays[minIndex] = arrays[i];
				arrays[i] = c;
			}
		}
	}
	
	/**
	 * 插入排序
	 * @param arrays
	 */
	public static void insertSort(int[] arrays){
		//从第二个开始，假设第一个已经是排好序的
		for (int i = 1; i < arrays.length; i++) {
			int target=arrays[i];  //待插入的
			int j=i;
			
			//如果待插入的数字比前面的数字（已经是有序的）小，那么前面的元素就后移，等待这个元素插入
			while(j>0&⌖<arrays[j-1]) {
				arrays[j]=arrays[j-1];
				j--;
			}
			
			//移动完之后，当前的j的位置就是待插入的
			arrays[j]=target;
		}
	}

二分查找算法

二叉树相关概念

• 二叉树
  • 每个节点最多有两个子树的结构，通常子树被称作“左子树”和“右子树” 。
• 满二叉树
  • http://www.cnblogs.com/K-artorias/p/8340182.html
  • 叶子节点只出现在最后一层
• 完全二叉树
  • http://www.cnblogs.com/K-artorias/p/8340182.html
  • 叶子节点只能出现在最后一层或者倒数第二层，并且如果存在叶子节点，那么只能出现在该层最左边的若干位置
  • 满二叉树是特殊的完全二叉树
• 二叉查找树
  • 满足二叉树的定义
  • 每个节点的键都大于左子树中任意节点的键而小于右子树中任意节点的键。
• 平衡二叉树
  • 满足二叉查找树的定义
  • 树的左右两边的层级数相差不会大于1;
• 红黑树
  • https://www.cnblogs.com/skywang12345/p/3245399.html
  • 特点：
    • 根节点是黑色的
    • 叶子节点必须是黑色的
    • 节点的颜色要么是黑色，要么是红色
    • 如果一个节点是红色的，则它的子节点必须是黑色的。
    • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

并发编程

定义

1. 线程：是进程的一个实体，是cpu调度和分派的基本单位，是比进程更小的可以独立运行的基本单位。
2. 进程：具有一定独立功能的程序关于某个数据集合上的一次运行活动，是操作系统进行资源分配和调度的一个独 立单位。

其他

• 继承Thread和实现Runable接口，第二种方式可以实现多个线程共享一个Runable
• 多线程的三大特性：原子性，可见性，有序性
• 线程同步代码块（ synchronized）、轻量级锁（volatile）、Lock
• volatile关键字的作用
  • https://www.cnblogs.com/monkeysayhi/p/7654460.html
  • 保证了 可见性 和 有序性 ，不能保证 原子性
• ThreadLocal的原理
  • https://www.cnblogs.com/dolphin0520/p/3920407.html
• 面试题：
  • https://www.cnblogs.com/kexianting/p/8566318.html
  • https://www.cnblogs.com/Jansens520/p/8624708.html
• 如何终止线程？
  • 调用stop方法，已经废弃，会立刻杀死线程，无论线程执行到哪里
  • 设置一个volatile标志变量，在run方法中手动退出即可（return）。
  • 线程自己执行完任务，自动退出。

如何确保高并发安全性

• 链接： https://blog.csdn.net/andong154564667/article/details/82153104

1、浏览器层或者APP层限制同一个用户或者IP的操作每x秒只能执行一次

2、浏览器或者APP做页面缓存，

3、图片和短信验证码的验证也能有效的限流

4、服务器层的限流，比如令牌桶算法，保证每秒限制多少个请求

5、数据的缓存，可以将一些热点数据存放到 redis 中，防止击穿db层

6、使用消息队列，既能保证任务的异步执行，也能达到限流的作用。

7、数据库层比如读写分离，分库分表等都能实现一定的优化。

8、服务器做负载均衡，使用分布式

消息队列

• 路由，路由键（routineKey），队列
• rabbitMq的四种路由：direct，fanout，topic，header
• https://segmentfault.com/a/1190000015301449?utm_source=tag-newest
• 消息队列的优势：解耦、异步、流量削峰
• 消息队列的缺点 ：
  • 系统的复杂性提高
  • 系统的可用性降低，一旦消息队列挂掉，系统也会随之瘫痪
• 消息队列的使用场景？
  • https://blog.csdn.net/jasonhui512/article/details/53231566

• 如何保证消息可靠性投递？

  • 生产者丢弄丢数据：只需要在生产者的开启事务，一旦消息投递失败，事务回滚即可，另外一种模式是confirm模式，一种异步的处理模式，一旦消息被成功投递到队列之后会异步发送一个ACK的消息，否则发送一个NACK的消息
  • 消息队列弄丢数据：开启消息队列持久化和消息确认机制，可以在消息持久化之后发送一个ACK消息给生产者，如果持久化之前没有接收到
  • 消费者弄丢数据：采用自动确认的模式即可，如果消费者成功消费了数据，那么发送一个ACK消息，否则发送一个NACK消息
• 如何保证消息的顺序性

• 如何保证消息不被重复消费？

  • 开启自动确认机制，一旦消息被成功消费，那么就发送一个ACK消息，否则发送一个NACK
• 如何保证消息的高可用？

Tomcat性能调优

• https://blog.csdn.net/u010195563/article/details/80966025，https://www.cnblogs.com/zhuawang/p/5213192.html，https://blog.csdn.net/lz13502800153/article/details/80089770

• 内存优化：指定tomcat的运行内存

• 线程优化：
• IO优化，使用NIO，在tomcat8之后使用的都是NIO，可以使用apr，这个是在操作系统级别提升并发的性能
• APR：
  • https://blog.csdn.net/goldenfish1919/article/details/78859620

JDK

HashMap

• HashMap的底层原理
  • https://blog.csdn.net/hefenglian/article/details/79763634
• 初始大小为16，负载因子默认为0.75，也就是如果元素个数大于16*0.75=12，那么将会扩容（resize）一倍（32），扩容的过程是非常消耗性能，因此如果清楚知道元素的个数，那么需要创建的时候就指定，避免中途扩容。
• JDK1.7是使用位桶(数组)+链表的方式实现的
  • 
  • 添加元素
    • 通过计算key的hash值找到在数组中的位置，如果此时数组位置为空，直接添加一个元素（Entry）
    • 如果此时数组的位置不为空，通过的equals方法查找当前链表中是否有相同的，如果没有，直接插入到链表的末尾，否则覆盖之前的元素。
  • get
    • 通过计算key的hash值找到数组中的位置
    • 通过key的equals方法在链表中查找和当前key的相等的，如果存在返回这个Entry即可。
  • 问题：
    • 链表的查询很慢，如果有成千上万个元素，那么此时的性能很低。
• JDK1.8使用的是位桶+链表+红黑树，当 位桶中的链表元素 的个数超过阀值8，那个链表将会转换为红黑树。
  • 链表的时候和JDK1.7是一致的，如果是红黑树，那么就是红黑树的遍历

数组和链表的区别

• 数组：
  • 初始化需要指定大小
  • 查询性能高
  • 添加、删除需要前后移动元素，性能低
• 链表：
  • 动态增长，不需要提前指定个数
  • 查询性能较低
  • 添加、删除、修改性能较高

ArrayList

• 初始化默认的容量为 10 ，当数组中的元素大于当前的默认容量了，那么调用 grow 方法，扩容 1.5倍 （ Arrays.copyOf ）
• ArrayList的扩容： https://blog.csdn.net/zymx14/article/details/78324464

类加载器

• https://www.cnblogs.com/gdpuzxs/p/7044963.html

• 类加载器的类型？

  • 根类加载器(Bootstrap) –C++写的 ，看不到源码 （BootStrapClassLoader）
  • 扩展类加载器（Extension） –加载位置 ： jre\lib\ext 中 (ExtStrapClassLoader)
  • 系统(应用)类加载器(System\App) –加载位置 ： classpath 中 (AppClassLoader)
  • 自定义加载器(必须继承 ClassLoader)
• 双亲委派机制
• 自定义类加载器，继承ClassLoader

HTTP

网络七层协议

• https://baike.baidu.com/item/%E7%BD%91%E7%BB%9C%E4%B8%83%E5%B1%82%E5%8D%8F%E8%AE%AE/6056879?fr=aladdin

• 应用层：FTP、HTTP、TELNET、SMTP、DNS等协议。

• 表示层
• 会话层
• 传输层：TCP协议与UDP协议。
• 网络层：IP协议、ICMP协议、ARP协议、RARP协议和BOOTP协议。
• 数据链路层
• 物理层

TCP和UDP

• https://www.cnblogs.com/xiohao/p/4439164.html

三次握手

• https://www.cnblogs.com/xiohao/p/4439164.html

四次挥手

长连接

• https://www.cnblogs.com/gotodsp/p/6366163.html

Spring

Spring中的BeanFactory和FactoryBean的区别

• http://www.cnblogs.com/aspirant/p/9082858.html

FactoryBean的作用

• https://www.cnblogs.com/davidwang456/p/3688250.html
• 一般情况下，Spring通过反射机制利用bean的class属性指定实现类来实例化bean 。在某些情况下，实例化bean过程比较复杂，如果按照传统的方式，则需要在 中提供大量的配置信息，配置方式的灵活性是受限的，这时采用编码的方式可能会得到一个简单的方案。Spring为此提供了一个org.Springframework.bean.factory.FactoryBean的工厂类接口，用户可以通过实现该接口定制实例化bean的逻辑。FactoryBean接口对于Spring框架来说占有重要的地位，Spring 自身就提供了70多个FactoryBean的实现。它们隐藏了实例化一些复杂bean的细节，给上层应用带来了便利。从Spring 3.0 开始， FactoryBean开始支持泛型，即接口声明改为FactoryBean 。

/**
 * 创建一个UserFactoryBean，实现FactoryBean，用来创建一个User对象
 * InitializingBean：初始化
 * ApplicationContextAware：设置ApplicationContext
 */
@Component
public class UserFactoryBeanimplements FactoryBean<User>,InitializingBean,ApplicationContextAware{

    //User对象
    private User user;
    //ApplicationContext对象，可以获取指定的Bean
    private ApplicationContext applicationContext;

    /**
     * 返回一个User
     */
    @Override
    public User getObject()throws Exception {
        return user;
    }

    @Override
    public Class<?> getObjectType() {
        return null;
    }

    @Override
    public void afterPropertiesSet()throws Exception {
        user=new User();
        user.setName("陈加兵");
    }

    @Override
    public void setApplicationContext(ApplicationContext applicationContext)throws BeansException {
        this.applicationContext=applicationContext;
    }
}