数据库

Redis常考的知识点

一、Redis是什么，有什么功能？

​ Redis 是一个使用 C 语言开发的数据库，也是一种Key-Value数据库,数据存储在内存中，常用作缓存数据库，速度较快。

功能：常用来作缓存，分布式锁，消息队列，排行榜等功能

二、Redis 和 Memcached 的对比

  1. Memcached 只支持String类型，Reids支持更为丰富的数据类型

  2. Redis支持数据的持久化

  3. Redis的速度更快

  4. Memcached 是多线程，非阻塞IO复用的网络模型，Redis使用单线程的IO复用

    相同点就是都是内存型数据库，都有过期策略，性能都不错，常用来做缓存

​

三、Redis支持的数据类型以及底层数据结构
  1. ​ string，底层数据结构为简单动态字符串（simple dynamic string，SDS），SDS 可以保存二进制数据，并且获取字符串长度复杂度为 O(1)（C 字符串为 O(N)）,此外,Redis 的 SDS API 是安全的，不会造成缓冲区溢出。
  2. list，底层数据结构是链表，C 语言并没有实现链表，所以 Redis 实现了自己的链表数据结构。Redis 的 list 的实现为一个 双向链表，即可以支持反向查找和遍历，更方便操作，不过带来了部分额外的内存开销，获取表头表尾和链表长度都是O(1)复杂度
  3. set，是一种无序集合，集合中的元素没有先后顺序。需要存储一个列表数据，又不希望出现重复时，可以选择set，并且 set 提供了判断某个成员是否在一个 set 集合内的重要接口
  4. hash，底层是字典结构，字典在Redis中广泛被使用，包括数据库和哈希键，每个字典有两个哈希表，哈希表使用的是链地址法解决哈希冲突，扩容时采用的是渐进式哈希
  5. Zset ，有点像是 Java 中 HashMap 和 TreeSet 的结合体，底层使用跳表实现
四、Redis为什么是单线程？

​ Redis核心就是我所有数据都在内存里，单线程操作效率就是最高的，为什么要多线程呢？多线程会有一个代价，就是上下文切换，对于当个CPU绑定一块内存的数据，没有上下文切换就是效率最高的；相反，如果是多次磁盘IO的话，多线程更优，因为在寻道和选择的时间，线程在阻塞的等待磁盘，这个时间CPU可以去处理其他线程。

​ 总之就是CPU不是redis的瓶颈，reids的瓶颈是机器内存和网络带宽，而单线程既不会成为瓶颈，又容易实现，那肯定单线程。

五、Redis是单线程吗？

​ 将第五题和第四题放在一起就是为了分辨一个大部分人的误区，大家称Redis是单线程，但是Redis并不是单线程，比如持久化的时候就会fork子线程，包括网络IO也不是单线程，Redis的单线程指的是事件处理模型的单线程。

​ Redis 基于 Reactor 模式开发了自己的网络事件处理器：这个处理器被称为文件事件处理器（file event handler），通过IO 多路复用程序 来监听来自客户端的大量连接（或者说是监听多个 socket），它会将感兴趣的事件及类型(读、写）注册到内核中并监听每个事件是否发生。

​ 文件事件处理器（file event handler）主要是包含 4 个部分：

  • 多个 socket（客户端连接）
  • IO 多路复用程序（支持多个客户端连接的关键）
  • 文件事件分派器（将 socket 关联到相应的事件处理器）
  • 事件处理器（连接应答处理器、命令请求处理器、命令回复处理器）
六、什么是缓存雪崩，什么是缓存穿透？

​ 缓存雪崩是指缓存中数据大批量到过期时间，而查询数据量巨大，引起数据库压力过大甚至down机。

​ 解决方案就是：

  1. ​ 设置缓存添加随机过期时间，防止大量缓存同时失效
  2. 采用Reids高可用架构比如主从或者Redis Cluster，避免Redis挂掉
  3. 及时利用本地缓存和限流，防止下游数据库崩溃
  4. 开启持久化，重启后快速恢复数据

​ 缓存穿透是指缓存和数据库中都没有的数据，而用户不断发起请求，如发起为id为“-1”的数据或id为特别大不存在的数据。这时的用户很可能是攻击者，攻击会导致数据库压力过大

​ 解决方案就是：

  1. 访问一个不存在的参数时，将这个结果进行缓存，下次直接返回null

  2. 使用布隆过滤器进行过滤

七、Redis的过期键的删除策略

  1. ​ 惰性删除 ：只会在取出key的时候才对数据进行过期检查。这样对CPU最友好，但是可能会造成太多过期 key 没有被删除。

  2. ​ 定期删除 ： 每隔一段时间抽取一批 key 执行删除过期key操作。并且，Redis 底层会通过限制删除操作执行的时长和频率来减少删除操作对CPU时间的影响。

八、Redis的内存淘汰机制

​ Redis 提供 6 种数据淘汰策略：

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

4.0 版本后增加以下两种：

  1. volatile-lfu（least frequently used）：从已设置过期时间的数据集(server.db[i].expires)中挑选最不经常使用的数据淘汰
  2. allkeys-lfu（least frequently used）：当内存不足以容纳新写入数据时，在键空间中，移除最不经常使用的 key
九、Reids和数据库的双写一致性

​ a. 先更新数据再更新缓存的话是不行的，更新结束，更新缓存失败岂不是gg

​ b. 先删缓存再更新数据库看起来可以，实际上也有问题：

​ i. A删缓存，B拿旧数据，放到缓存里，A更新数据库，就出问题了

​ ii. 解决方案：延时双删（但是第二次删除还是会出现不一致问题），（要设置过期时间，保证最终一致性）

​ c. 先更新数据库再删缓存

​ i. 问题：缓存刚好失效，然后A拿到旧数据，然后B更新缓存删缓存，A把旧数据放到数据库，但是碰上缓存刚好失效的概率比较低

十、Redis的持久化方式

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

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

十一、Redis的渐进式扩容

​ 每个字典有两个哈希表，一个ht[0],一个ht[1]，扩展或收缩哈希表需要将 ht[0] 里面的所有键值对 rehash 到 ht[1] 里面。如果哈希表里保存的键值对数量非常大， 那么要一次性将这些键值对全部 rehash 到 ht[1] 的话， 庞大的计算量可能会导致服务器在一段时间内停止服务。为了避免此情况，所以采用渐进式哈希。

​ 哈希表渐进式 rehash 的详细步骤：

  1. 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
  2. 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
  3. 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
  4. 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1， 表示 rehash 操作已完成。

在渐进式 rehash 进行期间， 字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行： 比如说， 要在字典里面查找一个键的话， 程序会先在 ht[0] 里面进行查找， 如果没找到的话， 就会继续到 ht[1] 里面进行查找， 诸如此类。

另外， 在渐进式 rehash 执行期间， 新添加到字典的键值对一律会被保存到 ht[1] 里面， 而 ht[0] 则不再进行任何添加操作

十二、Redis分布式锁（后续会有单独文章）

​ 方法一：SETNX key value

​ 将 key 的值设为 value，当且仅当 key 不存在。
​ 若给定的 key 已经存在，则 SETNX 不做任何动作。
​ SETNX 是SET if Not eXists的简写

​ 方法二（Redlock算法）：

​ 起 5 个 master 节点，分布在不同的机房尽量保证可用性。为了获得锁，client 会进行如下操作：

  1. 得到当前的时间，微秒单位
  2. 尝试顺序地在 5 个实例上申请锁，当然需要使用相同的 key 和 random value，这里一个 client 需要合理设置与 master 节点沟通的 timeout 大小，避免长时间和一个 fail 了的节点浪费时间
  3. 当 client 在大于等于 3 个 master 上成功申请到锁的时候，且它会计算申请锁消耗了多少时间，这部分消耗的时间采用获得锁的当下时间减去第一步获得的时间戳得到，如果锁的持续时长（lock validity time）比流逝的时间多的话，那么锁就真正获取到了。
  4. 如果锁申请到了，那么锁真正的 lock validity time 应该是 origin（lock validity time） - 申请锁期间流逝的时间
  5. 如果 client 申请锁失败了，那么它就会在少部分申请成功锁的 master 节点上执行释放锁的操作，重置状态

后续将会推送Reids集群的知识，敬请期待！

Netty

Netty—心跳机制

一、Netty心跳机制

​ Netty是由JBOSS提供的一个java开源框架。Netty提供异步的、事件驱动的网络应用程序框架和工具，用以快速开发高性能、高可靠性的网络服务器和客户端程序

​ 在Netty中，服务端启动后，等待客户端连接，客户端连接之后，向服务端发送消息。如果客户端在发送，那么服务端必定会收到数据，如果客户端停止发送消息，那么服务端就接收不到这个客户端的消息，既然客户端闲下来了，那么连接资源就是一种浪费，所以服务端检测到一定时间内客户端不活跃的时候，将客户端连接关闭。

二、心跳实现
  • 可以使用TCP协议层的Keeplive机制，但是该机制默认的心跳时间是2小时，依赖操作系统实现不够灵活；
  • 另一种就是，应用层实现自定义心跳机制，比如Netty实现心跳机制；
三、IdleStateHandler心跳检测

​ pipeline.addLast(new IdleStateHandler(60,45,20, TimeUnit.SECONDS))指的是60s读空闲，45写空闲，20s读写空闲就触发对应userEventTriggered()方法

四、代码实现

Server.java

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
import com.netty.constants.Constants;
import com.netty.factory.ZookeeperFactory;
import io.netty.bootstrap.ServerBootstrap;
import io.netty.channel.*;
import io.netty.channel.nio.NioEventLoopGroup;
import io.netty.channel.socket.SocketChannel;
import io.netty.channel.socket.nio.NioServerSocketChannel;
import io.netty.handler.codec.string.StringDecoder;
import io.netty.handler.codec.string.StringEncoder;
import io.netty.handler.timeout.IdleStateHandler;
import org.apache.curator.framework.CuratorFramework;
import org.apache.zookeeper.CreateMode;

import java.net.InetAddress;
import java.util.concurrent.TimeUnit;

public class NettyServer {

    public static void main(String[] args) {
        ServerBootstrap bootstrap = new ServerBootstrap();
        EventLoopGroup parentGroup = new NioEventLoopGroup();
        EventLoopGroup childGroup = new NioEventLoopGroup();

        try {
            bootstrap.group(parentGroup, childGroup)
                    .option(ChannelOption.SO_BACKLOG, 128)
                    .childOption(ChannelOption.SO_KEEPALIVE, false)//自己写心跳包
                    .channel(NioServerSocketChannel.class)
                    .childHandler(new ChannelInitializer<SocketChannel>() {
                        @Override
                        protected void initChannel(SocketChannel socketChannel) throws Exception {
                            ChannelPipeline pipeline = socketChannel.pipeline();
                            pipeline.addLast(new StringDecoder());
                            pipeline.addLast(new StringEncoder());
                            //实现心跳机制
                            pipeline.addLast(new IdleStateHandler(60,45,20, TimeUnit.SECONDS));

                            pipeline.addLast(new SimpleServerHandler());
                        }
                    });
            ChannelFuture sync = bootstrap.bind(8088).sync();
            sync.channel().closeFuture().sync();
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            parentGroup.shutdownGracefully();
            childGroup.shutdownGracefully();
        }
    }
}

ServerHandler.java

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
import io.netty.channel.ChannelHandlerContext;
import io.netty.channel.ChannelInboundHandlerAdapter;
import io.netty.handler.timeout.IdleState;
import io.netty.handler.timeout.IdleStateEvent;

public class SimpleServerHandler extends ChannelInboundHandlerAdapter {
    @Override
    public void channelRead(ChannelHandlerContext ctx, Object msg) throws Exception {
        System.out.println(msg);
        ctx.channel().writeAndFlush("is ok\r\n");
        ctx.channel().close();
    }

    @Override
    public void userEventTriggered(ChannelHandlerContext ctx, Object evt) throws Exception {
        if(evt instanceof IdleStateEvent) {
            IdleStateEvent event = (IdleStateEvent)evt;
            if(event.state().equals(IdleState.READER_IDLE)) {
                System.out.println("读空闲==");
                ctx.channel().close();
            }else if(event.state().equals(IdleState.WRITER_IDLE)) {
                System.out.println("写空闲==");
            }else if(event.state().equals(IdleState.ALL_IDLE)) {
                System.out.println("读写空闲==");
                ctx.channel().writeAndFlush("ping\r\n");
            }
        }
    }
}

Client.java

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
import io.netty.bootstrap.Bootstrap;
import io.netty.channel.*;
import io.netty.channel.nio.NioEventLoopGroup;
import io.netty.channel.socket.SocketChannel;
import io.netty.channel.socket.nio.NioSocketChannel;
import io.netty.handler.codec.string.StringDecoder;
import io.netty.handler.codec.string.StringEncoder;
import io.netty.util.AttributeKey;

public class NettyClient {
    public static void main(String[] args) {
        String host = "localhost";
        int port = 8088;
        EventLoopGroup group = new NioEventLoopGroup();
        try{
            Bootstrap bootstrap = new Bootstrap();
            bootstrap.group(group)
                    .channel(NioSocketChannel.class)
                    .option(ChannelOption.SO_KEEPALIVE, true)
                    .handler(new ChannelInitializer<SocketChannel>() {
                        @Override
                        protected void initChannel(SocketChannel ch) throws Exception {
                            ch.pipeline().addLast(new StringEncoder());
                            ch.pipeline().addLast(new StringDecoder());
                            ch.pipeline().addLast(new SimpleClientHandler());
                        }
                    });
            ChannelFuture f = bootstrap.connect(host, port).sync();
            f.channel().writeAndFlush("hello, server");
            f.channel().writeAndFlush("/r/n");
            f.channel().closeFuture().sync();
            Object result = f.channel().attr(AttributeKey.valueOf("ssssss")).get();
            System.out.println("获取到服务器返回的数据：" + result);
        }catch (Exception e) {
            e.printStackTrace();
        } finally {
            group.shutdownGracefully();
        }
    }
}

ClientHandler.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package com.netty.client;

import io.netty.channel.ChannelHandlerContext;
import io.netty.channel.ChannelInboundHandlerAdapter;
import io.netty.util.AttributeKey;

public class SimpleClientHandler extends ChannelInboundHandlerAdapter {

    @Override
    public void channelRead(ChannelHandlerContext ctx, Object msg) throws Exception {
        if("ping".equals(msg.toString())) {
            ctx.channel().writeAndFlush("pong\r\n");
            return;
        }
        System.out.println(msg.toString());
    }
五、总结

​ 使用 Netty 实现心跳机制的关键就是利用 IdleStateHandler 来产生对应的 idle 事件.

​ 对应userEventTriggered()方法来触发对应的idle事件处理

框架

pagehelper的使用方法

一、介绍

现在一般springboot，mybatis项目中的mapper，pojo都是通过逆向工程直接生成的，但是生成的mapper中的查询语句中是没有分页功能的，如果想要分页的话，只能自己再去xml配置文件中修改sql语句，显得特别麻烦。为了方便快捷的翻页，这里引入一个分页插件。

pagehelper，原理如下

fenye

使用这个插件后，会自动在我们的sql查询中加上limit，而不需要我们自己再去做limit处理

二、使用方法

​ 首先引入依赖

1
2
3
4
5
<dependency>
    <groupId>com.github.pagehelper</groupId>
    <artifactId>pagehelper-spring-boot-starter</artifactId>
    <version>1.2.11</version>
</dependency>

​ 然后再在yml文件中配置

1
2
3
4
5
#pagehelper配置
pagehelper:
  reasonable: true
  support-methods-arguments: true
  params: count=countSql

使用的时候只需要在我们的查询使用之前加上一句就行

​ PageHelper.startPage(pageNum,pageSize);

​ pageNum是显示第几页；pageSize是每页的记录数

1
2
3
4
5
6
7
@ResponseBody
    @RequestMapping("/list")
    public List<TbItem> selectAll() {
        PageHelper.startPage(1,10);
        List<TbItem> tbItems = tbItemService.selectAll();
        return tbItems;
    }

注意：查询语句必须紧跟在PageHelper.startPage(pageNum,pageSize);语句之后，不然分页会有问题。

为了方便，我们通常创建一个PageInfo的对象，从对象中获取分页信息

1
2
3
4
5
6
7
8
@ResponseBody
    @RequestMapping("/list")
    public PageInfo<TbItem> selectAll() {
        PageHelper.startPage(1,10);
        List<TbItem> tbItems = tbItemService.selectAll();
        PageInfo<TbItem> pageInfo = new PageInfo<>(tbItems);
        return pageInfo;
    }
设计模式

设计模式—创建型模式

1.什么是创建型模式？

​ 创建型模式提供了一种在创建对象的同时隐藏创建逻辑的方式，而不是使用new直接去实例化对象，这使得程序在创建对象时更加灵活和有针对性

​ 主要包括 单例模式，工厂模式，抽象工厂模式，建造者模式等

2.单例模式

单例（Singleton）模式的定义：指一个类只有一个实例，且该类能自行创建这个实例的一种模式

单例模式有 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
public class Singleton {

}


//懒汉式
class LazySingleton {
    private static volatile LazySingleton instance ;
    private LazySingleton() {}

    public static synchronized LazySingleton getInstance() {
        if(instance == null) {
            instance = new LazySingleton();
        }
        return instance;
    }
}

//饿汉式
class HungrySingleton {
    private static HungrySingleton instance = new HungrySingleton();
    private HungrySingleton () {}
    public static HungrySingleton getInstance() {
        return instance;
    }
}


//双重校验锁
class DoubleSingleton {
    private static volatile DoubleSingleton instance;
    private DoubleSingleton (){}

    public static DoubleSingleton getInstance() {
        if (instance == null) {
            synchronized (DoubleSingleton.class) {
                if (instance == null) {
                    instance = new DoubleSingleton();
                }
            }
        }
        return instance;
    }
}
3.简单工厂模式
  • 我们把被创建的对象称为“产品”，把创建产品的对象称为“工厂”。如果要创建的产品不多，只要一个工厂类就可以完成，这种模式叫“简单工厂模式”。
  • 在简单工厂模式中创建实例的方法通常为静态（static）方法，因此简单工厂模式（Simple Factory Pattern）又叫作静态工厂方法模式（Static Factory Method Pattern）。
  • 简单来说，简单工厂模式有一个具体的工厂类，可以生成多个不同的产品，属于创建型设计模式。简单工厂模式不在 GoF 23 种设计模式之列。
  • 简单工厂模式每增加一个产品就要增加一个具体产品类和一个对应的具体工厂类，这增加了系统的复杂度，违背了“开闭原则”。
  • “工厂方法模式”是对简单工厂模式的进一步抽象化，其好处是可以使系统在不修改原来代码的情况下引进新的产品，即满足开闭原则。
1
2
3
public interface Computer {
    void start();
}
1
2
3
4
5
6
public class AsusComputer implements Computer {
    @Override
    public void start() {
        System.out.println("华硕电脑启动");
    }
}
1
2
3
4
5
6
public class HpComputer implements Computer {
    @Override
    public void start() {
        System.out.println("惠普电脑启动");
    }
}
1
2
3
4
5
6
public class LenovoComputer implements Computer{
    @Override
    public void start() {
        System.out.println("联想电脑启动");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class SimpleFactory {

    public static Computer createComputer (String type) {
        Computer computer = null;
        switch (type) {
            case "lenovo" :
                computer = new LenovoComputer();
                break;
            case "hp":
                computer = new HpComputer();
                break;
            case "asus":
                computer = new AsusComputer();
                break;
        }
        return computer;
    }
}
1
2
3
4
5
public class test {
    public static void main(String[] args) {
        SimpleFactory.createComputer("hp").start();
    }
}
4.工厂方法模式

​ 工厂方法模式（Factory Method Pattern）：又称为工厂模式或者多态工厂模式。在 *工厂方法模式中，工厂父类负责定义创建产品对象的公共接口，而工厂子类则负责生成具 * 体的产品对象，这样做的目的是将产品的实例化操作延迟到工厂子类中完成，即通过工厂 * 子类来确定究竟应该实例化哪一个具体产品类。 

1
2
3
public interface MachineApi {
    void process (String material);
}
1
2
3
4
5
6
public class BoodleMachine implements MachineApi{
    @Override
    public void process(String material) {
        System.out.println("我把" + material + "加工成了面条");
    }
}
1
2
3
4
5
6
public class SteamedBunMachine implements MachineApi{
    @Override
    public void process(String material) {
        System.out.println("我把" + material + "加工成了馒头");
    }
}
1
2
3
4
5
6
7
8
public abstract class Factory {
    public abstract MachineApi newMachine();

    public void process (String material) {
        MachineApi machine = newMachine();
        machine.process(material);
    }
}
1
2
3
4
5
6
public class NoodleFactory extends Factory {
    @Override
    public MachineApi newMachine() {
        return new BoodleMachine();
    }
}
1
2
3
4
5
6
public class SteamedBunFactory extends Factory {
    @Override
    public MachineApi newMachine() {
        return new SteamedBunMachine();
    }
}
1
2
3
4
5
6
7
8
9
10
public class test {
    public static void main(String[] args) {
        Factory factory1  = new SteamedBunFactory ();
        factory1.process("面粉");//我把面粉加工成了馒头

        Factory factory2  = new NoodleFactory ();
        factory2.process("米粉");//我把面粉加工成了馒头
    }
}

5.抽象工厂模式

​ 抽象工厂模式（Abstract Factory Pattern）是围绕一个超级工厂创建其他工厂。该超级工厂又称为其他工厂的工厂。这种类型的设计模式属于创建型模式，它提供了一种创建对象的最佳方式。

在抽象工厂模式中，接口是负责创建一个相关对象的工厂，不需要显式指定它们的类。每个生成的工厂都能按照工厂模式提供对象。

1
2
3
public interface Shape {
   void draw();
}
1
2
3
4
5
6
7
public class Rectangle implements Shape {
 
   @Override
   public void draw() {
      System.out.println("Inside Rectangle::draw() method.");
   }
}
1
2
3
4
5
6
7
public class Square implements Shape {
 
   @Override
   public void draw() {
      System.out.println("Inside Square::draw() method.");
   }
}
1
2
3
4
5
6
7
public class Circle implements Shape {
 
   @Override
   public void draw() {
      System.out.println("Inside Circle::draw() method.");
   }
}
1
2
3
public interface Color {
   void fill();
}
1
2
3
4
5
6
7
public class Red implements Color {
 
   @Override
   public void fill() {
      System.out.println("Inside Red::fill() method.");
   }
}
1
2
3
4
5
6
7
public class Green implements Color {
 
   @Override
   public void fill() {
      System.out.println("Inside Green::fill() method.");
   }
}
1
2
3
4
5
6
7
public class Blue implements Color {
 
   @Override
   public void fill() {
      System.out.println("Inside Blue::fill() method.");
   }
}
1
2
3
4
public abstract class AbstractFactory {
   public abstract Color getColor(String color);
   public abstract Shape getShape(String shape) ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ShapeFactory extends AbstractFactory {
    
   @Override
   public Shape getShape(String shapeType){
      if(shapeType == null){
         return null;
      }        
      if(shapeType.equalsIgnoreCase("CIRCLE")){
         return new Circle();
      } else if(shapeType.equalsIgnoreCase("RECTANGLE")){
         return new Rectangle();
      } else if(shapeType.equalsIgnoreCase("SQUARE")){
         return new Square();
      }
      return null;
   }
   
   @Override
   public Color getColor(String color) {
      return null;
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ColorFactory extends AbstractFactory {
    
   @Override
   public Shape getShape(String shapeType){
      return null;
   }
   
   @Override
   public Color getColor(String color) {
      if(color == null){
         return null;
      }        
      if(color.equalsIgnoreCase("RED")){
         return new Red();
      } else if(color.equalsIgnoreCase("GREEN")){
         return new Green();
      } else if(color.equalsIgnoreCase("BLUE")){
         return new Blue();
      }
      return null;
   }
}
1
2
3
4
5
6
7
8
9
10
public class FactoryProducer {
   public static AbstractFactory getFactory(String choice){
      if(choice.equalsIgnoreCase("SHAPE")){
         return new ShapeFactory();
      } else if(choice.equalsIgnoreCase("COLOR")){
         return new ColorFactory();
      }
      return null;
   }
}
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
public class AbstractFactoryPatternDemo {
   public static void main(String[] args) {
 
      //获取形状工厂
      AbstractFactory shapeFactory = FactoryProducer.getFactory("SHAPE");
 
      //获取形状为 Circle 的对象
      Shape shape1 = shapeFactory.getShape("CIRCLE");
 
      //调用 Circle 的 draw 方法
      shape1.draw();
 
      //获取形状为 Rectangle 的对象
      Shape shape2 = shapeFactory.getShape("RECTANGLE");
 
      //调用 Rectangle 的 draw 方法
      shape2.draw();
      
      //获取形状为 Square 的对象
      Shape shape3 = shapeFactory.getShape("SQUARE");
 
      //调用 Square 的 draw 方法
      shape3.draw();
 
      //获取颜色工厂
      AbstractFactory colorFactory = FactoryProducer.getFactory("COLOR");
 
      //获取颜色为 Red 的对象
      Color color1 = colorFactory.getColor("RED");
 
      //调用 Red 的 fill 方法
      color1.fill();
 
      //获取颜色为 Green 的对象
      Color color2 = colorFactory.getColor("Green");
 
      //调用 Green 的 fill 方法
      color2.fill();
 
      //获取颜色为 Blue 的对象
      Color color3 = colorFactory.getColor("BLUE");
 
      //调用 Blue 的 fill 方法
      color3.fill();
   }
}

三大工厂模式的区别可见：

​ www.zhihu.com/question/20367734/answer/807965357

simplefactory

factorymethod

abstractfactory

6.建造者模式

​ 建造者模式（Builder Pattern）使用多个简单的对象一步一步构建成一个复杂的对象。这种类型的设计模式属于创建型模式，它提供了一种创建对象的最佳方式。

参考：https://www.runoob.com/design-pattern

SpringBoot 框架

SpringBoot 必须依赖spring-boot-parent？

在做项目的时候遇到一个问题
问题

做项目的时候遇到一个问题

子moudle的pom中已经引用了为父moudle,但是springboot项目又需要引用
spring-boot-start-parent，但是同时引用两个的话pom文件会报错，于是我们

翻看了官方文档已经查阅资料发现，可以不用,直接引包亦可以实现同样的功能，SpringBoot 不是必须依赖spring-boot-parent。

1
2
3
4
5
6
7
8
9
10
11
12
<dependencyManagement>
        <dependencies>
            <dependency>
                <!-- Import dependency management from Spring Boot -->
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-dependencies</artifactId>
                <version>2.4.0</version>
                <type>pom</type>
                <scope>import</scope>
            </dependency>
        </dependencies>
    </dependencyManagement>
算法

常见排序介绍及优化手段

1.插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
    int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
    //插入排序：每次将当前元素插入到左侧已经排好的数组中
    int len=arr.length;
    for (int i = 1; i < len; i++) {
        for (int j = i; j >0; j--) {
            if(arr[j]<arr[j-1]){
                int tmp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=tmp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}
2. 堆排序
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
public class duipaixu {
    public static void main(String[] args) {
        int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
        //插入排序：每次将当前元素插入到左侧已经拍好的数组中
        int len=arr.length;
        heap_sort(arr,len-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void heap_sort(int[] arr,int len){
        //形成二叉堆
        for (int i = (len-2)/2; i >=0; i--) {
            downadjust(arr,i,len+1);
        }
        for(int i=len;i>0;i--){
            int tmp=arr[i];
            arr[i]=arr[0];
            arr[0]=tmp;
            downadjust(arr,0,i);
        }
    }

    private static void downadjust(int[] arr,int parent,int len){
        int tmp=arr[parent];
        int child=2*parent+1;
        while(child<len){
            if(child+1<len&&arr[child]>=arr[child+1]){
                child++;
            }
            if(tmp<=arr[child]){
                break;
            }
            arr[parent]=arr[child];
            parent=child;
            child=2*parent+1;
        }
        arr[parent]=tmp;
    }
}
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

public class guibinpaixu {

    public static void main(String[] args) {
        int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
        //插入排序：每次将当前元素插入到左侧已经拍好的数组中
        int len=arr.length;
        gbsort(arr,0,len-1);
        System.out.println(Arrays.toString(arr));
    }
    private static void gbsort(int[] arr,int l,int r){
        if(l>=r){
            return;
        }
        int mid=l+(r-l)/2;
        gbsort(arr,l,mid);
        gbsort(arr,mid+1,r);
        help(arr,l,mid,r);
    }
    private static void help(int[] arr,int l,int mid,int r){
        int[] help=new int[r-l+1];
        int p=l;
        int q=mid+1;
        int index=0;
        while(p<=mid&&q<=r){
            help[index++]=arr[p]<arr[q]?arr[p++]:arr[q++];
        }
        while(p<=mid){
            help[index++]=arr[p++];
        }
        while(q<=mid){
            help[index++]=arr[q++];
        }
        for(int i=0;i<index;i++){
            arr[i+l]=help[i];
        }
    }
}
4. 快速排序
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
public class kuaipai {
    public static void main(String[] args) {
        int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
        //插入排序：每次将当前元素插入到左侧已经拍好的数组中
        int len=arr.length;
        quick_sort(arr,0,len-1);
        System.out.println(Arrays.toString(arr));
    }
    private static void quick_sort(int[] arr,int l ,int r){
        if(l>=r){
            return;
        }
        int index=partition(arr,l,r);
        quick_sort(arr,l,index-1);
        quick_sort(arr,index+1,r);
    }

    private static int partition(int[] arr,int l ,int r){
        int tmp=arr[l];
        while(l<r){
            while(l<r&&arr[r]>=tmp){
                r--;
            }
            arr[l]=arr[r];
            while (l<r&&arr[l]<=tmp){
                l++;
            }
            arr[r]=arr[l];
        }
        arr[l]=tmp;
        return l;
    }
}
``````

##### 5. 冒泡排序

```java
public static void main(String[] args) {
    int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
    //每次冒泡出一个结果到最后
    int len=arr.length;
    for(int i=len-2;i>=0;i--){
        for(int j=0;j<=i;j++){
            if(arr[j]>arr[j+1]){
                int tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}
6. 希尔排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void main(String[] args) {
    int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
    //插入排序：每次将当前元素插入到左侧已经拍好的数组中
    int len=arr.length;
    int h=1;
    while(h<len/3){
        h=h*3+1;
    }
    while(h>=1){
        for(int i=h;i<len;i++){
            for(int j=i;j>=h;j-=h){
                if(arr[j]<arr[j-h]){
                    int tmp=arr[j];
                    arr[j]=arr[j-h];
                    arr[j-h]=tmp;
                }
            }
        }
        h/=3;
    }
    System.out.println(Arrays.toString(arr));
}
7. 选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
        int[] arr={7,4,87,23,2324,57,34,87,345,68,23,1,567,345,77,33,2,1,1,76};
        //选择排序，每次选择一个最小的与前面的交换
        int len=arr.length;
        for (int i = 0; i < len-1; i++) {
            int min=i;
            for (int j = i+1; j <len ; j++) {
                if(arr[min]>arr[j]){
                    min=j;
                }
            }
            int tmp=arr[min];
            arr[min]=arr[i];
            arr[i]=tmp;
        }
        System.out.println(Arrays.toString(arr));
    }

image.png

各大排序优化：
冒泡：加入一个flag，如果有一轮flag没变说明没排序，说明已经排序好，可以直接退出
快排：小数组切换到插入排序，三数取中，三向切分
三向切分：类似于荷兰国旗改进，荷兰国旗问题和经典快排不同的就只是将<=num改为了< num和=num两部分，借用这个思想使得原来每次只可以让一个数找到正确的位置改进为了每次至少让一个数找到位置 在topk问题中，快排每次可以排除一半元素
随机快排 1. 选取最后一个数：如果是一个已经排好序的数组，每次找到位置之后，左边是要进行排序的部分，数组长度是原长度-1，它的时间复杂度就是O(N^2)；如果每次找到的数都是中间的位置，它的时间复杂度就只有O(logN) 2. 然而以随机数作为选取的标准num的时候，因为是随机的，就只能通过数学期望去计算它的时间复杂度，时间复杂度是O(logN)

数据结构

了解ConcurrentHashMap

  1. ConcurrentHashMap中没有负载因子和阈值吗

    是没有，改用了sizeCtl控制，0表示默认值，-1表示正在扩容，>0表示下一次扩容的门槛，-（1+nThreads）n个线程正在扩容，sizeCtl的变化都是CAS操作

    sizeCtl：

    （1）-1，表示有线程正在进行初始化操作

    （2）-(1 + nThreads)，表示有n个线程正在一起扩容

    （3）0，默认值，后续在真正初始化的时候使用默认容量

    （4）> 0，初始化或扩容完成后下一次的扩容门槛

    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
    public ConcurrentHashMap() {
    }

    public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                MAXIMUM_CAPACITY :
                tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }

    public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
        this.sizeCtl = DEFAULT_CAPACITY;
        putAll(m);
    }

    public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 1);
    }

    public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            initialCapacity = concurrencyLevel;   // as estimated threads
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
                MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;
    }
  2. 请讲讲ConcurrentHashMap的put操作？

    a. 控制key和value都不能为null
    b. 再用自旋+cas实现put过程，下面是具体的put
    c. 如果桶未初始化就初始化桶
    d. 如果桶中还没有元素就把这个元素插进去，插入这一步就是采用的CAS
    e. 如果要插入的桶正在扩容迁移元素，就当前线程一起帮忙协助扩容
    f. 如果桶已经存在且没有迁移元素
    g. 就锁住这个桶，是采用分段锁的思想（锁住后里面不需要cas）
    h. 如果元素存在就替换，不存在size+1，插到链表或者树的尾部
    i. 如果桶的元素个数达到了8就尝试树化
    j. 元素个数+1（分段锁思想），同时检查是否需要扩容
    k. 返回

    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
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    /**
        * Maps the specified key to the specified value in this table.
        * Neither the key nor the value can be null.
        *
        * <p>The value can be retrieved by calling the {@code get} method
        * with a key that is equal to the original key.
        *
        * @param key key with which the specified value is to be associated
        * @param value value to be associated with the specified key
        * @return the previous value associated with {@code key}, or
        *         {@code null} if there was no mapping for {@code key}
        * @throws NullPointerException if the specified key or value is null
        */
       public V put(K key, V value) {
           return putVal(key, value, false);
       }
    	
       /** Implementation for put and putIfAbsent */
       final V putVal(K key, V value, boolean onlyIfAbsent) {
           if (key == null || value == null) throw new NullPointerException();
           int hash = spread(key.hashCode());
           int binCount = 0;
           for (Node<K,V>[] tab = table;;) {
               Node<K,V> f; int n, i, fh;
               if (tab == null || (n = tab.length) == 0)
                   tab = initTable();
               else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                   if (casTabAt(tab, i, null,
                                new Node<K,V>(hash, key, value, null)))
                       break;                   // no lock when adding to empty bin
               }
               else if ((fh = f.hash) == MOVED)
                   tab = helpTransfer(tab, f);
               else {
                   V oldVal = null;
                   synchronized (f) {
                       if (tabAt(tab, i) == f) {
                           if (fh >= 0) {
                               binCount = 1;
                               for (Node<K,V> e = f;; ++binCount) {
                                   K ek;
                                   if (e.hash == hash &&
                                       ((ek = e.key) == key ||
                                        (ek != null && key.equals(ek)))) {
                                       oldVal = e.val;
                                       if (!onlyIfAbsent)
                                           e.val = value;
                                       break;
                                   }
                                   Node<K,V> pred = e;
                                   if ((e = e.next) == null) {
                                       pred.next = new Node<K,V>(hash, key,
                                                                 value, null);
                                       break;
                                   }
                               }
                           }
                           else if (f instanceof TreeBin) {
                               Node<K,V> p;
                               binCount = 2;
                               if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                              value)) != null) {
                                   oldVal = p.val;
                                   if (!onlyIfAbsent)
                                       p.val = value;
                               }
                           }
                       }
                   }
                   if (binCount != 0) {
                       if (binCount >= TREEIFY_THRESHOLD)
                           treeifyBin(tab, i);
                       if (oldVal != null)
                           return oldVal;
                       break;
                   }
               }
           }
           addCount(1L, binCount);
           return null;
       }
  3. 请讲讲ConcurrentHashMap的扩容操作？

    初始化桶操作：判断是否正在扩容，正在的话就让出cpu。否则就用CAS更新sizeCtl（CAS控制只有一个线程初始化桶数组），设置容量，并设置扩容门槛（写死的）赋值给sizeCtl

    addCount操作，元素数量+1，并会判断是否需要扩容，这里是数组数量采用分段锁的思想，根据不同线程存储到不同段上, 先尝试把数量加到baseCount上，如果失败再加到分段的CounterCell上（采用CAS添加）,如果不同线程对应的分段都添加失败，就要扩容段

    扩容：sizeCtl存储着扩容门槛，高位存储扩容邮戳，低位存储存储着扩容线程数加1，即1+nThreads),sc小于0，说明正在扩容，就当前线程加入到迁移元素中去，扩容线程+1；如果没有线程在扩容，自己就扩容，加入迁移元素，sizeCtl低位为2（1+nThreads）

    协助扩容：线程添加元素时发现正在扩容且当前元素所在的桶元素已经迁移完成了，则协助迁移其它桶的元素。迁移完成的标志：如果桶数组不为空，并且当前桶第一个元素为ForwardingNode类型，并且nextTab不为空

    迁移元素：扩容时容量变为两倍，并把部分元素迁移到其它桶中。迁移元素先从靠后的桶开始；迁移完成的桶在里面放置一ForwardingNode类型的元素，标记该桶迁移完成；

    过程：迁移元素是用sychronized锁住该桶，迁移的时候，根据迁移时根据hash&n是否等于0把桶中元素分化成两个链表或树；等于0的在原来的位置，不等于0 就在原来的位置+n,(n的扩大的大小)

    添加元素：

    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
    /**
        * Adds to count, and if table is too small and not already
        * resizing, initiates transfer. If already resizing, helps
        * perform transfer if work is available.  Rechecks occupancy
        * after a transfer to see if another resize is already needed
        * because resizings are lagging additions.
        *
        * @param x the count to add
        * @param check if <0, don't check resize, if <= 1 only check if uncontended
        */
       private final void addCount(long x, int check) {
           CounterCell[] as; long b, s;
           if ((as = counterCells) != null ||
               !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
               CounterCell a; long v; int m;
               boolean uncontended = true;
               if (as == null || (m = as.length - 1) < 0 ||
                   (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                   !(uncontended =
                     U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                   fullAddCount(x, uncontended);
                   return;
               }
               if (check <= 1)
                   return;
               s = sumCount();
           }
           if (check >= 0) {
               Node<K,V>[] tab, nt; int n, sc;
               while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                      (n = tab.length) < MAXIMUM_CAPACITY) {
                   int rs = resizeStamp(n);
                   if (sc < 0) {
                       if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                           sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                           transferIndex <= 0)
                           break;
                       if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                           transfer(tab, nt);
                   }
                   else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                                (rs << RESIZE_STAMP_SHIFT) + 2))
                       transfer(tab, null);
                   s = sumCount();
               }
           }
       }

    协助扩容：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    /**
         * Helps transfer if a resize is in progress.
         */
        final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
            Node<K,V>[] nextTab; int sc;
            if (tab != null && (f instanceof ForwardingNode) &&
                (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
                int rs = resizeStamp(tab.length);
                while (nextTab == nextTable && table == tab &&
                       (sc = sizeCtl) < 0) {
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                        transfer(tab, nextTab);
                        break;
                    }
                }
                return nextTab;
            }
            return table;
        }

    迁移元素：

    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
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    /**
         * Moves and/or copies the nodes in each bin to new table. See
         * above for explanation.
         */
        private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
            int n = tab.length, stride;
            if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
                stride = MIN_TRANSFER_STRIDE; // subdivide range
            if (nextTab == null) {            // initiating
                try {
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                    nextTab = nt;
                } catch (Throwable ex) {      // try to cope with OOME
                    sizeCtl = Integer.MAX_VALUE;
                    return;
                }
                nextTable = nextTab;
                transferIndex = n;
            }
            int nextn = nextTab.length;
            ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
            boolean advance = true;
            boolean finishing = false; // to ensure sweep before committing nextTab
            for (int i = 0, bound = 0;;) {
                Node<K,V> f; int fh;
                while (advance) {
                    int nextIndex, nextBound;
                    if (--i >= bound || finishing)
                        advance = false;
                    else if ((nextIndex = transferIndex) <= 0) {
                        i = -1;
                        advance = false;
                    }
                    else if (U.compareAndSwapInt
                             (this, TRANSFERINDEX, nextIndex,
                              nextBound = (nextIndex > stride ?
                                           nextIndex - stride : 0))) {
                        bound = nextBound;
                        i = nextIndex - 1;
                        advance = false;
                    }
                }
                if (i < 0 || i >= n || i + n >= nextn) {
                    int sc;
                    if (finishing) {
                        nextTable = null;
                        table = nextTab;
                        sizeCtl = (n << 1) - (n >>> 1);
                        return;
                    }
                    if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                        if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                            return;
                        finishing = advance = true;
                        i = n; // recheck before commit
                    }
                }
                else if ((f = tabAt(tab, i)) == null)
                    advance = casTabAt(tab, i, null, fwd);
                else if ((fh = f.hash) == MOVED)
                    advance = true; // already processed
                else {
                    synchronized (f) {
                        if (tabAt(tab, i) == f) {
                            Node<K,V> ln, hn;
                            if (fh >= 0) {
                                int runBit = fh & n;
                                Node<K,V> lastRun = f;
                                for (Node<K,V> p = f.next; p != null; p = p.next) {
                                    int b = p.hash & n;
                                    if (b != runBit) {
                                        runBit = b;
                                        lastRun = p;
                                    }
                                }
                                if (runBit == 0) {
                                    ln = lastRun;
                                    hn = null;
                                }
                                else {
                                    hn = lastRun;
                                    ln = null;
                                }
                                for (Node<K,V> p = f; p != lastRun; p = p.next) {
                                    int ph = p.hash; K pk = p.key; V pv = p.val;
                                    if ((ph & n) == 0)
                                        ln = new Node<K,V>(ph, pk, pv, ln);
                                    else
                                        hn = new Node<K,V>(ph, pk, pv, hn);
                                }
                                setTabAt(nextTab, i, ln);
                                setTabAt(nextTab, i + n, hn);
                                setTabAt(tab, i, fwd);
                                advance = true;
                            }
                            else if (f instanceof TreeBin) {
                                TreeBin<K,V> t = (TreeBin<K,V>)f;
                                TreeNode<K,V> lo = null, loTail = null;
                                TreeNode<K,V> hi = null, hiTail = null;
                                int lc = 0, hc = 0;
                                for (Node<K,V> e = t.first; e != null; e = e.next) {
                                    int h = e.hash;
                                    TreeNode<K,V> p = new TreeNode<K,V>
                                        (h, e.key, e.val, null, null);
                                    if ((h & n) == 0) {
                                        if ((p.prev = loTail) == null)
                                            lo = p;
                                        else
                                            loTail.next = p;
                                        loTail = p;
                                        ++lc;
                                    }
                                    else {
                                        if ((p.prev = hiTail) == null)
                                            hi = p;
                                        else
                                            hiTail.next = p;
                                        hiTail = p;
                                        ++hc;
                                    }
                                }
                                ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                    (hc != 0) ? new TreeBin<K,V>(lo) : t;
                                hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                    (lc != 0) ? new TreeBin<K,V>(hi) : t;
                                setTabAt(nextTab, i, ln);
                                setTabAt(nextTab, i + n, hn);
                                setTabAt(tab, i, fwd);
                                advance = true;
                            }
                        }
                    }
                }
            }
        }
  4. 删除流程：

    a. 删除元素跟添加元素一样，都是先找到元素所在的桶，然后采用分段锁的思想锁住整个桶，再进行操作。
    b. 流程：进入自旋，如果正在扩容，协助扩容，如果没有，对桶加锁，找到元素，删除，如果是树退化成链表，还要进行退化操作，删除了元素，就元素个数-1；返回旧值，没有删除元素就返回null

  5. 获取元素：

    a. 不加锁，
    b. 所以ConcurrentHashMap不是强一致性的‘

  6. Jdk1.7和1.8的区别，底层数据结构有什么不同，put和get操作的不同

    a. 数据结构差别：JDK1.7中ConcurrentHashMap采用了数组+Segment+分段锁，segment继承自ReentrantLock，缺点：需要两次hash，hash时间长。优点：并发能力高，segment之间相互不影响；JDK1.8中，数组+链表+红黑树的实现方式来设计，内部大量采用CAS操作
    b. 数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
    c. 保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
    d. 锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
    e. 链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
    f. 查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。

操作系统

操作系统-存储器管理

1.概述

​ 存储器管理涉及一下五个功能：

​ 1. 存储器分配，主要解决多道程序和多程序如何共享主存的问题

​ 2. 地址转换和重定位，研究各种地址变换方法及相应的地址变换机构

​ 3. 存储器保护

​ 4. 存储器扩充

​ 5. 存储器共享

地址空间：程序限定的空间叫逻辑地址空间，其中的地址叫做相对地址或逻辑地址

存储空间：存储空间是物理存储器中全部物理单元的集合所限定的空间，由字或字节组成的大大的阵列，每个字和字节有自己的编号。

地址重定位：

  1. 链接

    链接就是将汇编/编译产生的一个或多个目标代码与所需要的库函数装配成一个可执行程序；链接有两种方式：静态和动态。采用静态链接时，在程序装入内存运行前，就将目标模块和库事先连接成可执行程序；动态链接分为装入和运行时两种，装入就是指将目标模块装入主存时，边装入边链接，运行就是指运行时才链接。运行时链接的效率更高

  2. 静态重定位

    在逻辑地址转换为物理地址的过程中，地址变换是在进程装入时一次完成的，以后不再改变。

    优点：是无需增加硬件地址转换机构，便于实现程序的静态连接。在早期计算机系统中大多采用这种方案。

    缺点：内存空间不能移动；各个用户进程很难共享内存中同一程序的副本

  3. 动态重定位

    动态运行的装入程序把转入模块装入内存之后，并不立即把装入模块的逻辑地址进行转换，而是把这

    种地址转换推迟到程序执行时才进行，装入内存后的所有地址都仍是逻辑地址。这种方式需要寄存器的支持，其中

    放有当前正在执行的程序在内存空间中的起始地址。

    优点：内存空间可以移动；各个用户进程可以共享内存中同一程序的副本。

    缺点：增加了机器成本，而且实现存储管理的软件算法比较复杂。

    1. 存储器保护

    存储器分为两部分，一是操作系统占用区，另一部分是多用户进程分享的用户占用区。保护涉及两个方面：地址越界和存取方式的保护

    1. 存储器共享
2.单用户单道程序的存储器分配

​ 单一连续区分配，整个系统资源利用率低

3.多用户多道程序存储器分配——分区分配

​ 固定式分区、可变式分区

固定式分区

​ 固定式分区是适合多到程序运行的最简单的存储器管理，把主存用户区预先划分为几个大小不等的区域，当进程到达时，选择一个合适进程要求最小的，空闲分区分给进程；没有合适的空闲分区的时候，让其等待。为了充分利用存储器，将进程按照请求空间的大小在不同分区排队等待。

​ 这种方法管理简单，但有可能出现大分区队列空闲，小分区队列拥挤的现象。当这情况出现时，会使存储器造成更大的浪费，为了充分利用存储器，系统只维护一个存储器等待队列，任何时候，只要有一个分区变为空闲，队列中的一个进程就可装入运行

可变式分区

​ 为了提高存储器的利用率，存储空间的划分推迟到装入进程时进行，当进程要求运行时，系统从空闲的存储空间划分出大小正好等于进程大小的一个存储区分配给进程，这叫做可变式分区或者动态分区，使用这种技术时，分区的大小和个数不断变化。

​ 可变式分区能改进存储器的使用效率，但是却使存储的分配和释放工作复杂了

可变式分区管理使用的数据结构

​ 1.分区说明表：由两张表格组成，一张是已分配区表，记录已分配给进程的分区情况；另一张是未分区表，记录主存空闲区的情况。

​ 2.空闲区链：记录存储空间的一个较好方法就是表格信息附加在每个已分配取和未分配区中，通常将表格信息放在每个分区的首字或尾字中。已分配的信息放在各个进程的PCB表中，空闲区的信息用空闲链表管理

分区管理的地址重定位和存储器保护

​ 固定式分区采用静态重定位，在装入的时候，上下界限两个寄存器来保护存储器，方式地址越界错误

​ 可变式分区采用动态重定位，系统会设置一个基址（重定位）寄存器，存放运行进程分配的主存区起始地址，再增设一个限长寄存器，用来存放运行程序的大小，也是起到保护作用。

分区管理的优缺点

​ 优点：实现了多道程序共享主存、实现分区管理的系统设计相对简单、实现存储器保护的手段也比较简单

​ 缺点：主存利用不够充分、没有实现主存的扩充问题

Git

Git常用命令

git常用操作总结一下，也相当于做个笔记

1、git 配置

git config user.name 查看 用户名

git config user.email 查看 邮箱

git config –global user.name 修改 用户名

git config –global user.email 修改 邮箱

ssh-keygen -t rsa -C “ your_email@example.com“ 创建SSH key 【可以填写任意值作为注释key，例如邮箱】

ssh -T git@gitee.com 测试该SHH key 已添加到 gitee.com【码云】

2、创建版本库

git init 初始化本地版本库【创建一个 .git的子目录】

git init [project-name] 新建一个目录，并将其初始化为 git 代码库；

git clone 克隆远程版本库；

3、修改和提交

git status 显示文件的状态 【红色表示被修改没提交到暂存区，绿色代表已提交到暂存区；】

git status -s 以极简的方式显示文件的状态【红色的M 表示被修改没提交到暂存区，绿色的M代表已提交到暂存区；】

git add 将文件从工作目录添加至暂存区；

　　git add -u | –update 仅将被修改的文件添加至暂存区（不包含新添加的文件）；

　　git add . 将被修改的文件 和 新添加的文件提交到暂存区（不包含已经删除的文件）；

　　git add -a 将本地所有修改的内容添加至暂存区（包含新添加的 和 已经删除的）；

git commit 将暂存区的修改提交到本地仓库，同时生成一个commit-id；

　　git commit -m 将暂存区修改提交到本地仓库

　　git commit -a -m 将工作区的修改提交到本地仓库 【相当于 git add + git commit 】

　　git commit -amend 修改上一次提交【代码没有任何变化，则修改提交信息】

4、分支操作

git branch

　　git branch 列出所有本地分支

　　git branch -r 列出所有远程分支

　　git branch -a 列出所有本地和远程分支

　　git branch [branch-name] 新建一个分支，仍停留在当前分支

　　git branch -m 将分支nameA 改名为 nameB

　　git branch -d [branch-name] 删除分支

git checkout

　　git checkout [branch-name] 切换到指定分支

　　git checkout -b [branch-name] 新建一个分支，并切换到该分支

　　git checkout - 切换到上一个分支

git merge

　　git merge [branch-name] 合并指定分支到当前分支

5、远程操作

git fetch 将远程主机上所有分支的更新取回本地，并记录在 .git/FETCH_HEAD 中；

　　git fetch 下载远程仓库的所有变动；

　　git fetch master:test 在本地新建test 分支，并将主机上master分支代码下载到本地 test 分支；

git remote

　　git remote -v 显示所有远程仓库

　　git remote show 显示某个远程仓库的信息

　　git remote add [ url ] 增加一个新的远程仓库 并命名

git pull

　　git pull <远程主机名> <远程分支名> : <本地分支名> 取回远程仓库某个分支的更新，并与本地分支合并

　　git pull origin dev: master 取回远程主机的 dev 分支，与本地的master分支合并

　　git pull origin dev 相当于以下两个命令：

　　　　git fetch origin 获取远程主机上所有分支的更新

　　　　git merge origin/dev 与当前分支合并

git push

　　git push <远程主机名> <本地分支名> : <远程分支> 上传本地指定分支到远程仓库的指定分支

　　　　省略远程分支名，表示将本地分支推送到与之存在“追踪关系”的远程分支，通常两者同名，后者不存在，将会被创建；

　　　　省略本地分支名，表示删除指定的远程分支【这相当推送一个空的本地分支到远程分支】；

　　git push origin master 将本地的master 分支推送到 origin 主机的master 分支【后者不存在，将会被创建】

　　git push origin : master 删除 origin 主机的master 分支；【相当于 git push origin –delete master】

6、撤销修改

撤销工作区的修改： 【文件修改之后撤销】

　　git checkout – file 恢复暂存区的指定文件到工作区

　　git checkout . 恢复暂存区的所有文件到工作区

撤销暂存区的修改： 【git add 之后】

　　git reste HEAD

版本回退 ：

　　 git reset –hard

git log 查看提交历史，确定回退到那个版本；

git reflog 查看历史命令，确定回到未来的版本；

参考：https://www.cnblogs.com/james23dong/p/12375970.html

Netty

Netty介绍

一、什么是Netty

​ Netty是由JBOSS提供的一个java开源框架。Netty提供异步的、事件驱动的网络应用程序框架和工具，用以快速开发高性能、高可靠性的网络服务器和客户端程序

​ 也就是说，Netty 是一个基于NIO的客户、服务器端编程框架，使用Netty 可以确保你快速和简单的开发出一个网络应用，例如实现了某种协议的客户，服务端应用。Netty相当简化和流线化了网络应用的编程开发过程，例如，TCP和UDP的socket服务开发。

我们下面编写四个类

1.用于接收数据的服务器端Socket

2.用于接收客户端的消息，用于接收和反馈客户端发出的消息类ServertHandler

3.用于发送数据的服务器端Client

4.用于发送数据和接收服务器端发出的数据处理类ClientHandler

Socket.java

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
import io.netty.bootstrap.ServerBootstrap;
import io.netty.buffer.ByteBuf;
import io.netty.buffer.Unpooled;
import io.netty.channel.ChannelFuture;
import io.netty.channel.ChannelInitializer;
import io.netty.channel.ChannelOption;
import io.netty.channel.EventLoopGroup;
import io.netty.channel.nio.NioEventLoopGroup;
import io.netty.channel.socket.SocketChannel;
import io.netty.channel.socket.nio.NioServerSocketChannel;
import io.netty.handler.codec.DelimiterBasedFrameDecoder;
import io.netty.handler.codec.string.StringDecoder;
 
public class Server {
	
	public static void main(String[] args) throws InterruptedException {
		//1.第一个线程组是用于接收Client端连接的
		EventLoopGroup bossGroup = new NioEventLoopGroup(); 
		//2.第二个线程组是用于实际的业务处理的
		EventLoopGroup workerGroup = new NioEventLoopGroup();
		ServerBootstrap b = new ServerBootstrap();
		b.group(bossGroup, workerGroup);//绑定两个线程池
		b.channel(NioServerSocketChannel.class);//指定NIO的模式，如果是客户端就是NioSocketChannel
		b.option(ChannelOption.SO_BACKLOG, 1024);//TCP的缓冲区设置
		b.option(ChannelOption.SO_SNDBUF, 32*1024);//设置发送缓冲的大小
		b.option(ChannelOption.SO_RCVBUF, 32*1024);//设置接收缓冲区大小
		b.option(ChannelOption.SO_KEEPALIVE, true);//保持连续
		b.childHandler(new ChannelInitializer<SocketChannel>() {
			@Override
			protected void initChannel(SocketChannel sc) throws Exception {
				ByteBuf buf = Unpooled.copiedBuffer("$_".getBytes());//拆包粘包定义结束字符串（第一种解决方案）
				sc.pipeline().addLast(new DelimiterBasedFrameDecoder(1024,buf));//在管道中加入结束字符串
			//	sc.pipeline().addLast(new FixedLengthFrameDecoder(200));第二种定长
				sc.pipeline().addLast(new StringDecoder());//定义接收类型为字符串把ByteBuf转成String
				sc.pipeline().addLast(new ServertHandler());//在这里配置具体数据接收方法的处理
			}
		});
		ChannelFuture future = b.bind(8765).sync();//绑定端口
		future.channel().closeFuture().sync();//等待关闭(程序阻塞在这里等待客户端请求)
		bossGroup.shutdownGracefully();//关闭线程
		workerGroup.shutdownGracefully();//关闭线程
	}
}

1.在上面这个Server.java中，我们都要定义两个线程池，boss和worker，boss是用于管理连接到server端的client的连接数的线程池，而woeker是用于管理实际操作的线程池。

2.ServerBootstrap用一个ServerSocketChannelFactory 来实例化。ServerSocketChannelFactory 有两种选择，一种是NioServerSocketChannelFactory，一种是OioServerSocketChannelFactory。 前者使用NIO，后则使用普通的阻塞式IO。它们都需要两个线程池实例作为参数来初始化，一个是boss线程池，一个是worker线程池。

3.然后使ServerBookstrap管理boss和worker线程池。并且设置各个缓冲区的大小。

4.这里的事件处理类经常会被用来处理一个最近的已经接收的Channel。ChannelInitializer是一个特殊的处理类，他的目的是帮助使用者配置一个新的Channel。也许你想通过增加一些处理类比如NettyServerHandler来配置一个新的Channel 或者其对应的ChannelPipeline来实现你的网络程序。 当你的程序变的复杂时，可能你会增加更多的处理类到pipline上，然后提取这些匿名类到最顶层的类上。

5.在使用原始的encoder、decoder的情况下，Netty发送接收数据都是按照ByteBuf的形式，其它形式都是不合法的。 而在上面这个Socket中，我使用sc.pipeline().addLast()这个方法设置了接收为字符串类型，注意：只能设置接收为字符串类型，发送还是需要发送ByteBuf类型的数据。而且在这里我还设置了以$_为结尾的字符串就代表了本次请求字符串的结束。

6.通过b.bind绑定端口，用于监听的端口号。

ServerHandler.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class ServertHandler extends ChannelHandlerAdapter {
 
	@Override
	public void channelRead(ChannelHandlerContext ctx, Object msg) throws Exception {
		String body = (String) msg;
		System.out.println("server"+body);//前面已经定义了接收为字符串，这里直接接收字符串就可以
		//服务端给客户端的响应
		String response= " hi client!$_";//发送的数据以定义结束的字符串结尾
		ctx.writeAndFlush(Unpooled.copiedBuffer(response.getBytes()));//发送必须还是ByteBuf类型
	}
 
	@Override
	public void exceptionCaught(ChannelHandlerContext ctx, Throwable cause) throws Exception {
		 cause.printStackTrace();
		  ctx.close();
	}	
}

ServertHandler继承自 ChannelHandlerAdapter，这个类实现了ChannelHandler接口，ChannelHandler提供了许多事件处理的接口方法，然后你可以覆盖这些方法。现在仅仅只需要继承ChannelHandlerAdapter类而不是你自己去实现接口方法。

1.由于我们再server端开始的时候已经定义了接收类型为String，所以在这里我们接收到的msg直接强转成String就可以了。同时也要定义以什么为一次请求的结尾。

Client.java

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 class Client {
 
	public static void main(String[] args) throws InterruptedException {
		EventLoopGroup worker = new NioEventLoopGroup();
		Bootstrap b = new Bootstrap();
		b.group(worker)
		.channel(NioSocketChannel.class)
		.handler(new ChannelInitializer<SocketChannel>() {
			@Override
			protected void initChannel(SocketChannel sc) throws Exception {
				ByteBuf buf = Unpooled.copiedBuffer("$_".getBytes()); 
				sc.pipeline().addLast(new DelimiterBasedFrameDecoder(1024,buf));
				sc.pipeline().addLast(new StringDecoder());
				sc.pipeline().addLast(new ClientHandler());
			}
		});
		ChannelFuture f=b.connect("127.0.0.1",8765).sync();
		f.channel().writeAndFlush(Unpooled.copiedBuffer(" hi server2$_".getBytes()));
		f.channel().writeAndFlush(Unpooled.copiedBuffer(" hi server3$_".getBytes()));
		f.channel().writeAndFlush(Unpooled.copiedBuffer(" hi server4$_".getBytes()));
		f.channel().closeFuture().sync();
		worker.shutdownGracefully();
	}
}

client端和Socket端几乎代码相同，只是client端用的不是ServerBootstrap而是Bootstrap来管理连接

ClientHandler.java

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

public class ClientHandler extends ChannelHandlerAdapter{
	@Override
	public void channelRead(ChannelHandlerContext ctx, Object msg) throws Exception {
		try {
			System.out.println("client"+msg.toString());
		} finally {
			ReferenceCountUtil.release(msg);//释放缓冲区
		}
	}
 
	@Override
	public void exceptionCaught(ChannelHandlerContext ctx, Throwable cause) throws Exception {
		 cause.printStackTrace();
		  ctx.close();
	}
}

ClientHandler和ServertHandler代码和原理也是一样，只是在client端我们要释放缓冲区。为什么在ServerHandler我们不需要释放呢 ？因为在ServertHandler我们调用ctx.writeAndFlush方法的时候，这个方法默认已经帮我们释放了缓冲区。

参考：https://blog.csdn.net/a347911/article/details/53734255