0%

目录

什么是内部类?

  1. 可以将一个类的定义放在另一个类的定义内部,就是内部类。
  2. 内部类允许你把一些逻辑相关的类组织在一起,并控制位于内部的类的可视性。
  3. 内部类天然具有访问外围对象所有成员的能力,包括private成员。

特性

  1. 允许我们把一些逻辑相关的类组织在一起,并控制位于内部的类的可视性。

  2. 内部类可以有效地实现“多重继承”,即是内部类允许继承多个非接口类型(类或抽象类)。

  3. 内部类天然拥有对其外围类所有成员的访问权 ——当某个外围类对象创建了一个内部类对象时,此内部类对象必定会秘密地捕获一个指向那个外围类对象的引用。

    [code]
    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
          interface Selector {
    boolean end();
    Object current();
    void next();
    }
    public class Sequence {
    private Object[] items;
    private int next = 0;
    public Sequence(int size) {
    items = new Object[size];
    }
    public void add(Object x) {
    if (next < items.length)
    items[next++] = x;
    }
    private class SequenceSelector implements Selector {
    private int i = 0;
    public boolean end() {
    return i == items.length; //访问外围类私有属性
    }
    public Object current() {
    return items[i];
    }
    public void next() {
    if (i < items.length)
    i++;
    }
    }
    public Selector selector() {
    return new SequenceSelector();
    }
    public static void main(String[] args){
    Sequence sequence = new Sequence(10);
    for(int i = 0; i < 10; i++) {
    sequence.add(Integer.toString(i));
    Selector selector = sequence.selector();
    while (!selector.end()) {
    System.out.println(selector.current() + " ");
    selector.next();
    }
    }
    }
    }
    /* output:
    0 1 2 3 4 5 6 7 8 9
    */
    ```

    </details>


    ### 创建内部类对象

    - 从外部内的非静态方法之外的任意位置创建某个内部类的对象,必须具体的指明这个对象的类型:
    (在拥有外部类对象之前是不可能创建内部类(非static)对象的,当然,如果要创建的是嵌套类(静态内部类),那么它就不需要对外部类对象的引用)

    <details>
    <summary><b>[code]</b></summary>

    ```java
    /**外部类**/
    class OuterClassName {
    /**内部类**/
    class InnerClassName {
    }
    static class StaticInnerClass {
    }
    public InnerClassName inner() {
    return new InnerClassName();
    }
    public static void main(String[] args){
    OuterClassName outer = new OuterClassName();
    //创建内部类对象
    OuterClassName.InnerClassName inner = outer.inner();
    //创建嵌套类对象
    OuterClassName.StaticInnerClass staticInner = new StaticInnerClass();
    }
    }
  • 使用.new创建内部类的对象

    [code]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public class DotNew {
    class Contents {
    private int i = 11;
    public int value() {
    return i;
    }
    }
    class Destination {
    private String label;
    public Destination(String whereTo) {
    label = whereTo;
    }
    public String readLabel() {
    return label;
    }
    }

    public static void main(String[] args) {
    DotNew dn = new DotNew();
    DotNew.Contents contents = dn.new Contents();
    DotNew.Destination destination = dn.new Destination("Tahiti");
    }
    }

获取对外部类对象的引用

  • 使用OuterClassName.this生成对外部类对象的引用,这样产生的引用自动具有正确的类型

    [code]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public class DotThis {
    private class InnerClass {
    public DotThis outer() {
    return DotThis.this;
    }
    }
    public InnerClass inner() {
    return new InnerClass();
    }
    public void f() {
    System.out.println("DotThis.f()");
    }
    public static void main(String[] args) {
    DotThis outerClass = new DotThis();
    DotThis.InnerClass innerClass = outerClass.inner();
    innerClass.outer().f();
    }
    }
    /* output:
    DotThis.f()
    */

获取指向基类或接口的引用

将内部类向上转型为其基类或接口(通过实现某个接口,得到对此接口的引用),此时内部类能够完全不可见,并且不可用。
这样做所得到的只是指向基类或接口的引用,所以能够很方便地隐藏实现细节。

[code]
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
public class InnerClassUpcasting {

private class Contents implements IContents {
private int i = 11;
public int value() {
return i;
}
}
protected class Destination implements IDestination {
private String label;
public Destination(String whereTo) {
label = whereTo;
}
public String readLabel() {
return label;
}
}

public IDestination destination(String s) {
return new Destination(s);
}
public IContents contents() {
return new Contents();
}

public static void main(String[] args) {
InnerClassUpcasting up = new InnerClassUpcasting();

//不合法,Contents是private,Destination是protectd的,外部代码访问这些成员将受到限制
//InnerClassUpcasting.Contents contents = up.new Contents();
//InnerClassUpcasting.Destination destination = up.new Destination("Tahiti");

// 使内部类(某个接口的实现)完全不可见并且不可用,仅得到指向基类或接口的引用,这样能够很方便地隐藏具体实现细节。
IContents icontents = up.contents();
IDestination idestination = up.destination("Wakanda");

//ERROR:无法完成向下转型,说明该内部类被隐藏了
//Contents ct = (Contents)icontents;

}

}

内部类的继承

  • 因为内部类的构造器必须连接到指向其外围类对象的引用,所以在继承内部类的时候,事情会变得复杂。
    问题在于,那个指向外围类对象的引用必须被初始化,而在导出类中不再存在可连接的默认对象。

    要解决这个问题,必须使用特殊的语法来明确说清它们之间的关联:

    [code]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class WithInner {
    class Inner {}
    }
    public class InheritInner extends WithInner.Inner {
    InheritInner(WithInner wi) {
    wi.super();
    }

    public static void main(String[] args) {
    WithInner wi = new WithInner();
    InheritInner ii = new InheritInner(wi);
    }
    }

内部类可以被覆盖吗?

  • 内部类可以被覆盖,必须通过新内部类明确地继承该内部类,并且覆盖了其中的方法。

    [code]
    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
    public class OverridenInner extends Egg {
    public OverridenInner() {
    insertYolk(new Yolk());
    }
    // 小Y
    public class Yolk extends Egg.Yolk{
    public Yolk() {
    System.out.println("OverridenInner.Yolk()");
    }
    public void f() {
    System.out.println("OverridenInner.Yolk.f()");
    }
    }

    public static void main(String[] args) {
    OverridenInner oi = new OverridenInner();
    oi.g();
    }
    }
    class Egg {
    private Yolk y = new Yolk();

    public Egg() {
    System.out.println("New Egg()");
    }

    // 大Y
    protected class Yolk {
    public Yolk() {
    System.out.println("Egg.Yolk()");
    }
    public void f() {
    System.out.println("Egg.Yolk.f()");
    }

    }

    // 通过继承,此方法可以把小Y向上转型为大Y,故可以调用到小Y的f()
    public void insertYolk(Yolk yy) {
    y = yy;
    }
    public void g() {
    y.f();
    }
    }

内部类的种类

局部内部类

—— 在方法和作用域内定义内部类

什么情况下要这么做?
1. 实现了某个接口,于是可以创建并返回对其的引用;
2. 想创建一个类,又不希望这个类是公共可用的。

  • 在方法内定义内部类

    [code]
    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
    public class NestingInMethod {
    public IDestination destination(String s) {
    class Destination implements IDestination {
    private String label;
    public Destination(String whereTo) {
    label = whereTo;
    }
    public String readLabel() {
    return label;
    }
    }
    return new Destination(s);
    }

    public IContents contents() {
    class Contents implements IContents {
    private int i = 11;
    public int value() {
    return i;
    }
    }
    return new Contents();
    }

    public static void main(String[] args) {
    NestingInMethod ic = new NestingInMethod();
    IContents icontents = ic.contents();
    System.out.println(icontents.value());
    IDestination idestination = ic.destination("Wakanda");
    System.out.println(idestination.readLabel());
    }

    }
    InnerClassUpcasting.java的变体
  • 在任意作用域内嵌入一个内部类

    [code]
    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
    public class NestingInScope {

    private void internalTracking(boolean bool) {
    if (bool) {
    class TrackingSlip {
    private String id;
    TrackingSlip(String s) {
    this.id = s;
    }
    String getSlip() {
    return id;
    }
    }
    TrackingSlip ts = new TrackingSlip("slip");
    String s = ts.getSlip();
    }
    //ERROR:作用域外无法使用该内部类
    //TrackingSlip ts = new TrackingSlip("slip");
    }
    public void track() {
    internalTracking(true);
    }

    public static void main(String[] args) {
    NestingInScope ns = new NestingInScope();
    ns.track();
    }
    }

匿名内部类

  • 使用匿名类创建并返回对某个基类或接口的引用

    [code]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public class AnonymousInnerClass {
    public IContents contents() {
    // 通过new表达式返回的引用被自动向上转型为对IContents的引用
    return new IContents() { //创建一个继承自IContents的匿名类的对象
    private int i = 11;
    public int value() {
    return i;
    }
    }; //这种情况下此处需要一个分号
    }
    }
    /* 上述匿名内部类语法是下述形式的简化形式 */
    // class Contents implements IContents {
    // private int i = 11;
    // public int value() {
    // return i;
    // }
    // }
    // public IContents contents() {
    // return new Contents();
    // }
    • 基类构造器带参的情况,只需简单地传递参数给基类构造器

      [code]
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      public class AnonymousInnerClass {
      public Wrapping wrapping(int x) {
      return new Wrapping(x) {
      public int value() {
      return super.value() + 1;
      }
      };
      }
      public static void main(String[] args) {
      AnonymousInnerClass ai = new AnonymousInnerClass();
      Wrapping w = ai.wrapping(37);
      System.out.println(w.value());
      }
      }
    • 通过实例初始化实现匿名内部类创建构造器

    匿名内部类没有名字,不可能有命名构造器。要想达到构造器的效果,可以通过实例初始化来实现。
    当然,这种方式也有它的限制 —— 该实例初始化方法不能重载,所以你仅有这么一个构造器。

    [code]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    public class AnonymousConstructor {

    public IDestination destination(final String dest, final float price) {
    return new IDestination() {
    private int cost;
    //为每个对象进行实例初始化
    {
    cost = Math.round(price);
    if (cost > 100)
    System.out.println("预算要超支啦!");
    }
    private String label = dest;
    @Override
    public String readLabel() {
    return label;
    }
    };
    }

    public static void main(String[] args) {
    AnonymousConstructor ac = new AnonymousConstructor();
    IDestination d = ac.destination("Wakanda", 102.568F);
    }
    }
    • 匿名内部类与正规的继承相比有些受限,因为匿名内部类既可以扩展类,也可以实现接口,但是不能两者兼备。而且如果是实现接口,也只能实现一个接口。

    • 使用匿名内部类的工厂方法更优雅?

      [code]
      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
      interface Game {
      boolean move();
      }
      interface GameFactory {
      Game getGame();
      }

      class Checkers implements Game {
      private Checkers() {}
      private int moves = 0;
      private static final int MOVES = 3;
      @Override
      public boolean move() {
      System.out.println("Checkers move" + moves);
      return ++moves != MOVES;
      }
      //只需要创建单一的工厂对象,使用static
      public static GameFactory factory = new GameFactory() {
      @Override
      public Game getGame() {
      return new Checkers();
      }
      };
      }

      class Chess implements Game {
      private Chess() {}
      private int moves = 0;
      private static final int MOVES = 7;
      @Override
      public boolean move() {
      System.out.println("Chess move" + moves);
      return ++moves != MOVES;
      }
      public static GameFactory factory = new GameFactory() {
      @Override
      public Game getGame() {
      return new Chess();
      }
      };
      }

      public class Factories {
      public static void playGame(GameFactory factory) {
      Game s = factory.getGame();
      while (s.move())
      ;
      }
      public static void main(String[] args) {
      playGame(Checkers.factory);
      playGame(Chess.factory);
      }

      }

局部内部类和匿名内部类

局部内部类不能有访问说明符,因为它不是外围类的一部分,但是它可以访问当前代码块内的常量以及此外围类的所有成员。

  • 局部内部类和匿名内部类的区别?

    [code]
    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
    interface Counter {
    int next();
    }
    public class LocalInnerClass {
    private int count = 0;
    Counter getCounter(final String name) {
    class LocalCounter implements Counter {
    public LocalCounter() {
    System.out.println("LocalCounter()");
    }
    public int next() {
    System.out.print(name);
    return count++;
    }
    }
    return new LocalCounter();
    }

    Counter getCounter2(final String name) {

    return new Counter(){
    {
    System.out.println("Counter()");
    }
    public int next() {
    System.out.print(name);
    return count++;
    }

    };
    }

    public static void main(String[] args) {
    LocalInnerClass lic = new LocalInnerClass();
    Counter c1 = lic.getCounter("Local inner ");
    Counter c2 = lic.getCounter2("Anonymous inner");
    for (int i = 0; i < 5; i++)
    System.out.println(c1.next());
    for (int i = 0; i < 5; i++)
    System.out.println(c2.next());
    }

    }

    以上demo分别使用局部内部类和匿名内部类实现返回序列下一个值的功能,运行结果表明它们具有相同的行为和能力。

  • 既然行为和能力一直,那么什么情况使用局部内部类而不是匿名内部类呢?

    1. 需要一个已命名的构造器,或者需要重载构造器
    2. 需要不止一个该内部类的对象(匿名内部类是能用于实例初始化)

嵌套类

—— 声明为static的内部类

前面有提到,普通的内部类对象隐式地保存了一个指向创建它的外围类对象的引用,这使得内部类拥有对外围类所有成员的访问权。
然而,当内部类是static的时,就不是这样了。

如果不需要内部类对象与其外围类对象之间有联系,那么可以使用嵌套类(将内部类声明为static)。

嵌套类意味着:
1. 要创建嵌套类的对象,并不需要其外围类的对象。
2. 不能从嵌套类的对象中访问非静态的外围类对象。

  • 嵌套类和普通内部类有一个区别是:普通内部类的字段与方法,只能放在类的外部层次上,所以普通内部类不能有static数据和static字段,也不能包含嵌套类。
    但是嵌套类却可以包含这些东西。

    [code]
    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
    public class NestedClass {

    private static final int deed = 51;
    public int doSomething() {
    final double d = Math.random();
    final int i = (int)(d*deed);
    return i;
    }

    private class ParcelContents implements IContents {
    private int i = 37;
    public int value() {
    return i + doSomething();
    }
    // ERROR:普通内部类的字段和方法不能有static数据和static字段,也不能包含嵌套类。
    //public static void f() {}
    }

    // ParcelDestination不需要外围类的任何对象
    protected static class ParcelDestination implements IDestination {
    private String label;
    private ParcelDestination(String s) {
    this.label = s;
    }
    public String readLabel() {
    return label;
    }
    //嵌套类可以包含其他静态元素和静态字段
    public static void f() {}
    static int x = 7;
    static class AnotherLevel {
    public static void f() {}
    static int x = 3;
    }
    }

    public IContents contents() {
    return new ParcelContents();
    }

    public static IDestination destination(String s) {
    return new ParcelDestination(s);
    }

    public static void main(String[] args) {
    NestedClass nc = new NestedClass();
    IContents c = nc.contents();
    IDestination d = destination("Cool");
    }
    }
    接口内部的类
  • 正常情况下,不能在接口内部放置任何代码,但是嵌套类可以作为接口的一部分。

  • 接口的内部类甚至可以实现外围接口。

  • 如果想要有可以被某个接口的所有不同实现所共用的公共代码,那么使用接口内部的嵌套类会很适合。

    从多层嵌套类中访问外部类成员
  • 一个内部类被嵌套多少层并不重要 —— 它能透明地访问所有它嵌入的外围类的所有成员。

    [code]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class MNA {
    private void f() {}
    class A {
    private void g() {}
    public class B {
    void h() {
    g();
    f();
    }
    }
    }
    }
    public class MultiNestingAccess {
    public static void main(String[] args) {
    MNA mna = new MNA();
    MNA.A mnaa = mna.new A();
    MNA.A.B mnaab = mnaa.new B();
    mnaab.h();

    }

    }

为什么需要内部类?

  • 一般来说,内部类继承某个类或实现某个接口,内部类的代码操作创建它的外围类的对象。所以认为内部类提供了某种进入其外围类的窗口。
  • 如果我们需要一个对接口的引用,为什么不通过外围类实现那个接口呢?内部类实现那个接口和外围类实现那个接口有什么区别呢? 
     
    每个内部类都能独立地继承自一个接口的实现,所以无论外围类是否继承了某个接口的实现,对于内部类都没有影响。
  • 创建内部类对象的时刻并不依赖于外围类对象的创建。
  • 内部类并没有令人迷惑的“is-a”关系;它就是一个独立的实体。

通过内部类提供的闭包功能实现回调

  • 闭包(closure)是一个可调用的对象,它记录了一些信息,这些信息来自于创建它的作用域。

    通过这个定义,可以看出内部类是一个面向对象的闭包,因为它不仅包含外围类对象的信息,还自动拥有一个指向此外围类对象的引用,在此作用域内,内部类有权操作所有的成员,包括private成员。

  • 在Java中,通过内部类提供闭包功能是一个非常好的类似指针机制的回调的解决方案,它比指针更灵活,也更安全。

    [code]
    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
    interface Incrementable {
    void increment();
    }
    // 外围类直接实现接口的简单解决方式,用作对比
    class Callee1 implements Incrementable {
    private int i = 0;
    public void increment() {
    i++;
    System.out.println(i);
    }
    }

    class MyIncrement {
    public void increment() {
    System.out.println("Other operation");

    }
    static void f(MyIncrement mi){
    mi.increment();
    }
    }

    // Callee2继承了MyIncrement,它与Incrementable拥有不同的increment(),因此就不能为了Incrementable的用途而覆盖increment()方法,于是只能使用内部类独立地实现。
    class Callee2 extends MyIncrement {
    private int i = 0;
    public void increment() {
    super.increment();
    i++;
    System.out.println(i);
    }

    /**
    * 此内部类返回一个Callee2的“钩子”,而且是安全的钩子。
    * 无论谁获得此Incrementable的引用,都只能调用increment()。
    */
    private class Closure implements Incrementable{
    public void increment() {
    Callee2.this.increment();
    }
    }
    Incrementable getCallbackReference() {
    return new Closure();
    }
    }

    /**
    * Caller的构造器需要一个Incrementable的引用作为参数,然后在以后任意时刻都可以使用此引用来回调Callee类
    */
    class Caller {
    private Incrementable callbackReference;
    Caller(Incrementable cbh) {
    callbackReference = cbh;
    }
    void go() {
    callbackReference.increment();
    }
    }

    public class Callbacks {
    public static void main(String[] args) {
    Callee1 c1 = new Callee1();
    Callee2 c2 = new Callee2();
    MyIncrement.f(c2);
    Caller caller1 = new Caller(c1);
    Caller caller2 = new Caller(c2.getCallbackReference());
    caller1.go();
    caller1.go();
    caller2.go();
    caller2.go();
    }
    }

    回调的价值在于它的灵活性 —— 可以在运行时动态地决定需要调用什么方法。

内部类标识符

.class 文件中,内部类信息的规则 ==> 外围类的名字,加上“$”,再加上内部类的名字。

如果内部类是匿名的,编译器会简单地产生一个数字作为其标识符。

如果内部类是潜逃在别的内部类中,只需直接将它们的名字加在其外围类标识符与“$”的后面。

递归

递归的概念:一个函数直接或间接的调用自身。

一般来说,递归调用需要有边界条件,递归前进段和递归返回段。
当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

递归一般用于解决三类问题:

  1. 数据的定义是按递归定义的,如n的阶乘,斐波那契函数;

  2. 问题解法是按递归实现的,如回溯;

  3. 数据的数据结构是按递归定义的,如二叉树的遍历,图的搜索。

    [code]
    1
    2
    3
    4
    5
    6
    7
    int factorial(int n) {
    if(n == 1){ //递归边界
    return 1; //递归返回段
    } else {
    return n * factorial(n-1); //递归前进段
    }
    }

    机器层面的实现

    一个程序的执行在内存中就是一个个方法入栈和出栈的过程。堆栈中的每一个栈帧代表了被调用中的一个函数。

    例如计算factorial(4)的过程如图:
    计算factorial(4)的堆栈

    计算factorial(4)的时候,方法是4*factorial(3),但是还不知道factorial(3)的值,于是需要新增一个栈帧来计算,
    而factorial(3)需要factorial(2)……以此类推,到factorial(1)才能得到它的值,然后每个栈帧逐个出栈,最后计算得出factorial(4)的值。

    前面提到每个递归调用都需要一个边界条件,不满足该条件就会一直递归下去。但是内存中堆栈的容量是有限的,每个栈帧都需要占用空间,
    而且栈帧的维护也需要系统开销,递归层次太深可能会造成栈溢出

    使用递归的优缺点

  • 优点:
    精简代码,提高可读性;

  • 缺点:

    1. 在自身中调用自身,是嵌套调用(栈帧无法回收,开销巨大)
    2. 递归层数过多时容易造成内存溢出问题

    递归的优化——尾递归

    递归的巨大开销是因为过多的栈帧占用空间和维护的巨大开销,这种调用是可优化的。
    之前的递归中递归前进段返回值为n * factorial(n-1)的表达式,这样每个栈帧都需要记录下当前的n的值,还要记录下一个函数栈帧的返回值,
    然后才能运算出当前栈帧的结果。也就是说使用多个栈帧是不可避免的。

    如果在函数返回的时候,调用自身本身,并且return语句不包含表达式,这样,编译器或者解释器就可以把递归进行优化,使递归无论调用多少次,
    都只占用一个栈帧,不会出现栈溢出的情况。

    尾递归调用

何为进程?何为线程?(以Java为例)

  1. 进程

    在面向进程设计的系统(如早期的UNIX,Linux 2.4及更早的版本)中,进程是程序的基本执行实体;
    在面向线程设计的系统(如当代多数操作系统、Linux 2.6及更新的版本)中,进程本身不是基本运行单位,而是线程的容器。

    若干进程有可能与同一个程序相关系,且每个进程皆可以同步(循序)或异步(平行)的方式独立运行。

  2. 线程

    线程(英语:thread)是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位。
    一条线程指的是进程中一个单一顺序的控制流,一个进程中可以并发多个线程,每条线程并行执行不同的任务。

    线程是独立调度和分派的基本单位。线程可以为操作系统内核调度的内核线程,如Win32线程;由用户进程自行调度的用户线程,如的POSIX Thread;或者由内核与用户进程,如Windows 7的线程,进行混合调度。

    同一进程中的多条线程将共享该进程中的全部系统资源,如虚拟地址空间,文件描述符和信号处理等等。
    但同一进程中的多个线程有各自的调用栈(call stack),自己的寄存器环境(register context),自己的线程本地存储(thread-local storage)。

    线程是比进程更轻量级的调度执行单位,线程的引入,可以把一个进程的资源调配和执行调度分开,各个线程既可以共享进程资源(内存地址、文件I/O等),又可以独立调度(线程是CPU调度的基本单位)

关于进程和线程

  1. 进程之间是隔离的。Java的虚拟机就是一个进程,虚拟机可以屏蔽不同操作系统的差异。

    线程之间可以共享进程资源,又有各自的调用栈、寄存器环境和线程本地存储。(虚拟机栈、本地方法栈、程序计数器)

  2. 在一个进程内部,要同时干多件事,就需要同时运行多个“子任务”,我们把进程内的这些“子任务”称为线程(Thread)。

    单线程一次只能干一件事,无法并发和并存。

  3. 进程是拥有资源的基本单位;线程是cpu调度的基本单位。

实现线程的的3种方式

实现线程主要有3种方式:使用内核线程实现、使用用户线程实现和使用用户线程加亲良机进程混合实现。

1. 使用内核线程实现

内核线程:直接由操作系统内核支持的线程,这种线程由内核来完成线程切换,内核通过操纵调度器对线程进行调度,并负责将线程的任务映射到各个处理器上。

每个内核线程可以视为内核的一个分身,这样操作系统就有能力同时处理多件事情,支持多线程的内核就叫做多线程内核。

程序一般不会直接使用内核线程,而是去使用内核线程的一种高级接口 —— 轻量级进程(我们通常意义上所说的线程)。

由于每个轻量级进程都由一个内核线程支持,因此只有先支持内核线程,才能有轻量级进程。两者之间的关系为 1:1

轻量级进程局限性:
- 基于内核线程实现的线程的操作(如创建、析构及同步),都需要进行系统调用。而系统调用的代价相对较高,需要在用户态和内核态中来回切换,效率会受到限制。
- 每个轻量级进程都需要有一个内核线程支持,会消耗一定的内核资源(如内核线程的栈空间),也因此一个系统支持轻量级进程的数量是有限的

2. 使用用户线程实现

用户线程:广义上,不是内核线程的线程,就是用户线程。狭义上,用户线程指完全建立在用户空间的线程库上,系统内核不能感知线程存在的实现。

用户线程的建立、同步、销毁和调度完全是在用户态中完成的,不需要内核帮助,因此操作可以是快速且低消耗的,也可以支持规模更大的线程数量。

这种进程与用户线程之间的关系为 1:N

用户线程优势在不需要系统内核支援,劣势也在于没有系统内核的支援。由于没有系统内核的支援,线程的创建、切换、调度等问题的解决会变得复杂。

3. 使用用户线程加轻量级进程混合实现

这种混合实现下,既存在用户线程,也存在轻量级进程。用户线程还是完全建立在用户空间中,因此用户线程的创建、切换、析构等操作依然廉价,并且可以大规模的用户线程并发。
而操作系统提供支持的轻量级进程则作为用户线程和内核线程的桥梁,这样可以使用内核提供的线程调度功能及处理器映射,并且用户线程的系统调用要通过轻量级线程来完成,大大降低了整个进程被完全阻塞的风险。

两者的关系为 M:N

线程调度方式

线程调度是指系统为线程分配处理器使用权的过程,主要的调度方式有两种: 协同式线程调度 和 抢占式线程调度。

  1. 协同式调度:线程的执行时间由线程本身控制,线程工作完成后主动通知系统切换到其他线程。

    好处:线程的切换操作对线程自身是可知的,·所以没有什么线程同步的问题。
    坏处:线程执行时间不可控制,若线程运行有问题,一直不告知系统进行线程切换,那么程序会一直阻塞。

  2. 抢占式调度:线程的执行时间由系统来分配,线程切换不由线程本身决定

    好处:线程的执行时间由系统控制,不会有一个线程导致整个进程阻塞的问题

    线程优先级:

    Java语言一共设置了10个级别的线程优先级

线程状态转换

Java语言定义了5种线程状态:新建、运行、无限期等待、限期等待、阻塞、结束

  • 新建(New):创建后尚未启动的线程处于这种状态

  • 运行(Runnable): Runnable包括了操作系统线程状态中的Running和Ready,也就是处于此状态的线程可能是正在执行,也可能是在等待CPU为它分配执行时间。

  • 无限期等待(Waiting): 处于此状态的线程不会被分配CPU执行时间,它们要等待被其他线程显式地唤醒。
    以下方法会让线程陷入无限期的等待状态:

    • 没有设置Timeout参数的Object.wait()方法;
    • 没有设置Timeout参数的Thread.join()方法;
    • LockSupport.park()方法。
  • 限期等待(Timed Waiting): 处于这种状态的线程也不会被分配CPU执行时间,不过无须等待被其他线程显式地唤醒,在一定时间之后它们会由系统自动唤醒。
    以下方法会让线程陷入限期的等待状态:

    • Thread.sleep()方法;
    • 设置了Timeout参数的Object.wait()方法;
    • 设置了Timeout参数的Thread.join()方法;
    • LockSupport.parkNanos()方法;
    • LockSupport.parkUntil()方法。
  • 阻塞(Blocked): 线程被阻塞了,等待获取一个排他锁,这个时间将在另一个线程放弃这个锁的时候发生。
    在程序等待进入同步区域的时候,线程将进入这种状态。

  • 结束(Terminated): 已终止线程的线程状态,线程已经执行结束。

    定义线程任务 —— Runnable

    要想定义任务,只需实现Runnable接口并编写run()方法

    任务的run()方法通常会有某种形式的循环,使得任务一直运行下去直到不再需要,所以要设定跳出循环的条件(比如循环最后使用某个FLAG)。

    使用线程池管理多线程 —— Executor

    几种不同的Executor

    • CachedThreadPool
    • FixedThreadPool
    • SingleThreadPool

    它们的创建都是调用同一个构造器方法ExecutorThreadPoll(***),区别只是参数不同。

    public ThreadPoolExecutor(int corePoolSize,

    int maximumPoolSize,
    long keepAliveTime,
    TimeUnit unit,
    BlockingQueue<Runnable> workQueue,
    ThreadFactory threadFactory,
    RejectedExecutionHandler handler)

    使用何种类型?

    CachedThreadPool在程序执行过程中通常会创建与所需数量相同的线程,然后在它回收旧线程时停止创建新线程,
    因此它是合理的Executor的首选。只有当这种方式会引发问题时,我们才需要切换到FixedThreadPool。

    SingleThreadExecutor就像是线程数量为1 的FixedThreadPool。这个适用于你希望在另一个线程中连续运行的任何任务(长期存活的任务)。
    如果向SingleThreadExecutor提交了多个任务,那么这些任务将排队,每个任务都会在下一个任务开始之前运行结束,所有的任务将使用相同的线程。
    使用SingleThreadExecutor,可以确保任一时刻在任何线程中都只有唯一的任务在运行。此种方式可是你不需要在共享资源上同步(虽然有时候更好的解决方案是在资源商同步)。