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

今日题目1

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

思路

这道题相对比较简单，链表相关的操作一般首先考虑递归

1. 首先对l1和l2进行判空，否则直接返回非空的list
2. 然后循环遍历两个链表，对于两个链表中较小的节点，加到新链表去，同时该链表后移一位
3. 当有一条链表遍历结束后，若另一条链表还有剩余，将其加入新链表
4. 最后比较两个链表的表头大小，返回小的那个表头指针

代码实现

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

java复制代码public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }

        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38 MB, 在所有 Java 提交中击败了8.37%的用户

其他解法

能用递归解决的问题肯定能用迭代的方式解决，递归方式占用空间比较大，代码结构清晰

迭代则相反，结构稍显复杂

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

java复制代码public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null){
        return l2;
    }
    if (l2 == null){
        return l1;
    }
    ListNode head = new ListNode();
    ListNode cuur = head;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            cuur.next = l1;
            l1 = l1.next;
        } else {
            cuur.next = l2;
            l2 = l2.next;
        }
        cuur = cuur.next;
    }
    if (l1 == null) {
        cuur.next = l2;
    }
    if (l2 == null) {
        cuur.next = l1;
    }
    return head.next;
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：37.6 MB, 在所有 Java 提交中击败了85.34%的用户

今日题目2

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”
输出：true

示例 2：

输入：s = “()[]{}”
输出：true

示例 3：

输入：s = “(]”
输出：false

示例 4：

输入：s = “([)]”
输出：false

示例 5：

输入：s = “{[]}”
输出：true

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

思路

这道题会使用计算机常用的一种数据结构： 栈

利用栈的压栈、出栈操作，来实现括号的配对

1. 首选判断字符长度必须为偶数，奇数肯定不能配对的
2. 从左向右依次遍历字符串的每一个字符
3. 如果字符是左括号，则存入栈中，等待配对的右括号；
4. 如果是右括号，先判断此时栈是否为空。如果是空的，则右括号无法消除，返回false；如果栈不是空的，再将此字符于栈顶元素进行比较，判断是否符合条件。
5. 当遍历完所有字符元素，判断栈是否为空。如果是空，说明所有括号配对成功，反之不成功

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

java复制代码public boolean isValid(String s) {
    int n = s.length();
    if (n % 2 != 0) {
        return false;
    }
    Stack<Character> stack = new Stack<>();
    char[] c = s.toCharArray();
    for (int i=0;i<n;i++) {
        if (c[i] == '(') {
            stack.push(')');
        } else if (c[i] == '[') {
            stack.push(']');
        } else if (c[i] == '{'){
            stack.push('}');
        } else if (stack.isEmpty() || c[i] != stack.pop()) {
            return false;
        }
    }
    return stack.isEmpty();
}

执行用时：1 ms, 在所有 Java 提交中击败了98.88%的用户

内存消耗：36.7 MB, 在所有 Java 提交中击败了18.45%的用户

小结

这两道题都相对比较简单，只要合理的利用数据结构的特点，花点时间做出来还是不难的。

本文转载自: 掘金

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

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

正式的Python专栏第40篇，同学站住，别错过这个从0开始的文章！

前篇学委展示分享了类的继承和重写，面向对象还有一些概念，继续跟上吧，这次总结一下！

类和对象再次认识回顾

类和对象，类就像是3D建模里面的模型数据，对象跟用这个3D模型使用3D打印出来的具体模型。

类没有生命周期，因为你的代码写好了类，它就存在，并不因为被不被加载而存在！

但是我们没有加载类到PYTHONPATH中，它不被找到！但是不代表它不存在！

对象呢？仅存在于Python程序运行过程中，中间程序关闭了，对象就消失了。

对象有生命周期

对象被创建，被惦记着（使用），被销毁了。(Python有对应的函数）

类和对象之间的数据共享

这就跟一家人住在一个房子里面一样，整个房子的设施是共享的，这样子类比。

先补充一个知识点：@staticmethod

这是python内置的一个函数修饰符，用来装饰函数的，也就是在函数的上方。

比如下面的代码：

1
2
3
4
5
6
7

python复制代码class LeiXueWeiDemo():
    @staticmethod
    def call_without_object_creation():
        print("Run....")
        
#调用代码：
LeiXueWeiDemo.call_without_object_creation()

看看下面的程序：

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

python复制代码#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2021/11/15 11:58 下午
# @Author : LeiXueWei
# @CSDN/Juejin/Wechat: 雷学委
# @XueWeiTag: CodingDemo
# @File : __init__.py.py
# @Project : hello

class Value(object):
    pass

"""
下面是一个程序员类定义
"""


class PythonProgrammer(object):
    class_value = Value()

    def __init__(self, name):
        self.name = name

    def code(self):
        print(f"{self.name}: life is too short, why not python?")

    @staticmethod
    def learn(self):
        print(f"{self.name}: learn python")

    def __str__(self):
        return f"PythonProgrammer(name:{self.name})"

    def __eq__(self, other):
        if isinstance(other, self.__class__):
            return self.name == other.name
        return False


p1 = PythonProgrammer("学委粉丝2号")
# p.code() #TypeError: code() missing 1 required positional argument: 'lang'
p1.code()
print("pi id：", id(p1))
print("PythonProgrammer id：", id(PythonProgrammer))
print("p1：", p1.name)
print("class_value id：", id(p1.class_value))
print("PythonProgrammer.class_value id：", id(PythonProgrammer.class_value))
print("p1.__dict__:", p1.__dict__)
print("p1.code:", p1.code)
print("PythonProgrammer.code:", PythonProgrammer.code)
print("p1.learn:", p1.learn)
print("PythonProgrammer.learn:", PythonProgrammer.learn)
print("p1的类型:", p1.__class__)
print("PythonProgrammer命名空间:", PythonProgrammer.__dict__)
print("PythonProgrammer类:", PythonProgrammer.__class__)

下面的运行结果务必看懂理解：

这里学委想表达的是，共享变量/函数，在内存中地址一样。

其他函数和变量，类被加载过之后，函数被加载，函数引用地址跟创建的对象的地址不一样！

同时类的数据属性，没有任何地址引用（因为类是没有数据属性赋值的），仅仅实例化为对象，我们才能通过对象来修改属性，对象是有状态的！

就像下面的图一样，当然内存地址只是虚构，未必连续！

总结

类和对象，一个就像是3D建模里面的模型数据，跟3D打印出来的模型。

但是3D打印没存在共享变量/共享函数，因为模型数据文件，跟打印出来的实物没有任何物质关联！

喜欢Python的朋友，请关注学委的 Python基础专栏 or Python入门到精通大专栏

持续学习持续开发，我是雷学委！

编程很有趣，关键是把技术搞透彻讲明白。

欢迎关注微信，点赞支持收藏!

本文转载自: 掘金

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

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

哈希冲突的解决办法：

1. 开放地址法
2. 拉链法（链地址法）
3. 再哈希法

一、开放地址法

原理是当发生hash冲突时，会以当前地址为基准，然后根据寻址方法（探查寻址），去寻找下一次地址。若依旧发生冲突，则继续寻址，直到找到一个空的位置为止。
通用的散列函数形式为：

Hi=（H（key）+di）% m （i=1，2，…，n）

其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。

寻址方法

1. 线性探查

顺序查找表的下一个单元，直到找到一个空单元或查遍全表。

即当hash值为3冲突时(假设此时hash表长度为11)，利用线性探查的过程为：

H1 = (3+1)%11 = 4，此时若4依旧冲突，则再hash，即

H2 = (3+2)%11 = 5 …. 通过这种线性增长增量系列，直到找到空的位置为止。

2. 二次探查

这种方法的特点是，当哈希冲突时，在表的左右进行跳跃探测，比较灵活。

此时di = 1^2, -1^2, 2^2, -2^2 ….

假设当hash值为3冲突时(假设此时hash表长度为11)，利用二次探查的过程为：

H1 = (3+1^2)%11 = 4,此时若4依旧冲突，则再hash,即

H2 = (3+(-1)^2)%11 = 2 …

通过该方法直到找到空位置为止。

3. 伪随机探测

这种方法即是产生一些随机系列值，并给定随机数作为起点。

假设当hash值为3冲突时(假设此时hash表长度为11)，利用伪随机探测的过程为：

假设产生的随机系列为2，5，9 ….，则

H1 = (3+2)%11 = 5

H2 = (3+5)%11 = 8

通过该方法直到找到空位置为止。

二、拉链法

拉链法应用于hashMap和hashSet中，当产生hash冲突时，则会以该hash冲突的位置构建一个单链表（即将所有哈希地址为i的元素构成一个称为同义词链的单链表），并将单链表的头指针存储在哈希表的第i个位置中。

链地址法适用于经常进行插入和删除的情况。

三、再哈希法

指使用哈希函数计算散列位置时，当不同散列出现同一位置时就再次使用哈希，直到不冲突。

本文转载自: 掘金

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

前言

今天下英雄，惟使君与操耳。–曹操《三国演义》

对于在 IT 圈摸爬滚打多年的程序员来说，如果要问国内最主流的后端编程语言，我相信大部分会说 Java。这并不意外，因为 Java 存在了 30 多年，有着庞大的用户规模和生态体系，在软件工程领域似乎有着绝对霸主地位。但是，古人云：“得民心者得天下。” 用户最多的编程语言不一定是最受开发者们喜欢的。根据 StackOverflow 2021 年在 82,914 名开发者中做的关于编程语言满意度调查，喜欢 Java 的占比只有 47%，已经排到 20 名开外了，仅高于 PHP、C、COBOL。另一方面，我们从调查结果可以看到，有着 “山寨版 Java” 之称的 C#，反而在开发者心目中满意度达到了 62%，比 Java 高 15%。虽然 C# 的满意度跟 Rust、TypeScript 差距还比较大，但可以看出 C# 作为 Java 的替代编程语言，在开发效率、部署便捷性、文档完善度等方面已经逐渐占据优势。笔者因为工作的原因，在平时开发中使用 C# 和 Java 开发了不少项目，因此对它们之间的相同点、不同点以及优势、劣势有一定了解。笔者认为，C# 相对于 Java 来说更受开发者欢迎是有一定道理的，因为它的开发体验很好。

限于篇幅原因，整个 C# 的原理及实战介绍（即为何推荐用 C# 构建大型后端应用），将被拆分为一系列文章，该系列将从语法特性、开发模式、生态体系、部署构建等维度深度分析 C# 这门 “年轻” 的编程语言，并以跨平台框架 .NET Core 为例介绍如何用 C# 构建大型后端应用。

本篇文章是 C# 系列文章的第一篇，主要在语法特性方面介绍 C# 的一些现代语法特性，以及它们是如何提高开发效率的。

C# 简介

C# 是 2000 年由微软发布的新型编程语言。它在诞生之初就因为与 Java 极高的相似度而被贴上 “山寨 Java” 的标签。C# 跟 Java 类似，是面向对象编程（OOP）编程语言，包含类、方法、接口、单一继承等 OOP 元素，而且是 Windows .NET 网络框架的基础语言。C# 语言的发布与 SUN 公司对微软的一个诉讼有关，是为了取代造成纠纷的 Java 变种语言 Visual J++。

从发布 1.0 版本到现在，C# 大大小小经历了多次迭代，至今随 .NET 5 一起发布了 C# 9.0 版本。从最早的面向对象支持，到后来更为丰富的功能，例如异步编程、跨平台支持等。C# 在变得越来越强大的同时，也遵循着 “简单、现代、通用” 的设计标准，在如今越来越复杂的后端开发以及架构要求中显得如鱼得水，既可以开发 Windows 桌面端应用，还可以用于更加具有扩展需求的分布式系统和微服务架构等。

C# 语法特性

可能很多 C# 的特性都类似于 Java，例如类型系统、面向对象编程、依赖注入、异常处理等。这一小节将介绍更多跟 Java 不一样的特性，而这些特性很大程度上提升了 C# 的开发体验，让开发者更加青睐于 C#。

空值操作

在使用 C# 开发项目的过程中，我发现 C# 中对空值的判断和操作非常简单，不会像 Java 中这么繁琐。下面会举几个例子来说明 C# 的语法优越性。

例子 1

如果要从 JSON 对象中获取较深层的元素，一般来说需要做空值判断，这样不可避免的会导致很多诸如 if (value == null) { ... } 这样的判断语句，显得异常啰嗦。而在 C# 中，这个空值判断被简化为了一个问号 ?。例如，你可以这么来写获取深层 JSON 元素的代码。

1
2

css复制代码// access index C in member B of A
A?.B?[C];

用这样的方式，你避免了大量的 if 语句，如果其中一个成员不存在，将自动将整个获取值的表达式返回为 null，这大大简化了空值带来的冗余代码。

例子 2

不少时候，你可能会希望给一个表达式设置默认值，如果该表达式为空值 null，就返回该默认值。例如下面这个例子。

1
2

vbnet复制代码// set default value of text if input is null
var text = input ?? '-';

用两个问号的操作符 ??，你将可以在 C# 轻松的设置默认值。否则，例子 1 一样，你可能将不得不加入不必要的 if (value == null) 的判断语句。?? 这样的操作符也是 C# 中节省代码的方式。

C# 还有不少其他空值操作的语法，例如 null 包容运算符、可空类型，但是上面举的两个例子是 C# 中利用空值操作符的最常见例子，对平时的 C# 项目开发来说非常有用。

如果你对本技术博客另一篇介绍 TypeScript 的技术文章 《为什么说 TypeScript 是开发大型前端项目的必备语言》 有印象的话，你应该会记得 TypeScript 也有这样的空值操作语法。是的，TS 是借鉴 C# 过来的，因为 TypeScript 的创建者正是 C# 之父 Anders Hejlsberg！

隐式类型本地变量

为什么很多 Java 开发者会抱怨说写 Java 就像在写又臭又长的八股文，就是因为在 Java 中每声明一个新变量你都不得不去思考它的类型，从而需要花大量的脑容量来推演和记忆临时变量的类型。这对于开发效率来说真的不是好事情。

而 C# 借鉴了其他非强制要求变量类型声明的编程语言，集成了隐式类型本地变量（Implicitly typed local variables）语法。笔者认为隐式类型本地变量是 C# 中非常酷的特性，它让开发者不用强迫自己记住需要引用或需要声明的变量类型，从而将注意力聚焦在代码逻辑上。

C# 用 JavaScript 中的 var 关键字来声明隐式类型本地变量，它能够让该变量通过隐式的类型推断来 “自动” 声明该变量类型。下面附上 C# 文档的官方例子来说明如何使用隐式类型本地变量。

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

csharp复制代码// i is compiled as an int
var i = 5;
​
// s is compiled as a string
var s = "Hello";
​
// a is compiled as int[]
var a = new[] { 0, 1, 2 };
​
// expr is compiled as IEnumerable<Customer>
// or perhaps IQueryable<Customer>
var expr =
    from c in customers
    where c.City == "London"
    select c;
​
// anon is compiled as an anonymous type
var anon = new { Name = "Terry", Age = 34 };
​
// list is compiled as List<int>
var list = new List<int>();

当然，大量的使用 var 也可能会造成一些问题。例如，包含大量包含隐式类型本地变量的代码会让不熟悉的该代码的 C# 开发者花不少时间来琢磨该变量的实际类型，从而影响代码的可读性。不过，常用的 C# IDE 例如 Visual Studio 或 JetBrains Rider 都可以自动帮你显示该隐式类型本地变量的实际类型。正是借助这些强大的 IDE，笔者才放心推荐使用 C# 的 var 语法来声明变量。

语言集成查询 (LINQ)

除了上述两个提高开发效率的语法外，C# 还有一个非常新颖的语法特性：语言集成查询，简称为 LINQ。LINQ 的出现让数据源操作的表达式变得足够简单。笔者有理由相信 C# 的创造者一定是参考了 SQL 这样的查询语言来设计 LINQ 语法的。下面是一个使用 LINQ 的例子。

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

csharp复制代码class LINQQueryExpressions
{
    static void Main()
    {
​
        // Specify the data source.
        int[] scores = new int[] { 97, 92, 81, 60 };
​
        // Define the query expression.
        IEnumerable<int> scoreQuery =
            from score in scores
            where score > 80
            select score;
​
        // Execute the query.
        foreach (int i in scoreQuery)
        {
            Console.Write(i + " ");
        }
    }
}
// Output: 97 92 81

我们着重看 scoreQuery 这个变量的表达式，其中的 from ... in ... where ... select ... 语法就是用了 LINQ。其表达的意思是遍历 scores 这个数组，只选取 score 大于 80 的元素，最后返回 score 行程新的迭代器 scoreQuery。这跟 SQL 的 SELECT ... FROM 语法非常相似。LINQ 对于 C# 来说只是一个表达式，目的是为了将常规的数据特别是数组操作，变得跟写 SQL 一样简单。如果不用 LINQ，你可能会需要用 foreach 遍历数组并做 if 判断，然后加入更多操作来实现跟上述 LINQ 语句相同的逻辑。

在后面介绍 Entity Framework 数据库操作框架的部分，我们还会继续介绍 C# 中的数据操作。

属性语法

C# 定义模型的方式相对于 Java 要简单很多，同时还支持更高级的特性，例如 get 或 => 定义的计算属性。

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

csharp复制代码public class Person
{
  // private properties
  private int _gender;
  private int _age;
  
  // Auto-implemented property
  public string Name { get; set; }
  
  // Expression body definition
  public string Gender => _gender == 1 ? "Male" : "Female";
  
  // Property with backing fields
  public string Age
  {
    get
    {
      return $"{_age} years old";
    }
  }
}

在上面的例子中，我们看到有多种定义属性的方式。Name 是自动实现的属性，只需要带上 get 和 set 表示是可读写的属性；Gender 是用 => 表示简化的 get 访问器，用于较为简单的计算属性；Age 包含 get 访问器，用于较为复杂的计算属性。

可以看到，C# 的属性语法同时包含了简单和复杂的使用场景，因此更能够提高开发效率。

总结

本篇文章主要从语法特性的角度介绍了 C# 独有而方便的特性。特别是相对于传统的后端编程语言 Java，C# 具有很多让人喜爱的语法，例如空值操作、隐式类型推断、LINQ 等。虽然 Java 在新的版本中加入了部分类似语法试图提高开发效率，然而如今市面上的 Java 产品大多还是用经典的 Java 8 版本，因此没有这些功能。而 C# 背靠微软开发维护，有合理的 Roadmap 开发规划，文档也较为齐全，因此对于很多后端开发者是非常友好的。C# 目前开发方向贯彻了它 “简单、现代、通用” 的设计标准，综合来看很适合做中大型项目。不过，目前国内因为历史原因还暂时是 Java 占据主要市场，而新兴的 Go 也占据了分布式应用领域的份额（参考本博客之前文章 《大红大紫的 Golang 真的是后端开发中的万能药吗？》），所以 C# 在推广方面可能还需要假以时日。不过，酒香不怕巷子深。包括笔者在内的越来越多开发者已经意识到 C# 是一门非常优秀的后端编程语言，如果条件允许，可以将其应用在实战项目中。之后的系列文章将更进一步分析 C# 的生态，特别是 .NET Core、Entity Framework 等主流框架。

本文转载自: 掘金

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

二叉查找树(BST)

二叉查找树（Binary Search Tree），也称二叉搜索树、有序二叉树（ordered binary tree），排序二叉树（orted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点

二叉查找树在极端的情况下会退化成现线性的结构，降低查找效率

树的深度直接决定了最坏条件下的查找次数，也就是决定了查找的效率，因此降低树的深度很重要，所以引出了AVL树和红黑树

优点：有序
缺点：极端条件下会退化成链表，降低查找效率

平衡二叉树(AVL Tree)

AVL 树是一种平衡二叉树，得名于其发明者的名字（ Adelson-Velskii 以及 Landis）,平衡二叉树全称平衡二叉搜索树，也叫AVL树。是一种自平衡的树。

平衡二叉树也是一种特殊的二叉查找树，满足二叉查找树的特性

AVL树也规定了左结点小于根节点，右结点大于根节点。并且还规定了左子树和右子树的高度差不得超过1。这样保证了它不会成为线性的链表。
AVL树的查找稳定，查找、插入、删除的时间复杂度都为O（logN）
但是由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。

AVL树每一个节点只能存放一个元素，并且每个节点只有两个子节点。当进行查找时，就需要多次磁盘IO，（数据是存放在磁盘中的，每次查询是将磁盘中的一页数据加入内存，树的每一层节点存放在一页中，不同层数据存放在不同页。）这样如果需要多层查询就需要多次磁盘IO。为了解决AVL树的这个问题，就出现了B树。

优点：有序，解决了BST会退化成线性结构的问题
缺点：进行插入和删除结点操作的时候，需要对结点进行频繁的旋转

红黑树（R-B Tree）

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树示意图如下：

红黑树在查找方面和AVL树操作几乎相同。但是在插入和删除操作上，AVL树每次插入删除会进行大量的平衡度计算，红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，结合变色，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。

相比于BST，因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的，这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。

红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，在插入和删除中AVL树所做的后期维护操作肯定会比红黑树要耗时好多，但是他们的查找效率都是O(logN)，所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的。

红黑树广泛用于TreeMap、TreeSet，以及jdk1.8后的HashMap。

以上三种树都是基于二叉树

二叉树每一个节点只能存放一个元素，并且每个节点只有两个子节点。当进行查找时，就需要多次磁盘IO
在实际应用中，数据是存放在磁盘中的，每次查询是将磁盘中的一页数据加入内存，树的每一层节点存放在一页中，不同层数据存放在不同页。
这样如果需要多层查询就需要多次磁盘IO。为了解决这个问题，就出现了B树

B树（B-tree）

不叫B减树哦，别叫错了，B树不是二叉树，B树每一层存放了更多的节点，由AVL树的“瘦高”变成了“矮胖”。
B树属于多叉树又名平衡多路查找树（查找路径不只两个）
B树的阶数指的就是
该树每个节点最多有 m个子树，m为该树的阶数，

一个m阶的B树规定了：

1. 根结点至少有两个子女。
2. 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m，即k介于 m/2和m之间。
3. 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。
4. 所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

特点：

B树也是一种自平衡的树，在进行插入和删除操作时也需要对结点进行旋转等操作。
但是与AVL树和红黑树相比每个节点包含的关键字增多了，从而减小了树的深度，可以相对减少磁盘IO的次数。
特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度，因此B树被广泛用于文件系统及数据库中

弊端：
B树的查找不稳定，最好的情况就是在根节点查到了，最坏的情况就是在叶子结点查到。
B树在遍历方面比较麻烦，由于需要进行中序遍历，所以也会进行一定数量的磁盘IO。

除非完全重建数据库，否则无法改变键值的最大长度。这使得许多数据库系统将人名截断到70字符之内。

为了解决这些问题，出现了B+树。

应用场景：

• Windows：HPFS 文件系统
• Mac：HFS，HFS+ 文件系统
• Linux：ResiserFS，XFS，Ext3FS，JFS 文件系统
• MongoDB

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B+树

一个m阶的B+树具有如下几个特征：

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树的优点：

1. B+树的层级更少：非叶子结点中存放的元素不存放数据，所以每一层可以容纳更多元素，比B-树更加“矮胖”，也就是磁盘中的每一页可以存放更多元素。这样在查找时，磁盘IO的次数也会减少
2. B+树查询速度更稳定：每次查找都必须匹配到叶子节点，因此每一次查找都是稳定的。B-树由于中间节点也携带数据，因此只需要匹配到要查找的元素即可，最好的情况是在根节点就结束查找，最坏的情况是在叶子节点结束查找，查找性能不稳定
3. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在范围查询数据时候更方便，数据紧密性很高，缓存的命中率也会比B-树高。
4. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描
   【参考】
   知乎小灰

本文转载自: 掘金

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

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

对于web服务端应用开发来说，日志非常重要。它可以监控应用的运行状态，还可以用来进行问题排查。

如何打好日志需要关注的点非常多。

日志路径

日志可以放到项目文件夹下面，或者放到统一的日志文件夹。但是在多台机器的情况下，可以查找日志信息就不太方便。这时候可以考虑将日志打到统一的日志服务中，这样便于统一管理。

日志分类

需要根据不同的场景，对日志进行分类，这样可以根据不同的需求查看不同的日志。比如，可以分为业务相关日志、框架内核插件日志、错误日志等等，当然可以根据实际情况进行进一步的细分，初步的分类通常可以借助框架来实现。

如何打印日志

需要在一些关键节点打印日志，打印的日志内容需要带上相关且必要的信息。

需要注意的是对于错误日志，一定要构建Error类型，因为只有Error类型才会带上堆栈信息，能帮助定位问题。

日志切割

日志文件很多，为了方便查看，需要对日志文件进行恰当的管理。其中比较关键的就是日志切割，即日志按照什么维度进行切分管理。常见的有按文件大小进行切割、按时间进行切割等等，需要按照自己的需求进行选择。

性能

通常我们默认web服务是高频访问，不能每次产生一条日志都写入到磁盘中，或者通过网络请求发送到日志服务中，这样会产生大量io操作，影响性能。可以采用一些提高性能的策略，如将日志写入缓存然后每隔一段时间集中存储。

接入统一日志服务

下面以阿里云的日志服务为例说一下如何接入统一的日志服务。

1. 开通服务，通常为防止欠费停机最好申请下免停服务
2. 创建日志存储仓库logstore
3. 进行客户端配置，客户端接入日志sdk，通过sdk提供的api进行日志的生产及查看等
4. 如果有长时间保存日志的需求，还需要进行日志的投递等

接入统一的日志服务，也需要注意上面提到的日志分类问题，只有对日志进行合理的分类。

日志监控报警

日志里面有很多信息需要我们重点关注，这时候就需要引入跟日志系统打通的告警机制，通过设置合理告警规则，当日志出发告警规则，能第一时间采取措施，将损失降到最低。

本文转载自: 掘金

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

什么是位运算?

程序中的所有数值在计算机中都是以二进制的形式存储的，位运算就是对这些二进制形式存储的数据进行一元和二元操作，通俗点说就是对我们存储的数值的二进制进行操作。
没有了转换这一步而是直接对二进制进行操作，理论上位运算比加减运算略快，比乘除法要快很多，但是在现在 java程序架构 上位运算和加减法效率相同，比乘除法要快，当然如果是进行大量的计算使用位运算能有效的提升性能

JAVA中有哪些位运算符？

主要有以下几种位运算：&、|、^、~、>>、<<、>>>

像 &、| 虽然作为逻辑运算符使用在数值上时也可以做为位运算使用

位运算符的使用

&

当两个对应数的位数同为1时，结果为1，否则为0

简单点讲就是把十进制的数值转换成二进制，然后对应位数进行对比如果同为1那么最后的数字为1，否则该位数就位0
举例

1
2
3
4
5
6
7

js复制代码	十进制
	5 & 7
	二进制
	101 & 111
	结果：
	十进制：5
	二进制：101

过程：运算的时候二进制对应位数进行比对 101 和 111，两个数值对比只有中间位数没有同时为1，那么最后的运算结果就为 101。

扩展：判断数值的奇偶性，数值 & 1，由于1的二进制是001，那么不管数值是多少只会对比最后一位数是否为1，如果同为1则证明该数值为奇数，如果结果为0则证明该数为偶数。

|

和 & 运算刚好相反当两个对应数的位数值同为0时，结果为0，否则为1

简单点讲就是把十进制的数值转换成二进制，然后对应位数进行对比如果同为0那么最后的数字为0，否则该位数就位1
举例

1
2
3
4
5
6
7

js复制代码	十进制
	4 | 8
	二进制
	0100 & 1000
	结果：
	十进制：12
	二进制：1100

过程：运算的时候二进制对应位数进行比对 0100 和 1000，两个数值对比只有前面两位没有同时为0 则前面两位为1后两位为0，转为十进制为12

扩展：把数值转换为最接近的的奇数等于当前数为偶数时 +1，用法就是 数值 | 1

^

对应位数相同则为 0 ，不同则为 1

简单点讲就是把十进制的数值转换成二进制，对应位数进行比较如果相同则对应位数结果为0，否则为1
举例

1
2
3
4
5
6
7

js复制代码	十进制
	5 | 8
	二进制
	0101 & 1000
	结果：
	十进制：13
	二进制：1101

过程：运算的时候二进制对应位数进行比对 0101 和 1000，两个数值对比如果对应位数相同结果为0，否则为1，只有第二位相同其它不同所以输出结果为 1101

扩展：可以作为简单加密方式，比如我现在银行的支付密码为123456，然后把我开户年月作为密匙202111，123456 ^ 202111 = 194367，然后把194367进行持久化，最后得到支付密码的时候只需要反向再计算一次

~

这个会让二进制数值进行反运算，比如会 0变为1，1变为0

举例

1

js复制代码	二进制：101 就会变成 11111…..1010

过程：虽然二进制101前面没有值，但是对于二进制前面的值都是为0，所以进行反运算之后就会用1填满

<<

左位移运算，向左边进行位运算

简单点讲就是把十进制的数值转换成二进制，然后最高位向左移动，或者理解为2乘以数值次数
举例

1
2
3
4
5
6
7

js复制代码	十进制
	10<<2
	二进制
	1010 << 2
	结果：
	十进制：40
	二进制：101000

过程：十的二级制为1010 将该值往左边移动两位并补齐0最终值为101000，可以理解为1022。

–

右位移运算，向右边进行位运算，如果最后一位为1也会舍去

简单点讲就是把十进制的数值转换成二进制，然后从最高位开始向右移动，或者理解为2除以数值次数并向下取整，如 5 / 2 等于 2.5但是向下取整最后的结果会舍掉 0.5 所以结果为2
举例

1
2
3
4
5
6
7

js复制代码	十进制
	5>>1
	二进制
	101 >> 1
	结果：
	十进制：2
	二进制：10

过程：5转换为二进制为 101，然后向右边移动一位数最后的1会被舍去掉结果则为10

小结

在java中不止前面这几种位运算还有java特有的 >>> 不带符号的位运算,带符号的位运算 符 >> 总是自动的用它之前的最高位数值内容去补它的最高位这样就保留了之前值的符号，而不带符号的 >>> 不会在最高位保留之前的值而是在高位补0
不止有不带符号的 >>> 运算，还有 >>>=。

本文转载自: 掘金

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

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

• 一级缓存指的就是sqlsession，在sqlsession中有一个数据区域，是map结构，这个区域就是一级缓存区域。

+ 一级缓存中的key是由sql语句、条件、statement等信息组成一个唯一值。
+ 一级缓存中的value，就是查询出的结果对象。

• 二级缓存指的就是同一个namespace下的mapper

+ 二级缓存中，也有一个map结构。具体的结构和一级缓存是一样的，key和value的结构都相同。
+ 但是生命周期比一级缓存的生命周期要长。

一级缓存是默认使用的。
二级缓存需要手动开启。

一级缓存 (sqlsession缓存)

第一次查询会去缓存中去查，如果查不到，就查DB然后加入缓存。但是要是有增删改操作并且提交了，就会清空一级缓存。

一级缓存里面是一个hashmap：localCache 这个Map，key为 将Statement Id + Offset + Limmit + Sql + Params 等5个元素组合成一个CacheKey对象，并重写了他们的equals方法，通过这个对象作为缓存map的key。

【一级缓存有两个级别：SESSION 和 STATEMENT 默认是session的就是针对当前会话的。两个会话的缓存互不影响】

配置： <setting name="localCacheScope" value="SESSION"/>

存在问题

• 脏读多个sqlsession的缓存数据不一致。

二级缓存(mapper缓存)

每一个mapper的缓存区域。同样增删改会去清空缓存。二级缓存开启后，同一个namespace下的所有操作语句，都影响着同一个Cache，被多个sqlsession共享。

当开启缓存后，数据的查询执行的流程就是 二级缓存 -> 一级缓存 -> 数据库。先去二级缓存里面查，然后没有才去一级缓存。

配置

• 在mapper文件中配置<cached/>就是开启二级缓存。
• <setting name="cacheEnabled" value="true"/>

存在问题

当sql语句是多表查询的时候，我改了另外一个namespce的表内容，那个namespce的表就无法感知了。那个namespace就是脏数据。

总结

mybatis的缓存机制最好全关了不要使用。

• Mybatis本身是一个持久层框架，它不是专门的缓存框架，所以它对缓存的实现不够好，不能支持分布式。
• 我们缓存可以再外面做，比如Ehcache是一个分布式的缓存框架。需要这个ehcache包，实现分布式缓存。其实我们可以在我们的代码层面来实现缓存。想实现自己的缓存只要实现Cache接口即可，然后配置mapper中的cache使用自己写的类。

本文转载自: 掘金

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

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

写在前面

今天我们来聊聊如何解决跨域，聊解决跨域之前，首先应该知道什么是跨域。

什么是跨域

通俗讲，你浏览器中输入的域名请求的资源当中，其中又有不同的域名去请求其他资源去了，这种存在不同域名请求的 称之为跨域。

比如我们前端工程师在浏览器输入localhost进入前端工程开始调整逻辑，但是接口地址调用的是后端的api工程，会出现跨域。

比如我们常用nginx解决跨域（今天我们主要学习SpringBoot解决跨域）

nginx在本地启动，比如拦截80端口，给个拦截，然后转发到真实的api接口服务

1
2
3
4
5
6
7
8
9
10

java复制代码server {
        listen       80;
        server_name  ;

        #定义拦截api
        location /api {
            proxy_pass http://www.web.server/web-api/;
            index  index.html index.htm index.jsp;
        }
    }

比如我们要访问www.web.server/web-api 这个线上服务，那浏览器直接输入localhost/api 即可。

好的 稍带提下nginx 后面我们进入正题，SpringBoot解决跨域的几种姿势

实现 WebMvcConfigurer

这种比较经典，用的可能比较多

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

java复制代码@Configuration
public class CorsConfig implements WebMvcConfigurer {

    @Override
    public void addCorsMappings(CorsRegistry registry) {
        //所有请求都放过
        registry.addMapping("/**")
                //默认同域
                .allowedOrigins("*")
                //所有请求放过
                .allowedMethods("GET", "HEAD", "POST", "PUT", "DELETE", "OPTIONS")
                .allowCredentials(true)
                .maxAge(3600)
                .allowedHeaders("*");
    }
}

重新注入 CorsFilter

这种也相对比较常见

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

java复制代码/**
 * 解决跨域
 */
@Configuration
public class CorsFilterConfig {


    /**
     * 开启跨域访问拦截器
     *
     * @date 2021/4/29 9:50
     */
    @Bean
    public CorsFilter corsFilter() {
        //创建CorsConfiguration对象后添加配置
        CorsConfiguration corsConfiguration = new CorsConfiguration();
        //设置放行哪些原始域
        corsConfiguration.addAllowedOrigin("*");
        //放行哪些原始请求头部信息
        corsConfiguration.addAllowedHeader("*");
        //放行哪些请求方式
        corsConfiguration.addAllowedMethod("*");

        UrlBasedCorsConfigurationSource source = new UrlBasedCorsConfigurationSource();
        //2. 添加映射路径
        source.registerCorsConfiguration("/**", corsConfiguration);
        return new CorsFilter(source);
    }
}

创建一个 filter 解决跨域

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

java复制代码@Slf4j
@Component
@WebFilter(urlPatterns = { "/*" }, filterName = "headerFilter")
public class HeaderFilter implements Filter {
    @Override
    public void doFilter(ServletRequest request, ServletResponse resp, FilterChain chain) throws IOException, ServletException {
        HttpServletResponse response = (HttpServletResponse) resp;
        //解决跨域访问报错
        response.setHeader("Access-Control-Allow-Origin", "*");
        response.setHeader("Access-Control-Allow-Methods", "POST, PUT, GET, OPTIONS, DELETE");
        //设置过期时间
        response.setHeader("Access-Control-Max-Age", "3600");
        response.setHeader("Access-Control-Allow-Headers", "Origin, X-Requested-With, Content-Type, Accept, client_id, uuid, Authorization");
        // 支持HTTP 1.1.
        response.setHeader("Cache-Control", "no-cache, no-store, must-revalidate");
        // 支持HTTP 1.0. response.setHeader("Expires", "0");
        response.setHeader("Pragma", "no-cache");
        // 编码
        response.setCharacterEncoding("UTF-8");
        chain.doFilter(request, resp);
    }

    @Override
    public void init(FilterConfig filterConfig) {
        log.info("跨域过滤器启动");
    }

    @Override
    public void destroy() {
        log.info("跨域过滤器销毁");
    }
}

好了。今天关于后端如何解决跨域的就讲到这里 也欢迎大家在下方评论其他方案

总结

我们开头所讲的都是一些关于比如前端如何解决跨域。下面我简单总结几点 前端如何解决跨域，大家下面可以了解下

• 1、 通过jsonp跨域
• 2、 document.domain + iframe跨域
• 3、 location.hash + iframe
• 4、 window.name + iframe跨域
• 5、 postMessage跨域
• 6、 跨域资源共享（CORS）
• 7、 nginx代理跨域
• 8、 nodejs中间件代理跨域
• 9、 WebSocket协议跨域

这里就不一一展开赘述了，后面有时间再展开讨论

OK。我们下期再见，加油！

弦外之音

感谢你的阅读，如果你感觉学到了东西，您可以点赞，关注。也欢迎有问题我们下面评论交流

加油！ 我们下期再见！

给大家分享几个我前面写的几篇骚操作

copy对象，这个操作有点骚！

干货！SpringBoot利用监听事件，实现异步操作

本文转载自: 掘金

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

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

写在前面

最近在使用IDEA来开发一个新的项目，因为规范的问题，有些点就总是忘记，比如实体类实现了序列化接口后，需要生成一个UID。

再比如经常忘记写一些关键的注解，有些规范不能很好的执行。

今天就在此记录一下，同时希望可以帮助到大家。

实现了序列化接口后，提示生成随机UID

比如以下代码中：

1
2
3

java复制代码public class Test implements Serializable {

}

IDEA中的截图如下图：

有的时候就很容易忘记，所以在网上找到一种解决办法，那就是配置上提示，

通过操作File-Setting-搜索Serializable，到达如下界面：

勾选中以上的框框，我们就能看到下图的效果了。

类名标黄，非常难看，只能去点一下，就可以提示你生成UID了。

规范性问题的提示

关于规范性的问题，其实现在团队中一般都是用阿里巴巴的那套Java规范，可能不是完全遵守，但是大概没什么出入，最后也是找了个插件来解决这个问题。

有这么一款插件，可以自行扫描类中的编码是否符合阿里巴巴编码规约，那就是Alibaba Java Coding Guidelines。

进入到Plugins页面下，可以自行搜索安装即可。

有了这款插件，很多注释，不规范的类使用就会帮你提示出来了，免去很多不规范代码的出现。

总结

IDEA是一个很好的工具，其中也有着丰富的插件，很多功能，需要大家自行去发现，如果大家在开发过程中遇到工具类问题，那么就去搜一下，没准就有非常的好替代品。

本文转载自: 掘金

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