发表于

这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战

剑指 Offer II 033. 变位词组

给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。

注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
lua复制代码示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

 

提示：

    1 <= strs.length <= 104
    0 <= strs[i].length <= 100
    strs[i] 仅包含小写字母

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/sf…

思路

  • 这道题大家会不会想到之前的有效的变位词
    • 首先回忆有效的变位词这道题的思路
    • 判断abcdefg和gfedcba是异位词，我们只需要构建一个哈希表
    • 或者为了更简单，就创建一个26位的数组，最开始遍历第一个字符串，对应索引位置加一
    • 第二次遍历第二个字符串，对应索引位减一，如果最后数组都为零0️⃣，那么就代表这两个字符串真的是字母相同，而位置不同而已(异位词)
  • 回过头来看这道题，我们有两种方式去实现
    1. 第一种就是将字母进行排序，最后再定义一个哈希表
    2. 而第二种当时我们可以想到，如果将每个英文小写字母映射到对应一个质数的话
    • 那么每个字符串的字母对应质数最后的乘积，最后一定是相同的就一定为同一个字母
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
java复制代码class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int code[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
        43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

        Map<Long,List<String>> team = new HashMap<>();
        for (String str : strs) {
            long wordHash = 1;
            for (int i = 0; i < str.length(); i++) {
                wordHash *= code[str.charAt(i) - 'a'];
            }
            team.putIfAbsent(wordHash,new LinkedList<String>());
            team.get(wordHash).add(str);
        }

        return new LinkedList<>(team.values());
    }
}

本文转载自: 掘金

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

发表于

这是我参与11月更文挑战的第7天，活动详情查看：2021最后一次更文挑战

简介

本文在之前文章Druid使用流程文章基础下，来实现在多线程请求下的数据库连接池初步Demo，实现一个多线程下能跑的最基础版本

探索Alibaba Druid的物理连接生成

参考Alibaba Druid数据库的实现：Alibaba Druid 源码阅读（六）数据库连接使用流程初探

我们主要的实现思路如下：

  • 1.初始化配置的初始物理连接数
  • 2.获取连接时，从空闲线程池中阻塞获取
  • 3.获取连接时，发送生成物理连接指令去生成新的物理连接，但物理连接数不得大于配置的最大连接数
  • 4.连接关闭时，归还空闲线程池

在Alibaba Druid中是使用等待-通知机制来阻塞获取的，我们简单点，就用一个阻塞队列实现这个

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
java复制代码public class SelfDataSource implements DataSource {

    /**
     * 放置空闲可用的连接
     */
    private final LinkedBlockingDeque<SelfPoolConnection> idle = new LinkedBlockingDeque<>();
    /**
     * 放置正在使用的连接
     */
    private final LinkedBlockingDeque<SelfPoolConnection> active = new LinkedBlockingDeque<>();
    private final AtomicInteger connectCount = new AtomicInteger(0);

    private final String url;
    private final String username;
    private final String password;
    private int maxActive;
    private int timeout = 100;

    public SelfDataSource(final Properties properties) {
        this.url = properties.getProperty("url");
        this.username = properties.getProperty("username");
        this.password = properties.getProperty("password");
        this.maxActive = Integer.parseInt(properties.getProperty("maxActive"));
        this.timeout = Integer.parseInt(properties.getProperty("timeout", "100"));

        final int initCount = Integer.parseInt(properties.getProperty("initCount", "0"));
        if (initCount > maxActive) {
            throw new RuntimeException("initCount gt maxActive");
        }

        IntStream.range(0, initCount).forEach(i -> createPhysicsConnect());
    }

    private void createPhysicsConnect() {
        try {
            idle.put(new SelfPoolConnection(this, url, username, password));
            connectCount.addAndGet(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

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
java复制代码public class SelfDataSource implements DataSource {

    /**
     * 放置空闲可用的连接
     */
    private final LinkedBlockingDeque<SelfPoolConnection> idle = new LinkedBlockingDeque<>();
    /**
     * 放置正在使用的连接
     */
    private final LinkedBlockingDeque<SelfPoolConnection> active = new LinkedBlockingDeque<>();

    /**
     * 自定义的获取数据库物理连接
     * 1.无空闲连接则生成新的物理连接，并且放入正在运行连接池中
     * 2.如果有空闲连接，则获取，并放入正在运行连接池中
     * @return 自定义的数据库物理连接（自定义以能够自定义Close方法）
     * @throws SQLException
     */
    @Override
    public Connection getConnection() throws SQLException {
        try {
            final SelfPoolConnection connection = idle.take();
            System.out.println("获取连接，结束\n");
            active.put(connection);
            return connection;
        } catch (InterruptedException e) {
            e.printStackTrace();
            throw new RuntimeException(e);
        }
    }
}

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
java复制代码public class SelfDataSource implements DataSource {

    /**
     * 放置空闲可用的连接
     */
    private final LinkedBlockingDeque<SelfPoolConnection> idle = new LinkedBlockingDeque<>();
    /**
     * 放置正在使用的连接
     */
    private final LinkedBlockingDeque<SelfPoolConnection> active = new LinkedBlockingDeque<>();

    /**
     * 初步将Connection从运行池中异常，放入空闲池
     * 从正在使用连接池中移除，放入空闲连接池中
     * @param selfPoolConnection 自定义Connection
     */
    public void recycle(final SelfPoolConnection selfPoolConnection) {
        try {
            while (!active.remove(selfPoolConnection)) {}
            System.out.println("回收连接,结束\n");
            idle.put(selfPoolConnection);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

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
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
java复制代码public class MultiThreadSelfTest {

    public static final String DB_URL = "jdbc:h2:file:./demo-db";
    public static final String USER = "sa";
    public static final String PASS = "sa";
    public static final String QUERY = "SELECT id, name FROM user_example";


    public static void main(String[] args) throws InterruptedException, ExecutionException {
        // 第一次运行可以初始化数据库数据，后面可以取消
//        initData();

        final Properties properties = new Properties();
        properties.setProperty("url", "jdbc:h2:file:./demo-db");
        properties.setProperty("username", "sa");
        properties.setProperty("password", "sa");
        properties.setProperty("maxActive", "5");
        properties.setProperty("initCount", "5");

        SelfDataSource dataSource = new SelfDataSource(properties);

        FutureTask[] fs = new FutureTask[10];
        for (int i=0; i<10; i++) {
            fs[i] = new FutureTask(() -> druidQuery(dataSource));
            new Thread(fs[i]).start();
        }

        while (true) {
            for (int i = 0; i < 10; i++) {
                if (!fs[i].isDone()) {
                    continue;
                }
            }
            break;
        }
        
        Thread.sleep(3000);
        System.out.printf("当前数据库连接数：%d\n", dataSource.getConnectionCount());
    }

    /**
     * 生成数据
     */
    public static void initData() {
        final String drop = "drop table `user_example` if exists;";
        final String createTable = "CREATE TABLE IF NOT EXISTS `user_example` (" +
                "`id` bigint NOT NULL AUTO_INCREMENT, " +
                "`name` varchar(100) NOT NULL" +
                ");";
        final String addUser = "insert into user_example (name) values(%s)";
        try(Connection conn = DriverManager.getConnection(DB_URL, USER, PASS);
            Statement stmt = conn.createStatement()) {
            stmt.execute(drop);
            stmt.execute(createTable);
            for (int i=0; i<10; i++) {
                stmt.execute(String.format(addUser, i));
            }
            conn.commit();
        } catch (SQLException e) {
            e.printStackTrace();
        }
    }

    private static long druidQuery(SelfDataSource dataSource) {
        System.out.println("开始执行查询");
        final long cur = System.currentTimeMillis();
        try(Connection conn = dataSource.getConnection();
            Statement stmt = conn.createStatement();
            ResultSet rs = stmt.executeQuery(QUERY)) {
            while (rs.next()) {
            }
            Thread.sleep(1000);
        } catch (SQLException | InterruptedException e) {
            e.printStackTrace();
        }
        final long cost = System.currentTimeMillis() - cur;
        System.out.println("查询结束，耗时：" + cost);
        return cost;
    }
}

结果及分析如下：

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
tex复制代码// 生成最初的五个物理连接
初始化物理连接
初始化物理连接
初始化物理连接
初始化物理连接
初始化物理连接

开始执行查询
开始执行查询
获取连接，结束 // 使用数 1 空闲数 4
开始执行查询
获取连接，结束 // 使用数 2 空闲数 3
开始执行查询
获取连接，结束 // 使用数 3 空闲数 2
开始执行查询
开始执行查询
获取连接，结束 // 使用数 4 空闲数 1
开始执行查询
获取连接，结束 // 使用数 5 空闲数 0
开始执行查询
开始执行查询
开始执行查询
回收连接,结束 // 使用数 4 空闲数 1
回收连接,结束 // 使用数 3 空闲数 2
回收连接,结束 // 使用数 2 空闲数 3

查询结束，耗时：1034
查询结束，耗时：1034
查询结束，耗时：1034

获取连接，结束 // 使用数 3 空闲数 2
回收连接,结束 // 使用数 2 空闲数 3
获取连接，结束 // 使用数 3 空闲数 2
回收连接,结束 // 使用数 2 空闲数 3

查询结束，耗时：1034

获取连接，结束 // 使用数 3 空闲数 2
获取连接，结束 // 使用数 4 空闲数 1
获取连接，结束 // 使用数 5 空闲数 0

查询结束，耗时：1035

回收连接,结束
回收连接,结束

查询结束，耗时：2041

回收连接,结束
回收连接,结束
回收连接,结束

查询结束，耗时：2042
查询结束，耗时：2041
查询结束，耗时：2041
查询结束，耗时：2042

当前数据库连接数：5

总结

运行结果看起来大致符合我们的预期，但总感觉还有有一些不对劲的地方，现在暂时还看不出来

下面还有一些未完成的：

  • 最小空闲线程数的实现
  • 动态线程的生成

后面继续完善吧，还有就是和Alibaba Druid的运行对比，这些后面继续写和研究

代码参考地址，可查看Tag V0.0.1：github.com/lw124392545…

参考链接

本文转载自: 掘金

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

发表于

这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战

  1. 图文分析

来看下面这行代码。

1
java复制代码String alita = "阿丽塔";

这行代码在字符串常量池中创建了一个内容为“阿丽塔”的对象，并将其赋值给了字符串变量 alita（存储的是字符串对象”阿丽塔”的引用）。如下图所示。
在这里插入图片描述
再看下面这段代码：

1
java复制代码String wanger = alita;

这行代码将字符串变量 alita 赋值给了字符串变量 wanger。这时候，wanger 和 alita 存储的是同一个字符串对象的引用。如下图所示。
在这里插入图片描述
再来看下面这行代码。

1
java复制代码alita = "战斗天使".concat(alita);

这行代码将字符串“战斗天使”拼接在字符串变量 alita 的前面，并重新赋值给 alita。这个过程就比之前的复杂了。我们需要先来看看 concat() 方法做了什么，源码如下所示。

1
2
3
4
5
6
7
8
9
10
java复制代码public String concat(String str) {
  int otherLen = str.length();
  if (otherLen == 0) {
  	return this;
  }
  int len = value.length;
  char buf[] = Arrays.copyOf(value, len + otherLen);
  str.getChars(buf, len);
  return new String(buf, true);
}

可以看得出，“战斗天使”.concat(alita) 这行代码会先在字符串常量池中创建一个新的字符串对象，内容为“战斗天使”，然后 concat() 方法会将其对应的字符数组和“阿丽塔”对应的字符数组复制到一个新的字符数组 buf 中，最后，再通过 new 关键字创建了一个新的字符串对象，并返回。如下图所示。
在这里插入图片描述

从上图中可以得出结论，alita 此时引用的是在堆中新创建的字符串对象。

  1. 对象和对象引用

可能有些读者看完上面的图文分析没有理解反而更疑惑了：alita 不是变了吗？从“阿丽塔”变为“战斗天使阿丽塔”？怎么还说字符串是不可变的呢？

这里需要给大家解释一下，什么是对象，什么是对象引用。

在 Java 中，由于不能直接操作对象本身，所以就有了对象引用这个概念，对象引用存储的是对象在内存中的地址。

PS：Java 虚拟机在执行程序的过程中会把内存区域划分为若干个不同的数据区域，如下图所示。
在这里插入图片描述

对象存储在堆（heap）中，而对象的引用存储在栈（stack）中。

我们通常所说的“字符串是不可变的”是指“字符串对象是不可变的”。alita 是字符串对象“阿丽塔”或者“战斗天使阿丽塔”的引用。这下应该明白了吧？

  1. 源码分析

我们来看一下 String 类的部分源码。

1
2
3
4
5
java复制代码public final class String
implements java.io.Serializable, Comparable<String>, CharSequence {
/** The value is used for character storage. */
private final char value[];
}

可以看得出， String 类其实是通过操作字符数组 value 实现的。而 value 是 private 的，也没有提供 serValue() 这样的方法进行修改；况且 value 还是 final 的，意味着 value 一旦被初始化，就无法进行改变。

另外呢，String 类提供的方法，比如说 substring()：

1
2
3
4
5
6
7
8
9
java复制代码public String substring(int beginIndex) {
int subLen = value.length - beginIndex;
return (beginIndex == 0) ? this : new String(value, beginIndex, subLen);
}
toLowerCase()：

public String toLowerCase(Locale locale) {
return new String(result, 0, len + resultOffset);
}

还有之前提到的 concat()，看似都能改变字符串的内容，但其实都是在方法内部使用 new 关键字重新创建的新字符串对象。

  1. 为什么要不可变

String 类的源码中还有一个重要的字段 hash，用来保存字符串对象的 hashCode。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
java复制代码public final class String
implements java.io.Serializable, Comparable<String>, CharSequence {

  /** Cache the hash code for the string */
  private int hash; // Default to 0

  public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
    	char val[] = value;

    	for (int i = 0; i < value.length; i++) {
      	h = 31 * h + val[i];
      }
    	hash = h;
    }
    return h;
  }
}

因为字符串是不可变的，所以一旦被创建，它的 hash 值就不会再改变了。由此字符串非常适合作为 HashMap 的 key 值，这样可以==极大地提高效率==。

另外呢，不可变对象天生是==线程安全==的，因此字符串可以在多个线程之间共享。

举个反面的例子，假如字符串是可变的，那么数据库的用户名和密码（字符串形式获得数据库连接）将不再安全，一些高手可以随意篡改，从而导致严重的安全问题。

  1. 最后

总结一下，字符串一旦在内存中被创建，就无法被更改。String 类的所有方法都不会改变字符串本身，而是返回一个新的字符串对象。如果需要一个可修改的字符序列，建议使用 StringBuffer 或 StringBuilder 类代替 String 类，否则每次创建的字新符串对象会导致 Java 虚拟机花费大量的时间进行垃圾回收。

本文转载自: 掘金

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

发表于

这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战

==本文是基于Rest API的，返回的错误信息是json格式的数据！需要注意的是这个只是对发生异常的时候，统一了一下返回结果的格式，并不是对异常的try catch，控制台依旧会打印出异常日志==
完整项目地址：
github.com/Dr-Water/sp…

  1. springboot的默认异常处理方式，非常不美观：例如下面的：

在这里插入图片描述

  1. 我们可以使用springMVC的@ControllerAdvice注解实现全局的异常处理，并统一异常的返回格式，步骤如下：

  1. 创建统一的JSON返回对象，code：消息类型，message：消息内容，url：请求的url，data：请求返回的数据
1
2
3
4
5
6
7
8
9
10
11
12
java复制代码@Data
public class ErrorInfo<T> {

    public static final Integer OK = 0;
    public static final Integer ERROR = 100;

    private Integer code;
    private String message;
    private String url;
    private T data;

}
  1. 创建一个自定义异常，用来实验捕获该异常，并返回json
1
2
3
4
5
6
7
java复制代码public class MyException extends Exception {

    public MyException(String message) {
        super(message);
    }
    
}
  1. Controller中增加json映射，抛出MyException异常
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
java复制代码@RestController
public class HelloController {

    /** 用于测试自定义异常
     * @return
     * @throws Exception
     */
    @RequestMapping("/json")
    public String json() throws Exception {
        throw new MyException("发生错误啦啦啦啦");
    }

    /** 用于测试除自定义异常以外的异常
     * @return
     */
    @RequestMapping("/json2")
    public Integer json2(){
        return 2/0;
    }
}
  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
java复制代码@ControllerAdvice
public class GlobalExceptionHandler {

    /**
     * 最大的异常捕获类，用于最后兜底的异常的处理器
     * @param req
     * @param e
     * @return
     * @throws Exception
     */
    @ExceptionHandler(value = Exception.class)
    @ResponseBody
    public ErrorInfo<String> jsonErrorHandler(HttpServletRequest req, Exception e) throws Exception {
        ErrorInfo<String> r = new ErrorInfo<>();
        r.setMessage(e.getMessage());
        r.setCode(ErrorInfo.ERROR);
        r.setData("Some Data");
        r.setUrl(req.getRequestURL().toString());
        return r;
    }

    /**
     * 用于捕获自己自定的异常，自定义的异常是处理器可以有多个，
     * 发生异常的时候如果匹配到的自定义的异常则不再匹配上面的最大的异常处理器（即：jsonErrorHandler）
     * @param req
     * @param e
     * @return
     * @throws Exception
     */
    @ExceptionHandler(value = MyException.class)
    @ResponseBody
    public ErrorInfo<String> myjsonErrorHandler(HttpServletRequest req, MyException e) throws Exception {
        ErrorInfo<String> r = new ErrorInfo<>();
        r.setMessage(e.getMessage());
        r.setCode(ErrorInfo.ERROR);
        r.setData("Some Data====myjsonErrorHandler");
        r.setUrl(req.getRequestURL().toString());
        return r;
    }
}
  1. 测试

启动应用进行测试 访问：http://localhost:8080/json 可以得到如下的返回结果：
在这里插入图片描述
http://localhost:8080/json2 可以得到如下的返回结果：
在这里插入图片描述
第一个图由于是抛出的自定义的异常则返回的data信息里是自己在自定义异常处理器封装的数据即：==Some Data====myjsonErrorHandler== ，第二个图由于抛出的一个算术异常，默认被最大的exception拦截所以最后 data里的数据是：==”Some Data”==

本文转载自: 掘金

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

发表于

一、概述

书籍系统框架如图:

书籍系统.png

文件内容持续更新在GitHub上，可自行查看。

本篇主要是介绍：评论和阅读量中的评论

二、评论

思路

1.对文章的评论

2.对评论的回复

3.让数据呈现树状结构

数据库设计

评论数据表设计.png

parent_id指向父评论id，如果是文章的评论默认为0.

代码

1.因为评论是树状结构，所以在微服务部分做了树数据的嵌套。

action.proto

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
protobuf复制代码syntax = "proto3";

package action;

option go_package = "action";

message Request {
  string ping = 1;
}

message Response {
  bool ok = 1;
  string message = 2;
}

message CommentReq{
  int64 Id = 1;
  int64 ParentId = 2;
  int64 BookContentId = 3;
  string Comment = 4;
  int64 CommentByUserId = 5;
  string CommentByNickname = 6;
  int64 CommentToUserId = 7;
  string CommentToNickname = 8;
}

message CommentResp{
  int64 Id = 1;
  int64 ParentId = 2;
  int64 BookContentId = 3;
  string Comment = 4;
  int64 CommentByUserId = 5;
  string CommentByNickname = 6;
  int64 CommentToUserId = 7;
  string CommentToNickname = 8;
}

message CommentsNodeResp{
  CommentResp Comments = 1;
  repeated CommentsNodeResp CommentsNode = 2;
}

message CommentsTreeResp{
  repeated CommentsNodeResp CommentsTree = 1;
}

service Action {
  //Comments
  rpc GetCommentsByBookContentId(CommentReq) returns(CommentsTreeResp);
  rpc CreateComment(CommentReq) returns(Response);
  rpc UpdateComment(CommentReq) returns(Response);
  rpc DeleteComment(CommentReq) returns(Response);
}

2.在逻辑代码中把数据库中的数据组合成树数据

getcommentsbybookcontentidlogic.go

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
golang复制代码// Comments
func (l *GetCommentsByBookContentIdLogic) GetCommentsByBookContentId(in *action.CommentReq) (*action.CommentsTreeResp, error) {
	comments, err := l.svcCtx.CommentModel.FindCommentsByBookContentId(in.BookContentId)
	if err != nil {
		return nil, err
	}
	fmt.Println("comments", comments)

	f := func(cs []*model.Comment) *action.CommentsTreeResp {
		//树结构
		var res = action.CommentsTreeResp{
			CommentsTree: make([]*action.CommentsNodeResp, 0),
		}
		for i := 0; i < len(cs); i++ {
			if cs[i].ParentId == 0 {
				res.CommentsTree = append(res.CommentsTree, &action.CommentsNodeResp{
					Comments: &action.CommentResp{
						Id:                cs[i].Id,
						ParentId:          cs[i].ParentId,
						BookContentId:     cs[i].BookContentId,
						Comment:           cs[i].Comment,
						CommentByUserId:   cs[i].CommentByUserId,
						CommentByNickname: cs[i].CommentByNickname,
						CommentToUserId:   cs[i].CommentToUserId,
						CommentToNickname: cs[i].CommentToNickname,
					},
				})
			} else {
				node := FindCommentNodeByParentId(res.CommentsTree, cs[i].ParentId)
				if node != nil {
					node.CommentsNode = append(node.CommentsNode, &action.CommentsNodeResp{
						Comments: &action.CommentResp{
							Id:                cs[i].Id,
							ParentId:          cs[i].ParentId,
							BookContentId:     cs[i].BookContentId,
							Comment:           cs[i].Comment,
							CommentByUserId:   cs[i].CommentByUserId,
							CommentByNickname: cs[i].CommentByNickname,
							CommentToUserId:   cs[i].CommentToUserId,
							CommentToNickname: cs[i].CommentToNickname,
						},
					})
				}
			}
		}
		return &res
	}
	return f(comments), nil
}

//找到id对应的节点
func FindCommentNodeByParentId(res []*action.CommentsNodeResp, id int64) *action.CommentsNodeResp {
	for i := 0; i < len(res); i++ {
		if id == res[i].Comments.Id {
			return res[i]
		} else {
			if r := FindCommentNodeByParentId(res[i].CommentsNode, id); r != nil {
				return r
			}
		}
	}
	return nil
}

3.在做前端的时候，发现评论一般都是只有父子两级，所以在WebApi中把所有的对评论的回复又组合成子级。–！有苦说不出。

get_comment_handler.go

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
golang复制代码package action

import (
	"WebApi/Pb/action"
	"WebApi/Svc"
	"context"
	"github.com/gin-gonic/gin"
	"net/http"
	"strconv"
)

func GetCommentsByBookContentIdHandler(c *gin.Context) {
	bookContentId, err := strconv.ParseInt(c.Query("bookContentId"), 10, 64)
	if err != nil {
		c.JSON(http.StatusBadRequest, gin.H{"error": err.Error()})
		return
	}
	ctx := context.Background()
	//树状结构（评论)
	res, err := Svc.SvcContext.Grpc.ActionGrpc.GetCommentsByBookContentId(ctx, &action.CommentReq{
		BookContentId: bookContentId,
	})
	//树状结构 平铺为 只有父子节点结构（评论)  方便前端使用
	tn := func(t *action.CommentsTreeResp) action.CommentsTreeResp {
		var tree = action.CommentsTreeResp{}
		for i := 0; i < len(t.CommentsTree); i++ {
			//组合父节点
			tree.CommentsTree = append(tree.CommentsTree, &action.CommentsNodeResp{
				Comments: t.CommentsTree[i].Comments,
			})
			//组合父节点下所有的节点
			combChildComment(t.CommentsTree[i].CommentsNode, &tree.CommentsTree[i].CommentsNode)
		}
		return tree
	}

	if err != nil {
		c.JSON(http.StatusBadRequest, gin.H{"error": err.Error()})
	} else {
		c.JSON(http.StatusOK, tn(res))
	}
}

func combChildComment(src []*action.CommentsNodeResp, dest *[]*action.CommentsNodeResp) {
	for i := 0; i < len(src); i++ {
		*dest = append(*dest, &action.CommentsNodeResp{
			Comments: src[i].Comments,
		})
		if src[i].CommentsNode != nil {
			combChildComment(src[i].CommentsNode, dest)
		}
	}

}

4.POSTman的结果展示

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
postman复制代码{
    "CommentsTree": [
        {
            "Comments": {
                "Id": 1,
                "BookContentId": 2,
                "Comment": "写得好。",
                "CommentByUserId": 1,
                "CommentByNickname": "书店老板",
                "CommentToUserId": 1,
                "CommentToNickname": "书店老板"
            },
            "CommentsNode": [
                {
                    "Comments": {
                        "Id": 3,
                        "ParentId": 1,
                        "BookContentId": 2,
                        "Comment": "马屁精。",
                        "CommentByUserId": 2,
                        "CommentByNickname": "张三",
                        "CommentToUserId": 1,
                        "CommentToNickname": "书店老板"
                    }
                },
                {
                    "Comments": {
                        "Id": 4,
                        "ParentId": 3,
                        "BookContentId": 2,
                        "Comment": "来来来，笔给你，你来写",
                        "CommentByUserId": 3,
                        "CommentByNickname": "李四",
                        "CommentToUserId": 2,
                        "CommentToNickname": "张三"
                    }
                }
            ]
        },
        {
            "Comments": {
                "Id": 5,
                "BookContentId": 2,
                "Comment": "写得好1。",
                "CommentByUserId": 1,
                "CommentByNickname": "书店老板",
                "CommentToUserId": 1,
                "CommentToNickname": "书店老板"
            },
            "CommentsNode": [
                {
                    "Comments": {
                        "Id": 8,
                        "ParentId": 5,
                        "BookContentId": 2,
                        "Comment": "不好",
                        "CommentByUserId": 4,
                        "CommentByNickname": "王五",
                        "CommentToUserId": 1,
                        "CommentToNickname": "书店老板"
                    }
                },
                {
                    "Comments": {
                        "Id": 9,
                        "ParentId": 8,
                        "BookContentId": 2,
                        "Comment": "不好才怪",
                        "CommentByUserId": 4,
                        "CommentByNickname": "王五",
                        "CommentToUserId": 4,
                        "CommentToNickname": "王五"
                    }
                }
            ]
        },
        {
            "Comments": {
                "Id": 10,
                "BookContentId": 2,
                "Comment": "我是第一",
                "CommentByUserId": 4,
                "CommentByNickname": "王五",
                "CommentToUserId": 4,
                "CommentToNickname": "王五"
            }
        },
        {
            "Comments": {
                "Id": 11,
                "BookContentId": 2,
                "Comment": "第二",
                "CommentByUserId": 4,
                "CommentByNickname": "王五",
                "CommentToUserId": 4,
                "CommentToNickname": "王五"
            }
        },
        {
            "Comments": {
                "Id": 12,
                "BookContentId": 2,
                "Comment": "文章YYDS。",
                "CommentByUserId": 1,
                "CommentByNickname": "书店老板",
                "CommentToUserId": 1,
                "CommentToNickname": "书店老板"
            }
        }
    ]
}

5.前端成果展示

评论.png

三、Tips

最近工作中忙了起来，更新可能会比之前慢一些，请多多包涵。

本文转载自: 掘金

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

发表于

这是我参与11月更文挑战的第7天，活动详情查看：2021最后一次更文挑战

【每日一点事】

　　查克拉最早映入眼帘的是在《神雕侠侣》小说里，金轮法王所持的兵器名为查克拉。
image.png

一、前言

　　偶然发现，网上介绍Maven+SpringBoot的项目都有挺多的，偏有些五花八门，现在我就来说上一说。

二、Maven和SpringBoot的介绍与作用

1.Maven是什么？Maven的介绍与作用

　　Maven是一个项目管理工具，对Java项目能够进行构建，同时依赖管理。简单点说，就是你的Java项目缺点啥工具，在pom.xml文件里添加上依赖，Maven去找，找到了并且下载下来（拿过来），然后就能用了。

　　大白话：Maven就是一个工具箱，能够你完善你的小作品、大作品，你需要啥工具，告它一下，呐，你就拿去用吧！

2.SpringBoot是什么？SpringBoot的介绍与作用

　　SpringBoot是Spring超强化版，Spring是一种框架，Java平台上的一种开源应用框架。它可以是你Java项目的小地基，你的小作品的内容介绍目录。

　　大白话：SpringBoot是Spring加强版的框架，又加多了很多工具合成于自身。本来Spring配置是需要加上Tomcat完成Web项目的，但是SpringBoot的话，是已经把Tomcat合并一块。

三、它们两者之间的关系

　　首先，SpringBoot只是一个很好辅助开发的框架，相当于一个很好的工具。因此，我们要先有工具箱啊，没有工具箱哪来的工具呢。

　　话不多说，我们先简单卷起来一下，搞个简单的项目（Maven+SpringBoot）。

四、搞一个简单的Maven + SpringBoot项目

Eclipse版

创建Maven项目

依次点击——》File——》New Maven Project
image.png
Next——》
image.png
填写Group Id、Arifact Id——》Finish
image.png
成功创建Maven项目，查看pom.xml文件
image.png
添加SpringBoot框架

这里我就会很简单、粗暴。

直接在pom文件添加上parent便签和开发web项目需要依赖便签

<parent>标签（project标签下）

1
2
3
4
5
6
7
xml复制代码	<!-- 继承SpringBoot父级项目提供的依赖 -->
	<parent>
		<groupId>org.springframework.boot</groupId>
		<artifactId>spring-boot-starter-parent</artifactId>
		<version>2.2.6.RELEASE</version>
		<relativePath />
	</parent>

<dependency>标签（dependencies标签下）

1
2
3
4
5
xml复制代码<!-- springboot 开发web项目需要的依赖 -->
         <dependency>
			<groupId>org.springframework.boot</groupId>
			<artifactId>spring-boot-starter-web</artifactId>
		</dependency>

完整的pom.xml文件

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
xml复制代码<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
	<modelVersion>4.0.0</modelVersion>

	<groupId>com.nanfangzhe</groupId>
	<artifactId>anpai-demo</artifactId>
	<version>0.0.1-SNAPSHOT</version>
	<packaging>jar</packaging>

	<name>anpai-demo</name>
	<url>http://maven.apache.org</url>

	<properties>
		<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
	</properties>

	<!-- 继承SpringBoot父级项目提供的依赖 -->
	<parent>
		<groupId>org.springframework.boot</groupId>
		<artifactId>spring-boot-starter-parent</artifactId>
		<version>2.2.6.RELEASE</version>
		<relativePath />
	</parent>
	<dependencies>
		<!-- springboot 开发web项目需要的依赖 -->
		<dependency>
			<groupId>org.springframework.boot</groupId>
			<artifactId>spring-boot-starter-web</artifactId>
		</dependency>
		<dependency>
			<groupId>junit</groupId>
			<artifactId>junit</artifactId>
			<version>3.8.1</version>
			<scope>test</scope>
		</dependency>
	</dependencies>
</project>

添加后，可能要等待Maven库更新一会。

完善启动类（App.java的操作）

添加@SpringBootApplication注解

主方法（main方法）中添加SpringApplication.run(App.class, args);
App.java的完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
java复制代码package com.nanfangzhe.anpai_demo;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

/**
 * Hello world!
 *
 */
@SpringBootApplication
public class App {
	public static void main(String[] args) {
		System.out.println("Hello World!");
		SpringApplication.run(App.class, args);
	}
}

成功结果
——》启动项目——》成功展示结果
image.png

文章小尾巴

文章写作、模板、文章小尾巴可参考：《写作“小心思”》

　　感谢你看到最后，最后再说两点~
　　①如果你持有不同的看法，欢迎你在文章下方进行留言、评论。
　　②如果对你有帮助，或者你认可的话，欢迎给个小点赞，支持一下~
　　我是南方者，一个热爱计算机更热爱祖国的南方人。

　　（文章内容仅供学习参考，如有侵权，非常抱歉，请立即联系作者删除。）

本文转载自: 掘金

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

发表于

「这是我参与11月更文挑战的第 19 天，活动详情查看：2021最后一次更文挑战」

刷算法题，从来不是为了记题，而是练习把实际的问题抽象成具体的数据结构或算法模型，然后利用对应的数据结构或算法模型来进行解题。个人觉得，带着这种思维刷题，不仅能解决面试问题，也能更多的学会在日常工作中思考，如何将实际的场景抽象成相应的算法模型，从而提高代码的质量和性能

平衡二叉树

题目来源：LeetCode-110. 平衡二叉树

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1

示例

示例 1

1.png

1
2
csharp复制代码输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2

2.png

1
2
csharp复制代码输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3

1
2
ini复制代码输入：root = []
输出：true

提示：

  • 树中的节点数在范围 [0, 5000] 内
  • 10^4 <= Node.val <= 10^4

解题

解法一：递归：自顶向下的递归

思路

其实这道题的核心就是求二叉树中任意一个结点的高度，只要知道了任意结点的高度，就可以知道这棵二叉树是否平衡

其实常规的思维，最容易想到的思路是，我求出二叉树的最大高度，然后再求出二叉树的最小高度。然后计算他们的差值，跟1进行比较就可以了。其实这样也能实现，只是求最小高度，稍微麻烦点

其实二叉树的题，最长用到递归，而递归在树中的应用往往又比较抽象，但是用递归实现，代码却很简单。刚开始可能很简单的题，都不知道怎么用递归来实现，其实个人感觉这很正常。把LeetCode的前300道算法题里边的二叉树的题都做一遍，看十几分钟没思路就看答案，然后不看答案自己实现一遍。然后做一下总结，慢慢就有感觉了

假设有一个结点p，如果它是空的，高度就是0，如果非空，那它的高度就是左右子树高度的最大值。这应该很容易想到用递归吧，除了规模在边，求解的思路没变，很容易想到用递归。要求当前结点的高度，需要先求左右子树的高度，左右子树的高度求法跟求当前结点的高度思路是一样的。终止条件是左右子树为空了，则高度是0。所以可以写出一个求高度的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
go复制代码func height(root *TreeNode) int {
	if root == nil {
		return 0
	}

	return max(height(root.Left), height(root.Right)) + 1 //每往下遍历一层就+1
}

func max(x, y int) int {
	if x > y {
		return x
	}

	return y
}

剩余部分的实现，就像二叉树的前序遍历，遍历到当前结点，计算左右子树的高度，看左右子树高度差是否大于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
go复制代码//判断平衡二叉树
func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}

	return abs(height(root.Left) - height(root.Right)) <= 1 && isBalanced(root.Left) && isBalanced(root.Right) //先看以当前节点为根节点的树高度差，再分别判断左右子节点为根节点的左右子树的高度差
}

func height(root *TreeNode) int {
	if root == nil {
		return 0
	}

	return max(height(root.Left), height(root.Right)) + 1 //每往下遍历一层就+1
}

func max(x, y int) int {
	if x > y {
		return x
	}

	return y
}

func abs(x int) int {
	if x < 0 {
		return -1 * x
	}

	return x
}

解法二：递归：自底向上的递归

思路

自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，

再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整

数），否则返回 -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
go复制代码func isBalanced2(root *TreeNode) bool {
	return height2(root) >= 0
}

func height2(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftHeight := height(root.Left)
	rightHeight := height(root.Right)
	if leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1 {
		return -1
	}
	return max(leftHeight, rightHeight) + 1
}

func max(x, y int) int {
	if x > y {
		return x
	}

	return y
}

func abs(x int) int {
	if x < 0 {
		return -1 * x
	}

	return x
}

参考

LeetCode官方题解-平衡二叉树

本文转载自: 掘金

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

发表于
### 介绍 Redis 3.0以后，节点之间通过**去中心化的方式**提供了完整的sharding、replication(复制机制仍复用原有机制，只是cluster具备感知主备的能力)、failover解决方案，称为Redis Cluster。即将proxy/sentinel的工作融合到了普通的Redis节点里。 ### 拓扑结构 一个Redis Cluster 由多个Redis节点组构成。**不同节点组服务的数据无交集**（每一个节点组对应数据sharding的一个分片）。节点组内部为主备两类节点，两者数据准实时一致，通过异步化的主备复制机制保证。一个节点组有且仅有一个master节点（读写服务），同时有0到多个slave节点（读服务）。 Redis Cluster通过分片的方式保存键值对，整个数据库被分为**16384个槽（slot）**，数据库中的键都属于这16384个槽中的一个，每个节点可以处理0个或最多16384个槽（**每个节点处理的槽都是不相同的**）。 下面来看下Redis Cluster的节点结构示例图： ![Redis Cluster结构 (1).png](https://gitee.com/songjianzaina/juejin_p10/raw/master/img/7f1a949005a598163f9222fa857e8b2511337a83a8b4c6f73fd4c524cdc35b3d) 该示例图中key-value数据全集被分成了5个slot，只是举例说明，实际Redis Cluster总共有**16384个slot**。A和B节点为master，对外提供读写服务。其中A、A1作为主备关系构成一个节点组，通过主备复制方式同步数据。A1为A的slave，A持有1/2/3三个slot数据，A1作为A的slave也持有这三个节点。同理，B1和B2作为B的slave也构成一个节点组。 通过上面Redis Cluster的节点结构示例图，可以看到两两节点通过Redis Cluster Bus交互，交互信息如下： 1. 数据分片（slot）和节点的对应关系 2. 集群中每个节点可用状态 3. 集群结构（配置）发生变更时，通过一定的协议对配置信息达成一致。数据分片的迁移、主备切换、单点master的发现和其发生主备关系的变更等均会导致集群结构的变化。 4. publish/subscribe功能在cluster版的内部实现所需要交互的信息。 Redis Cluster Bus通过单独的接口连接，bus为节点间内部通信机制，交互的是**字节序列化信息**，和client到redis服务器的字符序列化相比，**交互效率更高**。**客户端可以和集群中任一节点连接**，通过交互流程，逐步获知全集群的**数据分片映射关系**。 ### 配置的一致性 对于一个去中心化的实现，**集群的拓扑结构并不存在在单独的配置节点上**，后者的引入同样会带来新的一致性问题。各个节点怎么就**集群拓扑结构达成一致**，Redis CLuster配置机制是怎么解决的那？Redis Cluster **通过引入两个自增的epoch变量**来使得集群配置在各个节点间达成最终一致。 #### 配置信息数据结构 Redis Cluster中的每一个节点（Node）内部都保存了集群的配置信息，存储在ClusterState中，结构如下图所示： ![Redis Cluster 配置数据结构.png](https://gitee.com/songjianzaina/juejin_p10/raw/master/img/38a7805d67290412e86cbb40976835c91804169a165e6b8d96d5174fb277bd19) 上面各个变量语义如下： * clusterState记录了从集群中某个节点视角的集群配置状态 * currentEpoch表示整个集群中的最大版本号，集群信息每变更一次，版本号都会自增 * nodes是一个列表，包含了本节点所知的集群所有节点信息(clusterNode),其中包含本节点本身 * clusterNode记录了每个节点的信息，比较关键的包括该信息的版本epoch,该版本信息的描述：该节点对应的数据分片（slot）、该节点为master时的slave节点列表、当该节点为slave时对应的master节点。 * 每个节点包含一个全局唯一的NodeId * 当数据分片在节点组之间迁移，Redis Cluster仍保持对外服务，迁移过程中，通过“分片迁移相关状态”的一组变变量来管控迁移过程 * 当集群中某个master宕机，Redis Cluster会自动发现并触发故障转移操作，将宕机master的某个slave升级为新的master（包含一组变量来控制） 可见每个节点都保存着**自己视角的集群结构**，描述数据的**分片方式、节点主备关系**，并通过**epoch作为版本号**实现集群结构信息（配置）的一致性，同时也控制着**数据迁移和故障转移**的过程。 #### 信息交互 去中心架构不存在统一配置中心，节点对集群认知来自节点间信息交互，信息交互通过Redis Cluster Bus（端口独立）完成。交互信息结构如下图所示： ![Redis Cluster 交互信息数据结构.png](https://gitee.com/songjianzaina/juejin_p10/raw/master/img/bee48904419aa8a6302fad6548d8052480cea8da19935c13802794afa528b34e) clusterMsg的**type字段指明了消息的类型**，配置信息的一致性达成主要依靠PING和PONG两种类型的msg。每个节点向其它节点频繁地周期性发送PING消息并接收PONG消息。在**交互信息的Gossip部分**，包含了发送者节点或者接收者节点所知的其它节点信息，接收者根据这些信息更新自己对集群的认识。 对于规模较大的集群，**PING/PONG频繁交互**都带有整个集群结构信息会造成极大网络负担。于是Redis Cluster每次PING/PONG包中，只包含随机选取的部分节点信息，这样短时间几次交互后，集群状态也会很快达成一致。 #### 一致性的达成 当Cluster不发生变化时，各节点通过gossip协议几轮交互之后得知Cluster的结构信息，达到一致状态。对于故障转移、分片迁移等情况会导致cluster结构发生变更，优先得知变更的节点**利用epoch变量将自己最新信息扩散到集群**，达到最终一致。 * clusterNode的epoch属性描述粒度是单个节点（某个节点的数据分片、主备信息版本） * clusterState的currentEpoch属性的粒度是整个集群，用来辅助epoch自增地生成。由于currentEpoch信息也是维护在各个节点，Redis Cluster在结构发生变更时，通过一定时间窗口控制和更新规则，保证每个节点的currentEpoch都是最新的。 更新遵循规则如下： * 当某个节点率先知道信息变更时，这个节点的currentEpoch自增使之成为集群中的最大值，再用自增后的currentEpoch作为新的epoch版本。 * 当某个节点收到比自己更大的currentEpoch，则更新自己的currentEpoch * 当收到的Redis Cluster Bus消息中的某个节点的epoch值大于自身的epoch的时候，则将自身的映射信息更新为消息的内容 * 当收到的Redis Cluster Bus消息中某个节点信息未包含在自身中，则将其加入到自身配置 上述规则保证了**信息的更新始终是单向的**，**朝着epoch值更大的信息收敛**，同时epoch也随着每次配置变更时currentEpoch的自增而单向增加，确保各节点信息更新方向的稳定。 ### sharding **不同节点分组服务于相互无交集的数据子集(分片,sharding)**。因为Redis Cluster不存在单独的proxy和配置服务器，需要将客户端的请求正确的路由到对应的分片。 #### 数据分片 Redis Cluster将所有的数据划分为16384个分片(slot),每个分片负责其中一部分。**每一条数据(key-value)根据key值通过数据分布算法映射到16384个slot中的一个**。数据分布算法如下： slotId = crc16(key)%16384 客户端根据**slotId**决定将请求路由到哪个Redis 节点。**cluster不支持跨节点的单命令**。例如SINTERSTORE，如果涉及的两个key对应的slot分布在不同的node，则操作失败。 通常key具备一定的业务含义，例如： -A商品交易记录的key值:product\_trade\_prod123 -A商品交易明细的key值:product\_detail\_prod123 上面两个key根据数据分布算法计算出的slotId可能分布在不同的slot中，当需要一个命令中操作这两条关联比较强的数据时，则不能以原子方式操作。为了解决这个问题，Redis引入了**HashsTag（可以根据key的某一部分计算）**，使得相关记录放在同一分片。上面举例的key可以改成如下所示： -A商品交易记录的key值:product\_trade\_{prod123} -A商品交易明细的key值:product\_detail\_{prod123} 可以看到Redis会以{}\color{red}{\{\}}{}之间的字符串作为数据分布算法的输入。 #### 客户端的路由 Redis Cluster的客户端相比单机的Redis具备**路由语义的识别能力**和**路由缓存能力**。 当client访问的key不在对应节点(例如A)，则会收到一个**moved命令**，告知其正确的路由信息(假设是B)。如下图所示： ![未命名文件 (28).png](https://gitee.com/songjianzaina/juejin_p10/raw/master/img/5c8370a2f5c65464bb86f6c0b726e7ba680a36c5b808b9cd40e23924e95aac19) 从client接收到moved命令后，再次向moved响应中指向的B节点发送期间，如果发生了**分片迁移**，使B节点也不是正确的节点，此时client会再次收到B响应的moved。client会根据moved响应更新内部路由缓存信息，以便下次能够直接路由到正确节点，降低交互次数。 当cluster在slot迁移过程中时，可通过ask命令控制客户端路由，如下图所示： ![Redis Cluster分片迁移的客户端路由.png](https://gitee.com/songjianzaina/juejin_p10/raw/master/img/18de6ec015f36e6ccf776692cc61238c510f5a761089e3d3802881d7065f7cf4) 上图可见，客户端请求节点A的key存储在slot2上，请求A节点时，slot2已不在节点A（slot2已迁移到B节点），则节点给client一个**ask转向命令**（例如ASK 2 127.0.0.1:7003）,告诉client可以尝试到ask命令返回中的节点请求尝试。然后客户端首先会**向B节点发送asking命令**(打开发送该命令的客户端的REDIS\_ASKING标识)，之后再重新发送需要执行的命令到B节点，B节点会执行如下图所示的执行过程： ![Redis节点判断是否执行客户端命令的过程.png](https://gitee.com/songjianzaina/juejin_p10/raw/master/img/24685bfe4d2f470e5ef01211acdce8961dcc2414a53d200c18c29fd83d7406ff) 从上面流程图可以看出ASKING标识的作用，当判断节点正在导入slot2并且客户端带有ASKING标识，则会执行命令，否则会返回moved命令。另外需要注意的是客户端的REDIS\_ASKING标识是一个一次性标识(执行一次后客户端的REDIS\_ASKING标识就会被移除)。 ask命令和moved命令的区别： * 返回的场景不一样。client访问的key不在节点slots中，返回moved命令；如果正在迁移中返回ask命令。 * moved命令会**更新client数据路由缓存**(后续相同操作会直接定位到目标节点)。ask命令**只是重定向到新节点**。(不会更新客户端路由缓存，后续相同slot操作仍路由到旧节点) 迁移过程可能持续一段时间，这段时间某个slot数据可能分布在新旧两个节点各分布一部分，由于moved操作会使客户端路由缓存变更，如果新旧节点对迁移中的slot所有的key都回应moved，client的路由缓存可能会频繁变动。因此引入ask类型消息，**将重定向和路由缓存更新分离**。 #### 分片迁移 稳定Redis Cluster下每一个slot对应的节点是确定的。但在一些情况下，节点和分片的对应关系需要发生变更： * 新的节点作为master加入 * 某个节点分组需要下线 * 负载不均需要调整slot分布 此时的话需要分片的迁移。迁移的触发和过程控制由外部系统完成，Redis Cluster只提供迁移过程需要的原语。原语主要包含两种： * **节点迁移状态设置，迁移前标记源/目标节点** * **key迁移的原子化命令：迁移的具体步骤** 下面我们来举个例子，slot1从节点A迁移至节点B的迁移流程。 ![Redis Cluster 数据分片迁移.png](https://gitee.com/songjianzaina/juejin_p10/raw/master/img/0b9ab95a6d2156438bfd75a22a03c8d5dcdee034c6c4aed2425a6b19bf5383df) 1.向节点B发送状态变更命令，将B的对应的slot状态置为importing 2.向节点A发送状态变更命令，将A对应slot状态置为migrating 3.针对A上的slot的所有key，发别向A发送migrate命令，告知A将对应key迁移到B 当节点A的状态置为MIGRATING后，表示对应的slot正在从A迁出，为保证**该slot数据数据的一致性**，A此时对slot提供读写服务的行为和通常状态有所区别，对于某个迁出的slot： * **若client访问的key未迁移出，正常处理该key** * **若key已经迁移出或者不存在该key，则回复客户端ASK信息让其跳转到B执行** 当节点B的状态设置为IMPORTING后，表示对应的slot正在向B迁入。即使B仍能对外提供该slot的读写服务，但也有所区别： * 当client请求不是从ASK跳转过来，client还不知道迁移在进行，很可能操作了一个尚未迁移完成正处在A上的key，此时key在A上被修改了，则B和A的修改值将来会发生冲突。**所以对于该slot上的非ASK跳转而来的操作，B不会进行处理，而是通过MOVED命令让client跳转至A执行**。 这样状态控制保证同一个key在迁移前总是在源节点执行，迁移后总是在目标节点执行，杜绝了两边同时写导致值冲突的问题。并且迁移过程中新增的key总是在目标节点执行(原节点不会再新增key)，使迁移过程时间有界，可以确定在某个时刻结束。 单个key的迁移过程通过原子化的MIGRATE命令(完成数据传输到B、等待B接收完成、在A上删除该key的动作)。A和B各自slave通过主备复制同步master的的增删数据。 当所有key迁移完成，client**通过CLUSTER SETSLOT命令设置B的分片信息，让其包含迁移的slot**。设置过程**自增epoch**(当前集群最大epoch)，然后利用epoch变量将自身信息扩散到整个集群(上面所述的一致性达成)。 ### failover 和sentinel一样，Redis Cluster也有一套完整节点故障发现、故障状态一致性保证、主备切换机制，我们下面来看下。 #### failover的状态变迁 1.**故障发现**：当某个master宕机时，如何被集群其它节点感知 2.**故障确认**：多个节点就某个master是否宕机如何达成一致 3.**slave选举**：集群确认某个master宕机后，如何将它的slave升级为新的master；多个slave，如何选择升级 4.**集群结构变更**：成功选举的slave升级为master后，如何让全集群知道以更新集群结构信息 #### 故障发现 Redis Cluster节点间通过Redis Cluster Bus**两两周期性地PING/PONG交互**，当某个节点宕机，其它发向它的PING消息将无法及时响应，**当PONG响应超过一定时间（NODE\_TIMEOUT）未收到，则认为该节点故障**，将其置为**PFAIL**（**POSSIBLE FAIL**）状态。后续通过Gossip发出的PING/PONG消息中，这个节点的PFAIL状态会传播到集群其它节点。 Redis Cluster节点间两两通过TCP保持Redis Cluster Bus连接，当PING无PONG回复，可能是**节点故障**，也可能是**TCP连接断开**。如果是TCP连接断开导致的响应超时将会产生误报，虽然误报消息同样会因为其它节点连接正常被忽略，但这种误报是可以通过一定方式尽可能避免的。Redis Cluster通过**预重试机制**排除此类误报,当NODE\_TIMEOUT/2时间内未收到回应，则重新连接重发PING消息，如果在短时间内就有响应，则说明对端正常。 #### 故障确认 在网络分隔的情况下,某节点并没有故障，但是和A无法连接，但是和C、D等其它节点可以正常连接，此时只会有A将B标记为**PFAIL状态**,其它节点认为B正常。此时A和C/D等其它节点信息不一致，Redis Cluster通过故障确认协议达成一致。 集群中的每个节点都是Gossip的接收者，A也会接收其它节点的Gossip消息，被告知B是否处于FFAIL状态。当A接收到其它master节点对于B的PFAIL达到一定数量以后，会将B的PFAIL状态升级为**FAIL状态**。表示B已经确认为故障状态，后面会发起slave选举流程。 A节点内部的集群信息中B的状态由PFAIl转为FAIl的的变迁流程图如下所示: ![Redis Cluster 故障确认流程(PFAIL到FAIl的变迁) (1).png](https://gitee.com/songjianzaina/juejin_p10/raw/master/img/8a1fcdde3198fc67ccd88d7837f1ad97e74cc30623aff17e62f9ba8d03e31296) #### slave选举 上图中B是A的master,并且B已经被集群公认为FAIL状态了，那么A发起竞选期望成为新的master。 如果B有多个slave(A/E/F)都认知到B处于FAIL状态，A/E/F可能会同时发起竞选。当B的**slave个数大于等于3**的时候，很有可能发起多轮竞选失败。**为了减少冲突，优先级最高（数据越新，也就是数据最完整的优先级最高）的slave更有可能发起竞选，从而提升成功的可能性**。 slave发送FAILOVER\_AUTH\_REQUEST消息竞选之前会将currentEpoch自增并将最新的Epoch带入到FAILOVER\_AUTH\_REQUEST消息中。slave通过向其它master发送**FAILOVER\_AUTH\_REQUEST**消息发起竞选，master收到后回复**FAILOVER\_AUTH\_ACK**消息告知是否同意，如果未投过票则回复同意，否则回复拒绝。 #### 结构变更通知 当slave收到超过半数master同意回复，则替代B成为新的master，此时它会以最新的epoch通过PONG消息广播自己成为master的信息，让集群其它节点尽快更新拓扑结构。 B恢复可用后，刚开始仍然认为自己是master，但逐渐通过Gossip协议得知A替代了自己之后降级为A的slave。 ### 可用性和性能 Redis Cluster还提供了一些手段提升性能和可用性。 #### Redis Cluster的读写分离 对于有读写分离需求的场景，应用对于某些读的请求允许舍弃一定的数据一致性来换取更高的吞吐量。此时希望将读的请求交由slave处理以分担master的压力。 数据分片映射关系中，**slot对应的节点一定是一个master**，客户端通过moved消息将请求路由到各个master。即便客户端将请求直接发送到slave，slave也会回复moved到master的响应。 为此，Redis Cluster引入了READONLY命令。客户端向slave发送该命令后，slave对于读操作不再moved到master而是直接处理，称为**slave的READONLY模式**。通过**READWRITE命令**可将slave的readonly模式重置。 #### master单点保护 对于master的单点保护我们来举个例子，假设集群初始结构如下图所示： ![未命名文件 (32).png](https://gitee.com/songjianzaina/juejin_p10/raw/master/img/4e03d119a6e6dda32c2397bd986f8ba8526b18d5183155bc61dccd8b8d2b16f1) A、B两个master分别有1个和2个自己的slave。假设A1发生宕机，集群结构会变成如下所示： ![未命名文件 (31).png](https://gitee.com/songjianzaina/juejin_p10/raw/master/img/0ae2a0d684dbceed6973a17db7210dcb037349f108b7ec8cf8eece36ce7f2c99) 此时A成为了单点，一旦A发生宕机，将会造成不可用。此时Redis Cluster会将B的某一个slave（假设是B1）进行副本迁移，让B1变成A的slave，副本迁移后的结构如下图所示： ![未命名文件 (33).png](https://gitee.com/songjianzaina/juejin_p10/raw/master/img/ade85f4af0d3a4d3007a47e1e3faa10ca4359392e722e385143922f0b7507d9f) 这使集群中的每个master至少有一个slave，那么集群只需要保持**2\*master+1**个节点就可以在任一节点宕机后仍能通过迁移**自动维持高可用**。

参考书籍：《深入分布式缓存》《Redis设计与实现》

本文转载自: 掘金

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

发表于

「这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战」

简介

java中和hash相关并且常用的有两个类hashTable和hashMap,两个类的底层存储都是数组，这个数组不是普通的数组，而是被称为散列表的东西。

散列表是一种将键映射到值的数据结构。它用哈希函数来将键映射到小范围的指数（一般为[0..哈希表大小-1]）。同时需要提供冲突和对冲突的解决方案。

今天我们来学习一下散列表的特性和作用。

文末有代码地址，欢迎下载。

散列表的关键概念

散列表中比较关键的三个概念就是散列表，hash函数，和冲突解决。

散列是一种算法（通过散列函数），将大型可变长度数据集映射为固定长度的较小整数数据集。

散列表是一种数据结构，它使用哈希函数有效地将键映射到值，以便进行高效的搜索/检索，插入和/或删除。

散列表广泛应用于多种计算机软件中，特别是关联数组，数据库索引，缓存和集合。

散列表必须至少支持以下三种操作，并且尽可能高效：

搜索（v） - 确定v是否存在于散列表中，
插入（v） - 将v插入散列表，
删除（v） - 从散列表中删除v。

因为使用了散列算法，将长数据集映射成了短数据集，所以在插入的时候就可能产生冲突，根据冲突的解决办法的不同又可以分为线性探测，二次探测，双倍散列和分离链接等冲突解决方法。

数组和散列表

考虑这样一个问题：找到给定的字符串中第一次重复出现的的字符。

怎么解决这个问题呢？最简单的办法就是进行n次遍历，第一次遍历找出字符串中是否有和第一个字符相等的字符，第二次遍历找出字符串中是否有和第二个字符相等的字符，以此类推。

因为进行了n*n的遍历，所以时间复杂度是O(n²)。

有没有简单点的办法呢？

考虑一下字符串中的字符集合其实是有限的，假如都是使用的ASCII字符，那么我们可以构建一个256长度的数组一次遍历即可。

具体的做法就是遍历一个字符就将相对于的数组中的相应index中的值+1，当我们发现某个index的值已经是1的时候，就知道这个字符重复了。

数组的问题

那么数组的实现有什么问题呢？

数组的问题所在：

键的范围必须很小。 如果我们有（非常）大范围的话，内存使用量会（非常的）很大。
键必须密集，即键值中没有太多空白。 否则数组中将包含太多的空单元。

我们可以使用散列函数来解决这个问题。

通过使用散列函数，我们可以：

将一些非整数键映射成整数键，
将大整数映射成较小的整数。

通过使用散列函数，我们可以有效的减少存储数组的大小。

hash的问题

有利就有弊，虽然使用散列函数可以将大数据集映射成为小数据集，但是散列函数可能且很可能将不同的键映射到同一个整数槽中，即多对一映射而不是一对一映射。

尤其是在散列表的密度非常高的情况下，这种冲突会经常发生。

这里介绍一个概念：影响哈希表的密度或负载因子α= N / M，其中N是键的数量，M是哈希表的大小。

其实这个冲突的概率要比我们想象的更大，举一个生日悖论的问题：

一个班级里面有多少个学生会使至少有两人生日相同的概率大于 50%？

我们来计算一下上面的问题。

假设Q（n）是班级中n个人生日不同的概率。

Q（n）= 365/365×364/365×363/365×…×（365-n + 1）/ 365，即第一人的生日可以是365天中的任何一天，第二人的生日可以是除第一人的生日之外的任何365天，等等。

设P（n）为班级中 n 个人的相同生日的概率，则P（n）= 1-Q（n）。

计算可得，当n=23的时候P(23) = 0.507> 0.5（50％）。

也就是说当班级拥有23个人的时候，班级至少有两个人的生日相同的概率已经超过了50%。 这个悖论告诉我们：个人觉得罕见的事情在集体中却是常见的。

好了，回到我们的hash冲突，我们需要构建一个好的hash函数来尽量减少数据的冲突。

什么是一个好的散列函数呢？

能够快速计算，即其时间复杂度是O（1）。
尽可能使用最小容量的散列表，
尽可能均匀地将键分散到不同的基地址∈[0..M-1]，
尽可能减少碰撞。

在讨论散列函数的实现之前，让我们讨论理想的情况：完美的散列函数。

完美的散列函数是键和散列值之间的一对一映射，即根本不存在冲突。 当然这种情况是非常少见的，如果我们事先知道了散列函数中要存储的key，还是可以办到的。

好了，接下来我们讨论一下hash中解决冲突的几种常见的方法。

线性探测

先给出线性探测的公式：i描述为i =（base + step * 1）％M，其中base是键v的散列值，即h（v），step是从1开始的线性探测步骤。

线性探测的探测序列可以正式描述如下：

h（v）//基地址
（h（v）+ 1 * 1）％M //第一个探测步骤，如果发生碰撞
（h（v）+ 2 * 1）％M //第二次探测步骤，如果仍有碰撞
（h（v）+ 3 * 1）％M //第三次探测步骤，如果仍有冲突
…
（h（v）+ k * 1）％M //第k个探测步骤等…

先看个例子，上面的数组中，我们的基数是9，数组中已经有1，3，5这三个元素。

现在我们需要插入10和12，根据计算10和12的hash值是1和3，但是1和3现在已经有数据了，那么需要线性向前探测一位，最终插入在1和3的后面。

上面是删除10的例子，同样的先计算10的hash值=1，然后判断1的位置元素是不是10，不是10的话，向前线性探测。

看下线性探测的关键代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
java复制代码    //插入节点
    void insertNode(int key, int value)
    {
        HashNode temp = new HashNode(key, value);

        //获取key的hashcode
        int hashIndex = hashCode(key);

        //find next free space
        while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
            && hashNodes[hashIndex].key != -1)
        {
            hashIndex++;
            hashIndex %= capacity;
        }
        //插入新节点，size+1
        if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {
            size++;
        }
        //将新节点插入数组
        hashNodes[hashIndex] = temp;
    }

如果我们把具有相同h(v)地址的连续存储空间叫做clusters的话，线性探测有很大的可能会创建大型主clusters，这会增加搜索（v）/插入（v）/删除（v）操作的运行时间。

为了解决这个问题，我们引入了二次探测。

二次探测

先给出二次探测的公式：i描述为i =（base + step * step）％M，其中base是键v的散列值，即h（v），step是从1开始的线性探测步骤。

h（v）//基地址
（h（v）+ 1 * 1）％M //第一个探测步骤，如果发生碰撞
（h（v）+ 2 * 2）％M //第2次探测步骤，如果仍有冲突
（h（v）+ 3 * 3）％M //第三次探测步骤，如果仍有冲突
…
（h（v）+ k * k）％M //第k个探测步骤等…

就是这样，探针按照二次方跳转，根据需要环绕哈希表。

看一个二次探测的例子，上面的例子中我们已经有38，3和18这三个元素了。现在要向里面插入10和12。大家可以自行研究下探测的路径。

再看一个二次探索删除节点的例子。

看下二次探测的关键代码：

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
java复制代码    //插入节点
    void insertNode(int key, int value)
    {
        HashNode temp = new HashNode(key, value);

        //获取key的hashcode
        int hashIndex = hashCode(key);

        //find next free space
        int i=1;
        while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
            && hashNodes[hashIndex].key != -1)
        {
            hashIndex=hashIndex+i*i;
            hashIndex %= capacity;
            i++;
        }

        //插入新节点，size+1
        if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {
            size++;
        }
        //将新节点插入数组
        hashNodes[hashIndex] = temp;
    }

在二次探测中，群集（clusters）沿着探测路径形成，而不是像线性探测那样围绕基地址形成。 这些群集称为次级群集（Secondary Clusters）。
由于在所有密钥的探测中使用相同的模式，所以形成次级群集。

二次探测中的次级群集不如线性探测中的主群集那样糟糕，因为理论上散列函数理论上应该首先将键分散到不同的基地址∈[0..M-1]中。

为了减少主要和次要clusters，我们引入了双倍散列。

双倍散列

先给出双倍散列的公式：i描述为i =（base + step * h2(v)）％M，其中base是键v的散列值，即h（v），step是从1开始的线性探测步骤。

h（v）//基地址
（h（v）+ 1 * h2（v））％M //第一个探测步骤，如果有碰撞
（h（v）+ 2 * h2（v））％M //第2次探测步骤，如果仍有冲突
（h（v）+ 3 * h2（v））％M //第三次探测步骤，如果仍有冲突
…
（h（v）+ k * h2（v））％M //第k个探测步骤等…

就是这样，探测器根据第二个散列函数h2（v）的值跳转，根据需要环绕散列表。

看下双倍散列的关键代码：

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
java复制代码    //插入节点
    void insertNode(int key, int value)
    {
        HashNode temp = new HashNode(key, value);

        //获取key的hashcode
        int hashIndex = hash1(key);

        //find next free space
        int i=1;
        while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
            && hashNodes[hashIndex].key != -1)
        {
            hashIndex=hashIndex+i*hash2(key);
            hashIndex %= capacity;
            i++;
        }

        //插入新节点，size+1
        if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {
            size++;
        }
        //将新节点插入数组
        hashNodes[hashIndex] = temp;
    }

如果h2（v）= 1，则双散列（Double Hashing）的工作方式与线性探测（Linear Probing）完全相同。 所以我们通常希望h2（v）> 1来避免主聚类。

如果h2（v）= 0，那么Double Hashing将会不起作用。

通常对于整数键，h2（v）= M’ - v％M’其中M’是一个小于M的质数。这使得h2（v）∈[1..M’]。

二次散列函数的使用使得理论上难以产生主要或次要群集问题。

分离链接

分离链接法（SC）冲突解决技术很简单。如果两个键 a 和 b 都具有相同的散列值 i，那么这两个键会以链表的形式附加在要插入的位置。

因为键（keys）将被插入的地方完全依赖于散列函数本身，因此我们也称分离链接法为封闭寻址冲突解决技术。

上面是分离链接插入的例子，向现有的hashMap中插入12和3这两个元素。

上面是分离链接删除的例子，从链接中删除10这个元素。

看下分离链接的关键代码：

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
java复制代码 //添加元素
    public void add(int key,int value)
    {

        int index=hashCode(key);
        HashNode head=hashNodes[index];
        HashNode toAdd=new HashNode(key,value);
        if(head==null)
        {
            hashNodes[index]= toAdd;
            size++;
        }
        else
        {
            while(head!=null)
            {
                if(head.key == key )
                {
                    head.value=value;
                    size++;
                    break;
                }
                head=head.next;
            }
            if(head==null)
            {
                head=hashNodes[index];
                toAdd.next=head;
                hashNodes[index]= toAdd;
                size++;
            }
        }
        //动态扩容
        if((1.0*size)/capacity>0.7)
        {
            HashNode[] tmp=hashNodes;
            hashNodes=new HashNode[capacity*2];
            capacity=2*capacity;
            for(HashNode headNode:tmp)
            {
                while(headNode!=null)
                {
                    add(headNode.key, headNode.value);
                    headNode=headNode.next;
                }
            }
        }

rehash

当负载因子α变高时，哈希表的性能会降低。 对于（标准）二次探测冲突解决方法，当哈希表的α> 0.5时，插入可能失败。
如果发生这种情况，我们可以重新散列（rehash）。 我们用一个新的散列函数构建另一个大约两倍的散列表。 我们遍历原始哈希表中的所有键，重新计算新的哈希值，然后将键值重新插入新的更大的哈希表中，最后删除较早的较小哈希表。

本文的代码地址：

learn-algorithm

本文已收录于 www.flydean.com/14-algorith…

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！

欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！

本文转载自: 掘金

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

发表于

「这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战」

前言

在了解了爬虫各种基础知识之后，我们有时需要快速搭建一个个爬虫的程序。有没有这么一个方便的工具或框架能让我们快速搭建起一个个爬虫程序呢？Scrapy呼之欲出。

一、什么是Scrapy

纯Python实现的一个为了爬取网站数据，提取结构性数据而编写的应用框架。框架本身把一些重复性的工作给你做好了；你就可以轻轻松松的按照其框架本身写几个简单的模块或者简单的扩展一些模块就可以你个性化的功能；当然带来的问题是首先你要学习了解框架，还有，想突破框架本身的限制，比较困难；

Scrapy是基于Twisted(竞争对手Tornado)异步网络框架，Scrapy的组件及架构图如下：

)​

Scrapy Engine(引擎): 负责Spider、ItemPipeline、Downloader、Scheduler中间的通讯，信号、数据传递等。

Scheduler(调度器): 它负责接受引擎发送过来Request请求，并按照一定的方式进行整理排列，入队，当引擎需要时，交还给引擎。

Downloader（下载器）：负责下载Scrapy Engine(引擎)发送的所有Requests请求，并将其获取到的Responses交还给Scrapy Engine(引擎)，由引擎交给Spider来处理。

Spider（爬虫）：它负责处理所有Responses,从中分析提取数据，获取Item字段需要的数据，并将需要跟进的URL提交给引擎，再次进入Scheduler(调度器)。

Item Pipeline(管道)：它负责处理Spider中获取到的Item，并进行进行后期处理（详细分析、过滤、存储等）的地方。

Downloader Middlewares（下载中间件）：可以当作是一个可以自定义扩展下载功能的组件。

Spider Middlewares（Spider中间件）：可以理解为是一个可以自定扩展和操作引擎和Spider中间通信的功能组件（比如进入Spider的Responses; 和从Spider出去的Requests）

二、怎么安装使用Scrapy

下面运行的环境是Ubuntu 17.04

1、 安装

安装Scrapy in Ubuntu：

sudo apt-get install python-dev python-pip libxml2-dev libxslt1-dev

sudo pip install scrapy

2、 制作一个Scrapy爬虫需要的四个步骤

1)新建项目 (scrapy startproject spiderName)新建一个新的爬虫项目，一个项目可能包含很多个爬虫;

scrapy startproject tencentSpider

查看项目结构：

tarena@tedu:~/Spider/tencentSpider$ tree.：

├── scrapy.cfg

└── tencentSpider

├── **init**.py


├── items.py


├── middlewares.py


├── pipelines.py


├── settings.py


└── spiders


    └── **init**.py

2 directories, 7 files

2)明确目标：明确你想要抓取的目标，生产一个具体的爬虫

scrapy genspider tencent

cd tencentSpider

scrapy genspider tencent hr.tencent.com

tarena@tedu:~/Spider/tencentSpider$ tree

├── scrapy.cfg

├── tecentLog.txt

└── tencentSpider

├── **init**.py


├── **init**.pyc


├── items.py


├── middlewares.py


├── pipelines.py


├── settings.py


├── settings.pyc


└── spiders


    ├── **init**.py


    ├── **init**.pyc


    └── tecent.py

2 directories, 12 files

下面需要具体取修改代码逻辑，按照我们的需求去实现自己的爬虫逻辑：

修改setttings.py 设置

                        pipelines.py 保存的逻辑


                        tecent.py,   抓取页面信息和继续跳转的逻辑


                        items.py     保存item的映射


3)制作爬虫 (spiders/spiderName.py)：制作爬虫开始爬取网页;


4)存储内容 (pipelines.py)：设计管道存储爬取内容;

5)在Scrapy下启动爬虫：

scrapy crawl tencent

​

本文转载自: 掘金

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

0%