【设计模式】行为型设计模式汇总（一）

行为型设计模式范围

1. 观察者模式
2. 模板方法
3. 策略模式
4. 职责链模式
5. 状态模式
6. 迭代器模式
7. 访问者模式
8. 备忘录模式
9. 命令模式
10. 解释器模式
11. 中介模式

行为型设计模式作用

行为型设计模式主要关注的是类与类之间的交互问题。

1. 观察者模式

1.1 定义

在对象之间定义一个一对多的依赖，当一个对象状态改变的时候，所有依赖的对象都会自动收到通知。

1.2 作用

1. 将原本一个复杂的更新数据的方法，拆分成基于接口的多个粒度更小，职责更单一的小方法，降低代码实现的复杂性。
2. 由于是观察者是基于接口实现的，如果有新的逻辑加入进来时，只需要实现相应的接口，并完成注册就可以接收到更新数据的通知，提供了代码的扩展性。

1.3 类结构图

image

1.4 经典实现

public interface Subject {
    void registerObserver(Observer observer);

    void removeObserver(Observer observer);

    void notifyObservers(Message message);
}

public class ConcreteSubject implements Subject {
    private List<Observer> mObservers = new ArrayList<>();

    @Override
    public void registerObserver(Observer observer) {
        mObservers.add(observer);
    }

    @Override
    public void removeObserver(Observer observer) {
        mObservers.remove(observer);
    }

    @Override
    public void notifyObservers(Message message) {
        mObservers.forEach(observer -> {
            observer.update(message);
        });
    }
}

public interface Observer {
    void update(Message message);
}

public class ConcreteObserver1 implements Observer {
    @Override
    public void update(Message message) {
        System.out.println("Observer1: " + message.content);
    }
}

public class ConcreteObserver2 implements Observer {
    @Override
    public void update(Message message) {
        System.out.println("Observer2: " + message.content);
    }
}

public class Client {
    public static void main(String[] args) {
        Observer observer1 = new ConcreteObserver1();
        Observer observer2 = new ConcreteObserver2();
        Subject subject = new ConcreteSubject();
        subject.registerObserver(observer1);
        subject.registerObserver(observer2);
        Message message = new Message();
        message.content = "notified information";
        subject.notifyObservers(message);

    }
}

1.5 设计模式的本质

设计模式要干的事情就是解耦。创建型模式是将对象的创建与使用解耦，结构型模式是将不同功能代码解耦，行为型模式是将不同的行为代码解耦。

这里的观察者模式是将观察者与被观察者解耦。

1.6 观察都模式的种类

1. 同步阻塞

观察者和被观察者的代码都是在同一个线程中执行的。被观察都直到所有观察都的代码都执行完成后，才会继续往后执行代码。

2. 异步非阻塞

最简单的实现是在每个 update 方法中开启一个线程来执行更新。另外一种方式是直接在被观察者中使用一个线程池来执行对各观察者的调用。当然，可以使用事件总线 EventBus 来实现异步非阻塞的。

3. 进程内实现

主要分为同步阻塞和异步非阻塞两种情况。

4. 跨进程实现

在不同的系统中需要实现观察者模式的时候，有两种方法：

1. 直接调用 RPC 接口通知观察者
2. 使用消息队列（MessageQueue）来通知观察者

消息队列的具体做法是：被观察者向消息队列中发送更新消息，观察者从消息队列中取出消息来执行相应的业务逻辑。在这个过程中，被观察者感知不到观察者的存在，观察者也感知不到被观察者是存在，是一种更加彻底的解耦实现。

1.7 应用场景

EventBus

框架的作用

1. 隐藏实现细节
2. 降低开发难度
3. 代码复用
4. 解耦业务与非业务代码
5. 让程序员聚焦功能的开发

应用示例

public class UserController {
  private UserService userService; // 依赖注入

  private EventBus eventBus;
  private static final int DEFAULT_EVENTBUS_THREAD_POOL_SIZE = 20;

  public UserController() {
    //eventBus = new EventBus(); // 同步阻塞模式
    eventBus = new AsyncEventBus(Executors.newFixedThreadPool(DEFAULT_EVENTBUS_THREAD_POOL_SIZE)); // 异步非阻塞模式
  }

  public void setRegObservers(List<Object> observers) {
    for (Object observer : observers) {
      eventBus.register(observer);
    }
  }

  public Long register(String telephone, String password) {
    //省略输入参数的校验代码
    //省略userService.register()异常的try-catch代码
    long userId = userService.register(telephone, password);

    eventBus.post(userId);

    return userId;
  }
}

public class RegPromotionObserver {
  private PromotionService promotionService; // 依赖注入

  @Subscribe
  public void handleRegSuccess(Long userId) {
    promotionService.issueNewUserExperienceCash(userId);
  }
}

public class RegNotificationObserver {
  private NotificationService notificationService;

  @Subscribe
  public void handleRegSuccess(Long userId) {
    notificationService.sendInboxMessage(userId, "...");
  }
}

使用方法：

1. 通过调用 EventBus 的 register 方法进行注册工作
2. 通过 @Subscribe 来注册哪些方法用来接收更新
3. 通过 @Subscribe 所注册方法中的参数来判断 EventBus 发送的数据哪些注册了 EventBus 的哪些方法可以接收到此更新

与传统观察者不同的地方

1. 传统的实现中被观察者只接收实现了同一接口的观察者，而 EventBus 可以接收任何对象
2. 传统的实现中订阅了被观察者的观察者都能够接收到消息更新，而 EventBus 是根据 post 中的参数来匹配当前消息需要发送给哪些观察者的，是部分发送

EventBus 的注册过程

当调用 EventBus 的 register 方法将类对象作为 Observer 注册到 EventBus 时，EventBus 会扫描当前类对象中的所有使用了 @Subscribe 注解的方法，并获取方法中的参数类型，然后通过将参数类型与当前类对象和函数进行关联。当通过 EventBus 调用 post 方法发送消息时，就会通过当前发送消息的类型去之前的映射关系中找到对应的对象和函数，完成调用。

EventBus 核心实现原理图

image

统一同步阻塞和异步非阻塞的逻辑

异步非阻塞是通过线程池来完成的。为了统一逻辑处理，同步阻塞也可以依赖线程池，只不过这个线程池里只有一个线程。

2. 模板方法模式

2.1 定义

在一个方法中定义一个算法骨架（业务逻辑），并将某些步骤延迟到子类中实现。模板方法模式可以让子类在不改变算法整体结构的情况下，重新定义算法中的某些步骤。

其中，模板指的是算法的骨架，而模板方法指的是包含算法骨架的方法。

2.2 作用

1. 通过继承的实现方式，复用逻辑，提高复用性
2. 通过提供抽象方法由子类来实现，提高扩展性

2.3. 类结构图

image

2.4. 经典实现

public abstract class AbstractClass {
  public final void templateMethod() {
    //...
    method1();
    //...
    method2();
    //...
  }
  
  protected abstract void method1();
  protected abstract void method2();
}

public class ConcreteClass1 extends AbstractClass {
  @Override
  protected void method1() {
    //...
  }

2.5 应用场景

Java InputStream

public abstract class InputStream implements Closeable {
.... ignore codes 

    public int read(byte b[], int off, int len) throws IOException {
        if (b == null) {
            throw new NullPointerException();
        } else if (off < 0 || len < 0 || len > b.length - off) {
            throw new IndexOutOfBoundsException();
        } else if (len == 0) {
            return 0;
        }

        int c = read();
        if (c == -1) {
            return -1;
        }
        b[off] = (byte)c;

        int i = 1;
        try {
            for (; i < len ; i++) {
                c = read();
                if (c == -1) {
                    break;
                }
                b[off + i] = (byte)c;
            }
        } catch (IOException ee) {
        }
        return i;
    }
    
 public abstract int read() throws IOException;
} 

public class ByteArrayInputStream extends InputStream {
    public synchronized int read() {
        return (pos < count) ? (buf[pos++] & 0xff) : -1;
    }
}

read(byte b[], int off, int len) 是模板方法，而 read() 是需要子类扩展的方法。

Java AbstractList

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    boolean modified = false;
    for (E e : c) {
        add(index++, e);
        modified = true;
    }
    return modified;
}

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

addAll 为模板方法，而 add(int index, E element) 是需要子类实现的方法。

Java Servlet

public void service(ServletRequest req, ServletResponse res)
    throws ServletException, IOException
{
    HttpServletRequest  request;
    HttpServletResponse response;
    if (!(req instanceof HttpServletRequest &&
            res instanceof HttpServletResponse)) {
        throw new ServletException("non-HTTP request or response");
    }
    request = (HttpServletRequest) req;
    response = (HttpServletResponse) res;
    service(request, response);
}

protected void service(HttpServletRequest req, HttpServletResponse resp)
    throws ServletException, IOException
{
    String method = req.getMethod();
    if (method.equals(METHOD_GET)) {
        long lastModified = getLastModified(req);
        if (lastModified == -1) {
            // servlet doesn't support if-modified-since, no reason
            // to go through further expensive logic
            doGet(req, resp);
        } else {
            long ifModifiedSince = req.getDateHeader(HEADER_IFMODSINCE);
            if (ifModifiedSince < lastModified) {
                // If the servlet mod time is later, call doGet()
                // Round down to the nearest second for a proper compare
                // A ifModifiedSince of -1 will always be less
                maybeSetLastModified(resp, lastModified);
                doGet(req, resp);
            } else {
                resp.setStatus(HttpServletResponse.SC_NOT_MODIFIED);
            }
        }
    } else if (method.equals(METHOD_HEAD)) {
        long lastModified = getLastModified(req);
        maybeSetLastModified(resp, lastModified);
        doHead(req, resp);
    } else if (method.equals(METHOD_POST)) {
        doPost(req, resp);
    } else if (method.equals(METHOD_PUT)) {
        doPut(req, resp);
    } else if (method.equals(METHOD_DELETE)) {
        doDelete(req, resp);
    } else if (method.equals(METHOD_OPTIONS)) {
        doOptions(req,resp);
    } else if (method.equals(METHOD_TRACE)) {
        doTrace(req,resp);
    } else {
        String errMsg = lStrings.getString("http.method_not_implemented");
        Object[] errArgs = new Object[1];
        errArgs[0] = method;
        errMsg = MessageFormat.format(errMsg, errArgs);
        resp.sendError(HttpServletResponse.SC_NOT_IMPLEMENTED, errMsg);
    }
}

HttpSevlet 中的 service() 是模板方法，而 doGet() 和 doPost() 是需要子类进行实现的方法。

Junit TestCase

public abstract class TestCase extends Assert implements Test {
  public void runBare() throws Throwable {
    Throwable exception = null;
    setUp();
    try {
      runTest();
    } catch (Throwable running) {
      exception = running;
    } finally {
      try {
        tearDown();
      } catch (Throwable tearingDown) {
        if (exception == null) exception = tearingDown;
      }
    }
    if (exception != null) throw exception;
  }
  
  /**
  * Sets up the fixture, for example, open a network connection.
  * This method is called before a test is executed.
  */
  protected void setUp() throws Exception {
  }

  /**
  * Tears down the fixture, for example, close a network connection.
  * This method is called after a test is executed.
  */
  protected void tearDown() throws Exception {
  }
}

runBare 为模块方法，而 setUp() 和 tearDown() 则是需要子类选择性进行扩展的方法。

2.6 模板方法和回调的关系

Callback 回调机制

比如：A 类事先注册了 F 函数到了 B 类，然后，A 类调用了 B 类的 P 函数，B 类返过来调用 A 类的 F 函数。这里的 F 函数就是“回调函数”。A 调用 B，B 反过来又调用 A，这种机制称为“回调”。

A 类如何将回调函数传递给 B

在 Java 中使用包裹了回调函数的类对象（通常是接口的实现对象）。

public interface ICallback {
   void callback();
}

public class ClassA {
   public void test(ICallback callback) {
       callback.callback();
   }
}

public class Client {
   public static void main(String[] args) {
       ClassA classA = new ClassA();
       classA.test(new ICallback() {
           @Override
           public void callback() {
               System.out.println("callback method is called");
           }
       });
   }
}

回调分类

回调分为同步回调和异步回调。同步回调是指函数返回之前执行回调函数。异步回调是指在函数返回之后再执行回调函数。

异步回调的应用有：业务系统与第三方支付系统之间的支付结果的回调。

同步回调看起来更像模板模式。
异步回调看起来更像观察者模式。

应用一：JdbcTemplate

public class JdbcTemplateDemo {
  private JdbcTemplate jdbcTemplate;

  public User queryUser(long id) {
    String sql = "select * from user where id="+id;
    return jdbcTemplate.query(sql, new UserRowMapper()).get(0);
  }

  class UserRowMapper implements RowMapper<User> {
    public User mapRow(ResultSet rs, int rowNum) throws SQLException {
      User user = new User();
      user.setId(rs.getLong("id"));
      user.setName(rs.getString("name"));
      user.setTelephone(rs.getString("telephone"));
      return user;
    }
  }
}

UserRowMapper 所实现的mapRow(ResultSet rs, int rowNum) 就是一个回调函数，负责将通过 JDBC 查询到的数据转换为对象，并返回。

下面是 JDBCTemplate 的部分实现源码：

@Override
public <T> List<T> query(String sql, RowMapper<T> rowMapper) throws DataAccessException {
 return query(sql, new RowMapperResultSetExtractor<T>(rowMapper));
}

@Override
public <T> T query(final String sql, final ResultSetExtractor<T> rse) throws DataAccessException {
 Assert.notNull(sql, "SQL must not be null");
 Assert.notNull(rse, "ResultSetExtractor must not be null");
 if (logger.isDebugEnabled()) {
  logger.debug("Executing SQL query [" + sql + "]");
 }

 class QueryStatementCallback implements StatementCallback<T>, SqlProvider {
  @Override
  public T doInStatement(Statement stmt) throws SQLException {
   ResultSet rs = null;
   try {
    rs = stmt.executeQuery(sql);
    ResultSet rsToUse = rs;
    if (nativeJdbcExtractor != null) {
     rsToUse = nativeJdbcExtractor.getNativeResultSet(rs);
    }
    return rse.extractData(rsToUse);
   }
   finally {
    JdbcUtils.closeResultSet(rs);
   }
  }
  @Override
  public String getSql() {
   return sql;
  }
 }

 return execute(new QueryStatementCallback());
}

@Override
public <T> T execute(StatementCallback<T> action) throws DataAccessException {
 Assert.notNull(action, "Callback object must not be null");

 Connection con = DataSourceUtils.getConnection(getDataSource());
 Statement stmt = null;
 try {
  Connection conToUse = con;
  if (this.nativeJdbcExtractor != null &&
    this.nativeJdbcExtractor.isNativeConnectionNecessaryForNativeStatements()) {
   conToUse = this.nativeJdbcExtractor.getNativeConnection(con);
  }
  stmt = conToUse.createStatement();
  applyStatementSettings(stmt);
  Statement stmtToUse = stmt;
  if (this.nativeJdbcExtractor != null) {
   stmtToUse = this.nativeJdbcExtractor.getNativeStatement(stmt);
  }
  T result = action.doInStatement(stmtToUse);
  handleWarnings(stmt);
  return result;
 }
 catch (SQLException ex) {
  // Release Connection early, to avoid potential connection pool deadlock
  // in the case when the exception translator hasn't been initialized yet.
  JdbcUtils.closeStatement(stmt);
  stmt = null;
  DataSourceUtils.releaseConnection(con, getDataSource());
  con = null;
  throw getExceptionTranslator().translate("StatementCallback", getSql(action), ex);
 }
 finally {
  JdbcUtils.closeStatement(stmt);
  DataSourceUtils.releaseConnection(con, getDataSource());
 }
}

JDBCTemplate 通过 execute 函数封装了通过 JDBC 获取数据过程中不变的执行逻辑，主要是获取到操作数据库的 Statement 对象，并通过StatementCallback<T>接口将 Statement 对象传递给用户自己去做业务逻辑。上面代码中 QueryStatementCallback 回调实现中，进行了数据查询的操作。并通过实现ResultSetExtractor<T> 接口，完成数据到对象的转换工作。

简单来说，就是通过一个回调嵌套来完成了数据的查询操作，同时，完成了数据到对象的转换操作。StatementCallback<T>接口实现中持有了ResultSetExtractor<T> 接口的实现。 然后将StatementCallback<T>中接口的实现传进 excute 方法中，通过在 excute 方法中回调StatementCallback<T> 接口，接着在StatementCallback<T>实现中回调ResultSetExtractor<T> 接口，来完成整个查询数据到数据转换到对象的操作。

应用二：Android SetOnclickListener

Button button = (Button)findViewById(R.id.button);
button.setOnClickListener(new OnClickListener() {
  @Override
  public void onClick(View v) {
    System.out.println("I am clicked.");
  }
});

这里的 Android 点击事件，从代码实现来看，点击事件监听器就是一个回调接口；而从业务实现来看，当用户点击了按钮后，监听器就会接收到响应，就是一个注册了点击事件的观察者。

这里的 setOnclickListener 是一个异步回调。当注册好回调函数后，并不需要等待回调函数执行，而是直接执行后面的业务注册后面的业务逻辑。这也再一次验证了异步回调比较像观察者模式。

应用三：addShutdownHook

Hook 和 Callback 的关系：Callback 更侧重于语法机制的描述，而 Hook 更侧重于应用场景的描述。Hook 是 Callback 的一种应用。

public class ShutdownThread extends Thread {
    @Override
    public void run() {
        System.out.println("I am called during shutting down");
    }
}

public static void main(String[] args) {
    ShutdownThread thread = new ShutdownThread();
    Runtime.getRuntime().addShutdownHook(thread);
    System.out.println("I'm dying");
}

上面的代码中，当 main 方法中的I'm dying打印后，该程序就执行完成，程序关闭。在关闭之间会回调 ShutdownThread 中的方法。

模板方法和回调的区别

在应用场景上，模板方法和同步回调基本上没有什么差别，都是在一个大的算法骨架中，自由替换某些步骤，起到代码复用和扩展的目的。而异步回调跟模块模式有较大差异，异步回调更像观察者模式。

在代码实现上，回调基于组合来实现，把一个对象传递到另一个对象，是一种对象之间的关系。而模板方法基于继承实现，子类重写父类的抽象方法，是一种类之间的关系。

回调相比模板方法实现的好处

1. Java 只支持单继承，如果使用模板方法实现后，该类就不在具有继承能力。
2. 回调可以使用匿名对象，可以不用事先定义类，而模板方法针对不同的实现，都要创建不同的子类来实现。
3. 如果某个类中实现了多个模板方法，每个模板方法都有抽象方法，需要子类来实现。即便子类只用到了其中的一个模板方法都需要实现所有模板方法中的所有抽象方法。而如果是使用回调就更加灵活，只需要向用到的模板方法中注入对应的回调对象即可。

3. 策略模式

3.1 定义

定义一簇算法类，将每个算法分别封装起来，让它们可以相互替换。策略模式可以使算法的变化独立于使用它们的客户端（使用算法的代码）。

3.2 作用

1. 解耦算法的定义、创建和使用，降低算法的复杂度。同时，满足单一职责，避免由于算法的切换带来的算法代码的个性。
2. 通过动态指定算法策略，提高程序切换算法的灵活性。
3. 基于接口实现，向客户端屏蔽算法实现细节，易扩展。
4. 将多个算法独立成类，提高了代码的复用性。

3.3 类结构图

image

3.4 经典实现

1. 策略的定义

public interface Strategy {
    void algorithm();
}

public class ConcreteStaragyA implements Strategy {
    @Override
    public void algorithm() {
        System.out.println("A algorithm");
    }
}

public class ConcreteStaragyB implements Strategy {
    @Override
    public void algorithm() {
        System.out.println("B algorithm");
    }
}

2. 策略的创建

public class StrategyFactory {
    static Map<String, Strategy> strategyMap = new HashMap<>();

    static {
        strategyMap.put("A", new ConcreteStaragyA());
        strategyMap.put("B", new ConcreteStaragyB());
    }

    public static Strategy getStrategy(String type) {
        return strategyMap.get(type);
    }
}

3. 策略的使用

1. 运行时动态指定策略：根据配置、用户输入或计算结果等这些不确定性因素，动态决定使用哪种策略。

// 运行时动态确定，根据配置文件的配置决定使用哪种策略
public class Application {
  public static void main(String[] args) throws Exception {
    EvictionStrategy evictionStrategy = null;
    Properties props = new Properties();
    props.load(new FileInputStream("./config.properties"));
    String type = props.getProperty("eviction_type");
    evictionStrategy = EvictionStrategyFactory.getEvictionStrategy(type);
    UserCache userCache = new UserCache(evictionStrategy);
    //...
  }
}

// 非运行时动态确定，在代码中指定使用哪种策略
public class Application {
  public static void main(String[] args) {
    //...
    EvictionStrategy evictionStrategy = new LruEvictionStrategy();
    UserCache userCache = new UserCache(evictionStrategy);
    //...
  }
}

非运行时动态确定，并没有发挥策略模式的优势。在这种场景下，策略模式就退化成了“面向对象多态编程”或者“基于接口而非实现编程原则”。

3.5 使用策略模式避免分支判断

常见多个算法耦合在一起的例子

public class OrderService {
  public double discount(Order order) {
    double discount = 0.0;
    OrderType type = order.getType();
    if (type.equals(OrderType.NORMAL)) { // 普通订单
      //...省略折扣计算算法代码
    } else if (type.equals(OrderType.GROUPON)) { // 团购订单
      //...省略折扣计算算法代码
    } else if (type.equals(OrderType.PROMOTION)) { // 促销订单
      //...省略折扣计算算法代码
    }
    return discount;
  }
}

改造流程

1. 将不同订单的打折策略设计成独立的类
2. 使用工厂类来对不同的策略进行统一管理

改造后代码

// 策略的定义
public interface DiscountStrategy {
  double calDiscount(Order order);
}
// 省略NormalDiscountStrategy、GrouponDiscountStrategy、PromotionDiscountStrategy类代码...

// 策略的创建
public class DiscountStrategyFactory {
  private static final Map<OrderType, DiscountStrategy> strategies = new HashMap<>();

  static {
    strategies.put(OrderType.NORMAL, new NormalDiscountStrategy());
    strategies.put(OrderType.GROUPON, new GrouponDiscountStrategy());
    strategies.put(OrderType.PROMOTION, new PromotionDiscountStrategy());
  }

  public static DiscountStrategy getDiscountStrategy(OrderType type) {
    return strategies.get(type);
  }
}

// 策略的使用
public class OrderService {
  public double discount(Order order) {
    OrderType type = order.getType();
    DiscountStrategy discountStrategy = DiscountStrategyFactory.getDiscountStrategy(type);
    return discountStrategy.calDiscount(order);
  }
}

对分支判断的改造本质上是对借助“查表”法替代了根据 type 的分支判断。

3.6 应用场景

给文件中数字排序

根据数据的规模将使用 4 种不同的排序算法：

1. 针对一次性读取到内存的数据，可以直接使用快排或者其它算法
2. 针对文件较大，比如：10 G，无法一次性读取到内存中，可以使用外部排序算法（如：桶排序、计数排序）
3. 针对文件更大，比如：100G，可以在外部排序的基础上使用多线程，实现一个单机版的 MapReduce
4. 针对文件巨大，比如：1T，这时可以通过使用真正的 MapReduce 框架来实现

代码实现

public interface ISortAlg {
  void sort(String filePath);
}

public class QuickSort implements ISortAlg {
  @Override
  public void sort(String filePath) {
    //...
  }
}

public class ExternalSort implements ISortAlg {
  @Override
  public void sort(String filePath) {
    //...
  }
}

public class ConcurrentExternalSort implements ISortAlg {
  @Override
  public void sort(String filePath) {
    //...
  }
}

public class MapReduceSort implements ISortAlg {
  @Override
  public void sort(String filePath) {
    //...
  }
}

public class Sorter {
  private static final long GB = 1000 * 1000 * 1000;

  public void sortFile(String filePath) {
    // 省略校验逻辑
    File file = new File(filePath);
    long fileSize = file.length();
    ISortAlg sortAlg;
    if (fileSize < 6 * GB) { // [0, 6GB)
      sortAlg = new QuickSort();
    } else if (fileSize < 10 * GB) { // [6GB, 10GB)
      sortAlg = new ExternalSort();
    } else if (fileSize < 100 * GB) { // [10GB, 100GB)
      sortAlg = new ConcurrentExternalSort();
    } else { // [100GB, ~)
      sortAlg = new MapReduceSort();
    }
    sortAlg.sort(filePath);
  }
}

对上面代码通过引入工厂类，使用“查表”法来缓存这些无状态的算法类。

public class SortAlgFactory {
  private static final Map<String, ISortAlg> algs = new HashMap<>();

  static {
    algs.put("QuickSort", new QuickSort());
    algs.put("ExternalSort", new ExternalSort());
    algs.put("ConcurrentExternalSort", new ConcurrentExternalSort());
    algs.put("MapReduceSort", new MapReduceSort());
  }

  public static ISortAlg getSortAlg(String type) {
    if (type == null || type.isEmpty()) {
      throw new IllegalArgumentException("type should not be empty.");
    }
    return algs.get(type);
  }
}

public class Sorter {
  private static final long GB = 1000 * 1000 * 1000;

  public void sortFile(String filePath) {
    // 省略校验逻辑
    File file = new File(filePath);
    long fileSize = file.length();
    ISortAlg sortAlg;
    if (fileSize < 6 * GB) { // [0, 6GB)
      sortAlg = SortAlgFactory.getSortAlg("QuickSort");
    } else if (fileSize < 10 * GB) { // [6GB, 10GB)
      sortAlg = SortAlgFactory.getSortAlg("ExternalSort");
    } else if (fileSize < 100 * GB) { // [10GB, 100GB)
      sortAlg = SortAlgFactory.getSortAlg("ConcurrentExternalSort");
    } else { // [100GB, ~)
      sortAlg = SortAlgFactory.getSortAlg("MapReduceSort");
    }
    sortAlg.sort(filePath);
  }
}

再次优化，移除 if-else 逻辑。

public class Sorter {
  private static final long GB = 1000 * 1000 * 1000;
  private static final List<AlgRange> algs = new ArrayList<>();
  static {
    algs.add(new AlgRange(0, 6*GB, SortAlgFactory.getSortAlg("QuickSort")));
    algs.add(new AlgRange(6*GB, 10*GB, SortAlgFactory.getSortAlg("ExternalSort")));
    algs.add(new AlgRange(10*GB, 100*GB, SortAlgFactory.getSortAlg("ConcurrentExternalSort")));
    algs.add(new AlgRange(100*GB, Long.MAX_VALUE, SortAlgFactory.getSortAlg("MapReduceSort")));
  }

  public void sortFile(String filePath) {
    // 省略校验逻辑
    File file = new File(filePath);
    long fileSize = file.length();
    ISortAlg sortAlg = null;
    for (AlgRange algRange : algs) {
      if (algRange.inRange(fileSize)) {
        sortAlg = algRange.getAlg();
        break;
      }
    }
    sortAlg.sort(filePath);
  }

  private static class AlgRange {
    private long start;
    private long end;
    private ISortAlg alg;

    public AlgRange(long start, long end, ISortAlg alg) {
      this.start = start;
      this.end = end;
      this.alg = alg;
    }

    public ISortAlg getAlg() {
      return alg;
    }

    public boolean inRange(long size) {
      return size >= start && size < end;
    }
  }
}

目前这种实现，在添加新的策略类时，需要同时在 Sorter 类和 SortAlgFactory 类中添加对应的逻辑，并不完全符合开闭原则。有什么办法让上面的代码完全符合开闭原则呢？

对于工厂类的修改，可以通过反射 + 注解的方式。这里有两种实现方式：

1. 通过配置文件配置对应的策略类，程序启动时，读取配置文件，并通过反射将所有的策略类对象添加到工厂类中。
2. 为每个策略类设置注解，程序启动时，会通过扫描所有的注解，并通过反射将所有的策略类对象添加到工厂类中。

对于 Sorter 类的修改，可以通过配置文件的方式，将文件区间大小和算法之间的对应关系放到配置文件中。当添加新算法时，只需要改动区间与算法的对应关系即可。

4. 责任链模式

其实现可以参考我的另一篇博客。里面做了更加详细的说明，点击跳转。

5. 状态模式

5.1 定义

允许对象在其内部状态改变时，更改其对应的行为。和有限状态机的概念非常相似。

什么是有限状态机

有限状态机简称状态机，由状态（State）、事件（Event）、和动作(Action)三部分组成。其中，事情也称为状态转移条件。事件触发状态的转移及动作的执行，当然，动作不是必须的，也可以是发生状态的转移。

5.2 作用

5.3 类结构图

image

5.4 状态机的实现方式

1. 状态模式实现

2. 分支逻辑法

3. 查表法

5.5 应用场景

超级玛丽奥

马里奥有多种形态：小巴里奥、超级马里奥、火焰马里奥和斗篷马里奥。

在不同的游戏情节下，各种形态会相互转化，并相应的增减积分。比如：小马里奥吃了一个蘑菇后，变成超级巴里奥，并增加 100 积分。

吃了一个蘑菇对应事件（Event）,变成超级马里奥对应状态的变化，增加 100 积分对应状态变化后的动作执行。

各状态之间的转换如下图：

image

分支逻辑法

public enum State {
  SMALL(0),
  SUPER(1),
  FIRE(2),
  CAPE(3);

  private int value;

  private State(int value) {
    this.value = value;
  }

  public int getValue() {
    return this.value;
  }
}

public class MarioStateMachine {
  private int score;
  private State currentState;

  public MarioStateMachine() {
    this.score = 0;
    this.currentState = State.SMALL;
  }

  public void obtainMushRoom() {
    if (currentState.equals(State.SMALL)) {
      this.currentState = State.SUPER;
      this.score += 100;
    }
  }

  public void obtainCape() {
    if (currentState.equals(State.SMALL) || currentState.equals(State.SUPER) ) {
      this.currentState = State.CAPE;
      this.score += 200;
    }
  }

  public void obtainFireFlower() {
    if (currentState.equals(State.SMALL) || currentState.equals(State.SUPER) ) {
      this.currentState = State.FIRE;
      this.score += 300;
    }
  }

  public void meetMonster() {
    if (currentState.equals(State.SUPER)) {
      this.currentState = State.SMALL;
      this.score -= 100;
      return;
    }

    if (currentState.equals(State.CAPE)) {
      this.currentState = State.SMALL;
      this.score -= 200;
      return;
    }

    if (currentState.equals(State.FIRE)) {
      this.currentState = State.SMALL;
      this.score -= 300;
      return;
    }
  }

  public int getScore() {
    return this.score;
  }

  public State getCurrentState() {
    return this.currentState;
  }
}

如果分支逻辑比较简单，是可以接受的。但如果对于复杂的状态机来说，这种情况极有可能漏写代码，同时，每个事件中所对应状态改变及动作执行会包含大量的 if-else 逻辑，可读性和可维护性非常差。而且，当要新增加一种状态的话，每个事件里里的代码都会被修改，代码将非常难以维护。

查表法

image

在上面的二维表中，第一维表示当前状态，第二维表示事件，值表示当前状态经过事件之后，转移到新的状态及要执行的动作。

public enum Event {
  GOT_MUSHROOM(0),
  GOT_CAPE(1),
  GOT_FIRE(2),
  MET_MONSTER(3);

  private int value;

  private Event(int value) {
    this.value = value;
  }

  public int getValue() {
    return this.value;
  }
}

public class MarioStateMachine {
  private int score;
  private State currentState;

  private static final State[][] transitionTable = {
          {SUPER, CAPE, FIRE, SMALL},
          {SUPER, CAPE, FIRE, SMALL},
          {CAPE, CAPE, CAPE, SMALL},
          {FIRE, FIRE, FIRE, SMALL}
  };

  private static final int[][] actionTable = {
          {+100, +200, +300, +0},
          {+0, +200, +300, -100},
          {+0, +0, +0, -200},
          {+0, +0, +0, -300}
  };

  public MarioStateMachine() {
    this.score = 0;
    this.currentState = State.SMALL;
  }

  public void obtainMushRoom() {
    executeEvent(Event.GOT_MUSHROOM);
  }

  public void obtainCape() {
    executeEvent(Event.GOT_CAPE);
  }

  public void obtainFireFlower() {
    executeEvent(Event.GOT_FIRE);
  }

  public void meetMonster() {
    executeEvent(Event.MET_MONSTER);
  }

  private void executeEvent(Event event) {
    int stateValue = currentState.getValue();
    int eventValue = event.getValue();
    this.currentState = transitionTable[stateValue][eventValue];
    this.score = actionTable[stateValue][eventValue];
  }

  public int getScore() {
    return this.score;
  }

  public State getCurrentState() {
    return this.currentState;
  }

}

上面使用两个二维数组非常巧妙的将触发事件后所对应的状态和对应状态所需要执行的动作都表示了出来。在具体实现的时候，只需要通过当前事件去这两个二维数组中获取对应的状态和需要执行的动作即可，非常的简单，代码实现也非常的简洁。

但也存在问题，就是这里的动作只是简单的加减积分，如果是一系列的操作，这种实现有无法满足需求了。

状态模式实现

状态模式实际上是对分支逻辑法的一种优化处理。状态模式是将事件触发的状态转移和动作执行，拆分到了不同的状态类中，来避免分支判断逻辑的。

public interface IMario { //所有状态类的接口
  State getName();
  //以下是定义的事件
  void obtainMushRoom();
  void obtainCape();
  void obtainFireFlower();
  void meetMonster();
}

public class SmallMario implements IMario {
  private MarioStateMachine stateMachine;

  public SmallMario(MarioStateMachine stateMachine) {
    this.stateMachine = stateMachine;
  }

  @Override
  public State getName() {
    return State.SMALL;
  }

  @Override
  public void obtainMushRoom() {
    stateMachine.setCurrentState(new SuperMario(stateMachine));
    stateMachine.setScore(stateMachine.getScore() + 100);
  }

  @Override
  public void obtainCape() {
    stateMachine.setCurrentState(new CapeMario(stateMachine));
    stateMachine.setScore(stateMachine.getScore() + 200);
  }

  @Override
  public void obtainFireFlower() {
    stateMachine.setCurrentState(new FireMario(stateMachine));
    stateMachine.setScore(stateMachine.getScore() + 300);
  }

  @Override
  public void meetMonster() {
    // do nothing...
  }
}

public class SuperMario implements IMario {
  private MarioStateMachine stateMachine;

  public SuperMario(MarioStateMachine stateMachine) {
    this.stateMachine = stateMachine;
  }

  @Override
  public State getName() {
    return State.SUPER;
  }

  @Override
  public void obtainMushRoom() {
    // do nothing...
  }

  @Override
  public void obtainCape() {
    stateMachine.setCurrentState(new CapeMario(stateMachine));
    stateMachine.setScore(stateMachine.getScore() + 200);
  }

  @Override
  public void obtainFireFlower() {
    stateMachine.setCurrentState(new FireMario(stateMachine));
    stateMachine.setScore(stateMachine.getScore() + 300);
  }

  @Override
  public void meetMonster() {
    stateMachine.setCurrentState(new SmallMario(stateMachine));
    stateMachine.setScore(stateMachine.getScore() - 100);
  }
}

// 省略CapeMario、FireMario类...

public class MarioStateMachine {
  private int score;
  private IMario currentState; // 不再使用枚举来表示状态

  public MarioStateMachine() {
    this.score = 0;
    this.currentState = new SmallMario(this);
  }

  public void obtainMushRoom() {
    this.currentState.obtainMushRoom();
  }

  public void obtainCape() {
    this.currentState.obtainCape();
  }

  public void obtainFireFlower() {
    this.currentState.obtainFireFlower();
  }

  public void meetMonster() {
    this.currentState.meetMonster();
  }

  public int getScore() {
    return this.score;
  }

  public State getCurrentState() {
    return this.currentState.getName();
  }

  public void setScore(int score) {
    this.score = score;
  }

  public void setCurrentState(IMario currentState) {
    this.currentState = currentState;
  }
}

MarioStateMachine 是一个状态维护类，所有状态的变更都是通过这里维护的。而实现了 IMario 接口的这些类，主要是负责维护在当前状态下，事件触发后的动作的执行。

两者是双向依赖关系，当事件触发后，会先 MarioStateMachine 中对应事件的方法，这些方法会调用到对应状态实现类中对应的动作的执行。而动作执行的过程中，又需要反过来更新 MarioStateMachine 中的状态。

由于状态类中不包含任何的成员变量（状态），所以，可以将其设计成单例对象。优化后的代码如下：

public interface IMario {
  State getName();
  void obtainMushRoom(MarioStateMachine stateMachine);
  void obtainCape(MarioStateMachine stateMachine);
  void obtainFireFlower(MarioStateMachine stateMachine);
  void meetMonster(MarioStateMachine stateMachine);
}

public class SmallMario implements IMario {
  private static final SmallMario instance = new SmallMario();
  private SmallMario() {}
  public static SmallMario getInstance() {
    return instance;
  }

  @Override
  public State getName() {
    return State.SMALL;
  }

  @Override
  public void obtainMushRoom(MarioStateMachine stateMachine) {
    stateMachine.setCurrentState(SuperMario.getInstance());
    stateMachine.setScore(stateMachine.getScore() + 100);
  }

  @Override
  public void obtainCape(MarioStateMachine stateMachine) {
    stateMachine.setCurrentState(CapeMario.getInstance());
    stateMachine.setScore(stateMachine.getScore() + 200);
  }

  @Override
  public void obtainFireFlower(MarioStateMachine stateMachine) {
    stateMachine.setCurrentState(FireMario.getInstance());
    stateMachine.setScore(stateMachine.getScore() + 300);
  }

  @Override
  public void meetMonster(MarioStateMachine stateMachine) {
    // do nothing...
  }
}

// 省略SuperMario、CapeMario、FireMario类...

public class MarioStateMachine {
  private int score;
  private IMario currentState;

  public MarioStateMachine() {
    this.score = 0;
    this.currentState = SmallMario.getInstance();
  }

  public void obtainMushRoom() {
    this.currentState.obtainMushRoom(this);
  }

  public void obtainCape() {
    this.currentState.obtainCape(this);
  }

  public void obtainFireFlower() {
    this.currentState.obtainFireFlower(this);
  }

  public void meetMonster() {
    this.currentState.meetMonster(this);
  }

  public int getScore() {
    return this.score;
  }

  public State getCurrentState() {
    return this.currentState.getName();
  }

  public void setScore(int score) {
    this.score = score;
  }

  public void setCurrentState(IMario currentState) {
    this.currentState = currentState;
  }
}

查表法和状态模式的应用场景

1. 查表法：像游戏这种比较复杂的状态机，包含的状态比较多，优先推荐查表法，而如果使用状态模式的话，会引入非常多的状态类，会导致代码比较难维护。
2. 状态模式：像电商下单、外卖下单这种类型的状态机，状态相对有限，而事件触发执行的动作包含的业务逻辑可能比较复杂的情况下，使用状态模式更合适。

6. 迭代器模式

6.1 定义

提供一种方法访问一个容器（container）对象中各个元素，而又不需暴露该对象的内部细节。

6.2 作用

1. 迭代器模式封装集合内部的复杂数据结构，开发者不需要了解如何遍历，直接使用窗口提供的迭代器即可，提供容器的易用性
2. 迭代器模式将对集合的遍历操作从集合类中拆分出来，放到迭代器中，让两者的职责更加单一
3. 迭代器让新增新的遍历算法非常的容易，只需要实现迭代器接口，并在容器接口中提供对应的创建方法即可，更加符合开闭原则

6.3 类结构图

image

6.4 经典实现

// 接口定义方式一
public interface Iterator<E> {
  boolean hasNext();
  void next();
  E currentItem();
}

public class ArrayIterator<E> implements Iterator<E> {
  private int cursor;
  private ArrayList<E> arrayList;

  public ArrayIterator(ArrayList<E> arrayList) {
    this.cursor = 0;
    this.arrayList = arrayList;
  }

  @Override
  public boolean hasNext() {
    return cursor != arrayList.size(); //注意这里，cursor在指向最后一个元素的时候，hasNext()仍旧返回true。
  }

  @Override
  public void next() {
    cursor++;
  }

  @Override
  public E currentItem() {
    if (cursor >= arrayList.size()) {
      throw new NoSuchElementException();
    }
    return arrayList.get(cursor);
  }
}

public class Demo {
  public static void main(String[] args) {
    ArrayList<String> names = new ArrayList<>();
    names.add("xzg");
    names.add("wang");
    names.add("zheng");
    
    Iterator<String> iterator = new ArrayIterator(names);
    while (iterator.hasNext()) {
      System.out.println(iterator.currentItem());
      iterator.next();
    }
  }
}

上面的实现是将容器对象通过构造函数直接传递给了迭代器对象，而为了封装迭代器的创建细节，我们可以在容器对象中定义一个 iterator 方法，来创建对应的迭代器。改造代码如下：

public interface List<E> {
  Iterator iterator();
  //...省略其他接口函数...
}

public class ArrayList<E> implements List<E> {
  //...
  public Iterator iterator() {
    return new ArrayIterator(this);
  }
  //...省略其他代码
}

public class Demo {
  public static void main(String[] args) {
    List<String> names = new ArrayList<>();
    names.add("xzg");
    names.add("wang");
    names.add("zheng");
    
    Iterator<String> iterator = names.iterator();
    while (iterator.hasNext()) {
      System.out.println(iterator.currentItem());
      iterator.next();
    }
  }
}

下图是容器对象和迭代器对象的依赖关系图：

image

6.5 迭代器遍历集合的优势

遍历集合的3种方式

1. for
2. foreach
3. iterator

而 foreach 是基于 iterator 实现的，也就是说，本质上只有 2 种遍历集合的方式。

迭代器优势

1. 迭代器模式封装集合内部的复杂数据结构，开发者不需要了解如何遍历，直接使用窗口提供的迭代器即可
2. 迭代器模式将对集合的遍历操作从集合类中拆分出来，放到迭代器中，让两者的职责更加单一
3. 迭代器让新增新的遍历算法非常的容易，只需要实现迭代器接口，并在容器接口中提供对应的创建方法即可，更加符合开闭原则

6.6 遍历集合的时候，为什么不能增删集合中元素

主要是由于集合底层数据结构是数组，当删除元素时，会将数组向前移动一位，而再去遍历元素的时候，就有可能出现有些数据被漏掉的情况。

而增加一个新的元素，插入位置之后的元素都会向后移动一位，就有可能出现某个元素会被重复遍历的情况。

ArrayList 的解决思路

在遍历的过程中，出现增删元素之后，直接报错。

如何确定是否有增删元素

ArrayList 定义了一个 modCount 变量，集合每次调用增删都会将 modCount 加 1。然后，将每次通过 ArrayList 的 iterator 函数创建迭代器的时候，会将 modCount 的值赋值给 expectedModCount 变量（expectedModCount 是 Iterator 对象中的变量）。之后，每次调用当前 Iterator 迭代器对象的 hasNext()、next()函数，都会检查 modCount 和 exceptedModCount 值是否相等。如果不相等，则说明迭代器在遍历过程中，元素进行了增删的操作。此时，遵循 fail-fast 原则，会抛出 ConcurrentModificationException 异常。

什么是 fail-fast 原则

fail-fast 是一种系统的设计思想，当程序有可能出现异常的时候，应该尽可能的上报其错误信息，让程序终止运行，而让程序设计者尽早知道问题，并解决问题。

6.7 如果在遍历的同时，安全地删除元素

Iterator 迭代器中提供了 remove() 的方法来支持在遍历过程中，删除元素的操作。但这个 remove 的操作的作用是有限的，它只能删除当前 遍历游标 cursor 所在位置的前一个元素，而且只能执行一次删除操作，连续调用两次操作，直接会报错。

具体的删除操作是：在 Iterator 中定义了 lastRet 变量，每次调用 next() 方法后，会将当前游标所指定的位置赋值给 lastRet，然后游标自加 1 并指向下一个位置。当调用了 remove() 方法后，会删除 lastRet 所指向位置的元素，并将 lastRet 赋值给当前的 cursor 游标，也就是将游标的位置向前移动了一位。

cursor = lastRet 赋值操作完成后，会将 lastRet 赋值为 -1，当再次调用 remove() 方法时，如果没有调用 next() 方法给 lastRet 重新赋值的话，由于 lastRet 仍然等于 -1，则会抛出异常。

6.8. 实现带“快照”功能的迭代器，彻底解决增删问题

方案一：直接拷贝集合数据

public class SnapshotArrayIterator<E> implements Iterator<E> {
  private int cursor;
  private ArrayList<E> snapshot;

  public SnapshotArrayIterator(ArrayList<E> arrayList) {
    this.cursor = 0;
    this.snapshot = new ArrayList<>();
    this.snapshot.addAll(arrayList);
  }

  @Override
  public boolean hasNext() {
    return cursor < snapshot.size();
  }

  @Override
  public E next() {
    E currentItem = snapshot.get(cursor);
    cursor++;
    return currentItem;
  }
}

直接在创建迭代器的时候，将原有集合中的元素拷贝一份。简单直接，但代价较高。

方案二：添加时间戳标记每个元素

public class ArrayList<E> implements List<E> {
  private static final int DEFAULT_CAPACITY = 10;

  private int actualSize; //不包含标记删除元素
  private int totalSize; //包含标记删除元素

  private Object[] elements;
  private long[] addTimestamps;
  private long[] delTimestamps;

  public ArrayList() {
    this.elements = new Object[DEFAULT_CAPACITY];
    this.addTimestamps = new long[DEFAULT_CAPACITY];
    this.delTimestamps = new long[DEFAULT_CAPACITY];
    this.totalSize = 0;
    this.actualSize = 0;
  }

  @Override
  public void add(E obj) {
    elements[totalSize] = obj;
    addTimestamps[totalSize] = System.currentTimeMillis();
    delTimestamps[totalSize] = Long.MAX_VALUE;
    totalSize++;
    actualSize++;
  }

  @Override
  public void remove(E obj) {
    for (int i = 0; i < totalSize; ++i) {
      if (elements[i].equals(obj)) {
        delTimestamps[i] = System.currentTimeMillis();
        actualSize--;
      }
    }
  }

  public int actualSize() {
    return this.actualSize;
  }

  public int totalSize() {
    return this.totalSize;
  }

  public E get(int i) {
    if (i >= totalSize) {
      throw new IndexOutOfBoundsException();
    }
    return (E)elements[i];
  }

  public long getAddTimestamp(int i) {
    if (i >= totalSize) {
      throw new IndexOutOfBoundsException();
    }
    return addTimestamps[i];
  }

  public long getDelTimestamp(int i) {
    if (i >= totalSize) {
      throw new IndexOutOfBoundsException();
    }
    return delTimestamps[i];
  }
}

public class SnapshotArrayIterator<E> implements Iterator<E> {
  private long snapshotTimestamp;
  private int cursorInAll; // 在整个容器中的下标，而非快照中的下标
  private int leftCount; // 快照中还有几个元素未被遍历
  private ArrayList<E> arrayList;

  public SnapshotArrayIterator(ArrayList<E> arrayList) {
    this.snapshotTimestamp = System.currentTimeMillis();
    this.cursorInAll = 0;
    this.leftCount = arrayList.actualSize();;
    this.arrayList = arrayList;

    justNext(); // 先跳到这个迭代器快照的第一个元素
  }

  @Override
  public boolean hasNext() {
    return this.leftCount >= 0; // 注意是>=, 而非>
  }

  @Override
  public E next() {
    E currentItem = arrayList.get(cursorInAll);
    justNext();
    return currentItem;
  }

  private void justNext() {
    while (cursorInAll < arrayList.totalSize()) {
      long addTimestamp = arrayList.getAddTimestamp(cursorInAll);
      long delTimestamp = arrayList.getDelTimestamp(cursorInAll);
      if (snapshotTimestamp > addTimestamp && snapshotTimestamp < delTimestamp) {
        leftCount--;
        break;
      }
      cursorInAll++;
    }
  }
}

添加三个时间戳，分别是元素添加时间戳 addTimestamp、元素删除时间戳 delTimestamp 和迭代器创建时时间戳 snapshotTimestamp。当满足 addTimestamp < snapshotTimestamp < delTimestamp 时，说明当前元素是创建 Iterator 迭代器时，快照的元素，需要被遍历到。

而当 addTimestamp > snapshotTimestamp 时，说明当前元素是快照生成之后添加到集合的，不属于快照中的元素；当 snapshotTimestamp > delTimestamp 时，说明当前元素在创建快照之前就已经被删除了，同样的，也不属于快照中的元素。这两种情况下，对应的元素都不应该被 遍历到。

方案二存在问题：

由于删除元素只是标记而非删除，这样就导致随机访问失效。相当于为了修复一个问题，引入了另一个问题。而本来随机访问特性是以数组为底层数据结构的一个优势，通过标记而非删除的方式实现后，这种优势就被丢弃了，得不偿失。

解决方案二中存在的问题：让容器既支持快照，又支持随机访问

可以在 ArrayList 中创建两个数组，一个用来支持标记清除的，用来实现快照功能。另一个不支持标记清除的，用来支持随机访问。

说明

此文是根据王争设计模式之美相关专栏内容整理而来，非原创。