Spring AOP ，SpringMVC ，这两个应该是国内面试必问题，网上有很多答案，其实背背就可以。但今天笔者带大家一起深入浅出源码，看看他的原理。以期让印象更加深刻，面试的时候游刃有余。

Spring AOP 原理

简单说说 AOP 的设计：

1. 每个 Bean 都会被 JDK 或者 Cglib 代理。取决于是否有接口。
2. 每个 Bean 会有多个“方法拦截器”。注意：拦截器分为两层，外层由 Spring 内核控制流程，内层拦截器是用户设置，也就是 AOP。
3. 当代理方法被调用时，先经过外层拦截器，外层拦截器根据方法的各种信息判断该方法应该执行哪些“内层拦截器”。内层拦截器的设计就是职责连的设计。

是不是贼简单。事实上，楼主之前已经写过一个简单的例子，地址：使用 Cglib 实现多重代理

看完之后更简单。

可以将 AOP 分成 2 个部分来扯，哦，不，来分析。。。
第一：代理的创建；
第二：代理的调用。

注意：我们尽量少贴代码，尽量用文字叙述，因为面试的时候，也是文字叙述，不可能让你把代码翻出来的。。。所以，这里需要保持一定的简洁，想知道细节，看 interface 21 源码，想知道的更细，看 Spring Framework 最新的 master 分支代码。

代码位置：com.interface21.aop 包下。

开始分析（扯）：

1. 代理的创建（按步骤）：

• 首先，需要创建代理工厂，代理工厂需要 3 个重要的信息：拦截器数组，目标对象接口数组，目标对象。
• 创建代理工厂时，默认会在拦截器数组尾部再增加一个默认拦截器 —— 用于最终的调用目标方法。
• 当调用 getProxy 方法的时候，会根据接口数量大余 0 条件返回一个代理对象（JDK or Cglib）。
• 注意：创建代理对象时，同时会创建一个外层拦截器，这个拦截器就是 Spring 内核的拦截器。用于控制整个 AOP 的流程。

2. 代理的调用

• 当对代理对象进行调用时，就会触发外层拦截器。
• 外层拦截器根据代理配置信息，创建内层拦截器链。创建的过程中，会根据表达式判断当前拦截是否匹配这个拦截器。而这个拦截器链设计模式就是职责链模式。
• 当整个链条执行到最后时，就会触发创建代理时那个尾部的默认拦截器，从而调用目标方法。最后返回。

题外话：Spring 的事务也就是个拦截器。

来张不是很标准的 UML 图：

关于调用过程，来张流程图：

大概就是这样子，具体更多的细节，请看源码，如果还不是很明白的话，请咨询本人，本人不确定这个图是否画的很浅显易懂 —— 最起码萌新看得懂才能称之为浅显易懂。

Spring MVC 过程

先来张图：

代码位置：com.interface21.web.servlet.DispatcherServlet#doService

（没错，就是 Spring 1.0 的代码，大道至简，现在的 Spring 经过 15 年的发展，已经太过臃肿，从学习角度来说，interface 21 是最好的代码，不接受反驳）

代码如下：

1. 设置属性

1
2
3
4
5
6
7
8
9

复制代码// 1. 设置属性
// Make web application context available
request.setAttribute(WEB_APPLICATION_CONTEXT_ATTRIBUTE, getWebApplicationContext());

// Make locale resolver available
request.setAttribute(LOCALE_RESOLVER_ATTRIBUTE, this.localeResolver);

// Make theme resolver available
request.setAttribute(THEME_RESOLVER_ATTRIBUTE, this.themeResolver);

2. 根据 Request 请求的 URL 得到对应的 handler 执行链，其实就是拦截器和 Controller 代理对象。

1
2

复制代码// 2. 找 handler 返回执行链
HandlerExecutionChain mappedHandler = getHandler(request);

3. 得到 handler 的适配器

1
2
3

复制代码// This will throw an exception if no adapter is found
// 3. 返回 handler 的适配器
HandlerAdapter ha = getHandlerAdapter(mappedHandler.getHandler());

关于这个适配器，作用到底是啥呢？HandlerAdapter 注释写到：This interface is not intended for application developers. It is available to handlers who want to develop their own web workflow.
译：此接口不适用于应用程序开发人员。它适用于想要开发自己的Web工作流程的处理程序。

也就说说，如果你想要在处理 handler 之前做一些操作的话，可能需要这个，即适配一下这个 handler。例如 Spring 的测试程序做的那样：

1
2
3
4
5
6

复制代码public ModelAndView handle(HttpServletRequest request, HttpServletResponse response, Object delegate)
		    throws IOException, ServletException {
                      // 你可能需要 doSomething.......
			((MyHandler) delegate).doSomething(request);
			return null;
		}

4. 循环执行 handler 的 pre 拦截器

1
2
3
4
5
6
7
8

复制代码// 4. 循环执行 handler 的 pre 拦截器
for (int i = 0; i < mappedHandler.getInterceptors().length; i++) {
	HandlerInterceptor interceptor = mappedHandler.getInterceptors()[i];
	// pre 拦截器
	if (!interceptor.preHandle(request, response, mappedHandler.getHandler())) {
		return;
	}
}

这个没什么好讲的吧？

5. 执行真正的 handler，并返回 ModelAndView(Handler 是个代理对象，可能会执行 AOP )

1
2

复制代码// 5. 执行真正的 handler，并返回  ModelAndView(Handler 是个代理对象，可能会执行 AOP )
ModelAndView mv = ha.handle(request, response, mappedHandler.getHandler());

6. 循环执行 handler 的 post 拦截器

1
2
3
4
5
6

复制代码// 6. 循环执行 handler 的 post 拦截器
for (int i = mappedHandler.getInterceptors().length - 1; i >=0 ; i--) {
	HandlerInterceptor interceptor = mappedHandler.getInterceptors()[i];
	// post 拦截器
	interceptor.postHandle(request, response, mappedHandler.getHandler());
}

7. 根据 ModelAndView 信息得到 View 实例

1
2
3
4
5
6

复制代码View view = null;
if (mv.isReference()) {
	// We need to resolve this view name
	// 7. 根据 ModelAndView 信息得到 View 实例
	view = this.viewResolver.resolveViewName(mv.getViewName(), locale);
}

8. 渲染 View 返回

1
2

复制代码// 8. 渲染 View 返回
view.render(mv.getModel(), request, response);

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

实战前言
RabbitMQ 作为目前应用相当广泛的消息中间件，在企业级应用、微服务应用中充当着重要的角色。特别是在一些典型的应用场景以及业务模块中具有重要的作用，比如业务服务模块解耦、异步通信、高并发限流、超时业务、数据延迟处理等。

RabbitMQ 官网拜读
首先，让我们先拜读 RabbitMQ 官网的技术开发手册以及相关的 Features，感兴趣的朋友可以耐心的阅读其中的相关介绍，相信会有一定的收获，地址可见：www.rabbitmq.com/getstarted.…

在阅读该手册过程中，我们可以得知 RabbitMQ 其实核心就是围绕 “消息模型” 来展开的，其中就包括了组成消息模型的相关组件：生产者，消费者，队列，交换机，路由，消息等！而我们在实战应用中，实际上也是紧紧围绕着 “消息模型” 来展开撸码的！

下面，我就介绍一下这一消息模型的演变历程，当然，这一历程在 RabbitMQ 官网也是可以窥览得到的！

上面几个图就已经概述了几个要点，而且，这几个要点的含义可以说是字如其名！

1. 生产者：发送消息的程序
2. 消费者：监听接收消费消息的程序
3. 消息：一串二进制数据流
4. 队列：消息的暂存区/存储区
5. 交换机：消息的中转站，用于接收分发消息。其中有 fanout、direct、topic、headers 四种
6. 路由：相当于密钥/第三者，与交换机绑定即可路由消息到指定的队列！

正如上图所展示的消息模型的演变，接下来我们将以代码的形式实战各种典型的业务场景！

SpringBoot 整合 RabbitMQ 实战

工欲善其事，必先利其器。我们首先需要借助 IDEA 的 Spring Initializr 用 Maven 构建一个 SpringBoot 的项目，并引入 RabbitMQ、Mybatis、Log4j 等第三方框架的依赖。搭建完成之后，可以简单的写个 RabbitMQController 测试一下项目是否搭建是否成功（可以暂时用单模块方式构建）

紧接着，我们进入实战的核心阶段，在项目或者服务中使用 RabbitMQ，其实无非是有几个核心要点要牢牢把握住，这几个核心要点在撸码过程中需要“时刻的游荡在自己的脑海里”，其中包括：

1. 我要发送的消息是什么
2. 我应该需要创建什么样的消息模型：DirectExchange+RoutingKey？TopicExchange+RoutingKey？等
3. 我要处理的消息是实时的还是需要延时/延迟的？
4. 消息的生产者需要在哪里写，消息的监听消费者需要在哪里写，各自的处理逻辑是啥

基于这样的几个要点，我们先小试牛刀一番，采用 RabbitMQ 实战异步写日志与异步发邮件。当然啦，在进行实战前，我们需要安装好 RabbitMQ 及其后端控制台应用，并在项目中配置一下 RabbitMQ 的相关参数以及相关 Bean 组件。

1.RabbitMQ 安装完成后，打开后端控制台应用：http://localhost:15672/ guest guest 登录，看到下图即表示安装成功

2.然后是项目配置文件层面的配置 application.properties

1
2
3
4
5
6
7

复制代码spring.rabbitmq.host=127.0.0.1
spring.rabbitmq.port=5672
spring.rabbitmq.username=guest
spring.rabbitmq.password=guest
spring.rabbitmq.listener.concurrency=10
spring.rabbitmq.listener.max-concurrency=20
spring.rabbitmq.listener.prefetch=5

其中，后面三个参数主要是用于“并发量的配置”，表示：并发消费者的初始化值，并发消费者的最大值，每个消费者每次监听时可拉取处理的消息数量。

接下来，我们需要以 Configuration 的方式配置 RabbitMQ 并以 Bean 的方式显示注入 RabbitMQ 在发送接收处理消息时相关 Bean 组件配置其中典型的配置是 RabbitTemplate 以及 SimpleRabbitListenerContainerFactory，前者是充当消息的发送组件，后者是用于管理**RabbitMQ监听器** 的容器工厂，其代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

复制代码@Configuration
    public class RabbitmqConfig {
    private static final Logger log= LoggerFactory.getLogger(RabbitmqConfig.class);

    @Autowired
    private Environment env;

    @Autowired
    private CachingConnectionFactory connectionFactory;

    @Autowired
    private SimpleRabbitListenerContainerFactoryConfigurer factoryConfigurer;

    /**
     * 单一消费者
     * @return
     */
    @Bean(name = "singleListenerContainer")
    public SimpleRabbitListenerContainerFactory listenerContainer(){
        SimpleRabbitListenerContainerFactory factory = new SimpleRabbitListenerContainerFactory();
        factory.setConnectionFactory(connectionFactory);
        factory.setMessageConverter(new Jackson2JsonMessageConverter());
        factory.setConcurrentConsumers(1);
        factory.setMaxConcurrentConsumers(1);
        factory.setPrefetchCount(1);
        factory.setTxSize(1);
        factory.setAcknowledgeMode(AcknowledgeMode.AUTO);
        return factory;
    }

    /**
     * 多个消费者
     * @return
     */
    @Bean(name = "multiListenerContainer")
    public SimpleRabbitListenerContainerFactory multiListenerContainer(){
        SimpleRabbitListenerContainerFactory factory = new SimpleRabbitListenerContainerFactory();
        factoryConfigurer.configure(factory,connectionFactory);
        factory.setMessageConverter(new Jackson2JsonMessageConverter());
        factory.setAcknowledgeMode(AcknowledgeMode.NONE);
        factory.setConcurrentConsumers(env.getProperty("spring.rabbitmq.listener.concurrency",int.class));
        factory.setMaxConcurrentConsumers(env.getProperty("spring.rabbitmq.listener.max-concurrency",int.class));
        factory.setPrefetchCount(env.getProperty("spring.rabbitmq.listener.prefetch",int.class));
        return factory;
    }

    @Bean
    public RabbitTemplate rabbitTemplate(){
        connectionFactory.setPublisherConfirms(true);
        connectionFactory.setPublisherReturns(true);
        RabbitTemplate rabbitTemplate = new RabbitTemplate(connectionFactory);
        rabbitTemplate.setMandatory(true);
        rabbitTemplate.setConfirmCallback(new RabbitTemplate.ConfirmCallback() {
            @Override
            public void confirm(CorrelationData correlationData, boolean ack, String cause) {
                log.info("消息发送成功:correlationData({}),ack({}),cause({})",correlationData,ack,cause);
            }
        });
        rabbitTemplate.setReturnCallback(new RabbitTemplate.ReturnCallback() {
            @Override
            public void returnedMessage(Message message, int replyCode, String replyText, String exchange, String routingKey) {
                log.info("消息丢失:exchange({}),route({}),replyCode({}),replyText({}),message:{}",exchange,routingKey,replyCode,replyText,message);
            }
        });
        return rabbitTemplate;
    }}

RabbitMQ 实战：业务模块解耦以及异步通信

在一些企业级系统中，我们经常可以见到一个执行 function 通常是由许多子模块组成的，这个 function 在执行过程中，需要 同步 的将其代码从头开始执行到尾，即执行流程是 module_A -> module_B -> module_C -> module_D，典型的案例可以参见汇编或者 C 语言等面向过程语言开发的应用，现在的一些 JavaWeb 应用也存在着这样的写法。

而我们知道，这个执行流程其实对于整个 function 来讲是有一定的弊端的，主要有两点：

1. 整个 function 的执行响应时间将很久；
2. 如果某个 module 发生异常而没有处理得当，可能会影响其他 module 甚至整个 function 的执行流程与结果；
3. 整个 function 中代码可能会很冗长，模块与模块之间可能需要进行强通信以及数据的交互，出现问题时难以定位与维护，甚至会陷入 “改一处代码而动全身”的尴尬境地！

故而，我们需要想办法进行优化，我们需要将强关联的业务模块解耦以及某些模块之间实行异步通信！下面就以两个场景来实战我们的优化措施！

场景一：异步记录用户操作日志

对于企业级应用系统或者微服务应用中，我们经常需要追溯跟踪记录用户的操作日志，而这部分的业务在某种程度上是不应该跟主业务模块耦合在一起的，故而我们需要将其单独抽出并以异步的方式与主模块进行异步通信交互数据。

下面我们就用 RabbitMQ 的 DirectExchange+RoutingKey 消息模型也实现“用户登录成功记录日志”的场景。如前面所言，我们需要在脑海里回荡着几个要点：

• 消息模型：DirectExchange+RoutingKey 消息模型
• 消息：用户登录的实体信息，包括用户名，登录事件，来源的IP，所属日志模块等信息
• 发送接收：在登录的 Controller 中实现发送，在某个 listener 中实现接收并将监听消费到的消息入数据表；实时发送接收

首先我们需要在上面的 RabbitmqConfig 类中创建消息模型：包括 Queue、Exchange、RoutingKey 等的建立，代码如下：

上图中 env 获取的信息，我们需要在 application.properties 进行配置，其中 mq.env=local：

此时，我们将整个项目/服务跑起来，并打开 RabbitMQ 后端控制台应用，即可看到队列以及交换机及其绑定已经建立好了，如下所示：

接下来，我们需要在 Controller 中执行用户登录逻辑，记录用户登录日志，查询获取用户角色视野资源信息等，由于篇幅关系，在这里我们重点要实现的是用MQ实现 “异步记录用户登录日志” 的逻辑，即在这里 Controller 将充当“生产者”的角色，核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

复制代码@RestController
    public class UserController {

    private static final Logger log= LoggerFactory.getLogger(HelloWorldController.class);

    private static final String Prefix="user";

    @Autowired
    private ObjectMapper objectMapper;

    @Autowired
    private UserMapper userMapper;

    @Autowired
    private UserLogMapper userLogMapper;

    @Autowired
    private RabbitTemplate rabbitTemplate;

    @Autowired
    private Environment env;

    @RequestMapping(value = Prefix+"/login",method = RequestMethod.POST,consumes = MediaType.MULTIPART_FORM_DATA_VALUE)
    public BaseResponse login(@RequestParam("userName") String userName,@RequestParam("password") String password){
        BaseResponse response=new BaseResponse(StatusCode.Success);
        try {
            //TODO：执行登录逻辑
            User user=userMapper.selectByUserNamePassword(userName,password);
            if (user!=null){
                //TODO：异步写用户日志
                try {
                    UserLog userLog=new UserLog(userName,"Login","login",objectMapper.writeValueAsString(user));
                    userLog.setCreateTime(new Date());
                    rabbitTemplate.setMessageConverter(new Jackson2JsonMessageConverter());
                    rabbitTemplate.setExchange(env.getProperty("log.user.exchange.name"));
                    rabbitTemplate.setRoutingKey(env.getProperty("log.user.routing.key.name"));

                    Message message=MessageBuilder.withBody(objectMapper.writeValueAsBytes(userLog)).setDeliveryMode(MessageDeliveryMode.PERSISTENT).build();
                    message.getMessageProperties().setHeader(AbstractJavaTypeMapper.DEFAULT_CONTENT_CLASSID_FIELD_NAME, MessageProperties.CONTENT_TYPE_JSON); 
                    rabbitTemplate.convertAndSend(message);         
                }catch (Exception e){
                    e.printStackTrace();
                }

                //TODO：塞权限数据-资源数据-视野数据
            }else{
                response=new BaseResponse(StatusCode.Fail);
            }
        }catch (Exception e){
            e.printStackTrace();
        }
        return response;
    }}

在上面的“发送逻辑”代码中，其实也体现了我们最开始介绍的演进中的几种消息模型，比如我们是将消息发送到 Exchange 的而不是 Queue，消息是以二进制流的形式进行传输等等。当用 postman 请求到这个 controller 的方法时，我们可以在 RabbitMQ 的后端控制台应用看到一条未确认的消息，通过 GetMessage 即可看到其中的详情，如下：

最后，我们将开发消费端的业务代码，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

复制代码@Component
    public class CommonMqListener {

    private static final Logger log= LoggerFactory.getLogger(CommonMqListener.class);

    @Autowired
    private ObjectMapper objectMapper;

    @Autowired
    private UserLogMapper userLogMapper;

    @Autowired
    private MailService mailService;

    /**
     * 监听消费用户日志
     * @param message
     */
    @RabbitListener(queues = "${log.user.queue.name}",containerFactory = "singleListenerContainer")
    public void consumeUserLogQueue(@Payload byte[] message){
        try {
            UserLog userLog=objectMapper.readValue(message, UserLog.class);
            log.info("监听消费用户日志 监听到消息： {} ",userLog);
            //TODO：记录日志入数据表
            userLogMapper.insertSelective(userLog);
        }catch (Exception e){
            e.printStackTrace();
        }
    }

将服务跑起来之后，我们即可监听消费到上面 Queue 中的消息，即当前用户登录的信息，而且，我们也可以看到“记录用户登录日志”的逻辑是由一条异于主业务线程的异步线程去执行的：

“异步记录用户操作日志”的案例我想足以用于诠释上面所讲的相关理论知识点了，在后续篇章中，由于篇幅限制，我将重点介绍其核心的业务逻辑！

场景二：异步发送邮件

发送邮件的场景，其实也是比较常见的，比如用户注册需要邮箱验证，用户异地登录发送邮件通知等等，在这里我以 RabbitMQ 实现异步发送邮件。实现的步骤跟场景一几乎一致！

1. 消息模型的创建

2. 配置信息的创建

3. 生产端

4. 消费端

彩蛋：本博文就先介绍RabbitMQ实战的典型业务场景之业务服务模块异步解耦与通信吧，下篇博文将继续讲解RabbitMQ实战在高并发系统的场景的应用记忆消息确认机制跟并发量的配置实战，相关源码数据库可以来这里下载

pan.baidu.com/s/1KUuz_eeF…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

1. 概述

排序算法分为内部排序和外部排序，内部排序把数据记录放在内存中进行排序，而外部排序因排序的数据量大，内存不能一次容纳全部的排序记录，所以在排序过程中需要访问外存。

经常提及的八大排序算法指的就是内部排序的八种算法，分别是冒泡排序、快速排序、直接插入排序、希尔排序、简单选择排序、堆排序、归并排序和基数排序，如果按原理划分，冒泡排序和快速排序都属于交换排序，直接插入排序和希尔排序属于插入排序，而简单选择排序和堆排序属于选择排序，如上图所示。

2. 冒泡排序

2.1 基本思想

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复访问要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。访问数列的工作是重复地进行直到没有再需要交换的数据，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，像水中的气泡从水底浮到水面。

2.2 算法描述

冒泡排序算法的算法过程如下：

①. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

②. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

③. 针对所有的元素重复以上的步骤，除了最后一个。

④. 持续每次对越来越少的元素重复上面的步骤①~③，直到没有任何一对数字需要比较。

2.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

复制代码package com.fufu.algorithm.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 * Created by zhoujunfu on 2018/8/2.
 */
public class BubbleSort {
    public static void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;
        //外层：需要length-1次循环比较
        for (int i = 0; i < length - 1; i++) {
            //内层：每次循环需要两两比较的次数，每次比较后，都会将当前最大的数放到最后位置，所以每次比较次数递减一次
            for (int j = 0; j < length - 1 - i; j++) {
                if (array[j] > array[j+1]) {
                    //交换数组array的j和j+1位置的数据
                    swap(array, j, j+1);
                }
            }
        }
    }

    /**
     * 交换数组array的i和j位置的数据
     * @param array 数组
     * @param i 下标i
     * @param j 下标j
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

2.4 算法效率

冒泡排序是稳定的排序算法，最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1)。

2.5 交换数字的三种方法

我们从冒泡排序的代码中看到了交换两个数字的方法 swap(int[] array, int i, int j)，这里使用了临时变量，而交换数字主要有三种方法，临时变量法、算术法、位运算法、面试中经常会问到，这里简单说一下，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

复制代码package com.fufu.algorithm.sort;

import java.util.Arrays;

/**
 * Created by zhoujunfu on 2018/9/10.
 */
public class SwapDemo {

    public static void main(String[] args) {
        // 临时变量法
        int[] array = new int[]{10, 20};
        System.out.println(Arrays.toString(array));
        swapByTemp(array, 0, 1);
        System.out.println(Arrays.toString(array));
        
        // 算术法
        array = new int[]{10, 20};
        swapByArithmetic(array, 0, 1);
        System.out.println(Arrays.toString(array));
        
        // 位运算法
        array = new int[]{10, 20};
        swapByBitOperation(array, 0, 1);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 通过临时变量交换数组array的i和j位置的数据
     * @param array 数组
     * @param i 下标i
     * @param j 下标j
     */
    public static void swapByTemp(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 通过算术法交换数组array的i和j位置的数据（有可能溢出）
     * @param array 数组
     * @param i 下标i
     * @param j 下标j
     */
    public static void  swapByArithmetic(int[] array, int i, int j) {
        array[i] = array[i] + array[j];
        array[j] = array[i] - array[j];
        array[i] = array[i] - array[j];
    }


    /**
     * 通过位运算法交换数组array的i和j位置的数据
     * @param array 数组
     * @param i 下标i
     * @param j 下标j
     */
    public static void  swapByBitOperation(int[] array, int i, int j) {
        array[i] = array[i]^array[j];
        array[j] = array[i]^array[j]; //array[i]^array[j]^array[j]=array[i]
        array[i] = array[i]^array[j]; //array[i]^array[j]^array[i]=array[j]
    }
}

3. 快速排序

3.1 基本思想

快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

3.2 算法描述

快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

①. 从数列中挑出一个元素，称为”基准”（pivot）。

②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

③. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

3.3 代码实现

①. 挖坑法
用伪代码描述如下：

（1）low = L; high = R; 将基准数挖出形成第一个坑a[low]。

（2）high–，由后向前找比它小的数，找到后挖出此数填前一个坑a[low]中。

（3）low++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[high]中。

（4）再重复执行②，③二步，直到low==high，将基准数填入a[low]中。

举例说明：
一个无序数组：[4, 3, 7, 5, 10, 9, 1, 6, 8, 2]

（1）随便先挖个坑，就在第一个元素（基准元素）挖坑，挖出来的“萝卜”（第一个元素4）在“篮子”（临时变量）里备用。
挖完之后的数组是这样：[ 坑, 3, 7, 5, 10, 9, 1, 6, 8,2]

（2）挖右坑填左坑：从右边开始，找个比“萝卜”（元素4）小的元素，挖出来，填到前一个坑里面。
填坑之后：[ 2, 3, 7, 5, 10, 9, 1, 6, 8,坑]

（3）挖左坑填右坑：从左边开始，找个比“萝卜”（元素4）大的元素，挖出来，填到右边的坑里面。
填坑之后：[ 2, 3,坑, 5, 10, 9, 1, 6, 8, 7]

（4）挖右坑填左坑：从右边开始，找个比“萝卜”（元素4）小的元素，挖出来，填到前一个坑里面。
填坑之后：[ 2, 3, 1, 5, 10, 9,坑, 6, 8, 7]

（5）挖左坑填右坑：从左边开始，找个比“萝卜”（元素4）大的元素，挖出来，填到右边的坑里面。
填坑之后：[ 2, 3, 1,坑, 10, 9, 5, 6, 8, 7]

（6）挖右坑填左坑：从右边开始，找个比“萝卜”（元素4）小的元素，挖出来，填到前一个坑里面，这一次找坑的过程中，找到了上一次挖的坑了，说明可以停了，用篮子里的的萝卜，把这个坑填了就行了，并且返回这个坑的位置，作为分而治之的中轴线。
填坑之后：[ 2, 3, 1, 4, 10, 9, 5, 6, 8, 7]

上面的步骤中，第2，4, 6其实都是一样的操作，3和5的操作也是一样的，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

复制代码  /**
     *  快速排序（挖坑法递归）
     * @param arr   待排序数组
     * @param low   左边界
     * @param high  右边界
     */
    public static void sort(int arr[], int low, int high) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;
        int temp = arr[left]; //挖坑1：保存基准的值

        while (left < right) {
            while (left < right && arr[right] >= temp) {
                right--;
            }
            arr[left] = arr[right]; //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
            while (left < right && arr[left] <= temp) {
                left ++;
            }
            arr[right] = arr[left]; //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
        }
        arr[left] = temp; //基准值填补到坑3中，准备分治递归快排
        System.out.println("Sorting: " + Arrays.toString(arr));
        sort(arr, low, left-1);
        sort(arr, left + 1, high);
    }

②. 左右指针法

用伪代码描述如下：

（1）low = L; high = R; 选取a[low]作为关键字记录为key。

（2）high–，由后向前找比它小的数

（3）low++，由前向后找比它大的数

（4）交换第（2）、（3）步找到的数

（5）重复（2）、（3），一直往后找，直到left和right相遇，这时将key和a[low]交换位置。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

复制代码/**
 * 快速排序
 * Created by zhoujunfu on 2018/8/6.
 */
public class QuickSort {
    /**
     * 快速排序（左右指针法）
     * @param arr 待排序数组
     * @param low 左边界
     * @param high 右边界
     */
    public static void sort2(int arr[], int low, int high) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;

        int key = arr[left];

        while (left < right) {
            while (left < right && arr[right] >= key) {
                right--;
            }
            while (left < right && arr[left] <= key) {
                left++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        swap(arr, low, left);
        System.out.println("Sorting: " + Arrays.toString(arr));
        sort2(arr, low, left - 1);
        sort2(arr, left + 1, high);
    }

    public static void swap(int arr[], int low, int high) {
        int tmp = arr[low];
        arr[low] = arr[high];
        arr[high] = tmp;
    }
}

3.4 算法效率

快速排序并不稳定，快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序。

4. 直接插入排序

4.1 基本思想

直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。

4.2 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

①. 从第一个元素开始，该元素可以认为已经被排序

②. 取出下一个元素，在已经排序的元素序列中从后向前扫描

③. 如果该元素（已排序）大于新元素，将该元素移到下一位置

④. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⑤. 将新元素插入到该位置后

⑥. 重复步骤②~⑤

4.3 代码实现

提供两种写法，一种是移位法，一种是交换法。移位法是完全按照以上算法描述实，再插入过程中将有序序列中比待插入数字大的数据向后移动，由于移动时会覆盖待插入数据，所以需要额外的临时变量保存待插入数据，代码实现如下：

①. 移位法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复制代码public static void sort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }

        for (int i = 1; i < a.length; i++) {
            int j = i - 1;
            int temp = a[i]; // 先取出待插入数据保存，因为向后移位过程中会把覆盖掉待插入数
            while (j >= 0 && a[j] > temp) { // 如果待是比待插入数据大，就后移
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = temp; // 找到比待插入数据小的位置，将待插入数据插入
        }
    }

而交换法不需求额外的保存待插入数据，通过不停的向前交换带插入数据，类似冒泡法，直到找到比它小的值，也就是待插入数据找到了自己的位置。

②. 交换法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复制代码  public static void sort2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        for (int i = 1; i < arr.length; i ++) {
            int j = i - 1;
            while (j >= 0 && arr[j] > arr[i]) {
                arr[j + 1] = arr[j] + arr[j+1];      //只要大就交换操作
                arr[j] = arr[j + 1] - arr[j];
                arr[j + 1] = arr[j + 1] - arr[j];
                System.out.println("Sorting:  " + Arrays.toString(arr));
            }
        }
    }

4.4 算法效率

直接插入排序不是稳定的排序算法。

5.希尔排序

希尔排序，也称递减增量排序算法，1959年Shell发明。是插入排序的一种高速而稳定的改进版本。

希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

5.1 基本思想

将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。

可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。更好的步长序列取值可以参考维基百科。

5.2 算法描述

①. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）

②. 按增量序列个数k，对序列进行k 趟排序；

③. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

在上面这幅图中：
初始时，有一个大小为 10 的无序序列。

在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。

接下来，按照直接插入排序的方法对每个组进行排序。

在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。

按照直接插入排序的方法对每个组进行排序。

在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
所以，希尔排序是不稳定的算法。

5.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复制代码public class ShellSort {

    public static void sort(int[] arr) {
        int gap = arr.length / 2;
        for (;gap > 0; gap = gap/2) {
            for (int j = 0; (j + gap) < arr.length; j++) { //不断缩小gap，直到1为止
                for (int k = 0; (k + gap) < arr.length; k+=gap) { //使用当前gap进行组内插入排序
                    if (arr[k] > arr[k+gap]) { //交换操作
                        arr[k] = arr[k] + arr[k+gap];
                        arr[k+gap] = arr[k] - arr[k+gap];
                        arr[k] = arr[k] - arr[k+gap];
                        System.out.println("    Sorting:  " + Arrays.toString(arr));
                    }
                }
            }
        }
    }
}

5.4 算法效率

不稳定排序算法，希尔排序第一个突破O(n2)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素，直接插入排序是稳定的；而希尔排序是不稳定的，希尔排序的时间复杂度和步长的选择有关，常用的是Shell增量排序，也就是N/2的序列，Shell增量序列不是最好的增量序列，其他还有Hibbard增量序列、Sedgewick 增量序列等，具体可以参考，希尔排序增量序列简介。

6.选择排序

6.1 基本思想

在未排序序列中找到最小（大）元素，存放到未排序序列的起始位置。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

6.2 算法描述

①. 从待排序序列中，找到关键字最小的元素；

②. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；

③. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复①、②步，直到排序结束。

6.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复制代码public class SelectSort {
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j ++) { //选出之后待排序中值最小的位置
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            if (min != i) {
                arr[min] = arr[i] + arr[min];
                arr[i] = arr[min] - arr[i];
                arr[min] = arr[min] - arr[i];
            }
        }
    }

6.4 算法效率

不稳定排序算法，选择排序的简单和直观名副其实，这也造就了它出了名的慢性子，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。 唯一值得高兴的是，它并不耗费额外的内存空间。

7.归并排序

归并排序是建立在归并操作上的一种有效的排序算法，1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

7.1 基本思想

归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

7.2 算法描述

采用递归法：
①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；

②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；

③. 重复步骤②，直到所有元素排序完毕

7.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

复制代码package com.fufu.algorithm.sort;

import java.util.Arrays;

/**
 * Created by zhoujunfu on 2018/8/10.
 */
public class MergeSort {

    public static int[] sort(int [] a) {
        if (a.length <= 1) {
            return a;
        }
        int num = a.length >> 1;
        int[] left = Arrays.copyOfRange(a, 0, num);
        int[] right = Arrays.copyOfRange(a, num, a.length);
        return mergeTwoArray(sort(left), sort(right));
    }

    public static int[] mergeTwoArray(int[] a, int[] b) {
        int i = 0, j = 0, k = 0;
        int[] result = new int[a.length + b.length]; // 申请额外空间保存归并之后数据

        while (i < a.length && j < b.length) { //选取两个序列中的较小值放入新数组
            if (a[i] <= b[j]) {
                result[k++] = a[i++];
            } else {
                result[k++] = b[j++];
            }
        }

        while (i < a.length) { //序列a中多余的元素移入新数组
            result[k++] = a[i++];
        }
        while (j < b.length) {//序列b中多余的元素移入新数组
            result[k++] = b[j++];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] b = {3, 1, 5, 4};
        System.out.println(Arrays.toString(sort(b)));
    }
}

7.4 算法效率

稳定排序算法，从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n，那么拆分数组共需logn, 又每步都是一个普通的合并子数组的过程，时间复杂度为O(n)， 故其综合时间复杂度为O(nlogn)。另一方面， 归并排序多次递归过程中拆分的子数组需要保存在内存空间， 其空间复杂度为O(n)。
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

8.基数排序

基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

8.1 基本思想

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序按照优先从高位或低位来排序有两种实现方案：

MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等, 再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来, 便得到一个有序序列。MSD方式适用于位数多的序列。

LSD（Least significant digital） 从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。

下图是LSD基数排序的示意图：

8.2 算法描述

以LSD为例，从最低位开始，具体算法描述如下：

①. 取得数组中的最大数，并取得位数；
②. arr为原始数组，从最低位开始取每个位组成radix数组；
③. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

8.3 代码实现

基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。

分配：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中

收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[]。对新形成的序列L[]重复执行分配和收集元素中的十位、百位…直到分配完该序列中的最高位，则排序结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

复制代码package com.fufu.algorithm.sort;

import java.util.Arrays;

/**
 * Created by zhoujunfu on 2018/9/11.
 * 基数排序LSD
 */
public class RadixSort {

    public static void main(String[] args) {
        int[] array = {10, 20, 5, 4, 100};
        sort(array);

    }

    public static void sort(int[] a) {

        if (a == null || a.length < 0) {
            return;
        }

        int max = a[0];
        for (int i = 0; i <a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        System.out.println("max, " + max);

        int maxDigit = 0;
        while (max != 0) {
            max = max / 10;
            maxDigit++;
        }
        System.out.println("maxDigit, " + maxDigit);

        int[][] buckets = new int[10][a.length];
        int base = 10;

        //从低位到高位，对每一位遍历，将所有元素分配到桶中
        for (int i = 0; i < maxDigit; i++) {
            int[] bucketLen = new int[10];  //存储各个桶中存储元素的数量

            //收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
            for (int j = 0; j < a.length; j++) {
                int whichBucket = (a[j] % base) / (base / 10);
                buckets[whichBucket][bucketLen[whichBucket]] = a[j];
                bucketLen[whichBucket]++;
            }

            int k = 0;
            //收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
            for (int l = 0; l < buckets.length; l++) {
                for (int m =0; m < bucketLen[l]; m++) {
                    a[k++] = buckets[l][m];
                }
            }
            System.out.println("Sorting: " + Arrays.toString(a));
            base *= 10;
        }
    }
}

8.4 算法效率

基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法，以下是基数排序算法复杂度：

其中，d 为位数，r 为基数，n 为原数组个数。在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d*(n + r))。

基数排序更适合用于对时间, 字符串等这些整体权值未知的数据进行排序，适用于。

(1)数据范围较小，建议在小于1000

(2)每个数值都要大于等于0

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶

计数排序：每个桶只存储单一键值

桶排序：每个桶存储一定范围的数值

计数排序和桶排序在这篇文章里具体就不写了，有需要的可以自行百度。

9.堆排序

看堆排序之前先介绍一下面几个概念：

完全二叉树： 若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树，很好理解如下图所示。

堆： 堆是具有以下性质的完全二叉树，每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子：

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：

9.1 基本思想

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

9.2 算法描述

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

1.假设给定无序序列结构如下

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

3.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，我们就将一个无需序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

b.重新调整结构，使其继续满足堆定义

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

再简单总结下堆排序的基本思路：

  a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

  b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;

  c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。      

9.3 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

复制代码package com.fufu.algorithm.sort;

import java.util.Arrays;

/**
 * Created by zhoujunfu on 2018/9/26.
 */
public class HeapSort {

    public static void main(String []args){
        int []arr = {4,6,8,5,9};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

9.4 算法效率

由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列。同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序。

①. 建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);

②. 调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(lgn);

③. 堆排序的过程由n次第②步完成, 时间复杂度为O(nlgn).

10. 总结

从时间复杂度来说：

(1). 平方阶O(n²)排序：各类简单排序：直接插入、直接选择和冒泡排序；

(2). 线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；

(3). O(n1+§))排序，§是介于0和1之间的常数：希尔排序

(4). 线性阶O(n)排序：基数排序，此外还有桶、箱排序。

时间复杂度极限：

当被排序的数有一些性质的时候（比如是整数，比如有一定的范围），排序算法的复杂度是可以小于O(nlgn)的。比如：

计数排序 复杂度O( k+n) 要求：被排序的数是0~k范围内的整数

基数排序 复杂度O( d(k+n) ) 要求：d位数，每个数位有k个取值

桶排序 复杂度 O( n ) （平均） 要求：被排序数在某个范围内，并且服从均匀分布

但是，当被排序的数不具有任何性质的时候，一般使用基于比较的排序算法，而基于比较的排序算法时间复杂度的下限必须是O( nlgn) 。参考很多高效排序算法的代价是 nlogn，难道这是排序算法的极限了吗？

说明
当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；

原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

11.参考资料

1. 八大排序算法总结与java实现
2. 图解排序算法(三)之堆排序

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

在上一篇《你真的懂ReentrantReadWriteLock吗？》中我给大家留了一个引子，一个更高效同时可以避免写饥饿的读写锁—StampedLock。StampedLock实现了不仅多个读不互相阻塞，同时在读操作时不会阻塞写操作。

为什么StampedLock这么神奇？能够达到这种效果，它的核心思想在于，在读的时候如果发生了写，应该通过重试的方式来获取新的值，而不应该阻塞写操作。这种模式也就是典型的无锁编程思想，和CAS自旋的思想一样。这种操作方式决定了StampedLock在读线程非常多而写线程非常少的场景下非常适用，同时还避免了写饥饿情况的发生。这篇文章将通过以下几点来分析StampedLock。

• StampedLock的官方使用示例分析
• 源码分析：读写锁共享的状态量
• 源码分析：写锁的释放和获取
• 源码分析：悲观读锁的释放和获取
• 性能测试

StampedLock的官方使用示例分析

先来看一个官方给出的StampedLock使用案例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

复制代码public class Point {

	private double x, y;
	
	private final StampedLock stampedLock = new StampedLock();
	
	//写锁的使用
	void move(double deltaX, double deltaY){
		
		long stamp = stampedLock.writeLock(); //获取写锁
		try {
			x += deltaX;
			y += deltaY;
		} finally {
			stampedLock.unlockWrite(stamp); //释放写锁
		}
	}
	
	//乐观读锁的使用
	double distanceFromOrigin() {
		
		long stamp = stampedLock.tryOptimisticRead(); //获得一个乐观读锁
		double currentX = x;
		double currentY = y;
		if (!stampedLock.validate(stamp)) { //检查乐观读锁后是否有其他写锁发生，有则返回false
			
			stamp = stampedLock.readLock(); //获取一个悲观读锁
			
			try {
				currentX = x;
			} finally {
				stampedLock.unlockRead(stamp); //释放悲观读锁
			}
		} 
		return Math.sqrt(currentX*currentX + currentY*currentY);
	}
	
	//悲观读锁以及读锁升级写锁的使用
	void moveIfAtOrigin(double newX,double newY) {
		
		long stamp = stampedLock.readLock(); //悲观读锁
		try {
			while (x == 0.0 && y == 0.0) {
				long ws = stampedLock.tryConvertToWriteLock(stamp); //读锁转换为写锁
				if (ws != 0L) { //转换成功
					
					stamp = ws; //票据更新
					x = newX;
					y = newY;
					break;
				} else {
					stampedLock.unlockRead(stamp); //转换失败释放读锁
					stamp = stampedLock.writeLock(); //强制获取写锁
				}
			}
		} finally {
			stampedLock.unlock(stamp); //释放所有锁
		}
	}
}

首先看看第一个方法move，可以看到它和ReentrantReadWriteLock写锁的使用基本一样，都是简单的获取释放，可以猜测这里也是一个独占锁的实现。需要注意的是 在获取写锁是会返回个只long类型的stamp，然后在释放写锁时会将stamp传入进去。这个stamp是做什么用的呢？如果我们在中间改变了这个值又会发生什么呢？这里先暂时不做解释，后面分析源码时会解答这个问题。

第二个方法distanceFromOrigin就比较特别了，它调用了tryOptimisticRead，根据名字判断这是一个乐观读锁。首先什么是乐观锁？乐观锁的意思就是先假定在乐观锁获取期间，共享变量不会被改变，既然假定不会被改变，那就不需要上锁。在获取乐观读锁之后进行了一些操作，然后又调用了validate方法，这个方法就是用来验证tryOptimisticRead之后，是否有写操作执行过，如果有，则获取一个读锁，这里的读锁和ReentrantReadWriteLock中的读锁类似，猜测也是个共享锁。

第三个方法moveIfAtOrigin，它做了一个锁升级的操作，通过调用tryConvertToWriteLock尝试将读锁转换为写锁，转换成功后相当于获取了写锁，转换失败相当于有写锁被占用，这时通过调用writeLock来获取写锁进行操作。

看过了上面的三个方法，估计大家对怎么使用StampedLock有了一个初步的印象。下面就通过对StampedLock源码的分析来一步步了解它背后是怎么解决锁饥饿问题的。

源码分析：读写锁共享的状态量

从上面的使用示例中我们看到，在StampedLock中，除了提供了类似ReentrantReadWriteLock读写锁的获取释放方法，还提供了一个乐观读锁的获取方式。那么这三种方式是如何交互的呢？根据AQS的经验，StampedLock中应该也是使用了一个状态量来标志锁的状态。通过下面的源码可以证明这点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复制代码// 用于操作state后获取stamp的值
private static final int LG_READERS = 7;
private static final long RUNIT = 1L;               //0000 0000 0001
private static final long WBIT  = 1L << LG_READERS; //0000 1000 0000
private static final long RBITS = WBIT - 1L;        //0000 0111 1111
private static final long RFULL = RBITS - 1L;       //0000 0111 1110
private static final long ABITS = RBITS | WBIT;     //0000 1111 1111
private static final long SBITS = ~RBITS;           //1111 1000 0000

//初始化时state的值
private static final long ORIGIN = WBIT << 1;       //0001 0000 0000

//锁共享变量state
private transient volatile long state;
//读锁溢出时用来存储多出的毒素哦
private transient int readerOverflow;

上面的源码中除了定义state变量外，还提供了一系列变量用来操作state，用来表示读锁和写锁的各种状态。为了方便理解，我将他们都表示成二进制的值，长度有限，这里用低12位来表示64的long，高位自动用0补齐。要理解这些状态的作用，就需要具体分析三种锁操作方式是怎么通过state这一个变量来表示的，首先来看看获取写锁和释放写锁。

源码分析：写锁的释放和获取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复制代码public StampedLock() {
    state = ORIGIN; //初始化state为 0001 0000 0000
}

public long writeLock() {
    long s, next; 
    return ((((s = state) & ABITS) == 0L && //没有读写锁
                U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ? //cas操作尝试获取写锁
            next : acquireWrite(false, 0L));    //获取成功后返回next，失败则进行后续处理，排队也在后续处理中
}

public void unlockWrite(long stamp) {
    WNode h;
    if (state != stamp || (stamp & WBIT) == 0L) //stamp值被修改，或者写锁已经被释放，抛出错误
        throw new IllegalMonitorStateException();
    state = (stamp += WBIT) == 0L ? ORIGIN : stamp; //加0000 1000 0000来记录写锁的变化，同时改变写锁状态
    if ((h = whead) != null && h.status != 0)
        release(h);
}

这里先说明两点结论：读锁通过前7位来表示，每获取一个读锁，则加1。写锁通过除前7位后剩下的位来表示，每获取一次写锁，则加1000 0000，这两点在后面的源码中都可以得倒证明。
初始化时将state变量设置为0001 0000 0000。写锁获取通过((s = state) & ABITS)操作等于0时默认没有读锁和写锁。写锁获取分三种情况：

• 没有读锁和写锁时，state为0001 0000 0000
  0001 0000 0000 & 0000 1111 1111 = 0000 0000 0000 // 等于0L，可以尝试获取写锁
• 有一个读锁时，state为0001 0000 0001
  0001 0000 0001 & 0000 1111 1111 = 0000 0000 0001 // 不等于0L
• 有一个写锁，state为0001 1000 0000
  0001 1000 0000 & 0000 1111 1111 = 0000 1000 0000 // 不等于0L

获取到写锁，需要将s + WBIT设置到state，也就是说每次获取写锁，都需要加0000 1000 0000。同时返回s + WBIT的值
0001 0000 0000 + 0000 1000 0000 = 0001 1000 0000

释放写锁首先判断stamp的值有没有被修改过或者多次释放，之后通过state = (stamp += WBIT) == 0L ? ORIGIN : stamp来释放写锁，位操作表示如下：
stamp += WBIT
0010 0000 0000 = 0001 1000 0000 + 0000 1000 0000
这一步操作是重点！！！写锁的释放并不是像ReentrantReadWriteLock一样+1然后-1，而是通过再次加0000 1000 0000来使高位每次都产生变化，为什么要这样做？直接减掉0000 1000 0000不就可以了吗？这就是为了后面乐观锁做铺垫，让每次写锁都留下痕迹。

大家可以想象这样一个场景，字母A变化为B能看到变化，如果在一段时间内从A变到B然后又变到A，在内存中自会显示A，而不能记录变化的过程，这也就是CAS中的ABA问题。在StampedLock中就是通过每次对高位加0000 1000 0000来达到记录写锁操作的过程，可以通过下面的步骤理解：

• 第一次获取写锁：
  0001 0000 0000 + 0000 1000 0000 = 0001 1000 0000
• 第一次释放写锁：
  0001 1000 0000 + 0000 1000 0000 = 0010 0000 0000
• 第二次获取写锁：
  0010 0000 0000 + 0000 1000 0000 = 0010 1000 0000
• 第二次释放写锁：
  0010 1000 0000 + 0000 1000 0000 = 0011 0000 0000
• 第n次获取写锁：
  1110 0000 0000 + 0000 1000 0000 = 1110 1000 0000
• 第n次释放写锁：
  1110 1000 0000 + 0000 1000 0000 = 1111 0000 0000

可以看到第8位在获取和释放写锁时会产生变化，也就是说第8位是用来表示写锁状态的，前7位是用来表示读锁状态的，8位之后是用来表示写锁的获取次数的。这样就有效的解决了ABA问题，留下了每次写锁的记录，也为后面乐观锁检查变化提供了基础。

关于acquireWrite方法这里不做具体分析，方法非常复杂，感兴趣的同学可以网上搜索相关资料。这里只对该方法做下简单总结，该方法分两步来进行线程排队，首先通过随机探测的方式多次自旋尝试获取锁，然后自旋一定次数失败后再初始化节点进行插入。

源码分析：悲观读锁的释放和获取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复制代码public long readLock() {
    long s = state, next;  
    return ((whead == wtail && (s & ABITS) < RFULL && //队列为空，无写锁，同时读锁未溢出，尝试获取读锁
                U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?   //cas尝试获取读锁+1
            next : acquireRead(false, 0L));     //获取读锁成功，返回s + RUNIT，失败进入后续处理，类似acquireWrite
}

public void unlockRead(long stamp) {
    long s, m; WNode h;
    for (;;) {
        if (((s = state) & SBITS) != (stamp & SBITS) ||
            (stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
            throw new IllegalMonitorStateException();
        if (m < RFULL) {    //小于最大记录值（最大记录值127超过后放在readerOverflow变量中）
            if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {  //cas尝试释放读锁-1
                if (m == RUNIT && (h = whead) != null && h.status != 0)
                    release(h);
                break;
            }
        }
        else if (tryDecReaderOverflow(s) != 0L) //readerOverflow - 1
            break;
    }
}

悲观读锁的获取和ReentrantReadWriteLock类似，不同在于StampedLock的读锁很容易溢出，最大只有127，超过后通过一个额外的变量readerOverflow来存储，这是为了给写锁留下更大的空间，因为写锁是在不停增加的。悲观读锁获取分下面四种情况：

• 没有读锁和写锁时，state为0001 0000 0000
  // 小于 0000 0111 1110，可以尝试获取读锁
  0001 0000 0000 & 0000 1111 1111 = 0000 0000 0000
• 有一个读锁时，state为0001 0000 0001
  // 小于 0000 0111 1110，可以尝试获取读锁
  0001 0000 0001 & 0000 1111 1111 = 0000 0000 0001
• 有一个写锁，state为0001 1000 0000
  // 大于 0000 0111 1110，不可以获取读锁
  0001 1000 0000 & 0000 1111 1111 = 0000 1000 0000
• 读锁溢出，state为0001 0111 1110
  // 等于 0000 0111 1110，不可以获取读锁
  0001 0111 1110 & 0000 1111 1111 = 0000 0111 1110
  读锁的释放过程在没有溢出的情况下是通过s - RUNIT操作也就是-1来释放的，当溢出后则将readerOverflow变量-1。

乐观读锁的获取和验证

乐观读锁因为实际上没有获取过锁，所以也就没有释放锁的过程，只是在操作后通过验证检查和获取前的变化。源码如下：

1
2
3
4
5
6
7
8
9
10
11
12

复制代码//尝试获取乐观锁
public long tryOptimisticRead() {
    long s;
    return (((s = state) & WBIT) == 0L) ? (s & SBITS) : 0L;
}

//验证乐观锁获取之后是否有过写操作
public boolean validate(long stamp) {
    //该方法之前的所有load操作在内存屏障之前完成，对应的还有storeFence()及fullFence()
    U.loadFence();  
    return (stamp & SBITS) == (state & SBITS);  //比较是否有过写操作
}

乐观锁基本原理就时获取锁时记录state的写状态，然后在操作完成之后检查写状态是否有变化，因为写状态每次都会在高位留下记录，这样就避免了写锁获取又释放后得不到准确数据。获取写锁记录有三种情况：

• 没有读锁和写锁时，state为0001 0000 0000
  //((s = state) & WBIT) == 0L) true
  0001 0000 0000 & 0000 1000 0000 = 0000 0000 0000
  //(s & SBITS)
  0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000
• 有一个读锁时，state为0001 0000 0001
  //((s = state) & WBIT) == 0L) true
  0001 0000 0001 & 0000 1000 0000 = 0000 0000 0000
  //(s & SBITS)
  0001 0000 0001 & 1111 1000 0000 = 0001 0000 0000
• 有一个写锁，state为0001 1000 0000
  //((s = state) & WBIT) == 0L) false
  0001 1000 0000 & 0000 1000 0000 = 0000 1000 0000
  //0L
  0000 0000 0000

验证过程中是否有过写操作，分四种情况

• 写过一次
  0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000
  0010 0000 0000 & 1111 1000 0000 = 0010 0000 0000 //false
• 未写过，但读过
  0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000
  0001 0000 1111 & 1111 1000 0000 = 0001 0000 0000 //true
• 正在写
  0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000
  0001 1000 0000 & 1111 1000 0000 = 0001 1000 0000 //false
• 之前正在写，无论是否写完都不会为0L
  0000 0000 0000 & 1111 1000 0000 = 0000 0000 0000 //false

性能测试

分析完了StampedLock的实现原理，这里对StampedLock、ReentrantReadWriteLock以及Synchronized分别在各种场景下进行性能测试，测试的基准代码采用https://blog.takipi.com/java-8-stampedlocks-vs-readwritelocks-and-synchronized/ 文章中的代码，首先贴出上述博客中的测试结果,文章中的OPTIMISTIC模式由于采用了“脏读”模式，这里不采用OPTIMISTIC的测试结果，只比较StampedLock、ReentrantReadWriteLock以及Synchronized。

5个读线程和5个写线程场景：表现最好的是StampedLock的正常模式以及ReentrantReadWriteLock。

10个读线程和10个写线程场景：表现最好的是StampedLock的正常模式以及Synchronized。

16个读线程和4个写线程场景：表现最好的是StampedLock的正常模式以及Synchronized。

19个读线程和1个写线程场景：表现最好的是Synchronized。

博客评论中还有一种测试场景2000读线程和1个写线程，测试结果如下：
StampedLock … 12814.2 ReentrantReadWriteLock … 18882.8 Synchronized … 22696.4
表现最好的是StampedLock。
看完了上面的测试，前面3种场景表现最好的都为StampedLock，但第4种情况下StampedLock表现很差，于是我自己对代码又进行了一遍测试，同时鉴于读写锁的大量应用在缓存场景下，读写差距极大，我增加了100个读和1个写的场景。

测试机器：MAC OS(10.12.6),CPU : 2.4 GHz Intel Core i5,内存：8G 软件版本：JDK1.8
测试结果如下：
19个读线程和1个写线程场景：表现最好的是StampedLock以及Synchronized。
读线程: 19. 写线程: 1. 循环次数: 5. 计算总和: 1000000

100个读线程和1个写线程场景：表现最好的是StampedLock以及Synchronized。
读线程: 100. 写线程: 1. 循环次数: 5. 计算总和: 100000

通过上述测试，可以发现整体性能平均而言StampedLock和Synchronized相差不大，StampedLock在读写差距加大时稍微有点优势。而ReentrantReadWriteLock性能之差有点出乎意料，基本可以达到抛弃使用的地步了，不知道大家对ReentrantReadWriteLock的使用场景有什么建议？
同时鉴于原生的Synchronized后期可优化空间比较大，而且在代码复杂性以及安全性上面都具有一定优势，因此在绝大多数场景可以使用Synchronized来进行同步，对性能有一定要求的在某些特定场景下可以使用StampedLock。测试所用代码在我所引用的博客中都可以找到，大家可以自行尝试测试，如果对结果有什么疑问，欢迎在评论中提出。

参考资料：

blog.takipi.com/java-8-stam…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

作者 | 蘇小小

编辑 | 王久一

来源 | 慕课网

导读：因为教程详细，所以行文有些长，新手边看边操作效果出乎你的预料。GitHub虽然有些许改版，但并无大碍。 优质教程请关注微信公众号“Web项目聚集地”

一：Git是什么？Git是目前世界上最先进的分布式版本控制系统。工作原理 / 流程：Workspace：工作区Index / Stage：暂存区Repository：仓库区（或本地仓库）Remote：远程仓库

二：SVN与Git的最主要的区别？

SVN是集中式版本控制系统，版本库是集中放在中央服务器的，而干活的时候，用的都是自己的电脑，所以首先要从中央服务器哪里得到最新的版本，然后干活，干完后，需要把自己做完的活推送到中央服务器。集中式版本控制系统是必须联网才能工作，如果在局域网还可以，带宽够大，速度够快，如果在互联网下，如果网速慢的话，就纳闷了。

Git是分布式版本控制系统，那么它就没有中央服务器的，每个人的电脑就是一个完整的版本库，这样，工作的时候就不需要联网了，因为版本都是在自己的电脑上。既然每个人的电脑都有一个完整的版本库，那多个人如何协作呢？比如说自己在电脑上改了文件A，其他人也在电脑上改了文件A，这时，你们两之间只需把各自的修改推送给对方，就可以互相看到对方的修改了。

三、在windows上如何安装Git？

msysgit是 windows版的Git,如下： 需要从网上下载一个，然后进行默认安装即可。安装完成后，在开始菜单里面找到 “Git –> Git Bash”,如下： 会弹出一个类似的命令窗口的东西，就说明Git安装成功。如下：

安装完成后，还需要最后一步设置，在命令行输入如下：

因为Git是分布式版本控制系统，所以需要填写用户名和邮箱作为一个标识。

注意：git config –global 参数，有了这个参数，表示你这台机器上所有的Git仓库都会使用这个配置，当然你也可以对某个仓库指定的不同的用户名和邮箱。

四：如何操作？

一：创建版本库。

什么是版本库？版本库又名仓库，英文名repository,你可以简单的理解一个目录，这个目录里面的所有文件都可以被Git管理起来，每个文件的修改，删除，Git都能跟踪，以便任何时刻都可以追踪历史，或者在将来某个时刻还可以将文件”还原”。

所以创建一个版本库也非常简单，如下我是D盘 –> www下 目录下新建一个testgit版本库。

pwd 命令是用于显示当前的目录。

通过命令 git init 把这个目录变成git可以管理的仓库，如下：

这时候你当前testgit目录下会多了一个.git的目录，这个目录是Git来跟踪管理版本的，没事千万不要手动乱改这个目录里面的文件，否则，会把git仓库给破坏了。如下：

下面先看下demo如下演示：

我在版本库testgit目录下新建一个记事本文件 readme.txt 内容如下：11111111

第一步：使用命令 git add readme.txt添加到暂存区里面去。如下：如果和上面一样，没有任何提示，说明已经添加成功了。

第二步：用命令 git commit告诉Git，把文件提交到仓库。现在我们已经提交了一个readme.txt文件了，我们下面可以通过命令git
status来查看是否还有文件未提交，如下： 说明没有任何文件未提交，但是我现在继续来改下readme.txt内容，比如我在下面添加一行2222222222内容，继续使用git
status来查看下结果，如下：上面的命令告诉我们
readme.txt文件已被修改，但是未被提交的修改。

把文件添加到版本库中。

首先要明确下，所有的版本控制系统，只能跟踪文本文件的改动，比如txt文件，网页，所有程序的代码等，Git也不列外，版本控制系统可以告诉你每次的改动，但是图片，视频这些二进制文件，虽能也能由版本控制系统管理，但没法跟踪文件的变化，只能把二进制文件每次改动串起来，也就是知道图片从1kb变成2kb，但是到底改了啥，版本控制也不知道。

接下来我想看下readme.txt文件到底改了什么内容，如何查看呢？可以使用如下命令：

git diff readme.txt 如下：如上可以看到，readme.txt文件内容从一行11111111改成
二行 添加了一行22222222内容。

知道了对readme.txt文件做了什么修改后，我们可以放心的提交到仓库了，提交修改和提交文件是一样的2步(第一步是git add 第二步是：git commit)。

如下：二：版本回退：如上，我们已经学会了修改文件，现在我继续对readme.txt文件进行修改，再增加一行

内容为33333333333333.继续执行命令如下：

现在我已经对readme.txt文件做了三次修改了，那么我现在想查看下历史记录，如何查呢？我们现在可以使用命令 git log 演示如下所示：git log命令显示从最近到最远的显示日志，我们可以看到最近三次提交，最近的一次是,增加内容为333333.上一次是添加内容222222，第一次默认是 111111.如果嫌上面显示的信息太多的话，我们可以使用命令 git log –pretty=oneline 演示如下： 现在我想使用版本回退操作，我想把当前的版本回退到上一个版本，要使用什么命令呢？可以使用如下2种命令，第一种是：git reset –hard HEAD^ 那么如果要回退到上上个版本只需把HEAD^
改成 HEAD^^ 以此类推。那如果要回退到前100个版本的话，使用上面的方法肯定不方便，我们可以使用下面的简便命令操作：git reset –hard HEAD~100 即可。未回退之前的readme.txt内容如下： 如果想回退到上一个版本的命令如下操作：

再来查看下 readme.txt内容如下：通过命令cat readme.txt查看

可以看到，内容已经回退到上一个版本了。我们可以继续使用git log 来查看下历史记录信息，如下：

我们看到 增加333333 内容我们没有看到了，但是现在我想回退到最新的版本，如：有333333的内容要如何恢复呢？我们可以通过版本号回退，使用命令方法如下：

git reset –hard 版本号 ，但是现在的问题假如我已经关掉过一次命令行或者333内容的版本号我并不知道呢？要如何知道增加3333内容的版本号呢？可以通过如下命令即可获取到版本号：git reflog 演示如下：

通过上面的显示我们可以知道，增加内容3333的版本号是 6fcfc89.我们现在可以命令

git reset –hard 6fcfc89来恢复了。演示如下：

可以看到 目前已经是最新的版本了。

三：理解工作区与暂存区的区别？工作区：就是你在电脑上看到的目录，比如目录下testgit里的文件(.git隐藏目录版本库除外)。或者以后需要再新建的目录文件等等都属于工作区范畴。版本库(Repository)：工作区有一个隐藏目录.git,这个不属于工作区，这是版本库。其中版本库里面存了很多东西，其中最重要的就是stage(暂存区)，还有Git为我们自动创建了第一个分支master,以及指向master的一个指针HEAD。

我们前面说过使用Git提交文件到版本库有两步：

第一步：是使用 git add 把文件添加进去，实际上就是把文件添加到暂存区。

第二步：使用git commit提交更改，实际上就是把暂存区的所有内容提交到当前分支上。

我们继续使用demo来演示下：

我们在readme.txt再添加一行内容为4444444，接着在目录下新建一个文件为test.txt 内容为test，我们先用命令 git status来查看下状态，如下：

现在我们先使用git add 命令把2个文件都添加到暂存区中，再使用git status来查看下状态，如下：

接着我们可以使用git commit一次性提交到分支上，如下：

四：Git撤销修改和删除文件操作。一：撤销修改：比如我现在在readme.txt文件里面增加一行 内容为555555555555，我们先通过命令查看如下： 在我未提交之前，我发现添加5555555555555内容有误，所以我得马上恢复以前的版本，现在我可以有如下几种方法可以做修改：

第一：如果我知道要删掉那些内容的话，直接手动更改去掉那些需要的文件，然后add添加到暂存区，最后commit掉。

第二：我可以按以前的方法直接恢复到上一个版本。使用 git reset –hard HEAD^

但是现在我不想使用上面的2种方法，我想直接想使用撤销命令该如何操作呢？首先在做撤销之前，我们可以先用 git status 查看下当前的状态。如下所示：

可以发现，Git会告诉你，git checkout – file 可以丢弃工作区的修改，如下命令：git checkout – readme.txt,如下所示：

命令 git checkout –readme.txt 意思就是，把readme.txt文件在工作区做的修改全部撤销，这里有2种情况，如下：

1.readme.txt自动修改后，还没有放到暂存区，使用 撤销修改就回到和版本库一模一样的状态。2.另外一种是readme.txt已经放入暂存区了，接着又作了修改，撤销修改就回到添加暂存区后的状态。对于第二种情况，我想我们继续做demo来看下，假如现在我对readme.txt添加一行 内容为6666666666666，我git add 增加到暂存区后，接着添加内容7777777，我想通过撤销命令让其回到暂存区后的状态。如下所示：

注意：命令git checkout – readme.txt 中的 – 很重要，如果没有 – 的话，那么命令变成创建分支了。

二：删除文件。假如我现在版本库testgit目录添加一个文件b.txt,然后提交。如下：

如上：一般情况下，可以直接在文件目录中把文件删了，或者使用如上rm命令：rm b.txt ，如果我想彻底从版本库中删掉了此文件的话，可以再执行commit命令 提交掉，现在目录是这样的，

只要没有commit之前，如果我想在版本库中恢复此文件如何操作呢？

可以使用如下命令 git checkout – b.txt，如下所示：

再来看看我们testgit目录，添加了3个文件了。如下所示：

五：远程仓库。在了解之前，先注册github账号，由于你的本地Git仓库和github仓库之间的传输是通过SSH加密的，所以需要一点设置：第一步：创建SSH Key。在用户主目录下，看看有没有.ssh目录，如果有，再看看这个目录下有没有id_rsa和id_rsa.pub这两个文件，如果有的话，直接跳过此如下命令，如果没有的话，打开命令行，输入如下命令：

ssh-keygen -t rsa –C “youremail@example.com”, 由于我本地此前运行过一次，所以本地有，如下所示：

id_rsa是私钥，不能泄露出去，id_rsa.pub是公钥，可以放心地告诉任何人。

第二步：登录github,打开” settings”中的SSH Keys页面，然后点击“Add SSH Key”,填上任意title，在Key文本框里黏贴id_rsa.pub文件的内容。

点击 Add Key，你就应该可以看到已经添加的key。

如何添加远程库？现在的情景是：我们已经在本地创建了一个Git仓库后，又想在github创建一个Git仓库，并且希望这两个仓库进行远程同步，这样github的仓库可以作为备份，又可以其他人通过该仓库来协作。

首先，登录github上，然后在右上角找到“create a new repo”创建一个新的仓库。如下：

在Repository name填入testgit，其他保持默认设置，点击“Create repository”按钮，就成功地创建了一个新的Git仓库：

1

复制代码目前，在GitHub上的这个testgit仓库还是空的，GitHub告诉我们，可以从这个仓库克隆出新的仓库，也可以把一个已有的本地仓库与之关联，然后，把本地仓库的内容推送到GitHub仓库。

现在，我们根据GitHub的提示，在本地的testgit仓库下运行命令：

1

复制代码git remote add origin https://github.com/tugenhua0707/testgit.git

所有的如下：

把本地库的内容推送到远程，使用 git push命令，实际上是把当前分支master推送到远程。

由于远程库是空的，我们第一次推送master分支时，加上了 –u参数，Git不但会把本地的master分支内容推送的远程新的master分支，还会把本地的master分支和远程的master分支关联起来，在以后的推送或者拉取时就可以简化命令。推送成功后，可以立刻在github页面中看到远程库的内容已经和本地一模一样了，上面的要输入github的用户名和密码如下所示：

从现在起，只要本地作了提交，就可以通过如下命令：

git push origin master

把本地master分支的最新修改推送到github上了，现在你就拥有了真正的分布式版本库了。

1. 如何从远程库克隆？

上面我们了解了先有本地库，后有远程库时候，如何关联远程库。

现在我们想，假如远程库有新的内容了，我想克隆到本地来 如何克隆呢？

首先，登录github，创建一个新的仓库，名字叫testgit2.如下：

如下，我们看到：

现在，远程库已经准备好了，下一步是使用命令git clone克隆一个本地库了。如下所示：

接着在我本地目录下 生成testgit2目录了，如下所示：

六：创建与合并分支。 在 版本回填退里，你已经知道，每次提交，Git都把它们串成一条时间线，这条时间线就是一个分支。截止到目前，只有一条时间线，在Git里，这个分支叫主分支，即master分支。HEAD严格来说不是指向提交，而是指向master，master才是指向提交的，所以，HEAD指向的就是当前分支。

首先，我们来创建dev分支，然后切换到dev分支上。如下操作：

git checkout 命令加上 –b参数表示创建并切换，相当于如下2条命令

git branch dev

git checkout dev

git branch查看分支，会列出所有的分支，当前分支前面会添加一个星号。然后我们在dev分支上继续做demo，比如我们现在在readme.txt再增加一行 7777777777777

首先我们先来查看下readme.txt内容，接着添加内容77777777，如下：

现在dev分支工作已完成，现在我们切换到主分支master上，继续查看readme.txt内容如下：

现在我们可以把dev分支上的内容合并到分支master上了，可以在master分支上，使用如下命令 git merge dev 如下所示：

git merge命令用于合并指定分支到当前分支上，合并后，再查看readme.txt内容，可以看到，和dev分支最新提交的是完全一样的。

注意到上面的Fast-forward信息，Git告诉我们，这次合并是“快进模式”，也就是直接把master指向dev的当前提交，所以合并速度非常快。

合并完成后，我们可以接着删除dev分支了，操作如下：

总结创建与合并分支命令如下：

查看分支：git branch

创建分支：git branch name

切换分支：git checkout name

创建+切换分支：git checkout –b name

合并某分支到当前分支：git merge name

删除分支：git branch –d name

如何解决冲突？下面我们还是一步一步来，先新建一个新分支，比如名字叫fenzhi1，在readme.txt添加一行内容8888888，然后提交，如下所示： 同样，我们现在切换到master分支上来，也在最后一行添加内容，内容为99999999，如下所示：

现在我们需要在master分支上来合并fenzhi1，如下操作：

Git用<<<<<<<，=======，>>>>>>>标记出不同分支的内容，其中<<<HEAD是指主分支修改的内容，>>>>>fenzhi1 是指fenzhi1上修改的内容，我们可以修改下如下后保存：

如果我想查看分支合并的情况的话，需要使用命令 git log.命令行演示如下：

3.分支管理策略。 通常合并分支时，git一般使用”Fast forward”模式，在这种模式下，删除分支后，会丢掉分支信息，现在我们来使用带参数 –no-ff来禁用”Fast forward”模式。首先我们来做demo演示下：

创建一个dev分支。修改readme.txt内容。添加到暂存区。切换回主分支(master)。合并dev分支，使用命令 git merge –no-ff -m “注释” dev查看历史记录截图如下：

分支策略：首先master主分支应该是非常稳定的，也就是用来发布新版本，一般情况下不允许在上面干活，干活一般情况下在新建的dev分支上干活，干完后，比如上要发布，或者说dev分支代码稳定后可以合并到主分支master上来。

七：bug分支： 在开发中，会经常碰到bug问题，那么有了bug就需要修复，在Git中，分支是很强大的，每个bug都可以通过一个临时分支来修复，修复完成后，合并分支，然后将临时的分支删除掉。

比如我在开发中接到一个404 bug时候，我们可以创建一个404分支来修复它，但是，当前的dev分支上的工作还没有提交。比如如下：

并不是我不想提交，而是工作进行到一半时候，我们还无法提交，比如我这个分支bug要2天完成，但是我issue-404 bug需要5个小时内完成。怎么办呢？还好，Git还提供了一个stash功能，可以把当前工作现场 ”隐藏起来”，等以后恢复现场后继续工作。如下：

所以现在我可以通过创建issue-404分支来修复bug了。

首先我们要确定在那个分支上修复bug，比如我现在是在主分支master上来修复的，现在我要在master分支上创建一个临时分支，演示如下：

修复完成后，切换到master分支上，并完成合并，最后删除issue-404分支。演示如下：

现在，我们回到dev分支上干活了。

工作区是干净的，那么我们工作现场去哪里呢？我们可以使用命令 git stash list来查看下。如下：

工作现场还在，Git把stash内容存在某个地方了，但是需要恢复一下，可以使用如下2个方法：

1.git stash apply恢复，恢复后，stash内容并不删除，你需要使用命令git stash drop来删除。2.另一种方式是使用git stash pop,恢复的同时把stash内容也删除了。演示如下

八：多人协作。 当你从远程库克隆时候，实际上Git自动把本地的master分支和远程的master分支对应起来了，并且远程库的默认名称是origin。

要查看远程库的信息 使用 git remote要查看远程库的详细信息 使用 git remote –v如下演示：

一：推送分支：

推送分支就是把该分支上所有本地提交到远程库中，推送时，要指定本地分支，这样，Git就会把该分支推送到远程库对应的远程分支上： 使用命令 git push origin master

比如我现在的github上的readme.txt代码如下：

本地的readme.txt代码如下：

现在我想把本地更新的readme.txt代码推送到远程库中，使用命令如下：

我们可以看到如上，推送成功，我们可以继续来截图github上的readme.txt内容 如下：

可以看到 推送成功了，如果我们现在要推送到其他分支，比如dev分支上，我们还是那个命令 git push origin dev

那么一般情况下，那些分支要推送呢？

master分支是主分支，因此要时刻与远程同步。一些修复bug分支不需要推送到远程去，可以先合并到主分支上，然后把主分支master推送到远程去。二：抓取分支：

多人协作时，大家都会往master分支上推送各自的修改。现在我们可以模拟另外一个同事，可以在另一台电脑上（注意要把SSH key添加到github上）或者同一台电脑上另外一个目录克隆，新建一个目录名字叫testgit2

但是我首先要把dev分支也要推送到远程去，如下

接着进入testgit2目录，进行克隆远程的库到本地来，如下：

现在目录下生成有如下所示： 现在我们的小伙伴要在dev分支上做开发，就必须把远程的origin的dev分支到本地来，于是可以使用命令创建本地dev分支：

git checkout –b dev origin/dev

现在小伙伴们就可以在dev分支上做开发了，开发完成后把dev分支推送到远程库时。

如下：

小伙伴们已经向origin/dev分支上推送了提交，而我在我的目录文件下也对同样的文件同个地方作了修改，也试图推送到远程库时，如下：

由上面可知：推送失败，因为我的小伙伴最新提交的和我试图推送的有冲突，解决的办法也很简单，上面已经提示我们，先用git pull把最新的提交从origin/dev抓下来，然后在本地合并，解决冲突，再推送。

git pull也失败了，原因是没有指定本地dev分支与远程origin/dev分支的链接，根据提示，设置dev和origin/dev的链接：如下：

这回git pull成功，但是合并有冲突，需要手动解决，解决的方法和分支管理中的 解决冲突完全一样。解决后，提交，再push：我们可以先来看看readme.txt内容了。

现在手动已经解决完了，我接在需要再提交，再push到远程库里面去。如下所示：

因此：多人协作工作模式一般是这样的：

首先，可以试图用git push origin branch-name推送自己的修改.如果推送失败，则因为远程分支比你的本地更新早，需要先用git pull试图合并。如果合并有冲突，则需要解决冲突，并在本地提交。再用git push origin branch-name推送。

参考：

www.cnblogs.com/tugenhua0707/p/4050072.html

作者 | 蘇小小

来源 | 慕课网

原文 | 点击阅读原文

推 荐 阅 读

1. 推荐几个原创公众号

2. 优雅的使用
ThreadLocal

3. Linux养成计划（六）

4. 微信扫码登录实战（附代码）

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

本文系掘金首发，禁止转载哦！ 如果觉得文章内容不错的话，欢迎为我转身，啊！不对，是给我一个赞！点赞之后会有惊喜哦！

看本文之前，推荐给大家一个阿里云双11活动，真的非常非常非常推荐，对于新人阿里云真的是下血本了，建议阿里云新人一定一定一定不要错过。如果觉得这单纯是广告的话，你可以直接跳过看正文。

阿里云双11最新活动（仅限阿里云新用户购买，老用户拉新用户可以获得返现红包，后续有机会平分百万红包），优惠力度非常非常非常大，另外加入拼团，后续还有机会平分100w红包！目前我的战队已经有12位新人了，现在是折上5折了也就是1折购买！！！。 划重点了： 1核2G云服务器1年仅需99.5元！！！1核2G云服务器3年仅需298.50元！！！一个月仅需8.2元 该折扣仅限新人！这是我的拼团团队地址：m.aliyun.com/act/team111… ！

写本文之前，其实我自己已经开源了一个 Java学习指南的文档，里面包含了一些基础知识和一些后端（偏 Java 方向）的知识。到目前为止收获了 6.1k star 以及 1.5 k fork，close 了 10个 pr 以及 10 个issue。开源只是为了让更多的人看到和参与进来，这样文档的正确性和质量才能很好的保证。毕竟，我个人能力、时间以及知识广度和深度有限，一份好的项目的诞生肯定离不开和其他人的共同努力。

另外，我个人觉得不论你是前端还是后端（部分内容可能会偏 Java 方向一点）都能从本文中学到东西。

本人技术水平有限，欢迎各位指正！写的不好的话，请多见谅！

目录

• 前言
• 一 简历该如何写
  • 1.1 为什么说简历很重要？
  • 1.2-这3点你必须知道
  • 1.3-两大法则了解一
  • 1.4-项目经历怎么写？
  • 1.5-专业技能该怎么写？
  • 1.6-开源程序员简历模板分享
  • 1.7 其他的一些小tips
• 二 计算机网络常见面试点总结
  • 计算机网络常见问题回顾
  • 2.1 TCP、UDP 协议的区别
  • 2.2 在浏览器中输入url地址 ->> 显示主页的过程
  • 2.3 各种协议与HTTP协议之间的关系
  • 2.4 HTTP长连接、短连接
  • 2.5 TCP 三次握手和四次挥手
• 三 Linux
  • 3.1-简单介绍一下-linux-文件系统？
  • 3.2 一些常见的 Linux 命令了解吗？
• 四 MySQL
  • 4.1 说说自己对于 MySQL 常见的两种存储引擎：MyISAM与InnoDB的理解
  • 4.2 数据库索引了解吗？
  • 4.3 对于大表的常见优化手段说一下
• 五 Redis
  • 5.1 redis 简介
  • 5.2 为什么要用 redis /为什么要用缓存
  • 5.3 为什么要用 redis 而不用 map/guava 做缓存?
  • 5.4 redis 和 memcached 的区别
  • 5.5 redis 常见数据结构以及使用场景分析
  • 5.6 redis 设置过期时间
  • 5.7 redis 内存淘汰机制
  • 5.8 redis 持久化机制（怎么保证 redis 挂掉之后再重启数据可以进行恢复）
  • 5.9 缓存雪崩和缓存穿透问题解决方案
  • 5.10 如何解决 Redis 的并发竞争 Key 问题
  • 5.11 如何保证缓存与数据库双写时的数据一致性？
• 六 Java
  • 6.1 Java 基础知识
  • 6.2 Java 集合框架
  • 6.3 Java多线程
  • 6.4 Java虚拟机
  • 6.5 设计模式
• 七 数据结构
• 八 算法
  • 8.1 举个栗子（手写快排）
• 九 Spring
  • 9.1 Spring Bean 的作用域
  • 9.2 Spring 事务中的隔离级别
  • 9.3 Spring 事务中的事务传播行为
  • 9.4 AOP
  • 9.5 IOC
• 十 实际场景题
• 写在最后

前言

不论是校招还是社招都避免不了各种面试、笔试，如何去准备这些东西就显得格外重要。不论是笔试还是面试都是有章可循的，我这个“有章可循”说的意思只是说应对技术面试是可以提前准备。 我其实特别不喜欢那种临近考试就提前背啊记啊各种题的行为，非常反对！我觉得这种方法特别极端，而且在稍有一点经验的面试官面前是根本没有用的。建议大家还是一步一个脚印踏踏实实地走。

运筹帷幄之后，决胜千里之外！不打毫无准备的仗，我觉得大家可以先从下面几个方面来准备面试：

1. 自我介绍。（你可千万这样介绍：“我叫某某，性别，来自哪里，学校是那个，自己爱干什么”，记住：多说点简历上没有的，多说点自己哪里比别人强！）
2. 自己面试中可能涉及哪些知识点、那些知识点是重点。
3. 面试中哪些问题会被经常问到、面试中自己改如何回答。(强烈不推荐背题，第一：通过背这种方式你能记住多少？能记住多久？第二：背题的方式的学习很难坚持下去！)
4. 自己的简历该如何写。

“80%的offer掌握在20%的人手中” 这句话也不是不无道理的。决定你面试能否成功的因素中实力固然占有很大一部分比例，但是如果你的心态或者说运气不好的话，依然无法拿到满意的 offer。运气暂且不谈，就拿心态来说，千万不要因为面试失败而气馁或者说怀疑自己的能力，面试失败之后多总结一下失败的原因，后面你就会发现自己会越来越强大。

另外，大家要明确的很重要的几点是：

1. 写在简历上的东西一定要慎重，这可能是面试官大量提问的地方；
2. 大部分应届生找工作的硬伤是没有工作经验或实习经历；
3. 将自己的项目经历完美的展示出来非常重要。

笔主能力有限，如果有不对的地方或者和你想法不同的地方，敬请雅正、不舍赐教。

如果想了解我的更多信息，可以关注我的 Github 或者微信公众号:”Java面试通关手册”。

一 简历该如何写

俗话说的好：“工欲善其事，必先利其器”。准备一份好的简历对于能不能找到一份好工作起到了至关重要的作用。

1.1 为什么说简历很重要？

假如你是网申，你的简历必然会经过HR的筛选，一张简历HR可能也就花费10秒钟看一下，然后HR就会决定你这一关是Fail还是Pass。

假如你是内推，如果你的简历没有什么优势的话，就算是内推你的人再用心，也无能为力。

另外，就算你通过了筛选，后面的面试中，面试官也会根据你的简历来判断你究竟是否值得他花费很多时间去面试。

1.2 这3点你必须知道

1. 大部分应届生找工作的硬伤是没有工作经验或实习经历；
2. 写在简历上的东西一定要慎重，这可能是面试官大量提问的地方；
3. 将自己的项目经历完美的展示出来非常重要。

1.3 两大法则了解一下

目前写简历的方式有两种普遍被认可，一种是 STAR， 一种是 FAB。

STAR法则（Situation Task Action Result）：

• Situation： 事情是在什么情况下发生；
• Task:： 你是如何明确你的任务的；
• Action： 针对这样的情况分析，你采用了什么行动方式；
• Result： 结果怎样，在这样的情况下你学习到了什么。

FAB 法则（Feature Advantage Benefit）：

• Feature： 是什么；
• Advantage： 比别人好在哪些地方；
• Benefit： 如果雇佣你，招聘方会得到什么好处。

1.4 项目经历怎么写？

简历上有一两个项目经历很正常，但是真正能把项目经历很好的展示给面试官的非常少。对于项目经历大家可以考虑从如下几点来写：

1. 对项目整体设计的一个感受
2. 在这个项目中你负责了什么、做了什么、担任了什么角色
3. 从这个项目中你学会了那些东西，使用到了那些技术，学会了那些新技术的使用
4. 另外项目描述中，最好可以体现自己的综合素质，比如你是如何协调项目组成员协同开发的或者在遇到某一个棘手的问题的时候你是如何解决的。

1.5 专业技能该怎么写？

先问一下你自己会什么，然后看看你意向的公司需要什么。一般HR可能并不太懂技术，所以他在筛选简历的时候可能就盯着你专业技能的关键词来看。对于公司有要求而你不会的技能，你可以花几天时间学习一下，然后在简历上可以写上自己了解这个技能。比如你可以这样写：

• Dubbo：精通
• Spring：精通
• Docker：掌握
• SOA分布式开发 ：掌握
• Spring Cloud:了解

1.6 开源程序员简历模板分享

分享一个Github上开源的程序员简历模板。包括PHP程序员简历模板、iOS程序员简历模板、Android程序员简历模板、Web前端程序员简历模板、Java程序员简历模板、C/C++程序员简历模板、NodeJS程序员简历模板、架构师简历模板以及通用程序员简历模板 。
Github地址：github.com/geekcompany…

如果想学如何用 Markdown 写简历写一份高质量简历，请看这里:github.com/Snailclimb/…

1.7 其他的一些小tips

1. 尽量避免主观表述，少一点语义模糊的形容词，尽量要简洁明了，逻辑结构清晰。
2. 注意排版（不需要花花绿绿的），尽量使用Markdown语法。
3. 如果自己有博客或者个人技术栈点的话，写上去会为你加分很多。
4. 如果自己的Github比较活跃的话，写上去也会为你加分很多。
5. 注意简历真实性，一定不要写自己不会的东西，或者带有欺骗性的内容
6. 项目经历建议以时间倒序排序，另外项目经历不在于多，而在于有亮点。
7. 如果内容过多的话，不需要非把内容压缩到一页，保持排版干净整洁就可以了。
8. 简历最后最好能加上：“感谢您花时间阅读我的简历，期待能有机会和您共事。”这句话，显的你会很有礼貌。

二 计算机网络常见面试点总结

计算机网络常见问题回顾

• TCP三次握手和四次挥手、
• 在浏览器中输入url地址->>显示主页的过程
• TCP 协议如何保证可靠传输
• HTTP和HTTPS的区别
• TCP、UDP协议的区别
• 常见的状态码。

下面列举几个常见问题的回答！

2.1 TCP、UDP 协议的区别

UDP 在传送数据之前不需要先建立连接，远地主机在收到 UDP 报文后，不需要给出任何确认。虽然 UDP 不提供可靠交付，但在某些情况下 UDP 确是一种最有效的工作方式（一般用于即时通信），比如： QQ 语音、 QQ 视频 、直播等等

TCP 提供面向连接的服务。在传送数据之前必须先建立连接，数据传送结束后要释放连接。 TCP 不提供广播或多播服务。由于 TCP 要提供可靠的，面向连接的运输服务（TCP的可靠体现在TCP在传递数据之前，会有三次握手来建立连接，而且在数据传递时，有确认、窗口、重传、拥塞控制机制，在数据传完后，还会断开连接用来节约系统资源），这一难以避免增加了许多开销，如确认，流量控制，计时器以及连接管理等。这不仅使协议数据单元的首部增大很多，还要占用许多处理机资源。TCP 一般用于文件传输、发送和接收邮件、远程登录等场景。

2.2 在浏览器中输入url地址 ->> 显示主页的过程

百度好像最喜欢问这个问题。

打开一个网页，整个过程会使用哪些协议

图片来源：《图解HTTP》

总体来说分为以下几个过程:

1. DNS解析
2. TCP连接
3. 发送HTTP请求
4. 服务器处理请求并返回HTTP报文
5. 浏览器解析渲染页面
6. 连接结束

具体可以参考下面这篇文章：

• segmentfault.com/a/119000000…

2.3 各种协议与HTTP协议之间的关系

一般面试官会通过这样的问题来考察你对计算机网络知识体系的理解。

图片来源：《图解HTTP》

2.4 HTTP长连接、短连接

在HTTP/1.0中默认使用短连接。也就是说，客户端和服务器每进行一次HTTP操作，就建立一次连接，任务结束就中断连接。当客户端浏览器访问的某个HTML或其他类型的Web页中包含有其他的Web资源（如JavaScript文件、图像文件、CSS文件等），每遇到这样一个Web资源，浏览器就会重新建立一个HTTP会话。

而从HTTP/1.1起，默认使用长连接，用以保持连接特性。使用长连接的HTTP协议，会在响应头加入这行代码：

1

复制代码Connection:keep-alive

在使用长连接的情况下，当一个网页打开完成后，客户端和服务器之间用于传输HTTP数据的TCP连接不会关闭，客户端再次访问这个服务器时，会继续使用这一条已经建立的连接。Keep-Alive不会永久保持连接，它有一个保持时间，可以在不同的服务器软件（如Apache）中设定这个时间。实现长连接需要客户端和服务端都支持长连接。

HTTP协议的长连接和短连接，实质上是TCP协议的长连接和短连接。

—— 《HTTP长连接、短连接究竟是什么？》

2.5 TCP 三次握手和四次挥手(面试常客)

为了准确无误地把数据送达目标处，TCP协议采用了三次握手策略。

漫画图解：

图片来源：《图解HTTP》

简单示意图：

• 客户端–发送带有 SYN 标志的数据包–一次握手–服务端
• 服务端–发送带有 SYN/ACK 标志的数据包–二次握手–客户端
• 客户端–发送带有带有 ACK 标志的数据包–三次握手–服务端

为什么要三次握手?

三次握手的目的是建立可靠的通信信道，说到通讯，简单来说就是数据的发送与接收，而三次握手最主要的目的就是双方确认自己与对方的发送与接收是正常的。

第一次握手：Client 什么都不能确认；Server 确认了对方发送正常

第二次握手：Client 确认了：自己发送、接收正常，对方发送、接收正常；Server 确认了：自己接收正常，对方发送正常

第三次握手：Client 确认了：自己发送、接收正常，对方发送、接收正常；Server 确认了：自己发送、接收正常，对方发送接收正常

所以三次握手就能确认双发收发功能都正常，缺一不可。

为什么要传回 SYN

接收端传回发送端所发送的 SYN 是为了告诉发送端，我接收到的信息确实就是你所发送的信号了。

SYN 是 TCP/IP 建立连接时使用的握手信号。在客户机和服务器之间建立正常的 TCP 网络连接时，客户机首先发出一个 SYN 消息，服务器使用 SYN-ACK 应答表示接收到了这个消息，最后客户机再以 ACK(Acknowledgement[汉译：确认字符 ,在数据通信传输中，接收站发给发送站的一种传输控制字符。它表示确认发来的数据已经接受无误。 ]）消息响应。这样在客户机和服务器之间才能建立起可靠的TCP连接，数据才可以在客户机和服务器之间传递。

传了 SYN,为啥还要传 ACK

双方通信无误必须是两者互相发送信息都无误。传了 SYN，证明发送方到接收方的通道没有问题，但是接收方到发送方的通道还需要 ACK 信号来进行验证。

断开一个 TCP 连接则需要“四次挥手”：

• 客户端-发送一个 FIN，用来关闭客户端到服务器的数据传送
• 服务器-收到这个 FIN，它发回一 个 ACK，确认序号为收到的序号加1 。和 SYN 一样，一个 FIN 将占用一个序号
• 服务器-关闭与客户端的连接，发送一个FIN给客户端
• 客户端-发回 ACK 报文确认，并将确认序号设置为收到序号加1

为什么要四次挥手

任何一方都可以在数据传送结束后发出连接释放的通知，待对方确认后进入半关闭状态。当另一方也没有数据再发送的时候，则发出连接释放通知，对方确认后就完全关闭了TCP连接。

举个例子：A 和 B 打电话，通话即将结束后，A 说“我没啥要说的了”，B回答“我知道了”，但是 B 可能还会有要说的话，A 不能要求 B 跟着自己的节奏结束通话，于是 B 可能又巴拉巴拉说了一通，最后 B 说“我说完了”，A 回答“知道了”，这样通话才算结束。

上面讲的比较概括，推荐一篇讲的比较细致的文章：

• blog.csdn.net/qzcsu/artic…

三 Linux

3.1 简单介绍一下 Linux 文件系统？

Linux文件系统简介

在Linux操作系统中，所有被操作系统管理的资源，例如网络接口卡、磁盘驱动器、打印机、输入输出设备、普通文件或是目录都被看作是一个文件。

也就是说在LINUX系统中有一个重要的概念：一切都是文件。其实这是UNIX哲学的一个体现，而Linux是重写UNIX而来，所以这个概念也就传承了下来。在UNIX系统中，把一切资源都看作是文件，包括硬件设备。UNIX系统把每个硬件都看成是一个文件，通常称为设备文件，这样用户就可以用读写文件的方式实现对硬件的访问。

文件类型与目录结构

Linux支持5种文件类型 ：

Linux的目录结构如下：

Linux文件系统的结构层次鲜明，就像一棵倒立的树，最顶层是其根目录：

常见目录说明：

• /bin： 存放二进制可执行文件(ls,cat,mkdir等)，常用命令一般都在这里；
• /etc： 存放系统管理和配置文件；
• /home： 存放所有用户文件的根目录，是用户主目录的基点，比如用户user的主目录就是/home/user，可以用~user表示；
• /usr ： 用于存放系统应用程序；
• /opt： 额外安装的可选应用程序包所放置的位置。一般情况下，我们可以把tomcat等都安装到这里；
• /proc： 虚拟文件系统目录，是系统内存的映射。可直接访问这个目录来获取系统信息；
• /root： 超级用户（系统管理员）的主目录（特权阶级^o^）；
• /sbin: 存放二进制可执行文件，只有root才能访问。这里存放的是系统管理员使用的系统级别的管理命令和程序。如ifconfig等；
• /dev： 用于存放设备文件；
• /mnt： 系统管理员安装临时文件系统的安装点，系统提供这个目录是让用户临时挂载其他的文件系统；
• /boot： 存放用于系统引导时使用的各种文件；
• /lib ： 存放着和系统运行相关的库文件 ；
• /tmp： 用于存放各种临时文件，是公用的临时文件存储点；
• /var： 用于存放运行时需要改变数据的文件，也是某些大文件的溢出区，比方说各种服务的日志文件（系统启动日志等。）等；
• /lost+found： 这个目录平时是空的，系统非正常关机而留下“无家可归”的文件（windows下叫什么.chk）就在这里。

3.2 一些常见的 Linux 命令了解吗？

目录切换命令

• cd usr： 切换到该目录下usr目录
• cd ..（或cd../）： 切换到上一层目录
• cd /： 切换到系统根目录
• cd ~： 切换到用户主目录
• cd -： 切换到上一个所在目录

目录的操作命令（增删改查）

1. mkdir 目录名称： 增加目录
2. ls或者ll（ll是ls -l的缩写，ll命令以看到该目录下的所有目录和文件的详细信息）：查看目录信息
3. find 目录 参数： 寻找目录（查）
4. mv 目录名称 新目录名称： 修改目录的名称（改）

注意：mv的语法不仅可以对目录进行重命名而且也可以对各种文件，压缩包等进行 重命名的操作。mv命令用来对文件或目录重新命名，或者将文件从一个目录移到另一个目录中。后面会介绍到mv命令的另一个用法。
5. mv 目录名称 目录的新位置： 移动目录的位置—剪切（改）

注意：mv语法不仅可以对目录进行剪切操作，对文件和压缩包等都可执行剪切操作。另外mv与cp的结果不同，mv好像文件“搬家”，文件个数并未增加。而cp对文件进行复制，文件个数增加了。
6. cp -r 目录名称 目录拷贝的目标位置： 拷贝目录（改），-r代表递归拷贝

注意：cp命令不仅可以拷贝目录还可以拷贝文件，压缩包等，拷贝文件和压缩包时不 用写-r递归
7. rm [-rf] 目录: 删除目录（删）

注意：rm不仅可以删除目录，也可以删除其他文件或压缩包，为了增强大家的记忆， 无论删除任何目录或文件，都直接使用rm -rf 目录/文件/压缩包

文件的操作命令（增删改查）

1. touch 文件名称: 文件的创建（增）
2. cat/more/less/tail 文件名称 文件的查看（查）

* **`cat`：** 只能显示最后一屏内容
* **`more`：** 可以显示百分比，回车可以向下一行， 空格可以向下一页，q可以退出查看
* **`less`：** 可以使用键盘上的PgUp和PgDn向上 和向下翻页，q结束查看
* **`tail-10` ：** 查看文件的后10行，Ctrl+C结束注意：命令 tail -f 文件 可以对某个文件进行动态监控，例如tomcat的日志文件， 会随着程序的运行，日志会变化，可以使用tail -f catalina-2016-11-11.log 监控 文 件的变化

3. vim 文件： 修改文件的内容（改）

vim编辑器是Linux中的强大组件，是vi编辑器的加强版，vim编辑器的命令和快捷方式有很多，但此处不一一阐述，大家也无需研究的很透彻，使用vim编辑修改文件的方式基本会使用就可以了。

在实际开发中，使用vim编辑器主要作用就是修改配置文件，下面是一般步骤：

vim 文件——>进入文件—–>命令模式——>按i进入编辑模式—–>编辑文件 ——->按Esc进入底行模式—–>输入:wq/q! （输入wq代表写入内容并退出，即保存；输入q!代表强制退出不保存。）
4. rm -rf 文件： 删除文件（删）

同目录删除：熟记 rm -rf 文件 即可

压缩文件的操作命令

1）打包并压缩文件：

Linux中的打包文件一般是以.tar结尾的，压缩的命令一般是以.gz结尾的。

而一般情况下打包和压缩是一起进行的，打包并压缩后的文件的后缀名一般.tar.gz。
命令：tar -zcvf 打包压缩后的文件名 要打包压缩的文件
其中：

z：调用gzip压缩命令进行压缩

c：打包文件

v：显示运行过程

f：指定文件名

比如：加入test目录下有三个文件分别是 :aaa.txt bbb.txt ccc.txt,如果我们要打包test目录并指定压缩后的压缩包名称为test.tar.gz可以使用命令：tar -zcvf test.tar.gz aaa.txt bbb.txt ccc.txt或：tar -zcvf test.tar.gz /test/

2）解压压缩包：

命令：tar [-xvf] 压缩文件

其中：x：代表解压

示例：

1 将/test下的test.tar.gz解压到当前目录下可以使用命令：tar -xvf test.tar.gz

2 将/test下的test.tar.gz解压到根目录/usr下:tar -xvf xxx.tar.gz -C /usr（- C代表指定解压的位置）

其他常用命令

• pwd： 显示当前所在位置
• grep 要搜索的字符串 要搜索的文件 --color： 搜索命令，–color代表高亮显示
• ps -ef/ps aux： 这两个命令都是查看当前系统正在运行进程，两者的区别是展示格式不同。如果想要查看特定的进程可以使用这样的格式：ps aux|grep redis （查看包括redis字符串的进程）

注意：如果直接用ps（（Process Status））命令，会显示所有进程的状态，通常结合grep命令查看某进程的状态。

• kill -9 进程的pid： 杀死进程（-9 表示强制终止。）

先用ps查找进程，然后用kill杀掉

• 网络通信命令：

+ 查看当前系统的网卡信息：ifconfig
+ 查看与某台机器的连接情况：ping
+ 查看当前系统的端口使用：netstat -an

• shutdown： shutdown -h now： 指定现在立即关机；shutdown +5 "System will shutdown after 5 minutes":指定5分钟后关机，同时送出警告信息给登入用户。
• reboot： reboot： 重开机。reboot -w： 做个重开机的模拟（只有纪录并不会真的重开机）。

四 MySQL

4.1 说说自己对于 MySQL 常见的两种存储引擎：MyISAM与InnoDB的理解

关于二者的对比与总结:

1. count运算上的区别：因为MyISAM缓存有表meta-data（行数等），因此在做COUNT(*)时对于一个结构很好的查询是不需要消耗多少资源的。而对于InnoDB来说，则没有这种缓存。
2. 是否支持事务和崩溃后的安全恢复： MyISAM 强调的是性能，每次查询具有原子性,其执行数度比InnoDB类型更快，但是不提供事务支持。但是InnoDB 提供事务支持事务，外部键等高级数据库功能。 具有事务(commit)、回滚(rollback)和崩溃修复能力(crash recovery capabilities)的事务安全(transaction-safe (ACID compliant))型表。
3. 是否支持外键： MyISAM不支持，而InnoDB支持。

MyISAM更适合读密集的表，而InnoDB更适合写密集的的表。 在数据库做主从分离的情况下，经常选择MyISAM作为主库的存储引擎。
一般来说，如果需要事务支持，并且有较高的并发读取频率(MyISAM的表锁的粒度太大，所以当该表写并发量较高时，要等待的查询就会很多了)，InnoDB是不错的选择。如果你的数据量很大（MyISAM支持压缩特性可以减少磁盘的空间占用），而且不需要支持事务时，MyISAM是最好的选择。

4.2 数据库索引了解吗？

Mysql索引使用的数据结构主要有BTree索引 和 哈希索引 。对于哈希索引来说，底层的数据结构就是哈希表，因此在绝大多数需求为单条记录查询的时候，可以选择哈希索引，查询性能最快；其余大部分场景，建议选择BTree索引。

Mysql的BTree索引使用的是B数中的B+Tree，但对于主要的两种存储引擎的实现方式是不同的。

• MyISAM: B+Tree叶节点的data域存放的是数据记录的地址。在索引检索的时候，首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其 data 域的值，然后以 data 域的值为地址读取相应的数据记录。这被称为“非聚簇索引”。
• InnoDB: 其数据文件本身就是索引文件。相比MyISAM，索引文件和数据文件是分离的，其表数据文件本身就是按B+Tree组织的一个索引结构，树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。这被称为“聚簇索引（或聚集索引）”。而其余的索引都作为辅助索引（非聚集索引），辅助索引的data域存储相应记录主键的值而不是地址，这也是和MyISAM不同的地方。在根据主索引搜索时，直接找到key所在的节点即可取出数据；在根据辅助索引查找时，则需要先取出主键的值，在走一遍主索引。 因此，在设计表的时候，不建议使用过长的字段作为主键，也不建议使用非单调的字段作为主键，这样会造成主索引频繁分裂。 PS：整理自《Java工程师修炼之道》

另外，再推荐几篇比较好的关于索引的文章：

• juejin.cn/post/684490…
• www.jianshu.com/p/1775b4ff1…

4.3 对于大表的常见优化手段说一下

当MySQL单表记录数过大时，数据库的CRUD性能会明显下降，一些常见的优化措施如下：

1. 限定数据的范围： 务必禁止不带任何限制数据范围条件的查询语句。比如：我们当用户在查询订单历史的时候，我们可以控制在一个月的范围内。；
2. 读/写分离： 经典的数据库拆分方案，主库负责写，从库负责读；
3. 缓存： 使用MySQL的缓存，另外对重量级、更新少的数据可以考虑使用应用级别的缓存；
4. 垂直分区：

根据数据库里面数据表的相关性进行拆分。 例如，用户表中既有用户的登录信息又有用户的基本信息，可以将用户表拆分成两个单独的表，甚至放到单独的库做分库。

简单来说垂直拆分是指数据表列的拆分，把一张列比较多的表拆分为多张表。 如下图所示，这样来说大家应该就更容易理解了。

垂直拆分的优点： 可以使得行数据变小，在查询时减少读取的Block数，减少I/O次数。此外，垂直分区可以简化表的结构，易于维护。

垂直拆分的缺点： 主键会出现冗余，需要管理冗余列，并会引起Join操作，可以通过在应用层进行Join来解决。此外，垂直分区会让事务变得更加复杂；
5. 水平分区：

保持数据表结构不变，通过某种策略存储数据分片。这样每一片数据分散到不同的表或者库中，达到了分布式的目的。 水平拆分可以支撑非常大的数据量。

水平拆分是指数据表行的拆分，表的行数超过200万行时，就会变慢，这时可以把一张的表的数据拆成多张表来存放。举个例子：我们可以将用户信息表拆分成多个用户信息表，这样就可以避免单一表数据量过大对性能造成影响。

水品拆分可以支持非常大的数据量。需要注意的一点是:分表仅仅是解决了单一表数据过大的问题，但由于表的数据还是在同一台机器上，其实对于提升MySQL并发能力没有什么意义，所以 水品拆分最好分库 。

水平拆分能够 支持非常大的数据量存储，应用端改造也少，但 分片事务难以解决 ，跨界点Join性能较差，逻辑复杂。《Java工程师修炼之道》的作者推荐 尽量不要对数据进行分片，因为拆分会带来逻辑、部署、运维的各种复杂度 ，一般的数据表在优化得当的情况下支撑千万以下的数据量是没有太大问题的。如果实在要分片，尽量选择客户端分片架构，这样可以减少一次和中间件的网络I/O。

下面补充一下数据库分片的两种常见方案：

* **客户端代理：** **分片逻辑在应用端，封装在jar包中，通过修改或者封装JDBC层来实现。** 当当网的 **Sharding-JDBC** 、阿里的TDDL是两种比较常用的实现。
* **中间件代理：** **在应用和数据中间加了一个代理层。分片逻辑统一维护在中间件服务中。** 我们现在谈的 **Mycat** 、360的Atlas、网易的DDB等等都是这种架构的实现。

五 Redis

关于 redis 必知必会的11个问题！后两个问题，暂未更新！如有需要，可以关注我的 Github 或者微信公众号：“Java面试通关手册”获取后续更新内容。

1. redis 简介
2. 为什么要用 redis /为什么要用缓存
3. 为什么要用 redis 而不用 map/guava 做缓存?
4. redis 和 memcached 的区别
5. redis 常见数据结构以及使用场景分析
6. redis 设置过期时间
7. redis 内存淘汰机制
8. redis 持久化机制（怎么保证 redis 挂掉之后再重启数据可以进行恢复）
9. 缓存雪崩和缓存穿透问题解决方案
10. 如何解决 Redis 的并发竞争 Key 问题
11. 如何保证缓存与数据库双写时的数据一致性？

5.1 redis 简介

简单来说 redis 就是一个数据库，不过与传统数据库不同的是 redis 的数据是存在内存中的，所以存写速度非常快，因此 redis 被广泛应用于缓存方向。另外，redis 也经常用来做分布式锁。redis 提供了多种数据类型来支持不同的业务场景。除此之外，redis 支持事务 、持久化、LUA脚本、LRU驱动事件、多种集群方案。

5.2 为什么要用 redis /为什么要用缓存

主要从“高性能”和“高并发”这两点来看待这个问题。

高性能：

假如用户第一次访问数据库中的某些数据。这个过程会比较慢，因为是从硬盘上读取的。将该用户访问的数据存在数缓存中，这样下一次再访问这些数据的时候就可以直接从缓存中获取了。操作缓存就是直接操作内存，所以速度相当快。如果数据库中的对应数据改变的之后，同步改变缓存中相应的数据即可！

高并发：

直接操作缓存能够承受的请求是远远大于直接访问数据库的，所以我们可以考虑把数据库中的部分数据转移到缓存中去，这样用户的一部分请求会直接到缓存这里而不用经过数据库。

5.3 为什么要用 redis 而不用 map/guava 做缓存?

下面的内容来自 segmentfault 一位网友的提问，地址：segmentfault.com/q/101000000…

缓存分为本地缓存和分布式缓存。以java为例，使用自带的map或者guava实现的是本地缓存，最主要的特点是轻量以及快速，生命周期随着 jvm 的销毁而结束，并且在多实例的情况下，每个实例都需要各自保存一份缓存，缓存不具有一致性。

使用 redis 或 memcached 之类的称为分布式缓存，在多实例的情况下，各实例共用一份缓存数据，缓存具有一致性。缺点是需要保持 redis 或 memcached服务的高可用，整个程序架构上较为复杂。

5.4 redis 和 memcached 的区别

对于 redis 和 memcached 我总结了下面四点。现在公司一般都是用 redis 来实现缓存，而且 redis 自身也越来越强大了！

1. redis支持更丰富的数据类型（支持更复杂的应用场景）：Redis不仅仅支持简单的k/v类型的数据，同时还提供list，set，zset，hash等数据结构的存储。memcache支持简单的数据类型，String。
2. Redis支持数据的持久化，可以将内存中的数据保持在磁盘中，重启的时候可以再次加载进行使用,而Memecache把数据全部存在内存之中。
3. 集群模式：memcached没有原生的集群模式，需要依靠客户端来实现往集群中分片写入数据；但是redis目前是原生支持cluster模式的，redis官方就是支持redis cluster集群模式的，比memcached来说要更好。
4. Memcached是多线程，非阻塞IO复用的网络模型；Redis使用单线程的多路 IO 复用模型。

来自网络上的一张图，这里分享给大家！

5.5 redis 常见数据结构以及使用场景分析

1. String

常用命令: set,get,decr,incr,mget 等。

String数据结构是简单的key-value类型，value其实不仅可以是String，也可以是数字。
常规key-value缓存应用；
常规计数：微博数，粉丝数等。

2.Hash

常用命令： hget,hset,hgetall 等。

Hash 是一个 string 类型的 field 和 value 的映射表，hash 特别适合用于存储对象，后续操作的时候，你可以直接仅仅修改这个对象中的某个字段的值。 比如我们可以Hash数据结构来存储用户信息，商品信息等等。比如下面我就用 hash 类型存放了我本人的一些信息：

1
2
3
4
5
6
7

复制代码key=JavaUser293847
value={
  “id”: 1,
  “name”: “SnailClimb”,
  “age”: 22,
  “location”: “Wuhan, Hubei”
}

3.List

常用命令: lpush,rpush,lpop,rpop,lrange等

list就是链表，Redis list的应用场景非常多，也是Redis最重要的数据结构之一，比如微博的关注列表，粉丝列表，消息列表等功能都可以用Redis的 list 结构来实现。

Redis list 的实现为一个双向链表，即可以支持反向查找和遍历，更方便操作，不过带来了部分额外的内存开销。

另外可以通过 lrange 命令，就是从某个元素开始读取多少个元素，可以基于 list 实现分页查询，这个很棒的一个功能，基于 redis 实现简单的高性能分页，可以做类似微博那种下拉不断分页的东西（一页一页的往下走），性能高。

4.Set

常用命令：
sadd,spop,smembers,sunion 等

set对外提供的功能与list类似是一个列表的功能，特殊之处在于set是可以自动排重的。

当你需要存储一个列表数据，又不希望出现重复数据时，set是一个很好的选择，并且set提供了判断某个成员是否在一个set集合内的重要接口，这个也是list所不能提供的。可以基于 set 轻易实现交集、并集、差集的操作。

比如：在微博应用中，可以将一个用户所有的关注人存在一个集合中，将其所有粉丝存在一个集合。Redis可以非常方便的实现如共同关注、共同粉丝、共同喜好等功能。这个过程也就是求交集的过程，具体命令如下：

1

复制代码sinterstore key1 key2 key3     将交集存在key1内

5.Sorted Set

常用命令： zadd,zrange,zrem,zcard等

和set相比，sorted set增加了一个权重参数score，使得集合中的元素能够按score进行有序排列。

举例： 在直播系统中，实时排行信息包含直播间在线用户列表，各种礼物排行榜，弹幕消息（可以理解为按消息维度的消息排行榜）等信息，适合使用 Redis 中的 SortedSet 结构进行存储。

5.6 redis 设置过期时间

Redis中有个设置时间过期的功能，即对存储在 redis 数据库中的值可以设置一个过期时间。作为一个缓存数据库，这是非常实用的。如我们一般项目中的token或者一些登录信息，尤其是短信验证码都是有时间限制的，按照传统的数据库处理方式，一般都是自己判断过期，这样无疑会严重影响项目性能。

我们set key的时候，都可以给一个expire time，就是过期时间，通过过期时间我们可以指定这个 key 可以存货的时间。

如果假设你设置一个一批 key 只能存活1个小时，那么接下来1小时后，redis是怎么对这批key进行删除的？

定期删除+惰性删除。

通过名字大概就能猜出这两个删除方式的意思了。

• 定期删除：redis默认是每隔 100ms 就随机抽取一些设置了过期时间的key，检查其是否过期，如果过期就删除。注意这里是随机抽取的。为什么要随机呢？你想一想假如 redis 存了几十万个 key ，每隔100ms就遍历所有的设置过期时间的 key 的话，就会给 CPU 带来很大的负载！
• 惰性删除 ：定期删除可能会导致很多过期 key 到了时间并没有被删除掉。所以就有了惰性删除。假如你的过期 key，靠定期删除没有被删除掉，还停留在内存里，除非你的系统去查一下那个 key，才会被redis给删除掉。这就是所谓的惰性删除，也是够懒的哈！

但是仅仅通过设置过期时间还是有问题的。我们想一下：如果定期删除漏掉了很多过期 key，然后你也没及时去查，也就没走惰性删除，此时会怎么样？如果大量过期key堆积在内存里，导致redis内存块耗尽了。怎么解决这个问题呢？

redis 内存淘汰机制。

5.7 redis 内存淘汰机制（MySQL里有2000w数据，Redis中只存20w的数据，如何保证Redis中的数据都是热点数据？）

redis 配置文件 redis.conf 中有相关注释，我这里就不贴了，大家可以自行查阅或者通过这个网址查看： download.redis.io/redis-stabl…

redis 提供 6种数据淘汰策略：

1. volatile-lru：从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰
2. volatile-ttl：从已设置过期时间的数据集（server.db[i].expires）中挑选将要过期的数据淘汰
3. volatile-random：从已设置过期时间的数据集（server.db[i].expires）中任意选择数据淘汰
4. allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key（这个是最常用的）.
5. allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰
6. no-enviction：禁止驱逐数据，也就是说当内存不足以容纳新写入数据时，新写入操作会报错。这个应该没人使用吧！

备注： 关于 redis 设置过期时间以及内存淘汰机制，我这里只是简单的总结一下，后面会专门写一篇文章来总结！

5.8 redis 持久化机制（怎么保证 redis 挂掉之后再重启数据可以进行恢复）

很多时候我们需要持久化数据也就是将内存中的数据写入到硬盘里面，大部分原因是为了之后重用数据（比如重启机器、机器故障之后回复数据），或者是为了防止系统故障而将数据备份到一个远程位置。

Redis不同于Memcached的很重一点就是，Redis支持持久化，而且支持两种不同的持久化操作。Redis的一种持久化方式叫快照（snapshotting，RDB）,另一种方式是只追加文件（append-only file,AOF）.这两种方法各有千秋，下面我会详细这两种持久化方法是什么，怎么用，如何选择适合自己的持久化方法。

快照（snapshotting）持久化（RDB）

Redis可以通过创建快照来获得存储在内存里面的数据在某个时间点上的副本。Redis创建快照之后，可以对快照进行备份，可以将快照复制到其他服务器从而创建具有相同数据的服务器副本（Redis主从结构，主要用来提高Redis性能），还可以将快照留在原地以便重启服务器的时候使用。

快照持久化是Redis默认采用的持久化方式，在redis.conf配置文件中默认有此下配置：

1
2
3
4
5
6

复制代码
save 900 1              #在900秒(15分钟)之后，如果至少有1个key发生变化，Redis就会自动触发BGSAVE命令创建快照。

save 300 10            #在300秒(5分钟)之后，如果至少有10个key发生变化，Redis就会自动触发BGSAVE命令创建快照。

save 60 10000        #在60秒(1分钟)之后，如果至少有10000个key发生变化，Redis就会自动触发BGSAVE命令创建快照。

AOF（append-only file）持久化

与快照持久化相比，AOF持久化 的实时性更好，因此已成为主流的持久化方案。默认情况下Redis没有开启AOF（append only file）方式的持久化，可以通过appendonly参数开启：

1

复制代码appendonly yes

开启AOF持久化后每执行一条会更改Redis中的数据的命令，Redis就会将该命令写入硬盘中的AOF文件。AOF文件的保存位置和RDB文件的位置相同，都是通过dir参数设置的，默认的文件名是appendonly.aof。

在Redis的配置文件中存在三种不同的 AOF 持久化方式，它们分别是：

1
2
3

复制代码appendfsync always     #每次有数据修改发生时都会写入AOF文件,这样会严重降低Redis的速度
appendfsync everysec  #每秒钟同步一次，显示地将多个写命令同步到硬盘
appendfsync no      #让操作系统决定何时进行同步

为了兼顾数据和写入性能，用户可以考虑 appendfsync everysec选项 ，让Redis每秒同步一次AOF文件，Redis性能几乎没受到任何影响。而且这样即使出现系统崩溃，用户最多只会丢失一秒之内产生的数据。当硬盘忙于执行写入操作的时候，Redis还会优雅的放慢自己的速度以便适应硬盘的最大写入速度。

补充内容：AOF 重写

AOF重写可以产生一个新的AOF文件，这个新的AOF文件和原有的AOF文件所保存的数据库状态一样，但体积更小。

AOF重写是一个有歧义的名字，该功能是通过读取数据库中的键值对来实现的，程序无须对现有AOF文件进行任伺读入、分析或者写人操作。

在执行 BGREWRITEAOF 命令时，Redis 服务器会维护一个 AOF 重写缓冲区，该缓冲区会在子进程创建新AOF文件期间，记录服务器执行的所有写命令。当子进程完成创建新AOF文件的工作之后，服务器会将重写缓冲区中的所有内容追加到新AOF文件的末尾，使得新旧两个AOF文件所保存的数据库状态一致。最后，服务器用新的AOF文件替换旧的AOF文件，以此来完成AOF文件重写操作

更多内容可以查看我的这篇文章：

• github.com/Snailclimb/…

5.9 缓存雪崩和缓存穿透问题解决方案

缓存雪崩

简介：缓存同一时间大面积的失效，所以，后面的请求都会落到数据库上，造成数据库短时间内承受大量请求而崩掉。

解决办法（中华石杉老师在他的视频中提到过）：

• 事前：尽量保证整个 redis 集群的高可用性，发现机器宕机尽快补上。选择合适的内存淘汰策略。
• 事中：本地ehcache缓存 + hystrix限流&降级，避免MySQL崩掉
• 事后：利用 redis 持久化机制保存的数据尽快恢复缓存

缓存穿透

简介：一般是黑客故意去请求缓存中不存在的数据，导致所有的请求都落到数据库上，造成数据库短时间内承受大量请求而崩掉。

解决办法： 有很多种方法可以有效地解决缓存穿透问题，最常见的则是采用布隆过滤器，将所有可能存在的数据哈希到一个足够大的bitmap中，一个一定不存在的数据会被 这个bitmap拦截掉，从而避免了对底层存储系统的查询压力。另外也有一个更为简单粗暴的方法（我们采用的就是这种），如果一个查询返回的数据为空（不管是数 据不存在，还是系统故障），我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟。

参考：

• blog.csdn.net/zeb_perfect…enter link description here

5.10 如何解决 Redis 的并发竞争 Key 问题

所谓 Redis 的并发竞争 Key 的问题也就是多个系统同时对一个 key 进行操作，但是最后执行的顺序和我们期望的顺序不同，这样也就导致了结果的不同！

推荐一种方案：分布式锁（zookeeper 和 redis 都可以实现分布式锁）。（如果不存在 Redis 的并发竞争 Key 问题，不要使用分布式锁，这样会影响性能）

基于zookeeper临时有序节点可以实现的分布式锁。大致思想为：每个客户端对某个方法加锁时，在zookeeper上的与该方法对应的指定节点的目录下，生成一个唯一的瞬时有序节点。 判断是否获取锁的方式很简单，只需要判断有序节点中序号最小的一个。 当释放锁的时候，只需将这个瞬时节点删除即可。同时，其可以避免服务宕机导致的锁无法释放，而产生的死锁问题。完成业务流程后，删除对应的子节点释放锁。

在实践中，当然是从以可靠性为主。所以首推Zookeeper。

参考：

• www.jianshu.com/p/8bddd381d…

5.11 如何保证缓存与数据库双写时的数据一致性？

你只要用缓存，就可能会涉及到缓存与数据库双存储双写，你只要是双写，就一定会有数据一致性的问题，那么你如何解决一致性问题？

一般来说，就是如果你的系统不是严格要求缓存+数据库必须一致性的话，缓存可以稍微的跟数据库偶尔有不一致的情况，最好不要做这个方案，读请求和写请求串行化，串到一个内存队列里去，这样就可以保证一定不会出现不一致的情况

串行化之后，就会导致系统的吞吐量会大幅度的降低，用比正常情况下多几倍的机器去支撑线上的一个请求。

参考：

• Java工程师面试突击第1季（可能是史上最好的Java面试突击课程）-中华石杉老师。视频地址见下面！
  • 链接： pan.baidu.com/s/18pp6g1xK…
  • 密码：5i58

六 Java

6.1 Java 基础知识

重载和重写的区别

重载： 发生在同一个类中，方法名必须相同，参数类型不同、个数不同、顺序不同，方法返回值和访问修饰符可以不同，发生在编译时。   

重写： 发生在父子类中，方法名、参数列表必须相同，返回值范围小于等于父类，抛出的异常范围小于等于父类，访问修饰符范围大于等于父类；如果父类方法访问修饰符为 private 则子类就不能重写该方法。

String 和 StringBuffer、StringBuilder 的区别是什么？String 为什么是不可变的？

可变性  

简单的来说：String 类中使用 final 关键字字符数组保存字符串，private final char value[]，所以 String 对象是不可变的。而StringBuilder 与 StringBuffer 都继承自 AbstractStringBuilder 类，在 AbstractStringBuilder 中也是使用字符数组保存字符串char[]value 但是没有用 final 关键字修饰，所以这两种对象都是可变的。

StringBuilder 与 StringBuffer 的构造方法都是调用父类构造方法也就是 AbstractStringBuilder 实现的，大家可以自行查阅源码。

AbstractStringBuilder.java

1
2
3
4
5
6
7
8

复制代码abstract class AbstractStringBuilder implements Appendable, CharSequence {
    char[] value;
    int count;
    AbstractStringBuilder() {
    }
    AbstractStringBuilder(int capacity) {
        value = new char[capacity];
    }

线程安全性

String 中的对象是不可变的，也就可以理解为常量，线程安全。AbstractStringBuilder 是 StringBuilder 与 StringBuffer 的公共父类，定义了一些字符串的基本操作，如 expandCapacity、append、insert、indexOf 等公共方法。StringBuffer 对方法加了同步锁或者对调用的方法加了同步锁，所以是线程安全的。StringBuilder 并没有对方法进行加同步锁，所以是非线程安全的。   

性能

每次对 String 类型进行改变的时候，都会生成一个新的 String 对象，然后将指针指向新的 String 对象。StringBuffer 每次都会对 StringBuffer 对象本身进行操作，而不是生成新的对象并改变对象引用。相同情况下使用 StirngBuilder 相比使用 StringBuffer 仅能获得 10%~15% 左右的性能提升，但却要冒多线程不安全的风险。

对于三者使用的总结：

1. 操作少量的数据 = String
2. 单线程操作字符串缓冲区下操作大量数据 = StringBuilder
3. 多线程操作字符串缓冲区下操作大量数据 = StringBuffer

自动装箱与拆箱

装箱：将基本类型用它们对应的引用类型包装起来；

拆箱：将包装类型转换为基本数据类型；

== 与 equals

== : 它的作用是判断两个对象的地址是不是相等。即，判断两个对象是不是同一个对象。(基本数据类型==比较的是值，引用数据类型==比较的是内存地址)

equals() : 它的作用也是判断两个对象是否相等。但它一般有两种使用情况：

• 情况1：类没有覆盖 equals() 方法。则通过 equals() 比较该类的两个对象时，等价于通过“==”比较这两个对象。
• 情况2：类覆盖了 equals() 方法。一般，我们都覆盖 equals() 方法来两个对象的内容相等；若它们的内容相等，则返回 true (即，认为这两个对象相等)。

举个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复制代码public class test1 {
    public static void main(String[] args) {
        String a = new String("ab"); // a 为一个引用
        String b = new String("ab"); // b为另一个引用,对象的内容一样
        String aa = "ab"; // 放在常量池中
        String bb = "ab"; // 从常量池中查找
        if (aa == bb) // true
            System.out.println("aa==bb");
        if (a == b) // false，非同一对象
            System.out.println("a==b");
        if (a.equals(b)) // true
            System.out.println("aEQb");
        if (42 == 42.0) { // true
            System.out.println("true");
        }
    }
}

说明：

• String 中的 equals 方法是被重写过的，因为 object 的 equals 方法是比较的对象的内存地址，而 String 的 equals 方法比较的是对象的值。
• 当创建 String 类型的对象时，虚拟机会在常量池中查找有没有已经存在的值和要创建的值相同的对象，如果有就把它赋给当前引用。如果没有就在常量池中重新创建一个 String 对象。

关于 final 关键字的一些总结

final关键字主要用在三个地方：变量、方法、类。

1. 对于一个final变量，如果是基本数据类型的变量，则其数值一旦在初始化之后便不能更改；如果是引用类型的变量，则在对其初始化之后便不能再让其指向另一个对象。
2. 当用final修饰一个类时，表明这个类不能被继承。final类中的所有成员方法都会被隐式地指定为final方法。
3. 使用final方法的原因有两个。第一个原因是把方法锁定，以防任何继承类修改它的含义；第二个原因是效率。在早期的Java实现版本中，会将final方法转为内嵌调用。但是如果方法过于庞大，可能看不到内嵌调用带来的任何性能提升（现在的Java版本已经不需要使用final方法进行这些优化了）。类中所有的private方法都隐式地指定为fianl。

6.2 Java 集合框架

Arraylist 与 LinkedList 异同

• 1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
• 2. 底层数据结构： Arraylist 底层使用的是Object数组；LinkedList 底层使用的是双向循环链表数据结构；
• 3. 插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
• 4. 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而ArrayList 实现了RandmoAccess 接口，所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
• 5. 内存空间占用： ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

补充：数据结构基础之双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表，如下图所示，同时下图也是LinkedList 底层使用的是双向循环链表数据结构。

ArrayList 与 Vector 区别

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。

Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。

HashMap的底层实现

①JDK1.8之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的时数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。

1
2
3
4
5
6
7

复制代码    static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

对比一下 JDK1.7的 HashMap 的 hash 方法源码.

1
2
3
4
5
6
7
8

复制代码static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

②JDK1.8之后

相比于之前的版本， JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

推荐阅读：

• 《Java 8系列之重新认识HashMap》 ：zhuanlan.zhihu.com/p/21673805

HashMap 和 Hashtable 的区别

1. 线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
2. 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
3. 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛出 NullPointerException。
4. 初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。
5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap 的长度为什么是2的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648到2147483648，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

HashMap 多线程操作导致死循环问题

在多线程下，进行 put 操作会导致 HashMap 死循环，原因在于 HashMap 的扩容 resize()方法。由于扩容是新建一个数组，复制原数据到数组。由于数组下标挂有链表，所以需要复制链表，但是多线程操作有可能导致环形链表。复制链表过程如下:

以下模拟2个线程同时扩容。假设，当前 HashMap 的空间为2（临界值为1），hashcode 分别为 0 和 1，在散列地址 0 处有元素 A 和 B，这时候要添加元素 C，C 经过 hash 运算，得到散列地址为 1，这时候由于超过了临界值，空间不够，需要调用 resize 方法进行扩容，那么在多线程条件下，会出现条件竞争，模拟过程如下：

线程一：读取到当前的 HashMap 情况，在准备扩容时，线程二介入

线程二：读取 HashMap，进行扩容

线程一：继续执行

这个过程为，先将 A 复制到新的 hash 表中，然后接着复制 B 到链头（A 的前边：B.next=A），本来 B.next=null，到此也就结束了（跟线程二一样的过程），但是，由于线程二扩容的原因，将 B.next=A，所以，这里继续复制A，让 A.next=B，由此，环形链表出现：B.next=A; A.next=B

HashSet 和 HashMap 区别

如果你看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone() 方法、writeObject()方法、readObject()方法是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。）

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

• 底层数据结构： JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
• 实现线程安全的方式（重要）： ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

两者的对比图：

图片来源：www.cnblogs.com/chengxiao/p…

HashTable:

JDK1.7的ConcurrentHashMap：

JDK1.8的ConcurrentHashMap（TreeBin: 红黑二叉树节点
Node: 链表节点）：

ConcurrentHashMap线程安全的具体实现方式/底层具体实现

①JDK1.7（上面有示意图）

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HahEntry 数组结构组成。

Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

1
2

复制代码static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。

②JDK1.8 （上面有示意图）

ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。

synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。

集合框架底层数据结构总结

Collection

1.List

• Arraylist： Object数组
• Vector： Object数组
• LinkedList： 双向循环链表

2.Set

• HashSet（无序，唯一）: 基于 HashMap 实现的，底层采用 HashMap 来保存元素
• LinkedHashSet： LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。
• TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树。)

Map

• HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
• LinkedHashMap: LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》
• HashTable: 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
• TreeMap: 红黑树（自平衡的排序二叉树）

6.3 Java多线程

关于 Java多线程，在面试的时候，问的比较多的就是①悲观锁和乐观锁（ 具体可以看我的这篇文章：面试必备之乐观锁与悲观锁）、②synchronized和lock区别以及volatile和synchronized的区别，③可重入锁与非可重入锁的区别、④多线程是解决什么问题的、⑤线程池解决什么问题、⑥线程池的原理、⑦线程池使用时的注意事项、⑧AQS原理、⑨ReentranLock源码，设计原理，整体过程 等等问题。

  面试官在多线程这一部分很可能会问你有没有在项目中实际使用多线程的经历。所以，如果你在你的项目中有实际使用Java多线程的经历 的话，会为你加分不少哦！

6.4 Java虚拟机

  关于Java虚拟机，在面试的时候一般会问的大多就是①Java内存区域、②虚拟机垃圾算法、③虚拟机垃圾收集器、④JVM内存管理、⑤JVM调优这些问题了。
  
具体可以查看我的这两篇文章：

• github.com/Snailclimb/…
• github.com/Snailclimb/…

6.5 设计模式

设计模式比较常见的就是让你手写一个单例模式（注意单例模式的几种不同的实现方法）或者让你说一下某个常见的设计模式在你的项目中是如何使用的，另外面试官还有可能问你抽象工厂和工厂方法模式的区别、工厂模式的思想这样的问题。

建议把代理模式、观察者模式、（抽象）工厂模式好好看一下，这三个设计模式也很重要。

七 数据结构

  数据结构比较常问的就是：二叉树、红黑树（很可能让你手绘一个红黑树出来哦！）、二叉查找树（BST）、平衡二叉树（Self-balancing binary search tree）、B-树，B+树与B*树的优缺点比较、 LSM 树这些知识点。

  数据结构很重要，而且学起来也相对要难一些。建议学习数据结构一定要循序渐进的来，一步一个脚印的走好。一定要搞懂原理，最好自己能用代码实现一遍。

八 算法

  常见的加密算法、排序算法都需要自己提前了解一下，排序算法最好自己能够独立手写出来。

  我觉得面试中最刺激、最有压力或者说最有挑战的一个环节就是手撕算法了。面试中大部分算法题目都是来自于Leetcode、剑指offer上面，建议大家可以每天挤出一点时间刷一下算法题。

推荐两个刷题必备网站：

LeetCode：

• LeetCode（中国）官网
• 如何高效地使用 LeetCode

牛客网：

• 牛客网首页

8.1 举个栗子（手写快排）

面试官可能会问你，了解哪些排序方法啊？除了冒泡排序和选择排序能不能给我手写一个其他的排序算法。或者面试官可能会直接问你：“能不能给我手写一个快排出来？”。

快排的基本思想： 通过选择的参考值将待排序记录分割成独立的两部分，一部分全小于选取的参考值，另一部分全大于选取的参考值。对分割之后的部分再进行同样的操作直到无法再进行该操作位置(可以使用递归)。

下面是我写的一个简单的快排算法，我选择的参考值是数组的第一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

复制代码import java.util.Arrays;

public class QuickSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] num = { 1, 3, 4, 8, 5, 10, 22, 15, 16 };
		QuickSort.quickSort(num, 0, num.length - 1);
		System.out.println(Arrays.toString(num));
	}

	public static void quickSort(int[] a, int start, int end) {
		// 该值定义了从哪个位置开始分割数组
		int ref;
		if (start < end) {
			// 调用partition方法对数组进行排序
			ref = partition(a, start, end);
			// 对分割之后的两个数组继续进行排序
			quickSort(a, start, ref - 1);
			quickSort(a, ref + 1, end);
		}
	}

	/**
	 * 选定参考值对给定数组进行一趟快速排序
	 * 
	 * @param a
	 *            数组
	 * @param start
	 *            （切分）每个数组的第一个的元素的位置
	 * @param end
	 *            （切分）每个数组的最后一个的元素位置
	 * @return 下一次要切割数组的位置
	 */
	public static int partition(int[] a, int start, int end) {
		// 取数组的第一个值作为参考值（关键数据）
		int refvalue = a[start];
		// 从数组的右边开始往左遍历，直到找到小于参考值的元素
		while (start < end) {
			while (end > start && a[end] >= refvalue) {
				end--;
			}
			// 将元素直接赋予给左边第一个元素，即pivotkey所在的位置
			a[start] = a[end];

			// 从序列的左边边开始往右遍历，直到找到大于基准值的元素
			while (end > start && a[start] <= refvalue) {
				start++;
			}
			a[end] = a[start];
			return end;
		}
		// 最后的start是基准值所在的位置
		a[start] = refvalue;
		return start;
	}

}

时间复杂度分析：

• 在最优的情况下，Partition每次都划分得很均匀，快速排序算法的时间复杂度为O(nlogn)。
• 最糟糕情况下的快排，当待排序的序列为正序或逆序排列时，时间复杂度为O(n^2)。

空间复杂度分析：

• 最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)
• 最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。

一种简单优化的方式：

三向切分快速排序 ：核心思想就是将待排序的数据分为三部分,左边都小于比较值,右边都大于比较值,中间的数和比较值相等.三向切分快速排序的特性就是遇到和比较值相同时,不进行数据交换, 这样对于有大量重复数据的排序时,三向切分快速排序算法就会优于普通快速排序算法,但由于它整体判断代码比普通快速排序多一点,所以对于常见的大量非重复数据,它并不能比普通快速排序多大多的优势 。

九 Spring

  Spring一般是不可避免的，如果你的简历上注明了你会Spring Boot或者Spring Cloud的话，那么面试官也可能会同时问你这两个技术,比如他可能会问你springboot和spring的区别。 所以，一定要谨慎对待写在简历上的东西，一定要对简历上的东西非常熟悉。

  另外，AOP实现原理、动态代理和静态代理、Spring IOC的初始化过程、IOC原理、自己怎么实现一个IOC容器？ 这些东西都是经常会被问到的。

9.1 Spring Bean 的作用域

9.2 Spring 事务中的隔离级别

TransactionDefinition 接口中定义了五个表示隔离级别的常量：

• TransactionDefinition.ISOLATION_DEFAULT: 使用后端数据库默认的隔离级别，Mysql 默认采用的 REPEATABLE_READ隔离级别 Oracle 默认采用的 READ_COMMITTED隔离级别.
• TransactionDefinition.ISOLATION_READ_UNCOMMITTED: 最低的隔离级别，允许读取尚未提交的数据变更，可能会导致脏读、幻读或不可重复读
• TransactionDefinition.ISOLATION_READ_COMMITTED: 允许读取并发事务已经提交的数据，可以阻止脏读，但是幻读或不可重复读仍有可能发生
• TransactionDefinition.ISOLATION_REPEATABLE_READ: 对同一字段的多次读取结果都是一致的，除非数据是被本身事务自己所修改，可以阻止脏读和不可重复读，但幻读仍有可能发生。
• TransactionDefinition.ISOLATION_SERIALIZABLE: 最高的隔离级别，完全服从ACID的隔离级别。所有的事务依次逐个执行，这样事务之间就完全不可能产生干扰，也就是说，该级别可以防止脏读、不可重复读以及幻读。但是这将严重影响程序的性能。通常情况下也不会用到该级别。

9.3 Spring 事务中的事务传播行为

支持当前事务的情况：

• TransactionDefinition.PROPAGATION_REQUIRED： 如果当前存在事务，则加入该事务；如果当前没有事务，则创建一个新的事务。
• TransactionDefinition.PROPAGATION_SUPPORTS： 如果当前存在事务，则加入该事务；如果当前没有事务，则以非事务的方式继续运行。
• TransactionDefinition.PROPAGATION_MANDATORY： 如果当前存在事务，则加入该事务；如果当前没有事务，则抛出异常。（mandatory：强制性）

不支持当前事务的情况：

• TransactionDefinition.PROPAGATION_REQUIRES_NEW： 创建一个新的事务，如果当前存在事务，则把当前事务挂起。
• TransactionDefinition.PROPAGATION_NOT_SUPPORTED： 以非事务方式运行，如果当前存在事务，则把当前事务挂起。
• TransactionDefinition.PROPAGATION_NEVER： 以非事务方式运行，如果当前存在事务，则抛出异常。

其他情况：

• TransactionDefinition.PROPAGATION_NESTED： 如果当前存在事务，则创建一个事务作为当前事务的嵌套事务来运行；如果当前没有事务，则该取值等价于TransactionDefinition.PROPAGATION_REQUIRED。

9.4 AOP

AOP思想的实现一般都是基于 代理模式 ，在JAVA中一般采用JDK动态代理模式，但是我们都知道，JDK动态代理模式只能代理接口而不能代理类。因此，Spring AOP 会这样子来进行切换，因为Spring AOP 同时支持 CGLIB、ASPECTJ、JDK动态代理。

• 如果目标对象的实现类实现了接口，Spring AOP 将会采用 JDK 动态代理来生成 AOP 代理类；
• 如果目标对象的实现类没有实现接口，Spring AOP 将会采用 CGLIB 来生成 AOP 代理类——不过这个选择过程对开发者完全透明、开发者也无需关心。

这部分内容可以查看下面这几篇文章：

• www.jianshu.com/p/fe8d1e8bd…
• www.cnblogs.com/puyangsky/p…
• juejin.cn/post/684490…

9.5 IOC

Spring IOC的初始化过程：

IOC源码阅读

• javadoop.com/post/spring…

十 实际场景题

  我觉得实际场景题就是对你的知识运用能力以及思维能力的考察。建议大家在平时养成多思考问题的习惯，这样面试的时候碰到这样的问题就不至于慌了。另外，如果自己实在不会就给面试官委婉的说一下，面试官可能会给你提醒一下。切忌不懂装懂，乱答一气。
  
  面试官可能会问你类似这样的问题：①假设你要做一个银行app，有可能碰到多个人同时向一个账户打钱的情况，有可能碰到什么问题，如何解决（锁）②你是怎么保证你的代码质量和正确性的？③下单过程中是下订单减库存还是付款减库存，分析一下两者的优劣；④同时给10万个人发工资，怎么样设计并发方案，能确保在1分钟内全部发完。⑤如果让你设计xxx系统的话，你会如何设计。   

写在最后

最后，再强调几点：

1. 一定要谨慎对待写在简历上的东西，一定要对简历上的东西非常熟悉。因为一般情况下，面试官都是会根据你的简历来问的；
2. 能有一个上得了台面的项目也非常重要，这很可能是面试官会大量发问的地方，所以在面试之前好好回顾一下自己所做的项目；
3. 和面试官聊基础知识比如设计模式的使用、多线程的使用等等，可以结合具体的项目场景或者是自己在平时是如何使用的；
4. 注意自己开源的Github项目，面试官可能会挖你的Github项目提问；
5. 建议提前了解一下自己想要面试的公司的价值观，判断一下自己究竟是否适合这个公司。

另外，我个人觉得面试也像是一场全新的征程，失败和胜利都是平常之事。所以，劝各位不要因为面试失败而灰心、丧失斗志。也不要因为面试通过而沾沾自喜，等待你的将是更美好的未来，继续加油！

初次之外，笔主也在这里给自己挖一个坑，关于 dubbo、zookeeper 等内容我会在后续做一个系统总结。保证大家看了之后，一定有收获！

最后，附上征文链接。

还有三个本次活动的合作伙伴：

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

作者 ：架构小黑 | 微信公众号：架构师之巅

一、背景

随着公司业务增长，如果每天1000多万笔订单的话，3个月将有约10亿的订单量，之前数据库采用单库单表的形式已经不满足于业务需求，数据库改造迫在眉睫。

二、订单数据如何划分

我们可以将订单数据划分成两大类型：分别是热数据和冷数据。

• 热数据：3个月内的订单数据，查询实时性较高;
• 冷数据A：3个月 ~ 12个月前的订单数据，查询频率不高;
• 冷数据B：1年前的订单数据，几乎不会查询，只有偶尔的查询需求;

可能这里有个疑惑为什么要将冷数据分成两类，因为根据实际场景需求，用户基本不会去查看1年前的数据，如果将这部分数据还存储在db中，那么成本会非常高，而且也不便于维护。另外如果真遇到有个别用户需要查看1年前的订单信息，可以让用户走离线数据查看。

对于这三类数据的存储，目前规划如下：

• 热数据： 使用mysql进行存储，当然需要分库分表；
• 冷数据A: 对于这类数据可以存储在ES中，利用搜索引擎的特性基本上也可以做到比较快的查询；
• 冷数据B: 对于这类不经常查询的数据，可以存放到Hive中；

三、MySql 如何分库分表

3.1、按业务拆分

在业务初始阶段，为了加快应用上线和快速迭代，很多应用都采用集中式的架构。但是随着业务系统的扩大，系统匾额越来越复杂，越来越难以维护，开发效率变得越来越低，并且对资源的消耗也变得越来越大，通过硬件提高系统性能的成本会变得更高。

通常一般的电商平台，包含了用户、商品、订单等几大模块，简单的做法是在同一个库中分别建4张表，如下图所示：

但是随着业务的提升，将所有业务都放在一个库中已经变得越来越难以维护，因此我们建议，将不同业务放在不同的库中，如下图所示：

由图中我们可以看出，我们将不同的业务放到不同的库中，将原来所有压力由同一个库中分散到不同的库中，提升了系统的吞吐量。

3.2、分库与分表

我们知道每台机器无论配置多么好它都有自身的物理上限，所以当我们应用已经能触及或远远超出单台机器的某个上限的时候，我们惟有寻找别的机器的帮助或者继续升级的我们的硬件，但常见的方案还是通过添加更多的机器来共同承担压力。

我们还得考虑当我们的业务逻辑不断增长，我们的机器能不能通过线性增长就能满足需求？因此，使用数据库的分库分表，能够立竿见影的提升系统的性能，关于为什么要使用数据库的分库分表的其他原因这里不再赘述，主要讲具体的实现策略。

（1）分表策略

我们以订单表为例，在订单表中，订单id肯定是不可重复的，因此将该字段当做shard key 是非常适合的,其他表类似。假设订单表的字段如下：

1create table order(2 order_id bigint(11) ,3

我们假设预估单个库需要分配100个表满足我们的业务需求，我们可以简单的取模计算出订单在哪个子表中，例如： order_id % 100,

这时候可能会有人问了，如果我根据order_id 进行分表规则，但是我想根据user_id 查询相应的订单，不是定位不到哪个子表了吗，的确是这样，一旦确定shard key，就只能根据shard key定位到子表进而查询该子表下的数据；如果确实想根据user_id 去查询相关订单，那应该将shard key设置为user_id, 那分表规则也相应的变更为： user_id % 100;

（1）分库实现策略

数据库分表能够解决单表数据量很大的时候数据查询的效率问题，但是无法给数据库的并发操作带来效率上的提高，因为分表的实质还是在一个数据库上进行的操作，很容易受数据库IO性能的限制。

因此，如何将数据库IO性能的问题平均分配出来，很显然将数据进行分库操作可以很好地解决单台数据库的性能问题。

分库策略与分表策略的实现很相似，最简单的都是可以通过取模的方式进行路由。

我们还是以order表举例，

例如：order_id % 库容量,

如果order_id 不是整数类型，可以先hash 在进行取模，

例如： hash(order_id) % 库容量

（3）分库分表结合使用策略

数据库分表可以解决单表海量数据的查询性能问题，分库可以解决单台数据库的并发访问压力问题。有时候，我们需要同时考虑这两个问题，因此，我们既需要对单表进行分表操作，还需要进行分库操作，以便同时扩展系统的并发处理能力和提升单表的查询性能，就是我们使用到的分库分表。

如果使用分库分表结合使用的话，不能简单进行order_id 取模操作，需要加一个中间变量用来打散到不同的子表，公式如下：

中间变量　＝ shard key %（库数量*单个库的表数量）;2库序号　＝　取整（中间变量／单

例如：数据库有10个，每一个库中有100个数据表，用户的order_id＝1001，按照上述的路由策略，可得：

这样的话，对于order_id＝1001，将被路由到第1个数据库的第2个表中(索引0 代表1，依次类推)。

三、整体架构设计

从图中我们将请求分成read和write请求，write请求比较简单，就是根据分库分表规则写入db即可。

对于read请求，我们需要计算出查询的是热数据还是冷数据，一般order_id生成规则如下，“商户所在地区号+时间戳+随机数”，我们可以根据时间戳计算出查询的是热数据还是冷数据，（当然具体业务需要具体对待，这里不再详细阐述）

另外架构图中的冷数据指的是3个月~12个月前的数据，如果是查询一年前的数据，建议直接离线查hive即可。

图中有一个定时Job，主要用来定时迁移订单数据，需要将冷数据分别迁移到ES和hive中。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

❈

在Java领域，动态代理应用非常广泛，特别是流行的Spring/MyBatis等框架。JDK本身是有实现动态代理技术的，不过要求被代理的类必须实现接口，不过cglib对这一不足进行了有效补充。本篇博客将涉及2个话题：

第一，JDK动态代理的实现原理，带你探索动态代理的实质面目；

第二，自己动手写代码去实现JDK动态代理，去创造世界！

❈

JDK动态代理

❈

先写一个例子，感性认识下动态代理~

❈

业务接口：

interface

业务实现类：

interface impl

业务处理类：

Handler

测试类：

test

运行结果：

result

❈

在JDK动态代理中涉及如下角色：

业务接口Interface、业务实现类target、业务处理类Handler、JVM在内存中生成的动态代理类$Proxy0

❈

动态代理原理图：

动态代理的真实面目

❈

说白了，动态代理的过程是这样的：

第一：Proxy通过传递给它的参数（interfaces/invocationHandler）生成代理类$Proxy0；

第二：Proxy通过传递给它的参数（ClassLoader）来加载生成的代理类$Proxy0的字节码文件；

❈

我们来看看上面例子中生成的$Proxy0的模样：

$Proxy0

❈

首先，$Proxy是实现了我们的业务接口（Man）的，所以客户端显然可以调用业务接口的方法。

其次，注意到$Proxy是继承自Proxy，并通过构造方法将业务处理类传入给父类Proxy进行初始化。（实质上，你可以看看源码，在Proxy中存在protected InvocationHandler h;）

❈

初始化Proxy

findObject

❈

很明显，我们看到了业务接口的方法是如何被调用的：

最终都是回调业务处理类（具体的Handler）的invoke方法完成调用！

❈

手写代码实现JDK动态代理

❈

在上面，我们已经分析了JDK动态代理的整个调用过程，接下来，我们就来手写实现它吧！

❈

先来看一眼图：

手写实现JDK动态代理

自定义InvocationHandler：

MyInvocationHandler

实现MyInvocationHandler的业务处理Handler：

MyHandler

自定义类加载器MyClassLoader：

MyClassLoader

❈

为什么要定义一个自定义的类加载器呢？它的作用是什么呢？

要知道，我们是想手写JDK动态代理，那么我们将自己在内存中生成动态代理类，那么我们如何加载呢？这时候，就可以利用自定义的类加载器做到！

上述代码，重写了findClass方法，就是为了在指定路径下加载指定的字节码文件。

❈

自定义MyProxy：

MyProxy

❈

MyProxy的作用就相当于JDK的Proxy。MyProxy做了哪些事情呢？

第一：需要根据interfaces接口构造出动态代理类需要的方法。（其实就是利用反射获取）

第二：把动态生成的代理类（即.java文件）进行编译，生成字节码文件（即.class文件），然后利用类加载进行加载

第三：动态代理类进行加载后，利用反射机制，通过构造方法进行实例化，并在实例化时，初始化业务Hanlder

❈

看一下MyProxy的其他方法：

编译方法

getMethodString方法

运行结果

我们来看一眼生成的$MyProxy0：

$MyProxy0

OK，到这里，整个JDK的动态代理的实现原理以及手写实现就结束了，你学到了么？

GoodBye My Friend~

原文链接：https://www.jianshu.com/p/58759fef38b8

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

当多个线程需要访问某个公共资源的时候，我们知道需要通过加锁来保证资源的访问不会出问题。java提供了两种方式来加锁，一种是关键字：synchronized，一种是concurrent包下的lock锁。synchronized是java底层支持的，而concurrent包则是jdk实现。关于synchronized的原理可以阅读再有人问你synchronized是什么，就把这篇文章发给他。

在这里，我会用尽可能少的代码，尽可能轻松的文字，尽可能多的图来看看lock的原理。

我们以ReentrantLock为例做分析，其他原理类似。

我把这个过程比喻成一个做菜的过程，有什么菜，做法如何？

我先列出lock实现过程中的几个关键词：计数值、双向链表、CAS+自旋

使用例子

1

复制代码import java.util.concurrent.locks.ReentrantLock;public class App {    public static void main(String[] args) throws Exception {        final int[] counter = {0};        ReentrantLock lock = new ReentrantLock();        for (int i= 0; i < 50; i++){            new Thread(new Runnable() {                @Override                public void run() {                    lock.lock();                    try {                        int a = counter[0];                        counter[0] = a + 1;                    }finally {                        lock.unlock();                    }                }            }).start();        }        // 主线程休眠，等待结果        Thread.sleep(5000);        System.out.println(counter[0]);    }}

在这个例子中，开50个线程同时更新counter。分成三块来看看源码（初始化、获取锁、释放锁）

实现原理

ReentrantLock() 干了啥

1

复制代码 /**     * Creates an instance of {@code ReentrantLock}.     * This is equivalent to using {@code ReentrantLock(false)}.     */    public ReentrantLock() {        sync = new NonfairSync();    }

在lock的构造函数中，定义了一个NonFairSync，

1

复制代码static final class NonfairSync extends Sync

NonfairSync 又是继承于Sync

1

复制代码abstract static class Sync extends AbstractQueuedSynchronizer

一步一步往上找，找到了这个鬼AbstractQueuedSynchronizer（简称AQS），最后这个鬼，又是继承于AbstractOwnableSynchronizer(AOS)，AOS主要是保存获取当前锁的线程对象，代码不多不再展开。最后我们可以看到几个主要类的继承关系。

锁的类的继承关系.jpg

FairSync 与 NonfairSync的区别在于，是不是保证获取锁的公平性，因为默认是NonfairSync，我们以这个为例了解其背后的原理。

其他几个类代码不多，最后的主要代码都是在AQS中，我们先看看这个类的主体结构。

AbstractQueuedSynchronizer是个什么

再看看Node是什么？

看到这里的同学，是不是有种热泪盈眶的感觉，这尼玛，不就是 双向链表么？我还记得第一次写这个数据结构的时候，发现居然还有这么神奇的一个东西。

最后我们可以发现锁的存储结构就两个东西:”双向链表” + “int类型状态”。需要注意的是，他们的变量都被” transient和volatile修饰。

一个int值，一个双向链表是如何烹饪处理锁这道菜的呢，Doug Lea大神就是大神，我们接下来看看，如何获取锁？

lock.lock()怎么获取锁？

1

复制代码/** * Acquires the lock. */public void lock() {    sync.lock();}

可以看到调用的是，NonfairSync.lock()

看到这里，我们基本有了一个大概的了解，还记得之前AQS中的int类型的state值，这里就是通过CAS（乐观锁）去修改state的值。 lock的基本操作还是通过乐观锁来实现的。

获取锁通过CAS，那么没有获取到锁，等待获取锁是如何实现的？我们可以看一下else分支的逻辑，acquire方法：

1

复制代码public final void acquire(int arg) {    if (!tryAcquire(arg) &&        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))        selfInterrupt();}

这里干了三件事情：

• tryAcquire：会尝试再次通过CAS获取一次锁。
• addWaiter：将当前线程加入上面锁的双向链表（等待队列）中
• acquireQueued：通过自旋，判断当前队列节点是否可以获取锁。

addWaiter 添加当前线程到等待链表中

可以看到，通过CAS确保能够在线程安全的情况下，将当前线程加入到链表的尾部。 enq是个自旋+上述逻辑，有兴趣的可以翻翻源码。

acquireQueued

自旋+CAS尝试获取锁

可以看到，当当前线程到头部的时候，尝试CAS更新锁状态，如果更新成功表示该等待线程获取成功。从头部移除。

每一个线程都在自旋+CAS

最后简要概括一下，获取锁的一个流程

获取锁流程.jpg

lock.unlock() 释放锁

1

复制代码public void unlock() {    sync.release(1);}

可以看到调用的是，NonfairSync.release()

image.png

最后有调用了NonfairSync.tryRelease()

image.png

基本可以确认，释放锁就是对AQS中的状态值State进行修改。同时更新下一个链表中的线程等待节点。

总结

• lock的存储结构：一个int类型状态值（用于锁的状态变更），一个双向链表（用于存储等待中的线程）
• lock获取锁的过程：本质上是通过CAS来获取状态值修改，如果当场没获取到，会将该线程放在线程等待链表中。
• lock释放锁的过程：修改状态值，调整等待链表。
• 可以看到在整个实现过程中，lock大量使用CAS+自旋。因此根据CAS特性，lock建议使用在低锁冲突的情况下。目前java1.6以后，官方对synchronized做了大量的锁优化（偏向锁、自旋、轻量级锁）。因此在非必要的情况下，建议使用synchronized做同步操作。

最后，希望我的分析，能对你理解锁的实现有所帮助。

PS：本文来自作者投稿，作者『林湾村龙猫』。

直面Java第125期：可以把List传递给一个接收List

成神之路第013期：Java集合类—Map。

- MORE | 更多精彩文章 -

• ****高级开发必须理解的Java中SPI机制****
• ****彻底理解HashMap的元素插入原理****
• ****漫话：如何给女朋友介绍什么是死锁****
• ****Java并发编程包中atomic的实现原理****

如果你看到了这里，说明你喜欢本文。

那么请长按二维码，关注Hollis

转发朋友圈，是对我最大的支持。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

引言

在前几篇文章中了解了ReentrantLock、Semaphore与CountDownLatch后，J.U.C包中基于AQS实现的并发工具类还剩一个比较重要的：读写锁ReentrantReadWriteLock。读写锁在Java面试过程中是一个经常性考的题目，他涉及到的知识点比较多，导致很多人不能透彻的理解他。举几个面试中常见的问题：

• ReentrantReadWriteLock和ReentrantLock的区别？
• 你能用ReentrantReadWriteLock实现一个简单的缓存管理吗？
• 你能自己实现一个简单的读写锁吗？
• ReentrantReadWriteLock会发生写饥饿的情况吗？如果发生，有没有比较好的解决办法？

上面的问题大家都能回答出来吗？如果都能很好的回答，那么这篇文章也许对你没有太大帮助。如果不能，别着急，下面就来一一分析解答上面的几个问题。

1. ReentrantReadWriteLock和ReentrantLock的区别？

这个问题大家应该都会回答：ReentrantLock是独占锁，ReentrantReadWriteLock是读写锁。那么这就引申出下一个问题：ReentrantReadWriteLock中的读锁和写锁分别是独占还是共享的？他们之间的关系又是什么样的？要了解透彻这两个问题，分析源码是再好不过的了。

1.1 ReentrantReadWriteLock中的读锁和写锁的实现方式

使用ReentrantReadWriteLock读写锁的方式，会调用readLock()和writeLock()两个方法，看下他们的源码：

1
2

复制代码public ReentrantReadWriteLock.WriteLock writeLock() { return writerLock; }
public ReentrantReadWriteLock.ReadLock  readLock()  { return readerLock; }

可以看到用到了WriteLock和ReadLock两个静态内部类，他们对锁的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复制代码public static class ReadLock implements Lock, java.io.Serializable {
    public void lock() {
        sync.acquireShared(1); //共享
    }

    public void unlock() {
        sync.releaseShared(1); //共享
    }
}

public static class WriteLock implements Lock, java.io.Serializable {
    public void lock() {
        sync.acquire(1); //独占
    }

    public void unlock() {
        sync.release(1); //独占
    }
}

abstract static class Sync extends AbstractQueuedSynchronizer {}

看到这里发现了ReentrantReadWriteLock和ReentrantLock的一个相同点和不同点，相同的是使用了同一个关键实现AbstractQueuedSynchronizer，不同的是ReentrantReadWriteLock使用了两个锁分别实现了AQS，而且WriteLock和ReentrantLock一样，使用了独占锁。而ReadLock和Semaphore一样，使用了共享锁。再往下的内容估计看过前面几篇文章的都很熟悉了，独占锁通过state变量的0和1两个状态来控制是否有线程占有锁，共享锁通过state变量0或者非0来控制多个线程访问。在上面的代码中，ReadLock和WriteLock使用了同一个AQS，那么在ReentrantReadWriteLock中又是怎么控制读锁和写锁关系的呢？

1.2 ReadLock和WriteLock共享变量

读写锁定义为：一个资源能够被多个读线程访问，或者被一个写线程访问，但是不能同时存在读写线程。

通过这句话很容易联想到通过两个不同的变量来控制读写，当获取到读锁时对读变量+1，当获取懂啊写变量时对写变量+1。但AQS中并没有为ReadLock和WriteLock添加额外的变量，还是通过一个state来实现的。那是怎么做到读写分离的呢？来看看下面这段代码：1。但AQS中并没有为ReadLock和WriteLock添加额外的变量，还是通过一个state来实现的。那是怎么做到读写分离的呢？来看看下面这段代码：

1
2
3
4
5
6
7
8
9

复制代码static final int SHARED_SHIFT   = 16;
static final int SHARED_UNIT    = (1 << SHARED_SHIFT);
static final int MAX_COUNT      = (1 << SHARED_SHIFT) - 1;
static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;

/** Returns the number of shared holds represented in count  */
static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }
/** Returns the number of exclusive holds represented in count  */
static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }

这段代码在Sync静态内部类中，这里有两个关键方法sharedCount和exclusiveCount，通过名字可以看出sharedCount是共享锁的数量，exclusiveCount是独占锁的数量。共享锁通过对c像右位移16位获得，独占锁通过和16位的1与运算获得。举个例子，当获取读锁的线程有3个，写锁的线程有1个（当然这是不可能同时有的），state就表示为0000 0000 0000 0011 0000 0000 0000 0001，高16位代表读锁，通过向右位移16位（c >>> SHARED_SHIFT）得倒10进制的3，通过和0000 0000 0000 0000 1111 1111 1111 1111与运算（c & EXCLUSIVE_MASK），获得10进制的1。弄懂了着几个方法，就明白了为什么通过一个state实现了读写共享。

这当中还有一个问题，由于16位最大全1表示为65535，所以读锁和写锁最多可以获取65535个。

1.3 WriteLock和ReentrantLock获取锁的区别

上面说过，WriteLock也是独占锁，那么他和ReentrantLock有什么区别呢？最大的区别就在获取锁时WriteLock不仅需要考虑是否有其他写锁占用，同时还要考虑是否有其他读锁，而ReentrantLock只需要考虑自身是否被占用就行了。来看下WriteLock获取锁的源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

复制代码public void lock() {
    sync.acquire(1);
}

public final void acquire(int arg) {
    if (!tryAcquire(arg) && //尝试获取独占锁
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) //获取失败后排队
        selfInterrupt();
}

protected final boolean tryAcquire(int acquires) {

    Thread current = Thread.currentThread();
    int c = getState();  //获取共享变量state
    int w = exclusiveCount(c); //获取写锁数量
    if (c != 0) { //有读锁或者写锁
        // (Note: if c != 0 and w == 0 then shared count != 0)
        if (w == 0 || current != getExclusiveOwnerThread()) //写锁为0（证明有读锁），或者持有写锁的线程不为当前线程
            return false;
        if (w + exclusiveCount(acquires) > MAX_COUNT)
            throw new Error("Maximum lock count exceeded");
        // Reentrant acquire
        setState(c + acquires);  //当前线程持有写锁，为重入锁，+acquires即可
        return true;
    }
    if (writerShouldBlock() ||
        !compareAndSetState(c, c + acquires)) //CAS操作失败，多线程情况下被抢占，获取锁失败。CAS成功则获取锁成功
        return false;
    setExclusiveOwnerThread(current);
    return true;
}

这段代码是不是很熟悉？和ReentrantLock中获取锁的代码很相似，差别在于其中调用了exclusiveCount方法来获取是否存在写锁，然后通过c != 0和w == 0判断了是否存在读锁。acquireQueued和addWaiter就不详细解说了，需要了解的可以查看前面ReentrantLock的文章。
到这里大家应该对ReentrantReadWriteLock和ReentrantLock的区别应该做到心里有数了吧。

1.4 ReadLock和Semaphore获取锁的区别

WriteLock是独占模式，我们比较了它和ReentrantLock独占锁获取锁的区别，这里我们再看看ReadLock在获取锁上有什么不同呢？先看下面的源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

复制代码protected final int tryAcquireShared(int unused) {

	Thread current = Thread.currentThread();
	int c = getState();
	if (exclusiveCount(c) != 0 &&
		getExclusiveOwnerThread() != current) //写锁不等于0的情况下，验证是否是当前写锁尝试获取读锁
		return -1;
	int r = sharedCount(c);  //获取读锁数量
	if (!readerShouldBlock() && //读锁不需要阻塞
		r < MAX_COUNT &&  //读锁小于最大读锁数量
		compareAndSetState(c, c + SHARED_UNIT)) { //CAS操作尝试设置获取读锁 也就是高位加1
		if (r == 0) {  //当前线程第一个并且第一次获取读锁，
			firstReader = current;
			firstReaderHoldCount = 1;
		} else if (firstReader == current) { //当前线程是第一次获取读锁的线程
			firstReaderHoldCount++;
		} else { // 当前线程不是第一个获取读锁的线程，放入线程本地变量
			HoldCounter rh = cachedHoldCounter;
			if (rh == null || rh.tid != getThreadId(current))
				cachedHoldCounter = rh = readHolds.get();
			else if (rh.count == 0)
				readHolds.set(rh);
			rh.count++;
		}
		return 1;
	}
	return fullTryAcquireShared(current);
}ß

在上面的代码中尝试获取读锁的过程和获取写锁的过程也很相似，不同在于读锁只要没有写锁占用并且不超过最大获取数量都可以尝试获取读锁，而写锁不仅需要考虑读锁是否占用，也要考虑写锁是否占用。上面的代码中firstReader，firstReaderHoldCount以及cachedHoldCounter都是为readHolds（ThreadLocalHoldCounter）服务的，用来记录每个读锁获取线程的获取次数，方便获取当前线程持有锁的次数信息。在ThreadLocal基础上添加了一个Int变量来统计次数，可以通过他们的实现来理解：

1
2
3
4
5
6
7
8
9
10
11
12

复制代码static final class ThreadLocalHoldCounter
	extends ThreadLocal<HoldCounter> { //ThreadLocal变量ß
	public HoldCounter initialValue() {
		return new HoldCounter();
	}
}

static final class HoldCounter {
	int count = 0;           //当前线程持有锁的次数
	// Use id, not reference, to avoid garbage retention
	final long tid = getThreadId(Thread.currentThread());   //当前线程ID
}

2. 你能用ReentrantReadWriteLock实现一个简单的缓存吗？

先来分析一个简单缓存需要满足的功能，这里我们为了实现简单，不考虑缓存过期策略等复杂因素。

• 缓存主要提供两个功能：读和写。
• 读时如果缓存中存在数据，则立即返回数据。
• 读时如果缓存中不存在数据，则需要从其他途径获取数据，同时写入缓存。
• 在写入缓存的同时，为了避免其他线程同时获取这个缓存中不存在的数据，需要阻塞其他读线程。
  下面我们就来通过ReentrantReadWriteLock实现上述功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

复制代码public static void ReentrantReadWriteLockCacheSystem() {

	//这里为了实现简单，将缓存大小设置为4。
	Map<String, String> cacheMap = new HashMap<>(4); 
	ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();

	for (int i = 0; i < 20; i++) { //同时开启20个线程访问缓存

		final String key = String.valueOf(i % 4); 
		Thread thread = new Thread(new Runnable() {

			@Override
			public void run() {
				try {
					//①读取缓存时获取读锁
					readWriteLock.readLock().lock();  
					//获取读锁后通过key获取缓存中的值
					String valueStr = cacheMap.get(key); 
					//缓存值不存在
					if (valueStr == null) { 
						//③释放读锁后再尝试获取写锁
						readWriteLock.readLock().unlock();  
						try {
							//④获取写锁来写入不存在的key值，
							readWriteLock.writeLock().lock();  
							valueStr = cacheMap.get(key);
							if (valueStr == null) {
								valueStr = key + " --- value";
								cacheMap.put(key, valueStr); //写入值
								System.out.println(Thread.currentThread().getName() + " --------- put " + valueStr);
							}
							// ⑥锁降级，避免被其他写线程抢占后再次更新值，保证这一次操作的原子性
							readWriteLock.readLock().lock(); 
							System.out.println(Thread.currentThread().getName() + " --------- get new " + valueStr);
						} finally {
							readWriteLock.writeLock().unlock(); //⑤释放写锁
						}
						
					} else {
						System.out.println(Thread.currentThread().getName() + " ------ get cache value");
					}
				} finally {
					readWriteLock.readLock().unlock();  //②释放读锁
				}
			}
		}, String.valueOf(i));
		thread.start();
	}
}

首先线程会尝试去获取数据，需要获取读锁①，如果存在值，则直接读取并释放读锁②。如果不存在值，则首先释放已经获取的读锁③，然后尝试获取写锁④。获取到写锁之后，再次检查值，因为此时可能存在其他写锁已经更新值，这时只需要读取，然后释放写锁⑤。如果还是没有值，则通过其他途径获取值并更新然后获取读锁⑥，这一步锁降级操作是为了直接抢占读锁，避免释放写锁之后再次获取读锁时被其他写线程抢占，这样保证了这一次读取数据的原子性。之后再执行⑤释放写锁和②释放读锁。

执行后输出结果如下，每次执行可能输出不同：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复制代码//1 --------- put 1 --- value
//1 --------- get new 1 --- value
//0 --------- put 0 --- value
//0 --------- get new 0 --- value
//9 ------ get cache value
//4 ------ get cache value
//2 --------- put 2 --- value
//2 --------- get new 2 --- value
//11 --------- put 3 --- value
//11 --------- get new 3 --- value
//5 ------ get cache value
//13 ------ get cache value
//6 ------ get cache value
//8 ------ get cache value
//7 ------ get cache value
//3 --------- get new 3 --- value
//10 ------ get cache value
//12 ------ get cache value
//14 ------ get cache value
//15 ------ get cache value
//16 ------ get cache value
//17 ------ get cache value
//18 ------ get cache value
//19 ------ get cache value

3. 你能自己实现一个简单的读写锁吗？

经过上面对读写锁原理的初步分析和使用，现在你能自己实现一个简单的读写锁了吗？这里列出了一步步实现一个简单的读写锁的过程，你可以按这个步骤自己先实现一遍。

• 1 定义一个读写锁共享变量state
• 2 state高16位为读锁数量，低16位为写锁数量。尽量模拟ReentrantReadWriteLock的实现
• 3 获取读锁时先判断是否有写锁，有则等待，没有则将读锁数量加1
• 4 释放读锁数量减1，通知所有等待线程
• 5 获取写锁时需要判断读锁和写锁是否都存在，有则等待，没有则将写锁数量加1
• 6 释放写锁数量减1，通知所有等待线程
  我给出的实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

复制代码public class MyReadWriteLock {

	private int state = 0; //1. 定义一个读写锁共享变量state
	
	//2. state高16位为读锁数量
	private int GetReadCount() { 
		return state >>> 16;
	}
	
	//2. 低16位为写锁数量
	private int GetWriteCount() { 
		return state & ((1 << 16) - 1);
	}
	
	//3. 获取读锁时先判断是否有写锁，有则等待，没有则将读锁数量加1
	public synchronized void lockRead() throws InterruptedException{  
		
		while (GetWriteCount() > 0) {
			wait();
		}
		
		System.out.println("lockRead ---" + Thread.currentThread().getName()); 
		state = state + (1 << 16);
	}
	
	//4. 释放读锁数量减1，通知所有等待线程
	public synchronized void unlockRead() {  
		state = state - ((1 << 16));
		notifyAll();
	}
	
	//5. 获取写锁时需要判断读锁和写锁是否都存在，有则等待，没有则将写锁数量加1
	public synchronized void lockWriters() throws InterruptedException{  
		
		while (GetReadCount() > 0 || GetWriteCount() > 0) {
			wait();
		}
		System.out.println("lockWriters ---" + Thread.currentThread().getName());
		state++;
	}
	
	//6. 释放写锁数量减1，通知所有等待线程
	public synchronized void unlockWriters(){  
		
		state--;
		notifyAll();
	}
}

4. 读写锁会发生写饥饿的情况吗？如果发生，有没有比较好的解决办法？

在读写的过程中，写操作一般是优先的，不能因为读操作过多，写操作一直等待的状况发生，这样会导致数据一直得不到更新，发生写饥饿。现在大家思考一下上面我们实现的简单读写锁，是否能做到这点呢？答案很明显，在读写线程都wait的情况下，通过notifyAll并不能保证写优先执行。那在这个例子中怎么改进这一点呢？

这里我通过添加一个中间变量来达到这个目的，这个中间变量在获取写锁之前先记录一个写请求，这样一旦notifyAll，优先检查是否有写请求，如果有，则让写操作优先执行，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

复制代码public class MyReadWriteLock {

	private int state = 0; //1. 定义一个读写锁共享变量state
	private int writeRequest = 0; //记录写请求数量
	
	//2. state高16位为读锁数量
	private int GetReadCount() { 
		return state >>> 16;
	}
	
	//2. 低16位为写锁数量
	private int GetWriteCount() { 
		return state & ((1 << 16) - 1);
	}
	
	//3. 获取读锁时先判断是否有写锁，有则等待，没有则将读锁数量加1
	public synchronized void lockRead() throws InterruptedException{  
		//写锁数量大于0或者写请求数量大于0的情况下都优先执行写
		while (GetWriteCount() > 0 || writeRequest > 0) { 
			wait();
		}
		
		System.out.println("lockRead ---" + Thread.currentThread().getName()); 
		state = state + (1 << 16);
	}
	
	//4. 释放读锁数量减1，通知所有等待线程
	public synchronized void unlockRead() {  
		state = state - ((1 << 16));
		notifyAll();
	}
	
	//5. 获取写锁时需要判断读锁和写锁是否都存在，有则等待，没有则将写锁数量加1
	public synchronized void lockWriters() throws InterruptedException{  
		
		writeRequest++; //写请求+1
		while (GetReadCount() > 0 || GetWriteCount() > 0) {
			wait();
		}
		writeRequest--; //获取写锁后写请求-1
		System.out.println("lockWriters ---" + Thread.currentThread().getName());
		state++;
	}
	
	//6. 释放写锁数量减1，通知所有等待线程
	public synchronized void unlockWriters(){  
		
		state--;
		notifyAll();
	}
}

大家可以测试下上面的代码看看是不是写请求都优先执行了呢？现在我们把这个问题放到ReentrantReadWriteLock中来考虑，显而易见，ReentrantReadWriteLock也会发生写请求饥饿的情况，因为写请求一样会排队，不管是公平锁还是非公平锁，在有读锁的情况下，都不能保证写锁一定能获取到，这样只要读锁一直占用，就会发生写饥饿的情况。那么JDK就没有提供什么好办法来解决这个问题吗？当然是有的，那就是JDK8中新增的改进读写锁—StampedLock，在下一篇文章中将会对StampedLock进行详细讲解。

本文转载自: 掘金