编程范式

Programming paradigm(编程范式) 是指某种编程语言典型的编程风格或编程方式。 编程范式是编程语言的一种分类方式，它并不针对某种编程语言。就编程语言而言，一种编程语言也可以适用多种编程范式。

常见的编程范型有：函数式编程、指令式编程、过程式编程、面向对象编程等等。

指令式编程

指令式编程、命令式编程（英语：Imperative programming）；是一种描述电脑所需作出的行为的编程典范。几乎所有电脑的硬件都是指令式工作；几乎所有电脑的硬件都是能执行机器代码，而机器代码是使用指令式的风格来写的。较高端的指令式编程语言使用变量和更复杂的语句，但仍依从相同的典范。菜谱和行动清单，虽非计算机程序，但与指令式编程有相似的风格：每步都是指令。因为指令式编程的基础观念，不但概念上比较熟悉，而且较容易具体表现于硬件，所以大部分的编程语言都是指令式的。

原理和基础

很多指令式编程语言（比如Fortran、BASIC和C）是汇编语言的抽象化。

大部分的高级语言都支持四种基本的语句：

1. 运算语句一般来说都表现了在存储器内的资料进行运算的行为，然后将结果存入存储器中以便日后使用。高端指令式编程语言更能处理复杂的表达式，可能会产生四则运算和函数计算的结合。
2. 循环语句容许一些语句反复执行数次。循环可依据一个默认的数目来决定执行这些语句的次数；或反复执行它们，直至某些条件改变。
3. 条件分支语句容许仅当某些条件成立时才执行某个区块。否则，这个区块中的语句会略去，然后按区块后的语句继续执行。
4. 无条件分支语句容许执行顺序转移到程序的其他部分之中。包括跳跃（在很多语言中称为Goto）、副程序和Procedure等。

循环、条件分支和无条件分支都是控制流程。

一些语言，如：Fortran, Java, C, C++

声明式编程

声明式编程（英语：Declarative programming）或译为声明式编程，是对与命令式编程不同的编程范型的一种合称。它们建造计算机程序的结构和元素，表达计算的逻辑而不用描述它的控制流程。开发人员更关心的答案。它声明那种我们想要的结果,编程语言只关注如何产生

区别

• 命令式编程：命令“机器”如何去做事情(how)，这样不管你想要的是什么(what)，它都会按照你的命令实现。
• 声明式编程：告诉“机器”你想要的是什么(what)，让机器想出如何去做(how)。

现在下面这样的表达式

1

(1+2) * 8 / 4

命令式

1
2
3

int a = 1 + 2;
int b = a * 8;
int c = b / 4;

声明式

1

divide(multiply(add(1, 2), 3), 4)

过程式编程

过程式程序设计（英语：Procedural programming），又称过程化编程，一种编程典范，派生自指令式编程，有时会被视为是同义语。主要要采取过程调用或函数调用的方式来进行流程控制。流程则由包涵一系列运算步骤的过程（Procedures），例程（routines），子程序（subroutines）, 方法（methods），或函数（functions）来控制。在程序执行的任何一个时间点，都可以调用某个特定的程序。任何一个特定的程序，也能被任意一个程序或是它自己本身调用。

过程化语言适合解决线性的算法问题，强调“自上而下”、“精益求精”的设计方式。

最初的主要过程式编程语言出现在大约1957年至1964年，包括Fortran、ALGOL、COBOL、PL/I和BASIC，后来的Pascal和C发表于大约1970年至1972年。

面向对象编程

面向对象程序设计（英语：Object-oriented programming，缩写：OOP）是种具有对象概念的编程典范，同时也是一种程序开发的抽象方针。它可能包含数据、特性、代码与方法。对象则指的是类（class）的实例。它将对象作为程序的基本单元，将程序和数据封装其中，以提高软件的重用性、灵活性和扩展性，对象里的程序可以访问及经常修改对象相关连的数据。在面向对象程序编程里，计算机程序会被设计成彼此相关的对象。

重要的面向对象编程语言包含Common Lisp、Python、C++、Objective-C、Smalltalk、Delphi、Java、Swift、C#、Perl、Ruby、JavaScript 与 PHP等。

并行编程模式

在计算机科学中，并行编程模型（Parallel programming model）是并行计算机架构的抽象化，通过它可方便的表达算法和它们在程序中的合成。判别编程模型的价值可以通过它的通用性：在各种不同架构上能表达多大范围的不同问题，和它的性能：编译的程序在执行时有多高的效率[1]。并行编程模型的实现形式可以是从“顺序编程”语言中调用的函数库，作为现存语言的扩展，或作为全新的语言。

围绕特定编程模型的共识是很重要的，这可导致建造不同的并行计算机来支持这个模型，从而促进软件的可移植性。在这个意义上，编程模型被称为在硬件和软件之间的桥接[2]。

关键：

• 任务分解，识别出多个能够并发执行的任务
• 数据分解，识别出从属于每个任务的局部数据
• 分组任务和排序分组的方式满足时间约束
• 任务之间的依赖分析

关键：

• 任务并行，重点要解决任务之间的依赖性，解决顺序依赖约束和共享数据依赖约束，可以通过消除依赖、分离依赖等方式解决；通过轮询、工作窃取法等方式来实现调度

关键：

• SPMD（单程序多数据）。在SPMD程序中，所有UE（执行单元）并行执行同一个程序（单程序），但每个UE都拥有自己的私有数据集（多数据）
• 主从模式。主进程为从进程建立一个工作池和一个任务包。所有从进程并发执行，每个从进程迭代的从任务包中移除一个任务并处理它，指导所有任务都处理完毕或到达某些终止条件为止
• 循环并行。该模式解决计算密集型循环为主导串行程序转成并行程序时出现的问题
• 派生聚合模式Fork/Join 模式。一个主UE里面Fork出多个子的UE，这些子UE并行完成任务的一部分，等待这一步的全部子UE完成了这些任务之后，进行聚合操作。
• 共享数据。解决多个UE共享数据时常见问题，并讨论正确性和性能。共享内存是在进程间传递数据的高效方式。在共享内存模型中，并行进程共享它们可以异步读与写的全局地址空间。异步并发访问可能导致竞争条件，和用来避免它们的机制如：锁、信号量和监视器。常规的多核处理器直接支持共享内存
• 分布式数组模式。一维或多维数组，被划分为多个子数组，并在进程或线程间进行分配

关键：

• UE管理。线程/进程的创建和销毁
• 同步。内存同步和围栅、栏栅、互斥
• 通信。消息传递、集合通信

逻辑编程

逻辑编程是种编程典范，它设定答案须符合的规则来解决问题，而非设定步骤来解决问题，过程是事实+规则=结果。

事实

实际上，每个逻辑程序都需要使用事实才能实现给定的目标。事实基本上是关于程序和数据的真实陈述。例如，新德里是印度的首都。

规则

实际上，规则是允许我们对问题域做出结论的约束。规则基本上写成逻辑条款来表达各种事实。例如，如果我们正在构建任何游戏，那么必须定义所有规则。

规则对于解决逻辑编程中的任何问题非常重要。规则基本上是逻辑结论，可以表达事实。以下是规则的语法

1

A∶− B1,B2,...,Bn.

这里，A是头部，B1，B2，… Bn是身体。

例如 − ancestor(X,Y) :- father(X,Y).

ancestor(X,Z) :- father(X,Y), ancestor(Y,Z).

这可以理解为，对于每个X和Y，如果X是Y的父亲而Y是Z的祖先，则X是Z的祖先。对于每个X和Y，X是Z的祖先，如果X是Y和Y的父亲是Z的祖先。

python-kanren

数据驱动编程

在计算机编程中，数据驱动编程，是一种编程范式，在其中程序语句描述要匹配的数据，和对它需要做的处理，程序本身不定义选取数据的一序列文件操作步骤[1]。数据驱动语言的标准例子是文本处理语言sed和AWK[1]，在其中数据是输入流中的一序列的行，因而它们也叫面向行的语言，而模式匹配主要通过正则表达式或行号来完成。

在数据驱动的编程中,由数据本身驱动程序的逻辑。在游戏编程中,通常是数据驱动的编程方式使用某种形式的脚本语言。游戏的行为由变化的数据文件决定,而不做任何重新编译。

无数据驱动的时候

1
2
3
4
5
6
7
8
9

data_lloyd = {'name': 'Lloyd', 'lives': 'Alcoy }
data_jason = {'name': 'Jason', 'lives': 'London' }
go = function(x) 
    if x.name == 'Lloyd' 
    then 
        print("Alcoy, Spain") 
    else 
        print("London, UK") 
end

数据驱动

1
2
3
4
5

data_lloyd = {'name': 'Lloyd', 'lives': function(){ print("Alcoy, Spain") }
data_jason = {'name': 'Jason', 'lives': function(){ print("London, UK") }
go = function(x)
    x.lives()
end

demo：

我们将使用一个简单的门。当玩家进入一个触发器区域,门打开时,当玩家离开引发地区,门关闭:

如果我们让触发器区域覆盖整个门,然后门更多的是一种视觉细节,像一个星际旅行输送机的门:

我们可以创建一个触发门对象有两个部分:一个触发器区域(即不是画在屏幕上),和一个物理的门,这是绘制在屏幕上,和通过阻止玩家/怪物。我们的门可以有两种状态,打开和关闭。关闭时,碰撞区域的门充满整个部分的走廊,当打开碰撞区域移动(或门对象标记为一个对象,不会撞上东西。)

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

class WorldObject
   {
       public Vector2 Position { get; set; }
       public Rectangle CollisionArea { get; set; }
       public bool CallbackIfNotColliding { get; set; }
    
       // Called when the world detects a collision, with a pointer
       //  to the object we collided with
       public virtual void Collide(WorldObject otherObject) { }
    
       // Called when we don't collide with anything, if our
       // CallbackIfNotColliding flag is set
       public virtual void NoCollision() { }
   }
   class Door : WorldObject
   {
       public void Draw(Spritebatch sb)
       {
            if (mIsOpen)
            {
            	// Draw open door
            }
            else
            {
            	// Draw closed door
            }
       
       		// Could also keep track if door is opening / closing, draw animation
       }
       
       public void Update(GameTime gameTime)
       {
            // Updating for any dynamic behavior (like animating opening / closing,
            //    or a revolving door, or something else)       
       }
       
       
        public bool IsOpen
        {
            get
            {
                return mIsOpen;
            }
            set
            {
            	if (value != mIsOpen)
                {
                  // Either modify collision volume that world uses, or set a flag
                  //  for the world to ignore / allow collisions with this door 
                  mIsOpen = value;
                }
            }
       }
       		
       private bool mIsOpen;
   }

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

class TriggeredDoor : WorldObject
{
     private Door mDoor;

     public override void Collide(WorldObject otherObject)
     {
     	Door.IsOpen = true;
     }
     
     public override void NoCollide()
     {
     	Door.IsOpen = false;
     }
}

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

<TriggeredDoor>
  <TriggerArea type = "Rectangle">
    <x>
      300
    </x>
    <y> 
      200
    </y>
    <w>
      30
    </w>
    <h>
      20
    </h>
  </TriggerArea>
  <ClosedCollisionArea type = "Rectangle">
    <x>
      320
    </x>
    <y> 
      200
    </y>
    <w>
      5
    </w>
    <h>
      20
    </h>
  </ClosedCollisionArea>
  <OpenCollisionArea type = "Rectangle">
    <x>
      320
    </x>
    <y> 
      200
    </y>
    <w>
      5
    </w>
    <h>
      2
    </h>
  </OpenCollisionArea>
  <OpenTexture type = "String">OpenDoor1</OpenTexture>
  <ClosedTexture type = "String">ClosedDoor1</ClosedTexture>
  <TexturePosition type = "Vector2">
    <x>
      100
    </x>
    <y> 
      100
      
      </TexturePosition>
</TriggeredDoor>

当你输入一个特定的体积。如果有一个全局函数,关掉灯,我们可以在我们的世界文件中创建一个条目,看起来像下面的:

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

<TriggeringArea>
   <Area type = "Rectangle">
      <x>
         100
      </x>
      <y>
         50
      </y> 
      <w>
         30
      </w> 
      <h>
          10
      </h>
   </Area>
   <code>
       TurnOffLights()
   </code>
</triggeringarea>

脚本执行器

1
2
3
4
5

Object obj = Scripting.GetInstance();                              // Get a pointer ot the object
MethodType method = obj.GetType().GetMethod("TurnOnLights");       // Get a pointer to the method object
Obj [] params = new Obj[0];                                        // Array of parameters (none, in this example)
method.Invoke(obj, params);                                        // Call the method

在其之下隐藏的设计思想

1、控制复杂度。通过把程序逻辑的复杂度转移到人类更容易处理的数据中来，从而达到控制复杂度的目标。代码流程从命令式变成了 声明式
2、隔离变化。像上面的例子，每个消息处理的逻辑是不变的，但是消息可能是变化的，那就把容易变化的消息和不容易变化的逻辑分离。
3、机制和策略的分离。机制就是消息的处理逻辑，策略就是不同的消息处理。

函数式编程

函数式编程，或称函数程序设计、泛函编程（英語：Functional programming），是一种编程范式，它将电脑运算视为函数运算，并且避免使用程式状态（英语：State (computer science)）以及易变物件。其中，λ演算为该语言最重要的基础。而且，λ演算的函数可以接受函数作为输入參數和输出返回值。

比起指令式編程，函数式编程更加强调程序执行的结果而非执行的过程，倡导利用若干简单的执行单元让计算结果不断渐进，逐层推导复杂的运算，而不是设计一个复杂的执行过程。

在函数式编程中，函数是头等对象，意思是说一个函数，既可以作为其它函数的输入参数值，也可以从函数中返回值，被修改或者被分配给一个变量。

早在50年代函数式编程开始之前，Lisp 语言就已经在 IBM 700/7000 系列的科学计算机上运行了。Lisp 引入了很多与我们现在的函数式编程有关的示例与功能，我们甚至可以称 Lisp 是所有函数式编程语言的鼻祖。

这也是函数式编程中最有趣的方面，所有函数式编程语言都是基于相同的 λ演算，这种简单数学基础。

λ演算是图灵完备的，它是一种通用的计算模型，可用于模拟任何一台单带图灵机。它名字中的希腊字母 lambda（λ），被使用在了 lambda 表达式和 lambda 项绑定函数中的变量中。

λ演算是一个极其简单但又十分强大的概念。它的核心主要有两个概念：

• 函数的抽象，通过引入变量来归纳得出表达式；
• 函数的应用，通过给变量赋值来对已得出的表达式进行计算；

让我们来看个小例子，单参数函数 f，将参数递增1。

1

f = λ x. x+1 

假设我们应用函数在数字5上，那么函数读取如下：

1

f(5) => 5 + 1

函数式编程的基本原理

现在，数学知识已经够了。让我们看一下使函数式编程变得强大的特性有哪些？

头等函数（first-class function）

在函数式编程中，函数是一等公民，意思是说函数可以赋值给变量，例如在 elixir 中，

1

double = fn(x) -> x * 2 

然后我们可以如下来调用函数：

1

double.(2) 

scala

1
2
3

def m(x: Int):Int = x * 2

m(2) //输出4

scala匿名函数/闭包

1

val m = (x: Int) => x * 2

java中的运用

1
2
3
4
5
6
7
8

@FunctionalInterface
interface FunctionMul{
    int multiTwo(int x);
}        


FunctionMul func = x -> x * 2;
func.multi(2); //输出4

一个最常用的Function

1
2
3

Function<Integer,Integer> function = x -> x * 2;

function.apply(2); // 

高阶函数（higher-order function）

高阶函数的定义是，接收一个或多个函数变量作为参数，然后生成的新函数，即为高阶函数。具体有两种情况：

1. 函数可以作为参数被传递
2. 函数可以作为返回值输出

让我们再次使用函数 double 来说明这个概念：

1
2

double = fn(x) -> x * 2
Enum.map(1..10, double) 

这例子中，Enum.map 将一个枚举列表作为第一参数，之前定义的函数作为第二参数；然后将这个函数应用到枚举中的每一个元素，结果为：

1

[2,4,6,8,10,12,14,16,18,20] 

scala中的高阶函数

1
2
3
4
5
6
7
8
9

def test(f:Int => String , num : Int) = f(num)

def f(num:Int) : String = {
  10 + num + ""
}

def main(args: Array[String]): Unit = {
  println(test(f,10))
}

java中的例子

1
2
3
4

Integer[] arr = new Integer[]{2,4,6,8,10,12,14,16,18,20};
Arrays.stream(arr)
                .map(function)
                .toArray();

java非常常见的写法

1

Arrays.sort(arr, (s1, s2)->s1.compareToIgnoreCase(s2));

不可变状态（Immutable State）

在函数式编程语言中，状态是不可变的。这意味着一旦一个变量被绑定了一个值，它将不能再被重新定义。这在防止副作用与条件竞争上有明显的优势，使并发编程更简单。

另外，函数式编程中的“值不可变性”避免了对公共的可变状态进行同步访问控制的复杂问题，能够较好满足分布式并行编程的需求，适应大数据时代的到来。

和上面一样，让我们使用 Elixir 来说明一下这概念：

1
2
3
4
5
6

iex> tuple = {:ok, "hello"} 
{:ok, "hello"} 
iex> put_elem(tuple, 1, "world") 
{:ok, "world"} 
iex> tuple 
{:ok, "hello"} 

这个例子中，tuple 的值从来没有改变过，第三行 put_elem 是返回了一个完全新的 tuple， 而没有去修改原有的值。

Scala 中定义变量分为 var（可变变量）和 val（不可变变量）

Scala 中集合框架也分为可变集合和不可变集合。比如 List（列表） 和 Tuple（元组）本身就是不可变的，set 和 map 分为可变和不可变的，默认为不可变。

1
2
3
4
5
6
7

//创建List
val list = List("abc","xyz")


//添加元素。list本身不变，返回一个新的list
val list1 = list :+ 6 //加到后面 List(abc, xyz, 6)
val list2 = 10 +: list //加到前面 List(10, abc, xyz)

函数组合子（Functional Combinators）

组合子逻辑意图作为简单的元逻辑，它能澄清在逻辑符号中的量化变量的意义，并真正的消除对它们的需要。消除量化变量的另一种方式是蒯因的谓词函子。尽管多数组合子逻辑系统超出了一阶逻辑的表达能力，蒯因的谓词函子的表达能力等价于一阶逻辑

• map对列表中的每个元素应用一个函数，返回应用后的元素所组成的列表。
• filter移除任何对传入函数计算结果为false的元素。返回一个布尔值的函数通常被称为谓词函数[或判定函数]。
• zip将两个列表的内容聚合到一个对偶列表中。
• partition将使用给定的谓词函数分割列表。
• find返回集合中第一个匹配谓词函数的元素。
• foldLeft，0为初始值（记住numbers是List[Int]类型），m作为一个累加器。
• flatten将嵌套结构扁平化为一个层次的集合。
• flatMap是一种常用的组合子，结合映射[mapping]和扁平化[flattening]。 flatMap需要一个处理嵌套列表的函数，然后将结果串连起来。

scala

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

scala> numbers.map((i: Int) => i * 2)
res0: List[Int] = List(2, 4, 6, 8)

scala> numbers.filter((i: Int) => i % 2 == 0)
res0: List[Int] = List(2, 4)

scala> List(1, 2, 3).zip(List("a", "b", "c"))
res0: List[(Int, String)] = List((1,a), (2,b), (3,c))

scala> val numbers = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
scala> numbers.partition(_ % 2 == 0)
res0: (List[Int], List[Int]) = (List(2, 4, 6, 8, 10),List(1, 3, 5, 7, 9))

scala> numbers.find((i: Int) => i > 5)
res0: Option[Int] = Some(6)

scala> numbers.foldLeft(0)((m: Int, n: Int) => m + n)
res0: Int = 55

1
2
3
4

Integer[] arr = new Integer[]{2,4,6,8,10,12,14,16,18,20};
Arrays.stream(arr)
        .map(x -> x * 2)
        .toArray();

柯里化函数(Currying)

在计算机科学中，柯里化（Currying）是把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数，并且返回接受余下的参数且返回结果的新函数的技术。

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

scala> def mul(x:Int,y:Int):Int = x *y
mul: (x: Int, y: Int)Int

scala> mul(6,7)
res12: Int = 42


scala> def mul2(x:Int)(y:Int)=x*y
mul2: (x: Int)(y: Int)Int


scala> mul2(6)(7)
res14: Int = 42

// 实际上是先变成这样一个函数
scala> def mul2(x:Int)=(y:Int)=>x*y
mul2: (x: Int)Int => Int


scala> val result = mul2(6)
result: (y:Int)=>6*y


scala> val sum = result(7)
sum: 42

运用

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

def getLines(filename: String)(isFileReadable: (File) => Boolean)(closableStream: (Closeable) => Unit):List[String] = {
  val file = new File(filename)
  if (isFileReadable(file)) {
    val readerStream = new FileReader(file)
    val buffer = new BufferedReader(readerStream)
    try {
      var list: List[String] = List()
      var str = ""
      var isReadOver = false
      while (!isReadOver) {
        str = buffer.readLine()
        if (str == null) isReadOver = true
        else list = str :: list
      }
      list.reverse
    } finally {
      closableStream(buffer)
      closableStream(readerStream)
    }
  } else {
    List()
  }
}

def isReadable(file: File) = {
  if (null != file && file.exists() && file.canRead()) true
  else false
}
def closeStream(stream: Closeable) {
  if (null != stream) {
    try {
      stream.close
    } catch {
      case ex => Log.error(“[”+this.getClass.getName+”.closeStream]”,ex.getMessage)
    }
  }
}


def getLines(filename:String):List[String]={
  getLines(filename)(isReadable)(closeStream)
}

spark源码

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

def sql(sqlText: String): DataFrame = {
    Dataset.ofRows(self, sessionState.sqlParser.parsePlan(sqlText))
}
        
        
override def parsePlan(sqlText: String): LogicalPlan = parse(sqlText) { parser =>
    astBuilder.visitSingleStatement(parser.singleStatement()) match {
      case plan: LogicalPlan => plan
      case _ =>
        val position = Origin(None, None)
        throw new ParseException(Option(sqlText), "Unsupported SQL statement", position, position)
    }
  }        





protected def parse[T](command: String)(toResult: SqlBaseParser => T): T = {
    logInfo(s"Parsing command: $command")

    val lexer = new SqlBaseLexer(new ANTLRNoCaseStringStream(command))
    lexer.removeErrorListeners()
    lexer.addErrorListener(ParseErrorListener)

    val tokenStream = new CommonTokenStream(lexer)
    val parser = new SqlBaseParser(tokenStream)
    parser.addParseListener(PostProcessor)
    parser.removeErrorListeners()
    parser.addErrorListener(ParseErrorListener)

    try {
      try {
        // first, try parsing with potentially faster SLL mode
        parser.getInterpreter.setPredictionMode(PredictionMode.SLL)
        toResult(parser)
      ...

java中的柯里化

1
2
3
4
5
6
7
8
9

Function<String,
Function<String,
Function<String, String>>> sum =
    a -> b -> c -> a + b + c; 

Function<String, Function<String, String>> hi =
    sum.apply("Hi ");
Function<String, String> ho = hi.apply("Ho ");
        System.out.println(ho.apply("Hup"));

函数式编程下的并发编程

一般来说有两种策略用来在并发线程中进行通信：共享数据和消息传递。使用共享数据方式的并发编程面临的最大的一个问题就是数据条件竞争。处理各种锁的问题是让人十分头痛的一件事。

传统多数流行的语言并发是基于多线程之间的共享内存，使用同步方法防止写争夺，Actors使用消息模型，每个Actor在同一时间处理最多一个消息，可以发送消息给其他Actor，保证了单独写原则。从而巧妙避免了多线程写争夺。和共享数据方式相比，消息传递机制最大的优点就是不会产生数据竞争状态。实现消息传递有两种常见的类型：基于channel（golang为典型代表）的消息传递和基于Actor（erlang为代表）的消息传递。

Actor简介

Actor模型(Actor model)首先是由Carl Hewitt在1973定义， 由Erlang OTP 推广，其 消息传递更加符合面向对象的原始意图。Actor属于并发组件模型，通过组件方式定义并发编程范式的高级阶段，避免使用者直接接触多线程并发或线程池等基础概念。

Actor模型=数据+行为+消息。

erlang，在语言层面就提供了Actor模型的支持，RabbitMQ 就是基于erlang开发的。

无锁

JAVA并发编程时需要特别的关注锁和内存原子性等一系列线程问题，而Actor模型内部的状态由它自己维护即它内部数据只能由它自己修改(通过消息传递来进行状态修改)，所以使用Actors模型进行并发编程可以很好地避免这些问题。Actor内部是以单线程的模式来执行的，类似于redis，所以Actor完全可以实现分布式锁类似的应用。

异步

每个Actor都有一个专用的MailBox来接收消息，这也是Actor实现异步的基础。当一个Actor实例向另外一个Actor发消息的时候，并非直接调用Actor的方法，而是把消息传递到对应的MailBox里，就好像邮递员，并不是把邮件直接送到收信人手里，而是放进每家的邮箱，这样邮递员就可以快速的进行下一项工作。所以在Actor系统里，Actor发送一条消息是非常快的。

这样的设计主要优势就是解耦了Actor，数万个Actor并发的运行，每个actor都以自己的步调运行，且发送消息，接收消息都不会被阻塞。

隔离

每个Actor的实例都维护这自己的状态，与其他Actor实例处于物理隔离状态，并非像 多线程+锁 模式那样基于共享数据。Actor通过消息的模式与其他Actor进行通信，与OO式的消息传递方式不同，Actor之间消息的传递是真正物理上的消息传递。

天生分布式

每个Actor实例的位置透明，无论Actor地址是在本地还是在远程机器上对于代码来说都是一样的。每个Actor的实例非常小，最多几百字节，所以单机几十万的Actor的实例很轻松。如果你写过golang代码，就会发现其实Actor在重量级上很像Goroutine。由于位置透明性，所以Actor系统可以随意的横向扩展来应对并发，对于调用者来说，调用的Actor的位置就在本地，当然这也得益于Actor系统强大的路由系统。

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

case class SetRequest(key: String, value: String)


class AkkademyDb extends Actor {
  val map = new HashMap[String, String]
  val log = Logging(context.system, this)

  override def receive = {
    case SetRequest(key, value) => {
      log.info("received SetRequest - key: {} value: {}", key, value)
      map.put(key, value)
    }
    case o => log.info("received unknown message: {}", o);
  }
}



val actorRef = TestActorRef(new AkkademyDb)
actorRef ! SetRequest("key", "value")

思维的转变

总结下函数式常用思维方式：

1. 表达式化
   就是去掉变量，去掉循环，通过表达式处理逻辑。
2. 数据与行为分离，无副作用
   由于严格作用域，必须没有副作用。
3. 高阶思维
   能用 map 解决的，就不要 for 循环
4. 组合思维
   函数式和面向对象是相反的，面向对象是自顶向下的设计，函数式是自底向上的设计，也就是先定义基本操作，然后不断组合。比如 sql 定义了 select， from， where … 这些组合子来满足查询需求。

编辑conf/server.xml文件

1
2
3
4
5
6
7
8

<Connector port="8080"               maxHttpHeaderSize="8192"
               maxThreads="150" minSpareThreads="25" maxSpareThreads="75"
               enableLookups="false" redirectPort="8443" acceptCount="100"
               connectionTimeout="20000" disableUploadTimeout="true"
      compression="on"
compressionMinSize="2048"
noCompressionUserAgents="gozilla,traviata" 
compressableMimeType="text/html,text/xml,text/javascript,text/css,text/plain" />

1. compression=”on” 打开压缩功能
2. compressionMinSize=”2048” 启用压缩的输出内容大小，这里面默认为2KB
3. noCompressionUserAgents=”gozilla, traviata” 对于以下的浏览器，不启用压缩<60;
4. compressableMimeType=”text/html,text/xml” 压缩类型

http://hongjiang.info/index/tomcat/

uu加速器需要会员非常麻烦，根据下面步骤可以绕过。

下载uu加速器

这个步骤省略，登录 https://uu.163.com/ 下载

下载安装翻墙软件

下载地址：https://www.mediafire.com/folder/sfqz8bmodqdx5/shadowsocks%E7%9B%B8%E5%85%B3%E5%AE%A2%E6%88%B7%E7%AB%AF

如果是windows系统，第一次电脑系统使用SSR/SS客户端时，如果提示你需要安装NET Framework 4.0，网上搜一下这个东西，安装一下即可。NET Framework 4.0是SSR/SS的运行库，没有这个SSR/SS客户端无法正常运行。有的电脑系统可能会自带NET Framework 4.0。

安装过程省略

使用免费账号

地址：https://github.com/Alvin9999/new-pac/wiki/ss%E5%85%8D%E8%B4%B9%E8%B4%A6%E5%8F%B7#%E5%85%8D%E8%B4%B9ssssr%E8%B4%A6%E5%8F%B7%E8%8A%82%E7%82%B9%E5%88%97%E8%A1%A8%E9%95%BF%E6%9C%9F%E6%9B%B4%E6%96%B0

选中其中一个链接复制到浏览器

打开自动导入

选中，并勾选打开shadowsocks

切换全局模式

开始uu加速

打开uu加速器。不要登录直接选择一款游戏选择节点，连接后按教程去配置你的switch或者ps4

关闭翻墙软件

把全局模式切回Pac模式或者直接关闭翻墙软件。

ps.如果发现部分不可描述的页面打不开，点开高级设置，替换GFW LIST URL 为： https://github.com/www1350/gfwlist/blob/master/gfwlist.txt

HighGui界面初步

图像的载入

imread函数，用在读取图像到Mat矩阵，可以看下官方注释

• 这个函数从指定文件加载图片返回，如果图片无法读取，就会返回空矩阵(Mat::data == null)，支持如下格式
  • windows位图，*.bmp, *.dib
  • JPEG文件，*.jpeg, *.jpg, *.jpe
  • JPEG2000文件，*.jp2
  • 便携式文件格式，*.pbm, *.pgm, *.ppm *.pxm, *.pnm
  • Sun rasters光栅文件，*.sr, *.ras
  • TIFF文件，*.tiff, *.tif
  • OpenEXR图片文件，*.exr
  • HDR文件，*.hdr, *.pic
  • 栅格和矢量地理空间数据
• 第二个参数，载入标识，指定一个加载图片的颜色类型，自带的默认值为1。也就是三通道BGR。
  • flag>0 返回一个三通道的彩色图像
  • flag=0 返回灰度图像
  • flag<0 返回包含alpha通道加载图像

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

enum ImreadModes {
       IMREAD_UNCHANGED            = -1, //!< If set, return the loaded image as is (with alpha channel, otherwise it gets cropped).已废弃
       IMREAD_GRAYSCALE            = 0,  //!< If set, always convert image to the single channel grayscale image (codec internal conversion).转成灰度
       IMREAD_COLOR                = 1,  //!< If set, always convert image to the 3 channel BGR color image.
       IMREAD_ANYDEPTH             = 2,  //!< If set, return 16-bit/32-bit image when the input has the corresponding depth, otherwise convert it to 8-bit.载入16或32位深度图像，否则转化为8位返回
       IMREAD_ANYCOLOR             = 4,  //!< If set, the image is read in any possible color format. 
       IMREAD_LOAD_GDAL            = 8,  //!< If set, use the gdal driver for loading the image.
       IMREAD_REDUCED_GRAYSCALE_2  = 16, //!< If set, always convert image to the single channel grayscale image and the image size reduced 1/2.
       IMREAD_REDUCED_COLOR_2      = 17, //!< If set, always convert image to the 3 channel BGR color image and the image size reduced 1/2.
       IMREAD_REDUCED_GRAYSCALE_4  = 32, //!< If set, always convert image to the single channel grayscale image and the image size reduced 1/4.
       IMREAD_REDUCED_COLOR_4      = 33, //!< If set, always convert image to the 3 channel BGR color image and the image size reduced 1/4.
       IMREAD_REDUCED_GRAYSCALE_8  = 64, //!< If set, always convert image to the single channel grayscale image and the image size reduced 1/8.
       IMREAD_REDUCED_COLOR_8      = 65, //!< If set, always convert image to the 3 channel BGR color image and the image size reduced 1/8.
       IMREAD_IGNORE_ORIENTATION   = 128 //!< If set, do not rotate the image according to EXIF's orientation flag.
     };

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

The function imread loads an image from the specified file and returns it. If the image cannot be
read (because of missing file, improper permissions, unsupported or invalid format), the function
returns an empty matrix ( Mat::data==NULL ).

Currently, the following file formats are supported:

-   Windows bitmaps - \*.bmp, \*.dib (always supported)
-   JPEG files - \*.jpeg, \*.jpg, \*.jpe (see the *Note* section)
-   JPEG 2000 files - \*.jp2 (see the *Note* section)
-   Portable Network Graphics - \*.png (see the *Note* section)
-   WebP - \*.webp (see the *Note* section)
-   Portable image format - \*.pbm, \*.pgm, \*.ppm \*.pxm, \*.pnm (always supported)
-   Sun rasters - \*.sr, \*.ras (always supported)
-   TIFF files - \*.tiff, \*.tif (see the *Note* section)
-   OpenEXR Image files - \*.exr (see the *Note* section)
-   Radiance HDR - \*.hdr, \*.pic (always supported)
-   Raster and Vector geospatial data supported by GDAL (see the *Note* section)

@note
-   The function determines the type of an image by the content, not by the file extension.
-   In the case of color images, the decoded images will have the channels stored in **B G R** order.
-   When using IMREAD_GRAYSCALE, the codec's internal grayscale conversion will be used, if available.
    Results may differ to the output of cvtColor()
-   On Microsoft Windows\* OS and MacOSX\*, the codecs shipped with an OpenCV image (libjpeg,
    libpng, libtiff, and libjasper) are used by default. So, OpenCV can always read JPEGs, PNGs,
    and TIFFs. On MacOSX, there is also an option to use native MacOSX image readers. But beware
    that currently these native image loaders give images with different pixel values because of
    the color management embedded into MacOSX.
-   On Linux\*, BSD flavors and other Unix-like open-source operating systems, OpenCV looks for
    codecs supplied with an OS image. Install the relevant packages (do not forget the development
    files, for example, "libjpeg-dev", in Debian\* and Ubuntu\*) to get the codec support or turn
    on the OPENCV_BUILD_3RDPARTY_LIBS flag in CMake.
-   In the case you set *WITH_GDAL* flag to true in CMake and @ref IMREAD_LOAD_GDAL to load the image,
    then the [GDAL](http://www.gdal.org) driver will be used in order to decode the image, supporting
    the following formats: [Raster](http://www.gdal.org/formats_list.html),
    [Vector](http://www.gdal.org/ogr_formats.html).
-   If EXIF information are embedded in the image file, the EXIF orientation will be taken into account
    and thus the image will be rotated accordingly except if the flag @ref IMREAD_IGNORE_ORIENTATION is passed.
-   By default number of pixels must be less than 2^30. Limit can be set using system
    variable OPENCV_IO_MAX_IMAGE_PIXELS

@param filename Name of file to be loaded.
@param flags Flag that can take values of cv::ImreadModes
*/
CV_EXPORTS_W Mat imread( const String& filename, int flags = IMREAD_COLOR );

1
2

Mat img = imread("a.jpg", 2 | 4); //载入无损源图像
Mat img = imread("a.jpg", 0); //载入灰度图

图像的显示

imshow函数，用在指定界面显示图像

• 如果窗口使用cv::WINDOW_AUTOSIZE创建，会显示原始大小（还是会受限屏幕），否则会将图片缩放适合窗口。缩放图像取决于深度：
  • 8位无符号，显示图像原来样子
  • 16位无符号或32位整型，用像素值除以256，值在 [0,255]
  • 如果图像是32位或64位浮点型，像素乘以255，[0,1] 映射到[0,255]
• 如果窗口创建，设定了支持openGL，imshow 还支持 ogl::Buffer , ogl::Texture2D 和
  cuda::GpuMat 作为输入.
• 如果你需要显示图像大于屏幕，在imshow前需要调用namedWindow(“”, WINDOW_NORMAL).

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

/** @brief Displays an image in the specified window.

The function imshow displays an image in the specified window. If the window was created with the
cv::WINDOW_AUTOSIZE flag, the image is shown with its original size, however it is still limited by the screen resolution.
Otherwise, the image is scaled to fit the window. The function may scale the image, depending on its depth:

-   If the image is 8-bit unsigned, it is displayed as is.
-   If the image is 16-bit unsigned or 32-bit integer, the pixels are divided by 256. That is, the
    value range [0,255\*256] is mapped to [0,255].
-   If the image is 32-bit or 64-bit floating-point, the pixel values are multiplied by 255. That is, the
    value range [0,1] is mapped to [0,255].

If window was created with OpenGL support, cv::imshow also support ogl::Buffer , ogl::Texture2D and
cuda::GpuMat as input.

If the window was not created before this function, it is assumed creating a window with cv::WINDOW_AUTOSIZE.

If you need to show an image that is bigger than the screen resolution, you will need to call namedWindow("", WINDOW_NORMAL) before the imshow.

@note This function should be followed by cv::waitKey function which displays the image for specified
milliseconds. Otherwise, it won't display the image. For example, **waitKey(0)** will display the window
infinitely until any keypress (it is suitable for image display). **waitKey(25)** will display a frame
for 25 ms, after which display will be automatically closed. (If you put it in a loop to read
videos, it will display the video frame-by-frame)

@note

[__Windows Backend Only__] Pressing Ctrl+C will copy the image to the clipboard.

[__Windows Backend Only__] Pressing Ctrl+S will show a dialog to save the image.

@param winname Name of the window.
@param mat Image to be shown.
 */
CV_EXPORTS_W void imshow(const String& winname, InputArray mat);

InputArray类型

1

typedef const _InputArray& InputArray;

_InputArray在core.hpp头文件里面

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

//////////////////////// Input/Output Array Arguments /////////////////////////////////

/** @brief This is the proxy class for passing read-only input arrays into OpenCV functions.

It is defined as:
@code
    typedef const _InputArray& InputArray;
@endcode
where _InputArray is a class that can be constructed from `Mat`, `Mat_<T>`, `Matx<T, m, n>`,
`std::vector<T>`, `std::vector<std::vector<T> >`, `std::vector<Mat>`, `std::vector<Mat_<T> >`,
`UMat`, `std::vector<UMat>` or `double`. It can also be constructed from a matrix expression.

Since this is mostly implementation-level class, and its interface may change in future versions, we
do not describe it in details. There are a few key things, though, that should be kept in mind:

-   When you see in the reference manual or in OpenCV source code a function that takes
    InputArray, it means that you can actually pass `Mat`, `Matx`, `vector<T>` etc. (see above the
    complete list).
-   Optional input arguments: If some of the input arrays may be empty, pass cv::noArray() (or
    simply cv::Mat() as you probably did before).
-   The class is designed solely for passing parameters. That is, normally you *should not*
    declare class members, local and global variables of this type.
-   If you want to design your own function or a class method that can operate of arrays of
    multiple types, you can use InputArray (or OutputArray) for the respective parameters. Inside
    a function you should use _InputArray::getMat() method to construct a matrix header for the
    array (without copying data). _InputArray::kind() can be used to distinguish Mat from
    `vector<>` etc., but normally it is not needed.

Here is how you can use a function that takes InputArray :
@code
    std::vector<Point2f> vec;
    // points or a circle
    for( int i = 0; i < 30; i++ )
        vec.push_back(Point2f((float)(100 + 30*cos(i*CV_PI*2/5)),
                              (float)(100 - 30*sin(i*CV_PI*2/5))));
    cv::transform(vec, vec, cv::Matx23f(0.707, -0.707, 10, 0.707, 0.707, 20));
@endcode
That is, we form an STL vector containing points, and apply in-place affine transformation to the
vector using the 2x3 matrix created inline as `Matx<float, 2, 3>` instance.

Here is how such a function can be implemented (for simplicity, we implement a very specific case of
it, according to the assertion statement inside) :
@code
    void myAffineTransform(InputArray _src, OutputArray _dst, InputArray _m)
    {
        // get Mat headers for input arrays. This is O(1) operation,
        // unless _src and/or _m are matrix expressions.
        Mat src = _src.getMat(), m = _m.getMat();
        CV_Assert( src.type() == CV_32FC2 && m.type() == CV_32F && m.size() == Size(3, 2) );

        // [re]create the output array so that it has the proper size and type.
        // In case of Mat it calls Mat::create, in case of STL vector it calls vector::resize.
        _dst.create(src.size(), src.type());
        Mat dst = _dst.getMat();

        for( int i = 0; i < src.rows; i++ )
            for( int j = 0; j < src.cols; j++ )
            {
                Point2f pt = src.at<Point2f>(i, j);
                dst.at<Point2f>(i, j) = Point2f(m.at<float>(0, 0)*pt.x +
                                                m.at<float>(0, 1)*pt.y +
                                                m.at<float>(0, 2),
                                                m.at<float>(1, 0)*pt.x +
                                                m.at<float>(1, 1)*pt.y +
                                                m.at<float>(1, 2));
            }
    }
@endcode
There is another related type, InputArrayOfArrays, which is currently defined as a synonym for
InputArray:
@code
    typedef InputArray InputArrayOfArrays;
@endcode
It denotes function arguments that are either vectors of vectors or vectors of matrices. A separate
synonym is needed to generate Python/Java etc. wrappers properly. At the function implementation
level their use is similar, but _InputArray::getMat(idx) should be used to get header for the
idx-th component of the outer vector and _InputArray::size().area() should be used to find the
number of components (vectors/matrices) of the outer vector.

In general, type support is limited to cv::Mat types. Other types are forbidden.
But in some cases we need to support passing of custom non-general Mat types, like arrays of cv::KeyPoint, cv::DMatch, etc.
This data is not intented to be interpreted as an image data, or processed somehow like regular cv::Mat.
To pass such custom type use rawIn() / rawOut() / rawInOut() wrappers.
Custom type is wrapped as Mat-compatible `CV_8UC<N>` values (N = sizeof(T), N <= CV_CN_MAX).
 */
class CV_EXPORTS _InputArray
{
public:
    enum {
        KIND_SHIFT = 16,
        FIXED_TYPE = 0x8000 << KIND_SHIFT,
        FIXED_SIZE = 0x4000 << KIND_SHIFT,
        KIND_MASK = 31 << KIND_SHIFT,

        NONE              = 0 << KIND_SHIFT,
        MAT               = 1 << KIND_SHIFT,
        MATX              = 2 << KIND_SHIFT,
        STD_VECTOR        = 3 << KIND_SHIFT,
        STD_VECTOR_VECTOR = 4 << KIND_SHIFT,
        STD_VECTOR_MAT    = 5 << KIND_SHIFT,
        EXPR              = 6 << KIND_SHIFT,
        OPENGL_BUFFER     = 7 << KIND_SHIFT,
        CUDA_HOST_MEM     = 8 << KIND_SHIFT,
        CUDA_GPU_MAT      = 9 << KIND_SHIFT,
        UMAT              =10 << KIND_SHIFT,
        STD_VECTOR_UMAT   =11 << KIND_SHIFT,
        STD_BOOL_VECTOR   =12 << KIND_SHIFT,
        STD_VECTOR_CUDA_GPU_MAT = 13 << KIND_SHIFT,
        STD_ARRAY         =14 << KIND_SHIFT,
        STD_ARRAY_MAT     =15 << KIND_SHIFT
    };

    _InputArray();
    _InputArray(int _flags, void* _obj);
    _InputArray(const Mat& m);
    _InputArray(const MatExpr& expr);
    _InputArray(const std::vector<Mat>& vec);
    template<typename _Tp> _InputArray(const Mat_<_Tp>& m);
    template<typename _Tp> _InputArray(const std::vector<_Tp>& vec);
    _InputArray(const std::vector<bool>& vec);
    template<typename _Tp> _InputArray(const std::vector<std::vector<_Tp> >& vec);
    _InputArray(const std::vector<std::vector<bool> >&);
    template<typename _Tp> _InputArray(const std::vector<Mat_<_Tp> >& vec);
    template<typename _Tp> _InputArray(const _Tp* vec, int n);
    template<typename _Tp, int m, int n> _InputArray(const Matx<_Tp, m, n>& matx);
    _InputArray(const double& val);
    _InputArray(const cuda::GpuMat& d_mat);
    _InputArray(const std::vector<cuda::GpuMat>& d_mat_array);
    _InputArray(const ogl::Buffer& buf);
    _InputArray(const cuda::HostMem& cuda_mem);
    template<typename _Tp> _InputArray(const cudev::GpuMat_<_Tp>& m);
    _InputArray(const UMat& um);
    _InputArray(const std::vector<UMat>& umv);

#ifdef CV_CXX_STD_ARRAY
    template<typename _Tp, std::size_t _Nm> _InputArray(const std::array<_Tp, _Nm>& arr);
    template<std::size_t _Nm> _InputArray(const std::array<Mat, _Nm>& arr);
#endif

    template<typename _Tp> static _InputArray rawIn(const std::vector<_Tp>& vec);
#ifdef CV_CXX_STD_ARRAY
    template<typename _Tp, std::size_t _Nm> static _InputArray rawIn(const std::array<_Tp, _Nm>& arr);
#endif

    Mat getMat(int idx=-1) const;
    Mat getMat_(int idx=-1) const;
    UMat getUMat(int idx=-1) const;
    void getMatVector(std::vector<Mat>& mv) const;
    void getUMatVector(std::vector<UMat>& umv) const;
    void getGpuMatVector(std::vector<cuda::GpuMat>& gpumv) const;
    cuda::GpuMat getGpuMat() const;
    ogl::Buffer getOGlBuffer() const;

    int getFlags() const;
    void* getObj() const;
    Size getSz() const;

    int kind() const;
    int dims(int i=-1) const;
    int cols(int i=-1) const;
    int rows(int i=-1) const;
    Size size(int i=-1) const;
    int sizend(int* sz, int i=-1) const;
    bool sameSize(const _InputArray& arr) const;
    size_t total(int i=-1) const;
    int type(int i=-1) const;
    int depth(int i=-1) const;
    int channels(int i=-1) const;
    bool isContinuous(int i=-1) const;
    bool isSubmatrix(int i=-1) const;
    bool empty() const;
    void copyTo(const _OutputArray& arr) const;
    void copyTo(const _OutputArray& arr, const _InputArray & mask) const;
    size_t offset(int i=-1) const;
    size_t step(int i=-1) const;
    bool isMat() const;
    bool isUMat() const;
    bool isMatVector() const;
    bool isUMatVector() const;
    bool isMatx() const;
    bool isVector() const;
    bool isGpuMat() const;
    bool isGpuMatVector() const;
    ~_InputArray();

protected:
    int flags;
    void* obj;
    Size sz;

    void init(int _flags, const void* _obj);
    void init(int _flags, const void* _obj, Size _sz);
};

• 如果你看到使用InputArray,可以当成 Mat, Matx, vector<T> 等

创建窗口namedWindow()函数

上面说过，简单显示不需要调用，如果需要用到窗口则需要用到.

• 如果窗口名已经存在，则不做任何处理
• 调用 cv::destroyWindow 或 cv::destroyAllWindows 关闭窗口 释放内存空间。如果是简单程序，退出时，资源会被系统释放掉

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

/** @brief Creates a window.

The function namedWindow creates a window that can be used as a placeholder for images and
trackbars. Created windows are referred to by their names.

If a window with the same name already exists, the function does nothing.

You can call cv::destroyWindow or cv::destroyAllWindows to close the window and de-allocate any associated
memory usage. For a simple program, you do not really have to call these functions because all the
resources and windows of the application are closed automatically by the operating system upon exit.

@note

Qt backend supports additional flags:
 -   **WINDOW_NORMAL or WINDOW_AUTOSIZE:** WINDOW_NORMAL enables you to resize the
     window, whereas WINDOW_AUTOSIZE adjusts automatically the window size to fit the
     displayed image (see imshow ), and you cannot change the window size manually.
 -   **WINDOW_FREERATIO or WINDOW_KEEPRATIO:** WINDOW_FREERATIO adjusts the image
     with no respect to its ratio, whereas WINDOW_KEEPRATIO keeps the image ratio.
 -   **WINDOW_GUI_NORMAL or WINDOW_GUI_EXPANDED:** WINDOW_GUI_NORMAL is the old way to draw the window
     without statusbar and toolbar, whereas WINDOW_GUI_EXPANDED is a new enhanced GUI.
By default, flags == WINDOW_AUTOSIZE | WINDOW_KEEPRATIO | WINDOW_GUI_EXPANDED

@param winname Name of the window in the window caption that may be used as a window identifier.
@param flags Flags of the window. The supported flags are: (cv::WindowFlags)
 */
CV_EXPORTS_W void namedWindow(const String& winname, int flags = WINDOW_AUTOSIZE);

• 第二个参数flags，窗口标识
  • WINDOW_NORMAL，用户可以改变窗口大小
  • WINDOW_AUTOSIZE，窗口自动适应显示图像，无法手动改变
  • WINDOW_OPENGL, 支持openGL
  • WINDOW_FULLSCREEN， 全屏

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

//! Flags for cv::namedWindow
enum WindowFlags {
       WINDOW_NORMAL     = 0x00000000, //!< the user can resize the window (no constraint) / also use to switch a fullscreen window to a normal size.
       WINDOW_AUTOSIZE   = 0x00000001, //!< the user cannot resize the window, the size is constrainted by the image displayed.
       WINDOW_OPENGL     = 0x00001000, //!< window with opengl support.

       WINDOW_FULLSCREEN = 1,          //!< change the window to fullscreen.
       WINDOW_FREERATIO  = 0x00000100, //!< the image expends as much as it can (no ratio constraint).
       WINDOW_KEEPRATIO  = 0x00000000, //!< the ratio of the image is respected.
       WINDOW_GUI_EXPANDED=0x00000000, //!< status bar and tool bar
       WINDOW_GUI_NORMAL = 0x00000010, //!< old fashious way
    };

输出图像到文件：imwrite()

函数会写入到指定文件，图像格式基于拓展名。只有8位单通道或者3通道BGR图像可以使用这个函数写入，

• 16位无符号图像可以保存PNG, JPEG 2000, and TIFF 格式

• 32位浮点可以保存TIFF, OpenEXR, and Radiance HDR格式；3通道TIFF图像可以使用LogLuv高动态范围编码（每像素4字节）保存

• 可以保存带有alpha通道的PNG图像。8或16位的4通道BGRA图像（最后一个通道是alpha通道）。把alpha设置为0就是透明像素，完全不透明像素应将alpha设置为255/65535

• 如果格式、通道、深度不同，用Mat::convertTo 和 cv::cvtColor转换或者使用通用文件存储I/O

  函数将图像保存为XML或YAML格式

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

/** @brief Saves an image to a specified file.

The function imwrite saves the image to the specified file. The image format is chosen based on the
filename extension (see cv::imread for the list of extensions). In general, only 8-bit
single-channel or 3-channel (with 'BGR' channel order) images
can be saved using this function, with these exceptions:

- 16-bit unsigned (CV_16U) images can be saved in the case of PNG, JPEG 2000, and TIFF formats
- 32-bit float (CV_32F) images can be saved in TIFF, OpenEXR, and Radiance HDR formats; 3-channel
(CV_32FC3) TIFF images will be saved using the LogLuv high dynamic range encoding (4 bytes per pixel)
- PNG images with an alpha channel can be saved using this function. To do this, create
8-bit (or 16-bit) 4-channel image BGRA, where the alpha channel goes last. Fully transparent pixels
should have alpha set to 0, fully opaque pixels should have alpha set to 255/65535 (see the code sample below).

If the format, depth or channel order is different, use
Mat::convertTo and cv::cvtColor to convert it before saving. Or, use the universal FileStorage I/O
functions to save the image to XML or YAML format.

The sample below shows how to create a BGRA image and save it to a PNG file. It also demonstrates how to set custom
compression parameters:
@include snippets/imgcodecs_imwrite.cpp
@param filename Name of the file.
@param img Image to be saved.
@param params Format-specific parameters encoded as pairs (paramId_1, paramValue_1, paramId_2, paramValue_2, ... .) see cv::ImwriteFlags
*/
CV_EXPORTS_W bool imwrite( const String& filename, InputArray img,
              const std::vector<int>& params = std::vector<int>());

• 第一个参数filename，文件名需要带拓展名
• 第二个参数输入一个矩阵Mat
• 第三个参数是为特定格式保存的参数编码。有默认值，一般不需要填。
  • JPEG格式图片，这个参数0-100(CV_IMWRITE_JPEG_QUALITY),默认95
  • PNG格式，压缩级别0-9（CV_IMWRITE_PNG_COMPRESSION），数值越大表明更小尺寸更长压缩时间，默认3
  • PPM，PGM或PBM，表示二进制格式标示（CV_IMWRITE_PXM_BINARY），参数0-1，默认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

enum
{
    CV_IMWRITE_JPEG_QUALITY =1,
    CV_IMWRITE_JPEG_PROGRESSIVE =2,
    CV_IMWRITE_JPEG_OPTIMIZE =3,
    CV_IMWRITE_JPEG_RST_INTERVAL =4,
    CV_IMWRITE_JPEG_LUMA_QUALITY =5,
    CV_IMWRITE_JPEG_CHROMA_QUALITY =6,
    CV_IMWRITE_PNG_COMPRESSION =16,
    CV_IMWRITE_PNG_STRATEGY =17,
    CV_IMWRITE_PNG_BILEVEL =18,
    CV_IMWRITE_PNG_STRATEGY_DEFAULT =0,
    CV_IMWRITE_PNG_STRATEGY_FILTERED =1,
    CV_IMWRITE_PNG_STRATEGY_HUFFMAN_ONLY =2,
    CV_IMWRITE_PNG_STRATEGY_RLE =3,
    CV_IMWRITE_PNG_STRATEGY_FIXED =4,
    CV_IMWRITE_PXM_BINARY =32,
    CV_IMWRITE_EXR_TYPE = 48,
    CV_IMWRITE_WEBP_QUALITY =64,
    CV_IMWRITE_PAM_TUPLETYPE = 128,
    CV_IMWRITE_PAM_FORMAT_NULL = 0,
    CV_IMWRITE_PAM_FORMAT_BLACKANDWHITE = 1,
    CV_IMWRITE_PAM_FORMAT_GRAYSCALE = 2,
    CV_IMWRITE_PAM_FORMAT_GRAYSCALE_ALPHA = 3,
    CV_IMWRITE_PAM_FORMAT_RGB = 4,
    CV_IMWRITE_PAM_FORMAT_RGB_ALPHA = 5,
};

滑动条创建和使用

• 创建滑动条，这个函数通过指定名字和范围来创建一个滑动条。

  • 第一个参数trackbarname，滑动条名字
  • 第二个参数winname，滑动条要依附的窗口名
  • 第三个参数value，指针，表示滑块的位置
  • 第四个参数count，表示滑块可以到达的最大位置
  • 第五个参数onChange，指向回调函数的指针，每次滑块改变位置都会回调该函数
    • 第一个参数是滑块条的位置
    • 第二个参数是用户数据

  1 2 3 4 5

  /** @brief Callback function for Trackbar see cv::createTrackbar @param pos current position of the specified trackbar. @param userdata The optional parameter. */ typedef void (*TrackbarCallback)(int pos, void* userdata);

  • 用户数据指针将会被传递到滑块回调函数

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

/** @brief Creates a trackbar and attaches it to the specified window.

The function createTrackbar creates a trackbar (a slider or range control) with the specified name
and range, assigns a variable value to be a position synchronized with the trackbar and specifies
the callback function onChange to be called on the trackbar position change. The created trackbar is
displayed in the specified window winname.

@note

[__Qt Backend Only__] winname can be empty (or NULL) if the trackbar should be attached to the
control panel.

Clicking the label of each trackbar enables editing the trackbar values manually.

@param trackbarname Name of the created trackbar.
@param winname Name of the window that will be used as a parent of the created trackbar.
@param value Optional pointer to an integer variable whose value reflects the position of the
slider. Upon creation, the slider position is defined by this variable.
@param count Maximal position of the slider. The minimal position is always 0.
@param onChange Pointer to the function to be called every time the slider changes position. This
function should be prototyped as void Foo(int,void\*); , where the first parameter is the trackbar
position and the second parameter is the user data (see the next parameter). If the callback is
the NULL pointer, no callbacks are called, but only value is updated.
@param userdata User data that is passed as is to the callback. It can be used to handle trackbar
events without using global variables.
 */
CV_EXPORTS int createTrackbar(const String& trackbarname, const String& winname,
                              int* value, int count,
                              TrackbarCallback onChange = 0,
                              void* userdata = 0);

• 获取当前滑动条位置.
  • 第一个参数指定要获取的滑动条名
  • 第二个参数指定滑块归属的窗口名

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

/** @brief Returns the trackbar position.

The function returns the current position of the specified trackbar.

@note

[__Qt Backend Only__] winname can be empty (or NULL) if the trackbar is attached to the control
panel.

@param trackbarname Name of the trackbar.
@param winname Name of the window that is the parent of the trackbar.
 */
CV_EXPORTS_W int getTrackbarPos(const String& trackbarname, const String& winname);

• 鼠标操作。

  1 2 3 4 5 6 7

  /** @brief Sets mouse handler for the specified window @param winname Name of the window. @param onMouse Callback function for mouse events. See OpenCV samples on how to specify and use the callback. @param userdata The optional parameter passed to the callback. */ CV_EXPORTS void setMouseCallback(const String& winname, MouseCallback onMouse, void* userdata = 0);

  • 第一个参数，窗口名

  • 第二个参数onMouse,鼠标事件回调函数

    • 事件

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

    //! Mouse Events see cv::MouseCallback enum MouseEventTypes { EVENT_MOUSEMOVE = 0, //!< indicates that the mouse pointer has moved over the window. EVENT_LBUTTONDOWN = 1, //!< indicates that the left mouse button is pressed. EVENT_RBUTTONDOWN = 2, //!< indicates that the right mouse button is pressed. EVENT_MBUTTONDOWN = 3, //!< indicates that the middle mouse button is pressed. EVENT_LBUTTONUP = 4, //!< indicates that left mouse button is released. EVENT_RBUTTONUP = 5, //!< indicates that right mouse button is released. EVENT_MBUTTONUP = 6, //!< indicates that middle mouse button is released. EVENT_LBUTTONDBLCLK = 7, //!< indicates that left mouse button is double clicked. EVENT_RBUTTONDBLCLK = 8, //!< indicates that right mouse button is double clicked. EVENT_MBUTTONDBLCLK = 9, //!< indicates that middle mouse button is double clicked. EVENT_MOUSEWHEEL = 10,//!< positive and negative values mean forward and backward scrolling, respectively. EVENT_MOUSEHWHEEL = 11 //!< positive and negative values mean right and left scrolling, respectively. };

    1 2 3 4 5 6 7 8 9

    //! Mouse Event Flags see cv::MouseCallback enum MouseEventFlags { EVENT_FLAG_LBUTTON = 1, //!< indicates that the left mouse button is down. EVENT_FLAG_RBUTTON = 2, //!< indicates that the right mouse button is down. EVENT_FLAG_MBUTTON = 4, //!< indicates that the middle mouse button is down. EVENT_FLAG_CTRLKEY = 8, //!< indicates that CTRL Key is pressed. EVENT_FLAG_SHIFTKEY = 16,//!< indicates that SHIFT Key is pressed. EVENT_FLAG_ALTKEY = 32 //!< indicates that ALT Key is pressed. };

  1 2 3 4 5 6 7 8 9

  /** @brief Callback function for mouse events. see cv::setMouseCallback @param event one of the cv::MouseEventTypes constants. @param x The x-coordinate of the mouse event. @param y The y-coordinate of the mouse event. @param flags one of the cv::MouseEventFlags constants. @param userdata The optional parameter. */ typedef void (*MouseCallback)(int event, int x, int y, int flags, void* userdata);

  • 第三个参数是传递给回调的用户数据指针

Mac环境，安装OpenCV，VScode调试C++程序

环境说明

• macOS版本 catalina 10.15版本
• opencv3
• vscode

步骤

1. 安装XCode工具Command Line **sudo** xcode-select --install

2. 安装homebrew，可以用Homebrew安装很多东西

   1	/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

   brew下载后发生很慢的情况，是因为某种不可描述的原因。这时候需要国内镜像

   1 2 3 4 5 6 7

   git -C "$(brew --repo)" remote set-url origin https://mirrors.tuna.tsinghua.edu.cn/git/homebrew/brew.git git -C "$(brew --repo homebrew/core)" remote set-url origin https://mirrors.tuna.tsinghua.edu.cn/git/homebrew/homebrew-core.git git -C "$(brew --repo homebrew/cask)" remote set-url origin https://mirrors.tuna.tsinghua.edu.cn/git/homebrew/homebrew-cask.git brew update

3. 安装cmake，如果你用的homebrew方式安裝opencv那麼CMake就不是必須的.

   到https://cmake.org/download/下下载cmake安装包安装

   

   或者使用brew install cmake

4. 安装opencv,使用brew安装brew install opencv@3

   如果遇到Cloning into '/Users/wangwenwei/Library/Caches/Homebrew/aom--git'... fatal: unable to access 'https://aomedia.googlesource.com/aom.git/': Failed to connect to aomedia.googlesource.com port 443: Operation timed out肯定又是因为某种不可描述的问题，无法安装aom

   解决方法如下：

   1 2 3 4 5 6 7 8

   $ wget https://raw.githubusercontent.com/Homebrew/homebrew-core/master/Formula/aom.rb # 用本站提供的一份代码拷贝来替代原来的地址 $ sed -i "" "s/https:\/\/aomedia\.googlesource\.com\/aom\.git/https:\/\/www.mobibrw.com\/wp-content\/uploads\/2019\/04\/aom.zip/g" aom.rb $ brew uninstall --ignore-dependencies aom $ brew install --build-from-source aom.rb --env=std

   (如果某种不可描述的原因连wget都不行，则直接访问https://raw.githubusercontent.com/Homebrew/homebrew-core/master/Formula/aom.rb把内容拷贝到aom.rb)

5. 写个demo测试gcc可用性

   新建编辑main.cpp

   1 2 3 4 5 6 7 8

   /// ./main.cpp #include <stdio.h> #include <iostream> int main(int argc, const char * argv[]) { std::cout << "absurd!\n"; return 0; }

   命令：

   1 2 3 4

   absurd$ g++ -g ./main.cpp -o ./main.o absurd$ ./main.o absurd! absurd$

6. 配置pkg-config

   由 brew list opencv可以看到现在opencv的路径，拷贝相关配置

   1	cp /usr/local/Cellar/opencv/4.1.2/lib/pkgconfig/opencv4.pc /usr/local/lib/pkgconfig/opencv.pc

   配置bash环境（永久的走/etc/profile）

   1 2 3

   absurd$ echo PKG_CONFIG_PATH=$PKG_CONFIG_PATH:/usr/local/lib/pkgconfig >> ~/.bash_profile absurd$ echo export PKG_CONFIG_PATH >> ~/.bash_profile absurd$ source ~/.bash_profile

   配置完后执行

   pkg-config opencv --libs --cflags opencv

7. 测试opencv的DEMO

   

   新建test.cpp

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

   #include <opencv2/opencv.hpp> //头文件 using namespace cv; //包含cv命名空间 int main() { // 【1】读入一张图片 Mat img=imread("1.jpg"); // 【2】在窗口中显示载入的图片 imshow("【载入的图片】",img); // 【3】等待6000 ms后窗口自动关闭 waitKey(6000); }

   编译g++ pkg-config opencv –libs –cflags opencv ./test.cpp -o ./test.o,

   执行./test.o

   可以看到弹出图片

8. 下载安装vscode，https://code.visualstudio.com/

   安装插件C/C++、C++ Intellisense、C++ Clang Command Adapter、Chinese (Simplified) Language Pack for Visual Studio Code（中文语言包，看个人喜好）

   

9. 配置vscode

   

   • “command+shift+p”打开命令行工具窗口，输入或者选择“Edit Configurations”命令。

     此时会在当前工作空间目录生成.vscode配置目录，同时在配置目录会生成一个c_cpp_properties.json文件。

     includePath使用的opencv通过 ~ brew list opencv@3获取到include

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

     { "configurations": [ { "name": "Mac", "includePath": [ "/usr/local/include", "/Library/Developer/CommandLineTools/SDKs/MacOSX10.15.sdk/usr/bin", "/usr/local/Cellar/opencv@3/3.4.5_6/include/", "${workspaceFolder}/**" ], "defines": [], "macFrameworkPath": [ "/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/System/Library/Frameworks" ], "compilerPath": "/usr/bin/clang", "cStandard": "c11", "cppStandard": "c++17", "intelliSenseMode": "clang-x64" } ], "version": 4 }

   • “command+shift+p”打开命令行工具窗口，输入或者选择“Tasks: Configure Task”

     配置 tasks.json文件

     

     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

     { // 有关 tasks.json 格式的文档，请参见 // https://go.microsoft.com/fwlink/?LinkId=733558 "version": "2.0.0", "tasks": [ { "type": "shell", "label": "g++ build active file", "command": "/usr/bin/g++", "args": [ "-g", "${file}", "-o", "${fileDirname}/${fileBasenameNoExtension}.out", "`pkg-config", "--libs", "--cflags", "opencv`" ], "options": { "cwd": "/usr/bin" }, "problemMatcher": [ "$gcc" ], "group": "build" } ] }

   • 配置launch.json。“command+shift+p”打开命令行工具窗口，输入或者选择Debug: Open launch.json命令。

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

     { // 使用 IntelliSense 了解相关属性。 // 悬停以查看现有属性的描述。 // 欲了解更多信息，请访问: https://go.microsoft.com/fwlink/?linkid=830387 "version": "0.2.0", "configurations": [ { "name": "g++ build active file", "type": "cppdbg", "request": "launch", "program": "${workspaceFolder}/${fileBasenameNoExtension}.out", "args": [], "stopAtEntry": false, "cwd": "${workspaceFolder}", "environment": [ {"name": "PKG_CONFIG_PATH", "value": "/usr/local/lib/pkgconfig"}, // 這是opencv解壓碼後創建的release目錄下的unix-install, 要保證該目錄下下有opencv.pc文件 {"name": "DYLD_LIBRARY_PATH", "value": "/usr/local/opencv/build/lib"} // 這個是你在編譯時，opencv make時`CMAKE_INSTALL_PREFIX`指定的目錄 ], "externalConsole": true, "MIMode": "lldb", "preLaunchTask":"g++ build active file" } ] }

10. 开始调试

调试如果出现图片就是成功了

如果类似上图显示波浪形，就是c_cpp_properties.json的includePath没有引用到正确的库，配置下就好了

B-Tree 索引（B+Tree）

当你需要查找两个值之间的多个元素时，成本是 O(N)，因为你必须查找树的每一个节点，以判断它是否处于那 2 个值之间（例如，对树使用中序遍历）。而且这个操作不是磁盘I/O有利的，因为你必须读取整个树。我们需要找到高效的范围查询方法。为了解决这个问题，现代数据库使用了B+树。在一个B+树里：

• 只有最底层的节点（叶子节点）才保存信息（相关表的行位置）
• 其它节点只是在搜索中用来指引到正确节点的。

你可以看到，节点更多了（多了两倍）。确实，你有了额外的节点，它们就是帮助你找到正确节点的『决策节点』（正确节点保存着相关表中行的位置）。但是搜索复杂度还是在 O(log(N))（只多了一层）。一个重要的不同点是，最底层的节点是跟后续节点相连接的。

用这个 B+树，假设你要找40到100间的值：

• 你只需要找 40（若40不存在则找40之后最贴近的值），就像你在上一个树中所做的那样。
• 然后用那些连接来收集40的后续节点，直到找到100。

比方说你找到了 M 个后续节点，树总共有 N 个节点。对指定节点的搜索成本是 log(N)，跟上一个树相同。但是当你找到这个节点，你得通过后续节点的连接得到 M 个后续节点，这需要 M 次运算。那么这次搜索只消耗了 M+log(N) 次运算，区别于上一个树所用的 N 次运算。此外，你不需要读取整个树（仅需要读 M+log(N) 个节点）,这意味着更少的磁盘访问。如果 M 很小（比如 200 行）并且 N 很大（1,000,000），那结果就是天壤之别了。

如果你在数据库中增加或删除一行（从而在相关的 B+树索引里）：

• 你必须在B+树中的节点之间保持顺序，否则节点会变得一团糟，你无法从中找到想要的节点。
• 你必须尽可能降低B+树的层数，否则 O(log(N)) 复杂度会变成 O(N)。

换句话说，B+树需要自我整理和自我平衡。谢天谢地，我们有智能删除和插入。但是这样也带来了成本：在B+树中，插入和删除操作是 O(log(N)) 复杂度。所以有些人听到过使用太多索引不是个好主意这类说法。没错，你减慢了快速插入/更新/删除表中的一个行的操作，因为数据库需要以代价高昂的每索引 O(log(N)) 运算来更新表的索引。再者，增加索引意味着给事务管理器带来更多的工作负荷。

MyISAM索引实现：

MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。

1）主键索引：

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图：

这里设表一共有三列，假设我们以Col1为主键，图myisam1是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。

2）辅助索引（Secondary key）

在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同.

1）主键索引：

InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

2）InnoDB的辅助索引

InnoDB的所有辅助索引都引用主键作为data域。

例如，下图为定义在Col3上的一个辅助索引：

InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一种非常快速的主键查找性能。不过，它的辅助索引（Secondary Index， 也就是非主键索引）也会包含主键列，所以，如果主键定义的比较大，其他索引也将很大。如果想在表上定义 、很多索引，则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。

  文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

  不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白

1、为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，

2、用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

InnoDB索引和MyISAM索引的区别：

一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。

二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

Hash 索引

基于哈希表实现，优点是查找非常快。

在 MySQL 中只有 Memory 引擎显式支持哈希索引。

InnoDB 引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B-Tree 索引之上再创建一个哈希索引，这样就让 B-Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

限制：哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能影响并不明显；无法用于分组与排序；只支持精确查找，无法用于部分查找和范围查找；如果哈希冲突很多，查找速度会变得很慢。

Fulltext 索引

全文索引是MyISAM的一个特殊索引类型，主要用于全文检索。

R-Tree 索引

MyISAM支持空间索引，主要用于地理空间数据类型，例如GEOMETRY。

聚集索引与非聚集索引区别？

聚集索引

索引的键值逻辑顺序决定了表数据行的物理存储顺序，也就是在数据库上连接的记录在磁盘上的物理存储地址也是相邻的。由于聚集索引规定了数据项，也可以说是记录在表中的物理存储顺序，物理顺序唯一，自然每张表中的聚集索引也是唯一的，但是它可以包含多个列，多个字段。

非聚集索引

非聚集索引也就是存储的键值逻辑连续，但是在表数据行物理存储顺序上不一定连续的索引，也就是索引的逻辑顺序与磁盘上的物理存储顺序不同。

Isolation.DEFAULT(TransactionDefinition.ISOLATION_DEFAULT)使用数据库默认的事务隔离级别。

Isolation.READ_UNCOMMITTED(TransactionDefinition.ISOLATION_READ_UNCOMMITTED),这是事务最低的隔离级别，它允许另外一个事务可以看到这个事务未提交的数据。这种隔离级别会产生脏读，不可重复读和幻像读。

实现：SET SESSION TRANSACTION ISOLATION LEVEL READ UNCOMMITTED

Isolation.READ_COMMITTED(TransactionDefinition.ISOLATION_READ_COMMITTED),保证一个事务修改的数据提交后才能被另外一个事务读取。另外一个事务不能读取该事务未提交的数据。这种事务隔离级别可以避免脏读出现，但是可能会出现不可重复读和幻像读。

实现：SET SESSION TRANSACTION ISOLATION LEVEL READ COMMITTED

Isolation.REPEATABLE_READ(TransactionDefinition.ISOLATION_REPEATABLE_READ),这种事务隔离级别可以防止脏读，不可重复读。但是可能出现幻像读。

实现：SET SESSION TRANSACTION ISOLATION LEVEL REPEATABLE READ

Isolation.SERIALIZABLE(TransactionDefinition.ISOLATION_SERIALIZABLE);这是花费最高代价但是最可靠的事务隔离级别。事务被处理为顺序执行。除了防止脏读，不可重复读外，还避免了幻读。

实现：SET SESSION TRANSACTION ISOLATION LEVEL SERIALIZABLE

√: 可能出现 ×: 不会出现

• 未提交读(Read Uncommitted)：允许脏读，也就是可能读取到其他会话中未提交事务修改的数据
• 提交读(Read Committed)：只能读取到已经提交的数据。Oracle等多数数据库默认都是该级别 (不重复读)
• 可重复读(Repeated Read)：可重复读。在同一个事务内的查询都是事务开始时刻一致的，InnoDB默认级别。在SQL标准中，该隔离级别消除了不可重复读，但是还存在幻象读
• 串行读(Serializable)：完全串行化的读，每次读都需要获得表级共享锁，读写相互都会阻塞

为什么RU级别会发生脏读，而其他的隔离级别能够避免？

RU级别的操作其实就是对事务内的每一条更新语句对应的行记录加上读写锁来操作，而不把一个事务当成一个整体来加锁，所以会导致脏读。但是RC和RR能够通过MVCC来保证记录只有在最后COMMIT后才会让别的事务看到。

Read Committed（读取提交内容）

在RC级别中，数据的读取都是不加锁的，但是数据的写入、修改和删除是需要加锁的。

由于MySQL的InnoDB默认是使用的RR级别，所以我们先要将该session开启成RC级别，并且设置binlog的模式

SET session transaction isolation level read committed;

SET SESSION binlog_format = ‘ROW’;（或者是MIXED）

Repeatable Read（可重读）

这是MySQL中InnoDB默认的隔离级别。我们姑且分“读”和“写”两个模块来讲解。

读

读就是可重读，可重读这个概念是一事务的多个实例在并发读取数据时，会看到同样的数据行，有点抽象，我们来看一下效果。

RC（不可重读）模式下的展现

事务B修改id=1的数据提交之后，事务A同样的查询，后一次和前一次的结果不一样，这就是不可重读（重新读取产生的结果不一样）。这就很可能带来一些问题，那么我们来看看在RR级别中MySQL的表现：

我们注意到，当teacher_id=1时，事务A先做了一次读取，事务B中间修改了id=1的数据，并commit之后，事务A第二次读到的数据和第一次完全相同。所以说它是可重读的。那么MySQL是怎么做到的呢？这里姑且卖个关子，我们往下看。

为什么RC级别不能重复读，而RR级别能够避免？

在RC事务隔离级别下,每次语句执行都关闭ReadView,然后重新创建一份ReadView。而在RR下,事务开始后第一个读操作创建ReadView,一直到事务结束关闭

不可重复读和幻读的区别

很多人容易搞混不可重复读和幻读，确实这两者有些相似。但不可重复读重点在于update和delete，而幻读的重点在于insert。

如果使用锁机制来实现这两种隔离级别，在可重复读中，该sql第一次读取到数据后，就将这些数据加锁，其它事务无法修改这些数据，就可以实现可重复读了。但这种方法却无法锁住insert的数据，所以当事务A先前读取了数据，或者修改了全部数据，事务B还是可以insert数据提交，这时事务A就会发现莫名其妙多了一条之前没有的数据，这就是幻读，不能通过行锁来避免。需要Serializable隔离级别 ，读用读锁，写用写锁，读锁和写锁互斥，这么做可以有效的避免幻读、不可重复读、脏读等问题，但会极大的降低数据库的并发能力。

所以说不可重复读和幻读最大的区别，就在于如何通过锁机制来解决他们产生的问题。

上文说的，是使用悲观锁机制来处理这两种问题，但是MySQL、ORACLE、PostgreSQL等成熟的数据库，出于性能考虑，都是使用了以乐观锁为理论基础的MVCC（多版本并发控制）来避免这两种问题。

• 快照读：就是select

• • select * from table ….;

• 当前读：特殊的读操作，插入/更新/删除操作，属于当前读，处理的都是当前的数据，需要加锁。

• • select * from table where ? lock in share mode;
  • select * from table where ? for update;
  • insert;
  • update ;
  • delete;

GAP间隙锁

RC级别：

RR级别：

通过对比我们可以发现，在RC级别中，事务A修改了所有teacher_id=30的数据，但是当事务Binsert进新数据后，事务A发现莫名其妙多了一行teacher_id=30的数据，而且没有被之前的update语句所修改，这就是“当前读”的幻读。

RR级别中，事务A在update后加锁，事务B无法插入新数据，这样事务A在update前后读的数据保持一致，避免了幻读。这个锁，就是Gap锁。

MySQL是这么实现的：

在class_teacher这张表中，teacher_id是个索引，那么它就会维护一套B+树的数据关系，为了简化，我们用链表结构来表达（实际上是个树形结构，但原理相同）

如图所示，InnoDB使用的是聚集索引，teacher_id身为二级索引，就要维护一个索引字段和主键id的树状结构（这里用链表形式表现），并保持顺序排列。

Innodb将这段数据分成几个个区间

• (negative infinity, 5],
• (5,30],
• (30,positive infinity)；

update class_teacher set class_name=’初三四班’ where teacher_id=30;不仅用行锁，锁住了相应的数据行；同时也在两边的区间，（5,30]和（30，positive infinity），都加入了gap锁。这样事务B就无法在这个两个区间insert进新数据。

受限于这种实现方式，Innodb很多时候会锁住不需要锁的区间。如下所示：

update的teacher_id=20是在(5，30]区间，即使没有修改任何数据，Innodb也会在这个区间加gap锁，而其它区间不会影响，事务C正常插入。

如果使用的是没有索引的字段，比如update class_teacher set teacher_id=7 where class_name=’初三八班（即使没有匹配到任何数据）’,那么会给全表加入gap锁。同时，它不能像上文中行锁一样经过MySQL Server过滤自动解除不满足条件的锁，因为没有索引，则这些字段也就没有排序，也就没有区间。除非该事务提交，否则其它事务无法插入任何数据。

行锁防止别的事务修改或删除，GAP锁防止别的事务新增，行锁和GAP锁结合形成的的Next-Key锁共同解决了RR级别在写数据时的幻读问题。

Read uncommitted 读未提交

公司发工资了，领导把5000元打到singo的账号上，但是该事务并未提交，而singo正好去查看账户，发现工资已经到账，是5000元整，非常高兴。可是不幸的是，领导发现发给singo的工资金额不对，是2000元，于是迅速回滚了事务，修改金额后，将事务提交，最后singo实际的工资只有2000元，singo空欢喜一场。

出现上述情况，即我们所说的脏读，两个并发的事务，“事务A：领导给singo发工资”、“事务B：singo查询工资账户”，事务B读取了事务A尚未提交的数据。

当隔离级别设置为Read uncommitted时，就可能出现脏读，如何避免脏读，请看下一个隔离级别。

Read committed 读提交

singo拿着工资卡去消费，系统读取到卡里确实有2000元，而此时她的老婆也正好在网上转账，把singo工资卡的2000元转到另一账户，并在singo之前提交了事务，当singo扣款时，系统检查到singo的工资卡已经没有钱，扣款失败，singo十分纳闷，明明卡里有钱，为何……

出现上述情况，即我们所说的不可重复读，两个并发的事务，“事务A：singo消费”、“事务B：singo的老婆网上转账”，事务A事先读取了数据，事务B紧接了更新了数据，并提交了事务，而事务A再次读取该数据时，数据已经发生了改变。

当隔离级别设置为Read committed时，避免了脏读，但是可能会造成不可重复读。

大多数数据库的默认级别就是Read committed，比如Sql Server , Oracle。如何解决不可重复读这一问题，请看下一个隔离级别。

Repeatable read 重复读

当隔离级别设置为Repeatable read时，可以避免不可重复读。当singo拿着工资卡去消费时，一旦系统开始读取工资卡信息（即事务开始），singo的老婆就不可能对该记录进行修改，也就是singo的老婆不能在此时转账。

虽然Repeatable read避免了不可重复读，但还有可能出现幻读。

singo的老婆工作在银行部门，她时常通过银行内部系统查看singo的信用卡消费记录。有一天，她正在查询到singo当月信用卡的总消费金额（select sum(amount) from transaction where month = 本月）为80元，而singo此时正好在外面胡吃海塞后在收银台买单，消费1000元，即新增了一条1000元的消费记录（insert transaction … ），并提交了事务，随后singo的老婆将singo当月信用卡消费的明细打印到A4纸上，却发现消费总额为1080元，singo的老婆很诧异，以为出现了幻觉，幻读就这样产生了。

注：Mysql的默认隔离级别就是Repeatable read。

Serializable 序列化

Serializable是最高的事务隔离级别，同时代价也花费最高，性能很低，一般很少使用，在该级别下，事务顺序执行，不仅可以避免脏读、不可重复读，还避免了幻像读。

MySql ACID如何保证？

ACID，指数据库事务正确执行的四个基本要素的缩写。包含：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）

为什么InnoDB能够保证原子性？

在事务里任何对数据的修改都会写一个Undo log，然后进行数据的修改，如果出现错误或者用户需要回滚的时候可以利用Undo log的备份数据恢复到事务开始之前的状态。

为什么InnoDB能够保证持久性？

在一个事务中的每一次SQL操作之后都会写入一个redo log到buffer中，在最后COMMIT的时候，必须先将该事务的所有日志写入到redo log file进行持久化（这里的写入是顺序写的），待事务的COMMIT操作完成才算完成。即使COMMIT后数据库有任何的问题，在下次重启后依然能够通过redo log的checkpoint进行恢复。

为什么InnoDB能够保证一致性？

在事务处理的ACID属性中，一致性是最基本的属性，其它的三个属性都为了保证一致性而存在的。

首先回顾一下一致性的定义。所谓一致性，指的是数据处于一种有意义的状态，这种状态是语义上的而不是语法上的。最常见的例子是转帐。例如从帐户A转一笔钱到帐户B上，如果帐户A上的钱减少了，而帐户B上的钱却没有增加，那么我们认为此时数据处于不一致的状态。

在数据库实现的场景中，一致性可以分为数据库外部的一致性和数据库内部的一致性。前者由外部应用的编码来保证，即某个应用在执行转帐的数据库操作时，必须在同一个事务内部调用对帐户A和帐户B的操作。如果在这个层次出现错误，这不是数据库本身能够解决的，也不属于我们需要讨论的范围。后者由数据库来保证，即在同一个事务内部的一组操作必须全部执行成功（或者全部失败）。这就是事务处理的原子性。（上面说过了是用Undo log来保证的）

但是，原子性并不能完全保证一致性。在多个事务并行进行的情况下，即使保证了每一个事务的原子性，仍然可能导致数据不一致的结果，比如丢失更新问题。

为了保证并发情况下的一致性，引入了隔离性，即保证每一个事务能够看到的数据总是一致的，就好象其它并发事务并不存在一样。用术语来说，就是多个事务并发执行后的状态，和它们串行执行后的状态是等价的。

一个安稳的周末，突然线上传来报警，保留现场过后紧急重启下，然后开始分析。让运维把oom 的dump数据和jstack数据传来

dump文件太大，传过来之前先分析下jstack日志。

jstack发现了一丝异样

“http-nio-8080-exec-197” #7490 daemon prio=5 os_prio=0 tid=0x00007fdd5806b000 nid=0xed1 waiting for monitor entry [0x00007fdd1b7d5000]
java.lang.Thread.State: BLOCKED (on object monitor)
at org.apache.catalina.webresources.CachedResource.validateResources(CachedResource.java:125)
- waiting to lock <0x000000008015c660> (a org.apache.catalina.webresources.CachedResource)
at org.apache.catalina.webresources.Cache.getResources(Cache.java:129)
at org.apache.catalina.webresources.StandardRoot.getResources(StandardRoot.java:315)
at org.apache.catalina.webresources.StandardRoot.getClassLoaderResources(StandardRoot.java:231)
at org.apache.catalina.loader.WebappClassLoaderBase.findResources(WebappClassLoaderBase.java:995)
at java.lang.ClassLoader.getResources(ClassLoader.java:1142)
at com.alibaba.fastjson.util.ServiceLoader.load(ServiceLoader.java:33)
at com.alibaba.fastjson.parser.ParserConfig.getDeserializer(ParserConfig.java:459)
at com.alibaba.fastjson.parser.ParserConfig.getDeserializer(ParserConfig.java:354)
at com.alibaba.fastjson.parser.DefaultJSONParser.parseObject(DefaultJSONParser.java:639)
at com.alibaba.fastjson.JSON.parseObject(JSON.java:350)
at com.alibaba.fastjson.JSON.parseObject(JSON.java:318)
at com.alibaba.fastjson.JSON.parseObject(JSON.java:281)

看到这个线程是阻塞状态，也就是tomcat请求http-nio-8080-exec-197现在是阻塞状态，等待<0x000000008015c660>释放。而且waiting to lock <0x000000008015c660>出现了11次，也就是有11个线程正在等待释放

关于线程状态：

新建（New）

创建后尚未启动。

可运行（Runnable）

可能正在运行，也可能正在等待 CPU 时间片。

包含了操作系统线程状态中的 Running 和 Ready。

阻塞（Blocking）

等待获取一个排它锁，如果其线程释放了锁就会结束此状态。

无限期等待（Waiting）

等待其它线程显式地唤醒，否则不会被分配 CPU 时间片。

限期等待（Timed Waiting）

无需等待其它线程显式地唤醒，在一定时间之后会被系统自动唤醒。

调用 Thread.sleep() 方法使线程进入限期等待状态时，常常用“使一个线程睡眠”进行描述。

调用 Object.wait() 方法使线程进入限期等待或者无限期等待时，常常用“挂起一个线程”进行描述。

睡眠和挂起是用来描述行为，而阻塞和等待用来描述状态。

阻塞和等待的区别在于，阻塞是被动的，它是在等待获取一个排它锁。而等待是主动的，通过调用 Thread.sleep() 和 Object.wait() 等方法进入。

死亡（Terminated）

可以是线程结束任务之后自己结束，或者产生了异常而结束。

往下一看

at org.apache.catalina.core.ApplicationFilterChain.doFilter(ApplicationFilterChain.java:207)
at org.apache.catalina.core.StandardWrapperValve.invoke(StandardWrapperValve.java:212)
at org.apache.catalina.core.StandardContextValve.invoke(StandardContextValve.java:94)
at org.apache.catalina.authenticator.AuthenticatorBase.invoke(AuthenticatorBase.java:496)
at org.apache.catalina.core.StandardHostValve.invoke(StandardHostValve.java:141)
at org.apache.catalina.valves.ErrorReportValve.invoke(ErrorReportValve.java:79)
at org.apache.catalina.core.StandardEngineValve.invoke(StandardEngineValve.java:88)
at org.apache.catalina.connector.CoyoteAdapter.service(CoyoteAdapter.java:502)
at org.apache.coyote.http11.AbstractHttp11Processor.process(AbstractHttp11Processor.java:1132)
at org.apache.coyote.AbstractProtocol$AbstractConnectionHandler.process(AbstractProtocol.java:684)
at org.apache.tomcat.util.net.NioEndpoint$SocketProcessor.doRun(NioEndpoint.java:1539)
at org.apache.tomcat.util.net.NioEndpoint$SocketProcessor.run(NioEndpoint.java:1495)

• locked <0x0000000094c40718> (a org.apache.tomcat.util.net.NioChannel)
  at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
  at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
  at org.apache.tomcat.util.threads.TaskThread$WrappingRunnable.run(TaskThread.java:61)
  at java.lang.Thread.run(Thread.java:745)

通过查找<0x000000008015c660> 发现有个线程badge-thread-18锁住了它 ，

“badge-thread-18” #438 prio=5 os_prio=0 tid=0x00007fdd6403d800 nid=0x5b36 runnable [0x00007fdd282bb000]
java.lang.Thread.State: RUNNABLE
at java.util.zip.ZipFile.open(Native Method)
at java.util.zip.ZipFile.(ZipFile.java:219)
at java.util.zip.ZipFile.(ZipFile.java:149)
at java.util.jar.JarFile.(JarFile.java:166)
at java.util.jar.JarFile.(JarFile.java:130)
at org.apache.tomcat.util.compat.JreCompat.jarFileNewInstance(JreCompat.java:170)
at org.apache.tomcat.util.compat.JreCompat.jarFileNewInstance(JreCompat.java:155)
at org.apache.catalina.webresources.AbstractArchiveResourceSet.openJarFile(AbstractArchiveResourceSet.java:316)
- locked <0x00000000903a4828> (a java.lang.Object)
at org.apache.catalina.webresources.AbstractSingleArchiveResourceSet.getArchiveEntry(AbstractSingleArchiveResourceSet.java:96)
at org.apache.catalina.webresources.AbstractArchiveResourceSet.getResource(AbstractArchiveResourceSet.java:265)
at org.apache.catalina.webresources.StandardRoot.getResourcesInternal(StandardRoot.java:327)
at org.apache.catalina.webresources.CachedResource.validateResources(CachedResource.java:127)
- locked <0x000000008015c660> (a org.apache.catalina.webresources.CachedResource)
at org.apache.catalina.webresources.Cache.getResources(Cache.java:147)
at org.apache.catalina.webresources.StandardRoot.getResources(StandardRoot.java:315)
at org.apache.catalina.webresources.StandardRoot.getClassLoaderResources(StandardRoot.java:231)
at org.apache.catalina.loader.WebappClassLoaderBase.findResources(WebappClassLoaderBase.java:995)
at java.lang.ClassLoader.getResources(ClassLoader.java:1142)
at com.alibaba.fastjson.util.ServiceLoader.load(ServiceLoader.java:33)
at com.alibaba.fastjson.parser.ParserConfig.getDeserializer(ParserConfig.java:459)
at com.alibaba.fastjson.parser.ParserConfig.getDeserializer(ParserConfig.java:354)
at com.alibaba.fastjson.parser.DefaultJSONParser.parseObject(DefaultJSONParser.java:639)
at com.alibaba.fastjson.JSON.parseObject(JSON.java:350)
at com.alibaba.fastjson.JSON.parseObject(JSON.java:318)
at com.alibaba.fastjson.JSON.parseObject(JSON.java:281)

通过上面的堆栈，我们先猜测下跟ParserConfig的getDeserializer方法可能有若干关系，先看下代码：

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

public ObjectDeserializer getDeserializer(Class<?> clazz, Type type) {
    ObjectDeserializer derializer = deserializers.get(type);
    if (derializer != null) {
        return derializer;
    }

    if (type == null) {
        type = clazz;
    }

    derializer = deserializers.get(type);
    if (derializer != null) {
        return derializer;
    }

    {
        JSONType annotation = clazz.getAnnotation(JSONType.class);
        if (annotation != null) {
            Class<?> mappingTo = annotation.mappingTo();
            if (mappingTo != Void.class) {
                return getDeserializer(mappingTo, mappingTo);
            }
        }
    }

    if (type instanceof WildcardType || type instanceof TypeVariable || type instanceof ParameterizedType) {
        derializer = deserializers.get(clazz);
    }

    if (derializer != null) {
        return derializer;
    }

    String className = clazz.getName();
    className = className.replace('$', '.');

    if (className.startsWith("java.awt.") //
        && AwtCodec.support(clazz)) {
        if (!awtError) {
            try {
                deserializers.put(Class.forName("java.awt.Point"), AwtCodec.instance);
                deserializers.put(Class.forName("java.awt.Font"), AwtCodec.instance);
                deserializers.put(Class.forName("java.awt.Rectangle"), AwtCodec.instance);
                deserializers.put(Class.forName("java.awt.Color"), AwtCodec.instance);
            } catch (Throwable e) {
                // skip
                awtError = true;
            }

            derializer = AwtCodec.instance;
        }
    }

    if (!jdk8Error) {
        try {
            if (className.startsWith("java.time.")) {
                
                deserializers.put(Class.forName("java.time.LocalDateTime"), Jdk8DateCodec.instance);
                deserializers.put(Class.forName("java.time.LocalDate"), Jdk8DateCodec.instance);
                deserializers.put(Class.forName("java.time.LocalTime"), Jdk8DateCodec.instance);
                deserializers.put(Class.forName("java.time.ZonedDateTime"), Jdk8DateCodec.instance);
                deserializers.put(Class.forName("java.time.OffsetDateTime"), Jdk8DateCodec.instance);
                deserializers.put(Class.forName("java.time.OffsetTime"), Jdk8DateCodec.instance);
                deserializers.put(Class.forName("java.time.ZoneOffset"), Jdk8DateCodec.instance);
                deserializers.put(Class.forName("java.time.ZoneRegion"), Jdk8DateCodec.instance);
                deserializers.put(Class.forName("java.time.ZoneId"), Jdk8DateCodec.instance);
                deserializers.put(Class.forName("java.time.Period"), Jdk8DateCodec.instance);
                deserializers.put(Class.forName("java.time.Duration"), Jdk8DateCodec.instance);
                deserializers.put(Class.forName("java.time.Instant"), Jdk8DateCodec.instance);
                
                derializer = deserializers.get(clazz);
            } else if (className.startsWith("java.util.Optional")) {
                
                deserializers.put(Class.forName("java.util.Optional"), OptionalCodec.instance);
                deserializers.put(Class.forName("java.util.OptionalDouble"), OptionalCodec.instance);
                deserializers.put(Class.forName("java.util.OptionalInt"), OptionalCodec.instance);
                deserializers.put(Class.forName("java.util.OptionalLong"), OptionalCodec.instance);
                
                derializer = deserializers.get(clazz);
            }
        } catch (Throwable e) {
            // skip
            jdk8Error = true;
        }
    }

    if (className.equals("java.nio.file.Path")) {
        deserializers.put(clazz, MiscCodec.instance);
    }

    if (clazz == Map.Entry.class) {
        deserializers.put(clazz, MiscCodec.instance);
    }

    final ClassLoader classLoader = Thread.currentThread().getContextClassLoader();
    try {
        for (AutowiredObjectDeserializer autowired : ServiceLoader.load(AutowiredObjectDeserializer.class,classLoader)) {
            for (Type forType : autowired.getAutowiredFor()) {
                deserializers.put(forType, autowired);
            }
        }
    } catch (Exception ex) {
        // skip
    }

    if (derializer == null) {
        derializer = deserializers.get(type);
    }

    if (derializer != null) {
        return derializer;
    }

    if (clazz.isEnum()) {
        derializer = new EnumDeserializer(clazz);
    } else if (clazz.isArray()) {
        derializer = ObjectArrayCodec.instance;
    } else if (clazz == Set.class || clazz == HashSet.class || clazz == Collection.class || clazz == List.class
               || clazz == ArrayList.class) {
        derializer = CollectionCodec.instance;
    } else if (Collection.class.isAssignableFrom(clazz)) {
        derializer = CollectionCodec.instance;
    } else if (Map.class.isAssignableFrom(clazz)) {
        derializer = MapDeserializer.instance;
    } else if (Throwable.class.isAssignableFrom(clazz)) {
        derializer = new ThrowableDeserializer(this, clazz);
    } else {
        derializer = createJavaBeanDeserializer(clazz, type);
    }

    putDeserializer(type, derializer);

    return derializer;
}

deserializers又指的是：

1

private final IdentityHashMap<Type, ObjectDeserializer> deserializers         = new IdentityHashMap<Type, ObjectDeserializer>();

大致逻辑是先通过缓存的IdentityHashMap查找，找不到就判断是否注解@JSONType，从中解析。如果还是找不到如果类型是WildcardType、TypeVariable 、 ParameterizedType从中解析。还是不行就使用当前线程类加载器 查找 META-INF/services/AutowiredObjectDeserializer.class实现类。余下就不分析了，当大多数json解析走至此处就要想一下，为什么从缓存的IdentityHashMap查找不到该类型？

通过dump分析可以得到com.alibaba.fastjson.util.IdentityHashMap非常大，也验证了我的看法。

IdentityHashMap是通过System.identityHashCode获取的key，但是这个几乎是唯一的，就算是同一个类型并不是同一个引用都将会有问题

引发这段代码的业务代码大致如下：

1
2
3
4
5
6
7
8
9
10
11

@Test
public void leak(){
    Student student=new Student();
    student.setName("1");
    CacheWrapper cacheWrapper = new CacheWrapper();
    cacheWrapper.setCacheObject(student);
    byte[] bytes = JSON.toJSONBytes(cacheWrapper);
    while (true){
        Object o = JSON.parseObject(bytes, new ParameterizedTypeImpl(new Type[]{Student.class}, CacheWrapper.class.getDeclaringClass(), CacheWrapper.class));
    }
}

1
2
3
4

@Data
public class Student implements Serializable{
    private String name;
}

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

public class CacheWrapper<T> implements Serializable, Cloneable {
    private static final long serialVersionUID=1L;


    /**
     * 缓存数据
     */
    private T cacheObject;

    /**
     * 缓存时长
     */
    private int expire;

    public CacheWrapper() {
    }

    public CacheWrapper(T cacheObject, int expire) {
        this.cacheObject=cacheObject;
        this.expire=expire;
    }


    @Override
    public Object clone() throws CloneNotSupportedException {
        @SuppressWarnings("unchecked")
        CacheWrapper<T> tmp=(CacheWrapper<T>)super.clone();
        tmp.setCacheObject(this.cacheObject);
        return tmp;
    }

    public T getCacheObject() {
        return cacheObject;
    }

    public void setCacheObject(T cacheObject) {
        this.cacheObject = cacheObject;
    }

    public int getExpire() {
        return expire;
    }

    public void setExpire(int expire) {
        this.expire = expire;
    }
}