Dunwu Blog

大道至简，知易行难

发表于 更新于 分类于 ， 本文字数： 7.7k 阅读时长 ≈ 7 分钟

设计模式之抽象工厂模式

意图

抽象工厂模式 （Abstract Factory）是一种创建型设计模式， 它能创建一系列相关的对象， 而无需指定其具体类。

**优点 **

  • 抽象工厂模式隔离了具体类的生成，用户并不需要知道什么被创建。由于这种隔离，更换一个具体工厂变得相对容易。所有的具体工厂都实现了抽象工厂中定义的那些公共接口，因此只需要改变具体工厂的实例，就可以在某种程度上改变整个软件系统的行为。另外，应用抽象工厂模式可以实现高内聚低耦合的设计目的，因此抽象工厂模式得到了广泛的应用。

  • 当一个产品族中的多个对象被设计成一起工作时，它能够保证客户端始终只使用同一个产品族中的对象。这对一些需要根据当前环境来决定其行为的软件系统来说，是一种非常实用的设计模式。

  • 增加新的具体工厂和产品族很方便，无须修改已有系统，符合“开放封闭原则”。

缺点

  • 在添加新的产品对象时，难以扩展抽象工厂来生产新种类的产品，这是因为在抽象工厂角色中规定了所有可能被创建的产品集合，要支持新种类的产品就意味着要对该接口进行扩展，而这将涉及到对抽象工厂角色及其所有子类的修改，显然会带来较大的不便。

适用场景

抽象工厂模式适用场景：

一个系统要独立于它的产品的创建、组合和表示时。

一个系统要由多个产品系列中的一个来配置时。

当你要强调一系列相关的产品对象的设计以便进行联合使用时。

当你提供一个产品类库，而只想显示它们的接口而不是实现时。

结构

img

结构说明

  1. 抽象产品 （Abstract Product） 为构成系列产品的一组不同但相关的产品声明接口。
  2. 具体产品 （Concrete Product） 是抽象产品的多种不同类型实现。 所有变体 （维多利亚/现代） 都必须实现相应的抽象产品 （椅子/沙发）。
  3. 抽象工厂 （Abstract Factory） 接口声明了一组创建各种抽象产品的方法。
  4. 具体工厂 （Concrete Factory） 实现抽象工厂的构建方法。 每个具体工厂都对应特定产品变体， 且仅创建此种产品变体。
  5. 尽管具体工厂会对具体产品进行初始化， 其构建方法签名必须返回相应的抽象产品。 这样， 使用工厂类的客户端代码就不会与工厂创建的特定产品变体耦合。 客户端 （Client） 只需通过抽象接口调用工厂和产品对象， 就能与任何具体工厂/产品变体交互。

结构代码范式

【AbstractProduct】

声明一个接口，这个接口中包含产品对象类型。

1
2
3
4
5
6
7
abstract class AbstractProductA {
    public abstract void show();
}

abstract class AbstractProductB {
    public abstract void show();
}

【ConcreteProduct】

定义一个产品对象，这个产品对象是由相关的具体工厂创建的。

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
class ConcreteProductA1 extends AbstractProductA {
    @Override
    public void show() {
        System.out.println("ConcreteProductA1");
    }
}

class ConcreteProductA2 extends AbstractProductA {
    @Override
    public void show() {
        System.out.println("ConcreteProductA2");
    }
}

class ConcreteProductB1 extends AbstractProductB {
    @Override
    public void show() {
        System.out.println("ConcreteProductB1");
    }
}

class ConcreteProductB2 extends AbstractProductB {
    @Override
    public void show() {
        System.out.println("ConcreteProductB2");
    }
}

【AbstractFactory】

声明一个接口，这个接口中包含创建抽象产品对象的方法。

1
2
3
4
abstract class AbstractFactory {
    public abstract AbstractProductA createProductA();
    public abstract AbstractProductB createProductB();
}

【ConcreteFactory】

实现创建具体产品对象的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ConcreteFactory1 extends AbstractFactory {
    @Override
    public AbstractProductA createProductA() {
        return new ConcreteProductA1();
    }

    @Override
    public AbstractProductB createProductB() {
        return new ConcreteProductB1();
    }
}

class ConcreteFactory2 extends AbstractFactory {
    @Override
    public AbstractProductA createProductA() {
        return new ConcreteProductA2();
    }

    @Override
    public AbstractProductB createProductB() {
        return new ConcreteProductB2();
    }
}

【客户端】

只使用 AbstractFactory 和 AbstractProduct 声明的接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class AbstarctFactoryPattern {
    public static void main(String[] args) {
        AbstractFactory  factory1  = new ConcreteFactory1();
        AbstractProductA productA1 = factory1.createProductA();
        AbstractProductB productB1 = factory1.createProductB();
        productA1.show();
        productB1.show();

        AbstractFactory  factory2  = new ConcreteFactory2();
        AbstractProductA productA2 = factory2.createProductA();
        AbstractProductB productB2 = factory2.createProductB();
        productA2.show();
        productB2.show();
    }
}

【输出】

1
2
3
4
ConcreteProductA1
ConcreteProductB1
ConcreteProductA2
ConcreteProductB2

伪代码

下面例子通过应用抽象工厂模式， 使得客户端代码无需与具体 UI 类耦合， 就能创建跨平台的 UI 元素， 同时确保所创建的元素与指定的操作系统匹配。

img

跨平台应用中的相同 UI 元素功能类似， 但是在不同操作系统下的外观有一定差异。 此外， 你需要确保 UI 元素与当前操作系统风格一致。 你一定不希望在 Windows 系统下运行的应用程序中显示 macOS 的控件。

抽象工厂接口声明一系列构建方法， 客户端代码可调用它们生成不同风格的 UI 元素。 每个具体工厂对应特定操作系统， 并负责生成符合该操作系统风格的 UI 元素。

其运作方式如下： 应用程序启动后检测当前操作系统。 根据该信息， 应用程序通过与该操作系统对应的类创建工厂对象。 其余代码使用该工厂对象创建 UI 元素。 这样可以避免生成错误类型的元素。

使用这种方法， 客户端代码只需调用抽象接口， 而无需了解具体工厂类和 UI 元素。 此外， 客户端代码还支持未来添加新的工厂或 UI 元素。

这样一来， 每次在应用程序中添加新的 UI 元素变体时， 你都无需修改客户端代码。 你只需创建一个能够生成这些 UI 元素的工厂类， 然后稍微修改应用程序的初始代码， 使其能够选择合适的工厂类即可。

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 GUIFactory is
    method createButton():Button
    method createCheckbox():Checkbox


// 具体工厂可生成属于同一变体的系列产品。工厂会确保其创建的产品能相互搭配
// 使用。具体工厂方法签名会返回一个抽象产品，但在方法内部则会对具体产品进
// 行实例化。
class WinFactory implements GUIFactory is
    method createButton():Button is
        return new WinButton()
    method createCheckbox():Checkbox is
        return new WinCheckbox()

// 每个具体工厂中都会包含一个相应的产品变体。
class MacFactory implements GUIFactory is
    method createButton():Button is
        return new MacButton()
    method createCheckbox():Checkbox is
        return new MacCheckbox()


// 系列产品中的特定产品必须有一个基础接口。所有产品变体都必须实现这个接口。
interface Button is
    method paint()

// 具体产品由相应的具体工厂创建。
class WinButton implements Button is
    method paint() is
        // 根据 Windows 样式渲染按钮。

class MacButton implements Button is
    method paint() is
        // 根据 macOS 样式渲染按钮

// 这是另一个产品的基础接口。所有产品都可以互动，但是只有相同具体变体的产
// 品之间才能够正确地进行交互。
interface Checkbox is
    method paint()

class WinCheckbox implements Checkbox is
    method paint() is
        // 根据 Windows 样式渲染复选框。

class MacCheckbox implements Checkbox is
    method paint() is
        // 根据 macOS 样式渲染复选框。

// 客户端代码仅通过抽象类型（GUIFactory、Button 和 Checkbox）使用工厂
// 和产品。这让你无需修改任何工厂或产品子类就能将其传递给客户端代码。
class Application is
    private field factory: GUIFactory
    private field button: Button
    constructor Application(factory: GUIFactory) is
        this.factory = factory
    method createUI() is
        this.button = factory.createButton()
    method paint() is
        button.paint()


// 程序会根据当前配置或环境设定选择工厂类型，并在运行时创建工厂（通常在初
// 始化阶段）。
class ApplicationConfigurator is
    method main() is
        config = readApplicationConfigFile()

        if (config.OS == "Windows") then
            factory = new WinFactory()
        else if (config.OS == "Mac") then
            factory = new MacFactory()
        else
            throw new Exception("错误！未知的操作系统。")

        Application app = new Application(factory)

案例

众所周知，苹果和三星这两家世界级的电子产品厂商都生产手机和电脑。

我们以生产手机和电脑为例，演示一下抽象工厂模式的应用

【AbstractProduct 角色】

首先，定义手机和电脑两个抽象接口，他们都有各自的产品信息。

1
2
3
4
5
6
7
interface Telephone {
    public String getProductInfo();
}

interface Computer {
    public String getProductInfo();
}

【ConcreteProduct 角色】

ConcreteProduct 根据 AbstractProduct 来定义具体的产品属性、方法。

在我们的例子中，苹果、三星两家公司的手机和电脑都有各自的具体产品信息。

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
class AppleTelephone implements Telephone {

    @Override
    public String getProductInfo() {
        return "苹果手机，采用ios系统";
    }
}

class SamsungTelephone implements Telephone {

    @Override
    public String getProductInfo() {
        return "三星手机，采用android系统";
    }
}

class AppleComputer implements Computer {

    @Override
    public String getProductInfo() {
        return "苹果电脑，采用mac系统";
    }
}

class SamsungComputer implements Computer {

    @Override
    public String getProductInfo() {
        return "三星电脑，采用windows系统";
    }
}

【AbstractFactory 角色】

苹果，三星这两个厂商都生产手机和电脑。所以它们可以有一个抽象父类或父接口，提供生产手机和生产电脑的方法。

1
2
3
4
5
6
interface ElectronicFactory {

    public Telephone produceTelephone();

    public Computer produceComputer();
}

【ConcreteFactory 角色】

苹果、三星工厂分别实现父接口，生产不同类型的产品。

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
class AppleFactory implements ElectronicFactory {

    @Override
    public Telephone produceTelephone() {
        return new AppleTelephone();
    }

    @Override
    public Computer produceComputer() {
        return new AppleComputer();
    }
}

class SamsungFactory implements ElectronicFactory {

    @Override
    public Telephone produceTelephone() {
        return new SamsungTelephone();
    }

    @Override
    public Computer produceComputer() {
        return new SamsungComputer();
    }
}

【客户端】

1
2
3
4
5
6
7
8
9
public class PhoneFactoryDemo {
    public static void main(String[] args) {
        ElectronicFactory appleFactory = new AppleFactory();
        Telephone phone = appleFactory.produceTelephone();
        System.out.println(phone.getProductInfo());
        Computer computer = appleFactory.produceComputer();
        System.out.println(computer.getProductInfo());
    }
}

【输出】

1
2
苹果手机，采用ios系统
苹果电脑，采用mac系统

与其他模式的关系

参考资料

发表于 更新于 分类于 ， 本文字数： 5.6k 阅读时长 ≈ 5 分钟

设计模式之工厂方法模式

意图

工厂方法模式 (Factory Method)是一种创建型设计模式， 其在父类中提供一个创建对象的方法， 让子类决定实例化对象的类型。

  • 工厂模式中，增加一种产品类，就要增加一个工厂类：因为每个工厂类只能创建一种产品的实例。
  • 工厂模式遵循“开放-封闭原则”：工厂模式中，新增一种产品并不需要修改原有类，仅仅是扩展。

简单工厂模式相比于工厂方法模式

优点：工厂类中包含必要的逻辑判断，可根据客户端的选择条件动态实例化需要的类。对于客户端来说，去除了对具体产品的依赖。

缺点：违背了开放封闭原则。 每添加一个新的产品，都需要对原有类进行修改。增加维护成本，且不易于维护。

开放封闭原则：一个软件实体如类、模块和函数应该对扩展开放，对修改关闭。

适用场景

  • 当你在编写代码的过程中， 如果无法预知对象确切类别及其依赖关系时， 可使用工厂方法。
  • 如果你希望用户能扩展你软件库或框架的内部组件， 可使用工厂方法。
  • 如果你希望复用现有对象来节省系统资源， 而不是每次都重新创建对象， 可使用工厂方法。

结构

img

结构说明

  1. 产品 （Product） 将会对接口进行声明。 对于所有由创建者及其子类构建的对象， 这些接口都是通用的。
  2. 具体产品 （Concrete Products） 是产品接口的不同实现。
  3. 创建者 （Creator） 类声明返回产品对象的工厂方法。 该方法的返回对象类型必须与产品接口相匹配。
  • 你可以将工厂方法声明为抽象方法， 强制要求每个子类以不同方式实现该方法。 或者， 你也可以在基础工厂方法中返回默认产品类型。
  • 注意， 尽管它的名字是创建者， 但他最主要的职责并不是创建产品。 一般来说， 创建者类包含一些与产品相关的核心业务逻辑。 工厂方法将这些逻辑处理从具体产品类中分离出来。 打个比方， 大型软件开发公司拥有程序员培训部门。 但是， 这些公司的主要工作还是编写代码， 而非生产程序员。
  1. 具体创建者 （Concrete Creators） 将会重写基础工厂方法， 使其返回不同类型的产品。
    注意， 并不一定每次调用工厂方法都会创建新的实例。 工厂方法也可以返回缓存、 对象池或其他来源的已有对象。

结构代码范式

【Product】

定义产品对象的接口。

1
2
3
abstract class Product {
    public abstract void use();
}

【ConcreteProduct】

实现 Product 接口。

1
2
3
4
5
6
7
8
9
10
class ConcreteProduct extends Product {
    public ConcreteProduct() {
        System.out.println("创建 ConcreteProduct 产品");
    }

    @Override
    public void Use() {
        System.out.println("使用 ConcreteProduct 产品");
    }
}

【Creator】

声明工厂方法，它会返回一个产品类型的对象。 Creator 也可以实现一个默认的工厂方法 factoryMethod() ，以返回一个默认的具体产品类型。

1
2
3
interface Creator {
    public Product factoryMethod();
}

【ConcreteCreator】

覆写 Creator 中的工厂方法 factoryMethod() 。

1
2
3
4
5
6
class ConcreteCreator implements Creator {
    @Override
    public Product factoryMethod() {
        return new ConcreteProduct();
    }
}

【客户端】

1
2
3
4
5
6
7
public class factoryMethodPattern {
    public static void main(String[] args) {
        Creator factory = new ConcreteCreator();
        Product product = factory.factoryMethod();
        product.Use();
    }
}

【输出】

1
2
创建 ConcreteProduct 产品
使用 ConcreteProduct 产品

伪代码

以下示例演示了如何使用工厂方法开发跨平台 UI （用户界面） 组件， 并同时避免客户代码与具体 UI 类之间的耦合。

img

基础对话框类使用不同的 UI 组件渲染窗口。 在不同的操作系统下， 这些组件外观或许略有不同， 但其功能保持一致。 Windows 系统中的按钮在 Linux 系统中仍然是按钮。

如果使用工厂方法， 就不需要为每种操作系统重写对话框逻辑。 如果我们声明了一个在基本对话框类中生成按钮的工厂方法， 那么我们就可以创建一个对话框子类， 并使其通过工厂方法返回 Windows 样式按钮。 子类将继承对话框基础类的大部分代码， 同时在屏幕上根据 Windows 样式渲染按钮。

如需该模式正常工作， 基础对话框类必须使用抽象按钮 （例如基类或接口）， 以便将其扩展为具体按钮。 这样一来， 无论对话框中使用何种类型的按钮， 其代码都可以正常工作。

你可以使用此方法开发其他 UI 组件。 不过， 每向对话框中添加一个新的工厂方法， 你就离抽象工厂模式更近一步。 我们将在稍后谈到这个模式。

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
// 创建者类声明的工厂方法必须返回一个产品类的对象。创建者的子类通常会提供
// 该方法的实现。
class Dialog is
    // 创建者还可提供一些工厂方法的默认实现。
    abstract method createButton():Button

    // 请注意，创建者的主要职责并非是创建产品。其中通常会包含一些核心业务
    // 逻辑，这些逻辑依赖于由工厂方法返回的产品对象。子类可通过重写工厂方
    // 法并使其返回不同类型的产品来间接修改业务逻辑。
    method render() is
        // 调用工厂方法创建一个产品对象。
        Button okButton = createButton()
        // 现在使用产品。
        okButton.onClick(closeDialog)
        okButton.render()


// 具体创建者将重写工厂方法以改变其所返回的产品类型。
class WindowsDialog extends Dialog is
    method createButton():Button is
        return new WindowsButton()

class WebDialog extends Dialog is
    method createButton():Button is
        return new HTMLButton()


// 产品接口中将声明所有具体产品都必须实现的操作。
interface Button is
    method render()
    method onClick(f)

// 具体产品需提供产品接口的各种实现。
class WindowsButton implements Button is
    method render(a, b) is
        // 根据 Windows 样式渲染按钮。
    method onClick(f) is
        // 绑定本地操作系统点击事件。

class HTMLButton implements Button is
    method render(a, b) is
        // 返回一个按钮的 HTML 表述。
    method onClick(f) is
        // 绑定网络浏览器的点击事件。


class Application is
    field dialog: Dialog

    // 程序根据当前配置或环境设定选择创建者的类型。
    method initialize() is
        config = readApplicationConfigFile()

        if (config.OS == "Windows") then
            dialog = new WindowsDialog()
        else if (config.OS == "Web") then
            dialog = new WebDialog()
        else
            throw new Exception("错误！未知的操作系统。")

    // 当前客户端代码会与具体创建者的实例进行交互，但是必须通过其基本接口
    // 进行。只要客户端通过基本接口与创建者进行交互，你就可将任何创建者子
    // 类传递给客户端。
    method main() is
        this.initialize()
        dialog.render()

案例

使用示例： 工厂方法模式在 Java 代码中得到了广泛使用。 当你需要在代码中提供高层次的灵活性时， 该模式会非常实用。

核心 Java 程序库中有该模式的应用：

识别方法： 工厂方法可通过构建方法来识别， 它会创建具体类的对象， 但以抽象类型或接口的形式返回这些对象。

还是以 简单工厂模式 里的例子来进行说明。

如何实现一个具有加减乘除基本功能的计算器？

两种模式的 Product 和 ConcreteProduct 角色代码没有区别，不再赘述。

差异在于 Factory 角色部分，以及客户端部分，请在代码中体会。

【Creator 角色】

1
2
3
4
// Creator 角色，定义返回产品实例的公共工厂方法
interface OperationFactory {
    public Operation factoryMethod();
}

【ConcreteCreator 角色】

和简单工厂模式相比，每一种产品都会有一个具体的工厂类负责生产实例。

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
// ConcreteCreator 角色，具体实现 Creator 中的方法
class AddFactory implements OperationFactory {
    @Override
    public Operation factoryMethod() {
        return new Add();
    }
}

// ConcreteCreator 角色，具体实现 Creator 中的方法
class SubFactory implements OperationFactory {
    @Override
    public Operation factoryMethod() {
        return new Sub();
    }
}

// ConcreteCreator 角色，具体实现 Creator 中的方法
class MulFactory implements OperationFactory {
    @Override
    public Operation factoryMethod() {
        return new Mul();
    }
}

// ConcreteCreator 角色，具体实现 Creator 中的方法
class DivFactory implements OperationFactory {
    @Override
    public Operation factoryMethod() {
        return new Div();
    }
}

【Client 角色】

与简单工厂模式中无需关注具体创建不同，工厂模式中需要指定具体工厂，以负责生产具体对应的产品。

1
2
3
4
5
6
7
8
9
10
11
// Client 角色，需要指定具体工厂，以负责生产具体产品
public class factoryMethodPattern {
    public static void main(String[] args) {
        OperationFactory factory = new SubFactory();
        Operation oper = factory.factoryMethod();
        oper.numA = 3;
        oper.numB = 2;
        double result = oper.getResult();
        System.out.println("result = " + result);
    }
}

与其他模式的关系

参考资料

发表于 更新于 分类于 ， 本文字数： 2.2k 阅读时长 ≈ 2 分钟

设计模式之简单工厂模式

简介

简单工厂模式思想

简单工厂模式 (Simple Factory) 又叫静态工厂方法（Static Factory Method）模式。

简单工厂模式通常是定义一个工厂类，这个类可以根据不同变量返回不同类的产品实例。

简单工厂模式是一种对象创建型模式。但是简单工厂模式不属于23 种 Gof 设计模式之一。

简单工厂模式要点

优点：简单工厂模式的工厂类是整个模式的关键。其中包含了必要的逻辑判断，根据外部信息，决定究竟应该创建哪个具体类的对象。通过使用简单工厂模式，用户无需了解对象如何创建的，只要传入必要信息就可以了。

缺点：工厂类集中了所有实例的创建逻辑，违背了高内聚责任分配原则。随着系统中具体产品类不断增多，势必要不断修改工厂类，不易维护和扩展。同时，这也违背了开放封闭原则。

开放封闭原则：一个软件实体如类、模块和函数应该对扩展开放，对修改关闭。

实例

如何实现一个具有加减乘除基本功能的计算器？

对于这四种运算来说，都需要两个操作数，差别仅在于返回的结果不同。

由此，我们可以抽象化它们的共性，提炼出一个父类。这个类中包含两个操作数，一个返回结果方法，这个方法期望在子类中得以实现。

以下通过具体代码来说明。

img

【Product (Operation) 】

产品角色，简单工厂模式所创建的所有对象的父类，它负责描述所有实例所共有的公共接口。

1
2
3
4
5
6
// Product角色，所有实例所共有的公共接口
abstract class Operation {
    public int numA;
    public int numB;
    public abstract int GetResult();
}

【ConcreteProduct 组】

具体产品角色，实现 Product 中的接口。

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
// ConcreteProduct 角色，实现 Product 中的接口
class Add extends Operation {
    @Override
    public int GetResult() {
        return numA + numB;
    }
}

//ConcreteProduct 角色，实现 Product 中的接口
class Sub extends Operation {
    @Override
    public int GetResult() {
        return numA - numB;
    }
}

//ConcreteProduct 角色，实现 Product 中的接口
class Mul extends Operation {
    @Override
    public int GetResult() {
        return numA * numB;
    }
}

//ConcreteProduct 角色，实现 Product 中的接口
class Div extends Operation {
    @Override
    public int GetResult() {
        if (numB == 0) {
            System.out.println("ERROR!");
            return -1;
        }
        return numA / numB;
    }
}

【Factory (OperationFactory) 】

工厂角色，简单工厂模式的核心，它负责实现创建所有实例的内部逻辑。工厂类的创建产品类的方法可以被外界直接调用，创建所需的产品对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 工厂角色，简单工厂模式的核心，它负责实现创建所有实例的内部逻辑
class OperationFactory {
    public static Operation CreateOperation (char operate) {
        Operation oper = null;
        switch(operate) {
        case '+':
            oper = new Add();
            break;
        case '-':
            oper = new Sub();
            break;
        case '*':
            oper = new Mul();
            break;
        case '/':
            oper = new Div();
            break;
        default:
            break;
        }
        return oper;
    }
}

【客户端】

1
2
3
4
5
6
7
8
9
10
11
12
public class SimpleFactoryPattern {
    public static void main(String[] args) {
        int numA = 10;
        int numB = 3;
        int result = 0;
        Operation oper = OperationFactory.CreateOperation('+');
        oper.numA = numA;
        oper.numB = numB;
        result = oper.GetResult();
        System.out.println(numA + " + " + numB + " = " + result);
    }
}

【输出】

1
10 + 3 = 13

参考资料

发表于 更新于 分类于 ， 本文字数： 4.9k 阅读时长 ≈ 4 分钟

设计模式之单例模式

意图

单例模式（Singleton）是一种创建型设计模式， 让你能够保证一个类只有一个实例， 并提供一个访问该实例的全局节点。

单例 （Singleton） 类声明了一个名为 get­Instance 获取实例的静态方法来返回其所属类的一个相同实例。

单例的构造函数必须对客户端 （Client） 代码隐藏。 调用 get­Instance 方法必须是获取单例对象的唯一方式。

所有单例的实现都包含以下两个相同的步骤：

  • 将默认构造函数设为私有， 防止其他对象使用单例类的 new运算符。
  • 新建一个静态构建方法作为构造函数。 该函数会 “偷偷” 调用私有构造函数来创建对象， 并将其保存在一个静态成员变量中。 此后所有对于该函数的调用都将返回这一缓存对象。

如果你的代码能够访问单例类， 那它就能调用单例类的静态方法。 无论何时调用该方法， 它总是会返回相同的对象。

单例模式的优点：

  • ✔️️️ 你可以保证一个类只有一个实例。
  • ✔️️️ 你获得了一个指向该实例的全局访问节点。
  • ✔️️️ 仅在首次请求单例对象时对其进行初始化。

单例模式的缺点：

  • ❌ 违反了单一职责原则。 该模式同时解决了两个问题。
  • ❌ 单例模式可能掩盖不良设计， 比如程序各组件之间相互了解过多等。
  • ❌ 该模式在多线程环境下需要进行特殊处理， 避免多个线程多次创建单例对象。
  • ❌ 单例的客户端代码单元测试可能会比较困难， 因为许多测试框架以基于继承的方式创建模拟对象。 由于单例类的构造函数是私有的， 而且绝大部分语言无法重写静态方法， 所以你需要想出仔细考虑模拟单例的方法。 要么干脆不编写测试代码， 或者不使用单例模式。

适用场景

  • 如果程序中的某个类对于所有客户端只有一个可用的实例， 可以使用单例模式。
    ⚡ 单例模式禁止通过除特殊构建方法以外的任何方式来创建自身类的对象。 该方法可以创建一个新对象， 但如果该对象已经被创建， 则返回已有的对象。
  • 如果你需要更加严格地控制全局变量， 可以使用单例模式。
    ⚡ 单例模式与全局变量不同， 它保证类只存在一个实例。 除了单例类自己以外， 无法通过任何方式替换缓存的实例。

请注意， 你可以随时调整限制并设定生成单例实例的数量， 只需修改 获取实例 方法， 即 getInstance 中的代码即可实现。

举例来说，一些资源管理器常常设计成单例模式。

在计算机系统中，需要管理的资源包括软件外部资源，譬如每台计算机可以有若干个打印机，但只能有一个 Printer Spooler， 以避免两个打印作业同时输出到打印机中。

每台计算机可以有若干通信端口，系统应当集中管理这些通信端口，以避免一个通信端口同时被两个请求同时调用。任务管理器中难以启动两个相同的 task。

结构

img

  1. 单例 （Singleton） 类声明了一个名为 get­Instance获取实例的静态方法来返回其所属类的一个相同实例。
    • 单例的构造函数必须对客户端 （Client） 代码隐藏。 调用 获取实例方法必须是获取单例对象的唯一方式。

伪代码

在本例中， 数据库连接类即是一个单例。

该类不提供公有构造函数， 因此获取该对象的唯一方式是调用 获取实例方法。 该方法将缓存首次生成的对象， 并为所有后续调用返回该对象。

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
// 数据库类会对`getInstance（获取实例）`方法进行定义以让客户端在程序各处
// 都能访问相同的数据库连接实例。
class Database is
    // 保存单例实例的成员变量必须被声明为静态类型。
    private static field instance: Database

    // 单例的构造函数必须永远是私有类型，以防止使用`new`运算符直接调用构
    // 造方法。
    private constructor Database() is
        // 部分初始化代码（例如到数据库服务器的实际连接）。
        // ...

    // 用于控制对单例实例的访问权限的静态方法。
    public static method getInstance() is
        if (Database.instance == null) then
            acquireThreadLock() and then
                // 确保在该线程等待解锁时，其他线程没有初始化该实例。
                if (Database.instance == null) then
                    Database.instance = new Database()
        return Database.instance

    // 最后，任何单例都必须定义一些可在其实例上执行的业务逻辑。
    public method query(sql) is
        // 比如应用的所有数据库查询请求都需要通过该方法进行。因此，你可以
        // 在这里添加限流或缓冲逻辑。
        // ...

class Application is
    method main() is
        Database foo = Database.getInstance()
        foo.query("SELECT ...")
        // ...
        Database bar = Database.getInstance()
        bar.query("SELECT ...")
        // 变量 `bar` 和 `foo` 中将包含同一个对象。

案例

使用示例： 许多开发者将单例模式视为一种反模式。 因此它在 Java 代码中的使用频率正在逐步减少。

尽管如此， Java 核心程序库中仍有相当多的单例示例：

识别方法： 单例可以通过返回相同缓存对象的静态构建方法来识别。

数据库连接类

数据库连接类即是一个单例。

该类不提供公有构造函数， 因此获取该对象的唯一方式是调用 获取实例方法。 该方法将缓存首次生成的对象， 并为所有后续调用返回该对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 数据库类会对`getInstance（获取实例）`方法进行定义以让客户端在程序各处
// 都能访问相同的数据库连接实例。
class Database is
    // 保存单例实例的成员变量必须被声明为静态类型。
    private static field instance: Database

    // 单例的构造函数必须永远是私有类型，以防止使用`new`运算符直接调用构
    // 造方法。
    private constructor Database() is
        // 部分初始化代码（例如到数据库服务器的实际连接）。
        // ...

    // 用于控制对单例实例的访问权限的静态方法。
    public static method getInstance() is
        if (Database.instance == null) then
            acquireThreadLock() and then
                // 确保在该线程等待解锁时，其他线程没有初始化该实例。
                if (Database.instance == null) then
                    Database.instance = new Database()
        return Database.instance

    // 最后，任何单例都必须定义一些可在其实例上执行的业务逻辑。
    public method query(sql) is
        // 比如应用的所有数据库查询请求都需要通过该方法进行。因此，你可以
        // 在这里添加限流或缓冲逻辑。
        // ...

class Application is
    method main() is
        Database foo = Database.getInstance()
        foo.query("SELECT ...")
        // ...
        Database bar = Database.getInstance()
        bar.query("SELECT ...")
        // 变量 `bar` 和 `foo` 中将包含同一个对象。

懒汉式

懒汉式的实现思路是：你不找懒汉，懒汉根本就懒得去初始化自己。

instance 初始时没有初始化，只有当第一次调 getInstance() 时才创建实例。

缺点：当有两个线程调 getInstance() 方法，当它们同时执行到 if (null == instance) 这行代码，instance 为 null。

继续向下执行，会生成两个实例，违背了单例模式的初衷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LazySingleton {
    private LazySingleton() {
        System.out.println("Singleton()");
    }

    private static LazySingleton instance = null;

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

饿汉式

懒汉式的实现思路是：饿汉根本等不及别人来找他，不管三七二十一先初始化了自身的实例，生怕自己饿着了。

类默认先直接初始化一个实例，以后调用 getInstance() 总是返回这个已创建好的实例。

缺点：在没有必要获取实例时，已经预先产生了开销。

优点：规避了懒汉式方法的线程问题，不用显示编写线程安全代码。

1
2
3
4
5
6
7
8
9
10
11
public class HungerSinleton {
    private HungerSinleton() {
        System.out.println("Singleton()");
    }

    private static HungerSinleton instance = new HungerSinleton();

    public static HungerSinleton getInstance() {
        return instance;
    }
}

双重锁的形式

如果既不想在没有调用 getInstance() 方法时产生开销，又不想发生线程安全问题，就可以采用双重锁的形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class SyncSingleton {
    private SyncSingleton() {
        System.out.println("Singleton()");
    }

    private static SyncSingleton instance = null;

    public static SyncSingleton getInstance() {
        if (null == instance) {
            synchronized(SyncSingleton.class) {
                if (null == instance) {
                    instance = new SyncSingleton();
                }
            }
        }
        return instance;
    }
}

注：在外面判断了 instance 实例是否存在，为什么在锁定后又要在内部又判断一次？

这是因为，如果 instance 为 null 时有两个线程同时调用 getInstance()，由于 synchronized 机制，只允许一个线程进入，另一个需要等待。

这时如果没有第二道 instance 是否为 null 的判断，就可能发生第一个线程创建一个实例，而第二个线程又创建一个实例的情况。

与其他模式的关系

  • 外观模式类通常可以转换为单例模式类， 因为在大部分情况下一个外观对象就足够了。
  • 如果你能将对象的所有共享状态简化为一个享元对象， 那么享元模式就和单例类似了。 但这两个模式有两个根本性的不同。
    1. 只会有一个单例实体， 但是享元类可以有多个实体， 各实体的内在状态也可以不同。
    2. 单例对象可以是可变的。 享元对象是不可变的。
  • 抽象工厂模式、 生成器模式和原型模式都可以用单例来实现。

参考资料

发表于 更新于 分类于 ， 本文字数： 6.2k 阅读时长 ≈ 6 分钟

数组和链表

数组和链表分别代表了连续空间和不连续空间的存储方式，它们是线性表（Linear List）的典型代表。其他所有的数据结构，比如栈、队列、二叉树、B+ 树等，实际上都是这两者的结合和变化。

数组

数组用 连续 的内存空间来存储数据。

数组的访问

数组元素的访问是以行或列索引的单一下标表示。

img

在上面的例子中，数组 a 中有 5 个元素。也就是说，a 的长度是 6 。我们可以使用 a[0] 来表示数组中的第一个元素。因此，a[0] = A 。类似地，a[1] = B，a[2] = C，依此类推。

数组的插入

img

数组的删除

img

数组的特性

数组设计之初是在形式上依赖内存分配而成的，所以必须在使用前预先分配好空间大小。这使得数组有以下特性：

  1. 用连续的内存空间来存储数据。
  2. **数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)**。
  3. **数组的插入、删除操作，平均时间复杂度为 O(n)**。
  4. 空间大小固定，一旦建立，不能再改变。扩容只能采用复制数组的方式。
  5. 在旧式编程语言中（如有中阶语言之称的 C），程序不会对数组的操作做下界判断，也就有潜在的越界操作的风险。

多维数组

数组是有下标和值组成集合。

如果数组的下标有多个维度，即为多维数组。比如：二维数组可以视为“数组元素为一维数组”的一维数组；三维数组可以视为“数组元素为二维数组”的一维数组；依次类推。

下图是由 M 个行向量，N 个列向量组成的二维数组.

img

链表

链表用不连续的内存空间来存储数据；并通过一个指针按顺序将这些空间串起来，形成一条链。

区别于数组，链表中的元素不是存储在内存中连续的一片区域，链表中的数据存储在每一个称之为“结点”复合区域里，在每一个结点除了存储数据以外，还保存了到下一个节点的指针（Pointer）。由于不必按顺序存储，链表在插入数据的时候可以达到 O(1) 的复杂度，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间。

链表具有以下特性：

  • 链表允许插入和移除任意位置上的节点，其时间复杂度为 O(1)
  • 链表没有数组的随机访问特性，链表只支持顺序访问，其时间复杂度为 O(n)。
  • 数组的空间大小是固定的，而链表的空间大小可以动态增长。相比于数组，链表支持扩容，显然更为灵活，但是由于多了指针域，空间开销也更大。
  • 链表相比于数组，多了头指针、尾指针（非必要），合理使用可以大大提高访问效率。

链表有多种类型：

  • 单链表
  • 双链表
  • 循环链表

单链表

单链表中的每个结点不仅包含数据值，还包含一个指针，指向其后继节点。通过这种方式，单链表将所有结点按顺序组织起来。

img

与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按 索引 来 访问元素 平均要花费 O(N) 时间，其中 N 是链表的长度。

单链表插入

如果我们想在给定的结点 prev 之后添加新值，我们应该：

（1）使用给定值初始化新结点 cur；

img

（2）将 cur 的 next 字段链接到 prev 的下一个结点 next ；

img

（3）将 prev 中的 next 字段链接到 cur 。

img

与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。

单链表删除

如果我们想从单链表中删除现有结点 cur，可以分两步完成：

（1）找到 cur 的上一个结点 prev 及其下一个结点 next ；

img

（2）接下来链接 prev 到 cur 的下一个节点 next 。

img

在我们的第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。

空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。

双链表

双链表中的每个结点不仅包含数据值，还包含两个指针，分别指向指向其前驱节点和后继节点。

单链表的访问是单向的，而双链表的访问是双向的。显然，双链表比单链表操作更灵活，但是空间开销也更大。

img

双链表以类似的方式工作，但还有一个引用字段，称为“prev”字段。有了这个额外的字段，您就能够知道当前结点的前一个结点。

双链表插入

如果我们想在给定的结点 prev 之后添加新值，我们应该：

（1）使用给定值初始化新结点 cur；

img

（2）链接 cur 与 prev 和 next，其中 next 是 prev 原始的下一个节点；

img

（3）用 cur 重新链接 prev 和 next。

img

与单链表类似，添加操作的时间和空间复杂度都是 O(1)。

双链表删除

如果我们想从双链表中删除一个现有的结点 cur，我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。

与单链表不同，使用 prev 字段可以很容易地在常量时间内获得前一个结点。

因为我们不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是 O(1)。

循环链表

循环单链表

循环单链表是一种特殊的单链表。它和单链表唯一的区别就在最后结点。

  • 单链表的最后一个结点的后继指针 next 指向空地址。
  • 循环链表的最后一个结点的后继指针 next 指向第一个节点（如果有头节点，就指向头节点）。

img

循环双链表

img

数组 vs. 链表

  • 存储方式
    • 数组用 连续 的内存空间来存储数据。
    • 链表用 不连续 的内存空间来存储数据；并通过一个指针按顺序将这些空间串起来，形成一条链。
  • 访问方式
    • 数组支持随机访问。根据下标随机访问的时间复杂度为 O(1)
    • 链表不支持随机访问，只能顺序访问，时间复杂度为 O(n)。
  • 空间大小
    • 数组空间大小固定，扩容只能采用复制数组的方式。
    • 链表空间大小不固定，扩容灵活。
  • 效率比较
    • 数组的 查找 效率高于链表。
    • 链表的 添加、删除 效率高于数组。

数组和链表的基本操作示例

关于数组和链表的基本操作，网上和各种书籍、教程中已经有大量的示例，感兴趣可以自行搜索。本文只是简单展示一下数组和链表的基本操作。

一维数组的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Main {
    public static void main(String[] args) {
        // 1. Initialize
        int[] a0 = new int[5];
        int[] a1 = {1, 2, 3};
        // 2. Get Length
        System.out.println("The size of a1 is: " + a1.length);
        // 3. Access Element
        System.out.println("The first element is: " + a1[0]);
        // 4. Iterate all Elements
        System.out.print("[Version 1] The contents of a1 are:");
        for (int i = 0; i < a1.length; ++i) {
            System.out.print(" " + a1[i]);
        }
        System.out.println();
        System.out.print("[Version 2] The contents of a1 are:");
        for (int item: a1) {
            System.out.print(" " + item);
        }
        System.out.println();
        // 5. Modify Element
        a1[0] = 4;
        // 6. Sort
        Arrays.sort(a1);
    }
}

二维数组的基本操作

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
public class TwoDimensionArray {
    private static void printArray(int[][] a) {
        for (int i = 0; i < a.length; ++i) {
            System.out.println(a[i]);
        }
        for (int i = 0; i < a.length; ++i) {
            for (int j = 0; a[i] != null && j < a[i].length; ++j) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        System.out.println("Example I:");
        int[][] a = new int[2][5];
        printArray(a);
        System.out.println("Example II:");
        int[][] b = new int[2][];
        printArray(b);
        System.out.println("Example III:");
        b[0] = new int[3];
        b[1] = new int[5];
        printArray(b);
    }
}

单链表的基本操作

单链表节点的数据结构

1
2
3
4
5
6
7
8
public class ListNode<E> {
    E value;
    ListNode<E> next; // 指向后继节点
}

public class SingleLinkList<E> {
    private ListNode<E> head; // 头节点
}

（1）从头部添加节点（即头插法）

1
2
3
4
5
void addHead(E value) {
    ListNode<E> newNode = new ListNode<>(value, null);
    newNode.next = this.head.next;
    this.head.next = newNode;
}

（2）从尾部添加节点（即尾插法）

1
2
3
4
5
6
7
8
9
10
11
12
13
void addTail(E value) {
    // init new node
    ListNode<E> newNode = new ListNode<>(value, null);

    // find the last node
    ListNode<E> node = this.head;
    while (node.next != null) {
        node = node.next;
    }

    // add new node to tail
    node.next = newNode;
}

（3）删除节点

找到要删除元素的前驱节点，将前驱节点的 next 指针指向下一个节点。

1
2
3
4
5
6
7
8
9
10
11
public void remove(E value) {
    ListNode<E> prev = this.head;
    while (prev.next != null) {
        ListNode<E> curr = prev.next;
        if (curr.value.equals(value)) {
            prev.next = curr.next;
            break;
        }
        prev = prev.next;
    }
}

（4）查找节点

从头开始查找，一旦发现有数值与查找值相等的节点，直接返回此节点。如果遍历结束，表明未找到节点，返回 null。

1
2
3
4
5
6
7
8
9
10
public ListNode<E> find(E value) {
    ListNode<E> node = this.head.next;
    while (node != null) {
        if (node.value.equals(value)) {
            return node;
        }
        node = node.next;
    }
    return null;
}

双链表的基本操作

双链表节点的数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
static class DListNode<E> {
    E value;
    DListNode<E> prev; // 指向前驱节点
    DListNode<E> next; // 指向后继节点
}

public class DoubleLinkList<E> {
    /** 头节点 */
    private DListNode<E> head;
    /** 尾节点 */
    private DListNode<E> tail;
}

（1）从头部添加节点

1
2
3
4
5
6
7
8
9
public void addHead(E value) {
    DListNode<E> newNode = new DListNode<>(null, value, null);

    this.head.next.prev = newNode;
    newNode.next = this.head.next;

    this.head.next = newNode;
    newNode.prev = this.head;
}

（2）从尾部添加节点

1
2
3
4
5
6
7
8
9
public void addTail(E value) {
    DListNode<E> newNode = new DListNode<>(null, value, null);

    this.tail.prev.next = newNode;
    newNode.prev = this.tail.prev;

    this.tail.prev = newNode;
    newNode.next = this.tail;
}

（3）删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void remove(E value) {
    DListNode<E> prev = this.head;
    while (prev.next != this.tail) {
        DListNode<E> curr = prev.next;
        if (curr.value.equals(value)) {
            prev.next = curr.next;
            curr.next.prev = prev;
            curr.next = null;
            curr.prev = null;
            break;
        }
        prev = prev.next;
    }
}

（4）查找节点

1
2
3
4
5
6
7
8
9
10
public DListNode<E> find(E value) {
    DListNode<E> node = this.head.next;
    while (node != this.tail) {
        if (node.value.equals(value)) {
            return node;
        }
        node = node.next;
    }
    return null;
}

练习

参考资料

发表于 更新于 分类于 本文字数： 1.2k 阅读时长 ≈ 1 分钟

图

在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。

img

什么是图

  • 阶（Order） - 图 G 中点集 V 的大小称作图 G 的阶。
  • 子图（Sub-Graph） - 当图 G’=(V’,E’)其中 V‘包含于 V，E’包含于 E，则 G’称作图 G=(V,E)的子图。每个图都是本身的子图。
  • 生成子图（Spanning Sub-Graph） - 指满足条件 V(G’) = V(G)的 G 的子图 G’。
  • 导出子图（Induced Subgraph） - 以图 G 的顶点集 V 的非空子集V1 为顶点集，以两端点均在 V1 中的全体边为边集的 G 的子图，称为 V1 导出的导出子图；以图 G 的边集 E 的非空子集 E1 为边集，以 E1 中边关联的顶点的全体为顶点集的 G 的子图，称为 E1 导出的导出子图。
  • 有向图 - 如果给图的每条边规定一个方向，那么得到的图称为有向图。
  • 无向图 - 边没有方向的图称为无向图。
  • 度（Degree） - 一个顶点的度是指与该顶点相关联的边的条数，顶点 v 的度记作 d(v)。
  • 入度（In-degree）和出度（Out-degree） - 对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。
  • 自环（Loop） - 若一条边的两个顶点为同一顶点，则此边称作自环。
  • 路径（Path） - 从 u 到 v 的一条路径是指一个序列 v0,e1,v1,e2,v2,…ek,vk，其中 ei 的顶点为 vi 及 vi - 1，k 称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。
  • 行迹（Trace） - 如果路径 P(u,v)中的边各不相同，则该路径称为 u 到 v 的一条行迹。闭的行迹称作回路（Circuit）。
  • 轨迹（Track） - 如果路径 P(u,v)中的顶点各不相同，则该路径称为 u 到 v 的一条轨迹。闭的轨迹称作圈（Cycle）。
  • 桥（Bridge） - 若去掉一条边，便会使得整个图不连通，该边称为桥。

如果图的边没有方向性，则被成为无向图。

img

图的基本操作

  • 创建一个图结构 - CreateGraph(G)
  • 检索给定顶点 - LocateVex(G,elem)
  • 获取图中某个顶点 - GetVex(G,v)
  • 为图中顶点赋值 - PutVex(G,v,value)
  • 返回第一个邻接点 - FirstAdjVex(G,v)
  • 返回下一个邻接点 - NextAdjVex(G,v,w)
  • 插入一个顶点 - InsertVex(G,v)
  • 删除一个顶点 - DeleteVex(G,v)
  • 插入一条边 - InsertEdge(G,v,w)
  • 删除一条边 - DeleteEdge(G,v,w)
  • 遍历图 - Traverse(G,v)

参考资料

发表于 更新于 分类于 本文字数： 3.5k 阅读时长 ≈ 3 分钟

哈希表

哈希表 是一种使用 哈希函数 组织数据，以支持快速插入和搜索的数据结构。

有两种不同类型的哈希表：哈希集合 和 哈希映射。

  • 哈希集合 是集合数据结构的实现之一，用于存储非重复值。
  • 哈希映射 是映射 数据结构的实现之一，用于存储(key, value)键值对。

什么是哈希表

哈希表的英文叫“Hash Table”，我们平时也叫它“散列表”或者“Hash 表”。

哈希表 是一种使用 哈希函数 组织数据，以支持快速插入和搜索的数据结构。

有两种不同类型的哈希表：哈希集合 和 哈希映射。

  • 哈希集合 是集合数据结构的实现之一，用于存储非重复值。
  • 哈希映射 是映射 数据结构的实现之一，用于存储(key, value)键值对。

哈希表用的是数组支持按照下标随机访问数据的特性，所以哈希表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有哈希表。

img

哈希表通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。按照键值查询元素时，用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

有两种不同类型的哈希表：哈希集合和哈希映射。

  • 哈希集合是集合数据结构的实现之一，用于存储非重复值。
  • 哈希映射是映射 数据结构的实现之一，用于存储(key, value)键值对。

在标准模板库的帮助下，哈希表是易于使用的。大多数常见语言（如 Java，C ++ 和 Python）都支持哈希集合和哈希映射。

散列函数

散列函数，顾名思义，它是一个函数。我们可以把它定义成 **hash(key)**，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。

哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说，

  1. 当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
  2. 当我们想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索。

散列函数将取决于 键值的范围 和 桶的数量 。

散列函数设计的基本要求：

  1. 散列函数计算得到的散列值是一个非负整数；
  2. 如果 key1 = key2，那 hash(key1) == hash(key2)；
  3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

散列冲突

即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。

该如何解决散列冲突问题呢？我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

装载因子

当哈希表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证哈希表的操作效率，一般情况下，我们会尽可能保证哈希表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。

装载因子的计算公式是：

1
哈希表的装载因子 = 填入表中的元素个数 / 哈希表的长度

装载因子越大，说明空闲位置越少，冲突越多，哈希表的性能会下降。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。

当装载因子过大时，就需要对哈希表扩容。新申请一个更大的哈希表，将数据搬移到这个新哈希表中。针对数组的扩容，数据搬移操作比较简单。但是，针对哈希表的扩容，数据搬移操作要复杂很多。因为哈希表的大小变了，数据的存储位置也变了，所以我们需要通过散列函数重新计算每个数据的存储位置。

插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 O(1)。最坏情况下，哈希表装载因子过高，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数据，所以时间复杂度是 O(n)。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是 O(1)。

装载因子阈值需要选择得当。如果太大，会导致冲突过多；如果太小，会导致内存浪费严重。

开放寻址法

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。

当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的 ThreadLocalMap 使用开放寻址法解决散列冲突的原因。

线性探测（Linear Probing）：当我们往哈希表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

对于使用线性探测法解决冲突的哈希表，删除操作稍微有些特别。我们不能单纯地把要删除的元素设置为空。这是为什么呢？在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定哈希表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。这个问题如何解决呢？

我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。

线性探测法其实存在很大问题。当哈希表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个哈希表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张哈希表，才能找到要查找或者删除的数据。

链表法

在哈希表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

链表法比起开放寻址法，对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于 1 的情况。接近 1 时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成 10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的哈希表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。那查找或删除操作的时间复杂度是多少呢？

实际上，这两个操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示哈希表中“槽”的个数。

开放寻址法 vs. 链表法

开放寻址法适用于数据量比较小、装载因子小的场景。

链表法适用于存储大对象、大数据量的哈希表。比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

哈希表的应用场景

哈希算法的应用非常非常多，最常见的七个，分别是：

  • 安全加密：如：MD5、SHA
  • 唯一标识：UUID
  • 数据校验：数字签名
  • 散列函数：
  • 负载均衡：会话粘滞（session sticky）负载均衡算法。可以通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。 这样，我们就可以把同一个 IP 过来的所有请求，都路由到同一个后端服务器上。
  • 数据分片
  • 分布式存储：一致性哈希算法、虚拟哈希槽

典型应用场景

Java 的 HashMap 工具类，其

  • HashMap 默认的初始大小是 16
  • 最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示哈希表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。
  • HashMap 底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现链表过长的情况，一旦出现链表过长，则会严重影响 HashMap 的性能。在 JDK1.8 版本中，对 HashMap 做了进一步优化：引入了红黑树。当链表长度太长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。

练习

Leetcode 练习题：

思考

  1. 假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？
  2. 有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？

参考资料

发表于 更新于 分类于 ， 本文字数： 318 阅读时长 ≈ 1 分钟

数据结构和算法指南

1. 为什么学习数据结构和算法

  • 为了找到一份好工作：大厂面试喜欢考算法
  • 更深入了解流行技术的设计思想：数据结构和算法是计算机基础学科，很多框架、中间、底层系统设的设计，都借鉴了其思想。因此，掌握数据结构和算法，有利于更深入了解这些技术的设计思想。
  • 提升个人的编程水平
  • 不满足于做业务狗，拓展性能思考的视角

2. 如何学习数据结构和算法

数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。

数据结构和算法是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。

先要学会复杂度分析，才能识别数据结构和算法的利弊。

  • 循序渐进
  • 边学边练，适度刷题
  • 学习并思考：学而不思则罔，思而不学则殆
  • 知识需要沉淀，不要想试图一下子掌握所有

发表于 更新于 分类于 ， 本文字数： 4.6k 阅读时长 ≈ 4 分钟

线性表的查找

查找简介

什么是查找？

查找是根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。

查找算法的分类

若在查找的同时对表记录做修改操作（如插入和删除），则相应的表称之为动态查找表；

否则，称之为静态查找表。

此外，如果查找的全过程都在内存中进行，称之为内查找；

反之，如果查找过程中需要访问外存，称之为外查找。

查找算法性能比较的标准

——平均查找长度 ASL（Average Search Length）

由于查找算法的主要运算是关键字的比较过程，所以通常把查找过程中对关键字需要执行的平均比较长度（也称为平均比较次数）作为衡量一个查找算法效率优劣的比较标准。

img

选取查找算法的因素

(1) 使用什么数据存储结构（如线性表、树形表等）。

(2) 表中的次序，即对无序表还是有序表进行查找。

顺序查找

要点

它是一种最简单的查找算法，效率也很低下。

存储结构

没有存储结构要求，可以无序，也可以有序。

基本思想

从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值 k 相比较，若相等则表示查找成功；

若扫描结束仍没有找到关键字等于 k 的结点，表示查找失败。

核心代码

1
2
3
4
5
6
7
8
9
10
11
public int orderSearch(int[] list, int length, int key) {
    // 从前往后扫描list数组，如果有元素的值与key相等，直接返回其位置
    for (int i = 0; i < length; i++) {
        if (key == list[i]) {
            return i;
        }
    }

    // 如果扫描完，说明没有元素的值匹配key，返回-1，表示查找失败
    return -1;
}

算法分析

顺序查找算法最好的情况是，第一个记录即匹配关键字，则需要比较 1 次；

最坏的情况是，最后一个记录匹配关键字，则需要比较 N 次。

所以，顺序查找算法的平均查找长度为

ASL = (N + N-1 + … + 2 + 1) / N = (N+1) / 2

顺序查找的平均时间复杂度为**O(N)**。

二分查找

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

存储结构

使用二分查找需要两个前提：

(1) 必须是顺序存储结构。

(2) 必须是有序的表。

基本思想

首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；

否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int binarySearch(int[] list, int length, int key) {
    int low = 0, mid = 0, high = length - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (list[mid] == key) {
            return mid; // 查找成功，直接返回位置
        } else if (list[mid] < key) {
            low = mid + 1; // 关键字大于中间位置的值，则在大值区间[mid+1, high]继续查找
        } else {
            high = mid - 1; // 关键字小于中间位置的值，则在小值区间[low, mid-1]继续查找
        }
    }
    return -1;
}

算法分析

二分查找的过程可看成一个二叉树。

把查找区间的中间位置视为树的根，左区间和右区间视为根的左子树和右子树。

由此得到的二叉树，称为二分查找的判定树或比较树。

由此可知，二分查找的平均查找长度实际上就是树的高度**O(log2N)**。

二分查找的局限性

  • 二分查找依赖的是顺序表结构，简单点说就是数组
  • 二分查找针对的是有序数据
  • 数据量太小不适合二分查找
  • 数据量太大也不适合二分查找

分块查找

要点

分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。

分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。

存储结构

分块查找表是由“分块有序”的线性表和索引表两部分构成的。

所谓“分块有序”的线性表，是指：

假设要排序的表为 R[0…N-1]，将表均匀分成 b 块，前 b-1 块中记录个数为 s=N/b，最后一块记录数小于等于 s；

每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字。

注：这是使用分块查找的前提条件。

如上将表均匀分成 b 块后，抽取各块中的最大关键字和起始位置构成一个索引表 IDX[0…b-1]。

由于表 R 是分块有序的，所以索引表是一个递增有序表。

下图就是一个分块查找表的存储结构示意图

img

基本思想

分块查找算法有两个处理步骤：

(1) 首先查找索引表

因为分块查找表是“分块有序”的，所以我们可以通过索引表来锁定关键字所在的区间。

又因为索引表是递增有序的，所以查找索引可以使用顺序查找或二分查找。

(2) 然后在已确定的块中进行顺序查找

因为块中不一定是有序的，所以只能使用顺序查找。

代码范例

img

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
class BlockSearch {

    class IndexType {
        public int key; // 分块中的最大值
        public int link; // 分块的起始位置
    }

    // 建立索引方法，n 是线性表最大长度，gap是分块的最大长度
    public IndexType[] createIndex(int[] list, int n, int gap) {
        int i = 0, j = 0, max = 0;
        int num = n / gap;
        IndexType[] idxGroup = new IndexType[num]; // 根据步长数分配索引数组大小

        while (i < num) {
            j = 0;
            idxGroup[i] = new IndexType();
            idxGroup[i].link = gap * i; // 确定当前索引组的第一个元素位置
            max = list[gap * i]; // 每次假设当前组的第一个数为最大值
            // 遍历这个分块，找到最大值
            while (j < gap) {
                if (max < list[gap * i + j]) {
                    max = list[gap * i + j];
                }
                j++;
            }
            idxGroup[i].key = max;
            i++;
        }

        return idxGroup;
    }

    // 分块查找算法
    public int blockSearch(IndexType[] idxGroup, int m, int[] list, int n, int key) {
        int mid = 0;
        int low = 0;
        int high = m -1;
        int gap = n / m; // 分块大小等于线性表长度除以组数

        // 先在索引表中进行二分查找，找到的位置存放在 low 中
        while (low <= high) {
            mid = (low + high) / 2;
            if (idxGroup[mid].key >= key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        // 在索引表中查找成功后，再在线性表的指定块中进行顺序查找
        if (low < m) {
            for (int i = idxGroup[low].link; i < idxGroup[low].link + gap; i++) {
                if (list[i] == key)
                    return i;
            }
        }

        return -1;
    }

    // 打印完整序列
    public void printAll(int[] list) {
        for (int value : list) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    // 打印索引表
    public void printIDX(IndexType[] list) {
        System.out.println("构造索引表如下：");
        for (IndexType elem : list) {
            System.out.format("key = %d, link = %d\n", elem.key, elem.link);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int key = 85;
        int array2[] = { 8, 14, 6, 9, 10, 22, 34, 18, 19, 31, 40, 38, 54, 66, 46, 71, 78, 68, 80, 85 };
        BlockSearch search = new BlockSearch();

        System.out.print("线性表: ");
        search.printAll(array2);

        IndexType[] idxGroup = search.createIndex(array2, array2.length, 5);
        search.printIDX(idxGroup);
        int pos = search.blockSearch(idxGroup, idxGroup.length, array2,
                array2.length, key);
        if (-1 == pos) {
            System.out.format("查找key = %d失败", key);
        } else {
            System.out.format("查找key = %d成功，位置为%d", key, pos);
        }
    }

}

运行结果

1
2
3
4
5
6
7
8
线性表: 8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85
构造索引表如下：
key = 14, link = 0
key = 34, link = 5
key = 66, link = 10
key = 85, link = 15

查找key = 85成功，位置为19

算法分析

因为分块查找实际上是两次查找过程之和。若以二分查找来确定块，显然它的查找效率介于顺序查找和二分查找之间。

三种线性查找的 PK

(1) 以平均查找长度而言，二分查找 > 分块查找 > 顺序查找。

(2) 从适用性而言，顺序查找无限制条件，二分查找仅适用于有序表，分块查找要求“分块有序”。

(3) 从存储结构而言，顺序查找和分块查找既可用于顺序表也可用于链表；而二分查找只适用于顺序表。

(4) 分块查找综合了顺序查找和二分查找的优点，既可以较为快速，也能使用动态变化的要求。

参考资料

发表于 更新于 分类于 ， 本文字数： 741 阅读时长 ≈ 1 分钟

堆

什么是堆？

堆（Heap）是一个可以被看成近似完全二叉树的数组。

  • 堆是一个完全二叉树。完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
  • 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

堆可以分为大顶堆和小顶堆。

  • 对于每个节点的值都大于等于子树中每个节点值的堆，叫作“大顶堆”。

  • 对于每个节点的值都小于等于子树中每个节点值的堆，叫作“小顶堆”。

如何实现堆

完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

img

堆常见的操作：

  • HEAPIFY 建堆：把一个乱序的数组变成堆结构的数组，时间复杂度为 $$O(n)$$。
  • HEAPPUSH：把一个数值放进已经是堆结构的数组中，并保持堆结构，时间复杂度为 $$O(log N)$$
  • HEAPPOP：从最大堆中取出最大值或从最小堆中取出最小值，并将剩余的数组保持堆结构，时间复杂度为 $$O(log N)$$。
  • HEAPSORT：借由 HEAPFY 建堆和 HEAPPOP 堆数组进行排序，时间复杂度为$$ O(N log N)$$，空间复杂度为 $$O(1)$$。

堆的应用场景

求 TOP N

堆结构的一个常见应用是建立优先队列（Priority Queue）。

求 Top K 的问题抽象成两类。一类是针对静态数据集合；另一类是针对动态数据集合

优先级队列

在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队。

堆和优先级队列非常相似：往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。

参考：Java 的 PriorityQueue 类

求中位数