【設(shè)計(jì)模式】行為型設(shè)計(jì)模式匯總（一）

行為型設(shè)計(jì)模式范圍

  1. 觀察者模式
  2. 模板方法
  3. 策略模式
  4. 職責(zé)鏈模式
  5. 狀態(tài)模式
  6. 迭代器模式
  7. 訪問(wèn)者模式
  8. 備忘錄模式
  9. 命令模式
  10. 解釋器模式
  11. 中介模式

行為型設(shè)計(jì)模式作用

行為型設(shè)計(jì)模式主要關(guān)注的是類與類之間的交互問(wèn)題。

1. 觀察者模式

1.1 定義

在對(duì)象之間定義一個(gè)一對(duì)多的依賴，當(dāng)一個(gè)對(duì)象狀態(tài)改變的時(shí)候，所有依賴的對(duì)象都會(huì)自動(dòng)收到通知。

1.2 作用

  1. 將原本一個(gè)復(fù)雜的更新數(shù)據(jù)的方法，拆分成基于接口的多個(gè)粒度更小，職責(zé)更單一的小方法，降低代碼實(shí)現(xiàn)的復(fù)雜性。
  2. 由于是觀察者是基于接口實(shí)現(xiàn)的，如果有新的邏輯加入進(jìn)來(lái)時(shí)，只需要實(shí)現(xiàn)相應(yīng)的接口，并完成注冊(cè)就可以接收到更新數(shù)據(jù)的通知，提供了代碼的擴(kuò)展性。

1.3 類結(jié)構(gòu)圖

image

1.4 經(jīng)典實(shí)現(xiàn)

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 設(shè)計(jì)模式的本質(zhì)

設(shè)計(jì)模式要干的事情就是解耦。創(chuàng)建型模式是將對(duì)象的創(chuàng)建與使用解耦，結(jié)構(gòu)型模式是將不同功能代碼解耦，行為型模式是將不同的行為代碼解耦。

這里的觀察者模式是將觀察者與被觀察者解耦。

1.6 觀察都模式的種類

1. 同步阻塞

觀察者和被觀察者的代碼都是在同一個(gè)線程中執(zhí)行的。被觀察都直到所有觀察都的代碼都執(zhí)行完成后，才會(huì)繼續(xù)往后執(zhí)行代碼。

2. 異步非阻塞

最簡(jiǎn)單的實(shí)現(xiàn)是在每個(gè) update 方法中開(kāi)啟一個(gè)線程來(lái)執(zhí)行更新。另外一種方式是直接在被觀察者中使用一個(gè)線程池來(lái)執(zhí)行對(duì)各觀察者的調(diào)用。當(dāng)然，可以使用事件總線 EventBus 來(lái)實(shí)現(xiàn)異步非阻塞的。

3. 進(jìn)程內(nèi)實(shí)現(xiàn)

主要分為同步阻塞和異步非阻塞兩種情況。

4. 跨進(jìn)程實(shí)現(xiàn)

在不同的系統(tǒng)中需要實(shí)現(xiàn)觀察者模式的時(shí)候，有兩種方法：

  1. 直接調(diào)用 RPC 接口通知觀察者
  2. 使用消息隊(duì)列（MessageQueue）來(lái)通知觀察者

消息隊(duì)列的具體做法是：被觀察者向消息隊(duì)列中發(fā)送更新消息，觀察者從消息隊(duì)列中取出消息來(lái)執(zhí)行相應(yīng)的業(yè)務(wù)邏輯。在這個(gè)過(guò)程中，被觀察者感知不到觀察者的存在，觀察者也感知不到被觀察者是存在，是一種更加徹底的解耦實(shí)現(xiàn)。

1.7 應(yīng)用場(chǎng)景

EventBus

框架的作用

  1. 隱藏實(shí)現(xiàn)細(xì)節(jié)
  2. 降低開(kāi)發(fā)難度
  3. 代碼復(fù)用
  4. 解耦業(yè)務(wù)與非業(yè)務(wù)代碼
  5. 讓程序員聚焦功能的開(kāi)發(fā)

應(yīng)用示例

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) {
    //省略輸入?yún)?shù)的校驗(yàn)代碼
    //省略u(píng)serService.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. 通過(guò)調(diào)用 EventBus 的 register 方法進(jìn)行注冊(cè)工作
  2. 通過(guò) @Subscribe 來(lái)注冊(cè)哪些方法用來(lái)接收更新
  3. 通過(guò) @Subscribe 所注冊(cè)方法中的參數(shù)來(lái)判斷 EventBus 發(fā)送的數(shù)據(jù)哪些注冊(cè)了 EventBus 的哪些方法可以接收到此更新

與傳統(tǒng)觀察者不同的地方

  1. 傳統(tǒng)的實(shí)現(xiàn)中被觀察者只接收實(shí)現(xiàn)了同一接口的觀察者，而 EventBus 可以接收任何對(duì)象
  2. 傳統(tǒng)的實(shí)現(xiàn)中訂閱了被觀察者的觀察者都能夠接收到消息更新，而 EventBus 是根據(jù) post 中的參數(shù)來(lái)匹配當(dāng)前消息需要發(fā)送給哪些觀察者的，是部分發(fā)送

EventBus 的注冊(cè)過(guò)程

當(dāng)調(diào)用 EventBus 的 register 方法將類對(duì)象作為 Observer 注冊(cè)到 EventBus 時(shí)，EventBus 會(huì)掃描當(dāng)前類對(duì)象中的所有使用了 @Subscribe 注解的方法，并獲取方法中的參數(shù)類型，然后通過(guò)將參數(shù)類型與當(dāng)前類對(duì)象和函數(shù)進(jìn)行關(guān)聯(lián)。當(dāng)通過(guò) EventBus 調(diào)用 post 方法發(fā)送消息時(shí)，就會(huì)通過(guò)當(dāng)前發(fā)送消息的類型去之前的映射關(guān)系中找到對(duì)應(yīng)的對(duì)象和函數(shù)，完成調(diào)用。

EventBus 核心實(shí)現(xiàn)原理圖

image

統(tǒng)一同步阻塞和異步非阻塞的邏輯

異步非阻塞是通過(guò)線程池來(lái)完成的。為了統(tǒng)一邏輯處理，同步阻塞也可以依賴線程池，只不過(guò)這個(gè)線程池里只有一個(gè)線程。

2. 模板方法模式

2.1 定義

在一個(gè)方法中定義一個(gè)算法骨架（業(yè)務(wù)邏輯），并將某些步驟延遲到子類中實(shí)現(xiàn)。模板方法模式可以讓子類在不改變算法整體結(jié)構(gòu)的情況下，重新定義算法中的某些步驟。

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

2.2 作用

  1. 通過(guò)繼承的實(shí)現(xiàn)方式，復(fù)用邏輯，提高復(fù)用性
  2. 通過(guò)提供抽象方法由子類來(lái)實(shí)現(xiàn)，提高擴(kuò)展性

2.3. 類結(jié)構(gòu)圖

image

2.4. 經(jīng)典實(shí)現(xiàn)

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 應(yīng)用場(chǎng)景

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() 是需要子類擴(kuò)展的方法。

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) 是需要子類實(shí)現(xiàn)的方法。

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() 是需要子類進(jìn)行實(shí)現(xiàn)的方法。

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() 則是需要子類選擇性進(jìn)行擴(kuò)展的方法。

2.6 模板方法和回調(diào)的關(guān)系

Callback 回調(diào)機(jī)制

比如：A 類事先注冊(cè)了 F 函數(shù)到了 B 類，然后，A 類調(diào)用了 B 類的 P 函數(shù)，B 類返過(guò)來(lái)調(diào)用 A 類的 F 函數(shù)。這里的 F 函數(shù)就是“回調(diào)函數(shù)”。A 調(diào)用 B，B 反過(guò)來(lái)又調(diào)用 A，這種機(jī)制稱為“回調(diào)”。

A 類如何將回調(diào)函數(shù)傳遞給 B

在 Java 中使用包裹了回調(diào)函數(shù)的類對(duì)象（通常是接口的實(shí)現(xiàn)對(duì)象）。

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");
           }
       });
   }
}

回調(diào)分類

回調(diào)分為同步回調(diào)和異步回調(diào)。同步回調(diào)是指函數(shù)返回之前執(zhí)行回調(diào)函數(shù)。異步回調(diào)是指在函數(shù)返回之后再執(zhí)行回調(diào)函數(shù)。

異步回調(diào)的應(yīng)用有：業(yè)務(wù)系統(tǒng)與第三方支付系統(tǒng)之間的支付結(jié)果的回調(diào)。

同步回調(diào)看起來(lái)更像模板模式。
異步回調(diào)看起來(lái)更像觀察者模式。

應(yīng)用一：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 所實(shí)現(xiàn)的mapRow(ResultSet rs, int rowNum) 就是一個(gè)回調(diào)函數(shù)，負(fù)責(zé)將通過(guò) JDBC 查詢到的數(shù)據(jù)轉(zhuǎn)換為對(duì)象，并返回。

下面是 JDBCTemplate 的部分實(shí)現(xiàn)源碼：

@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 通過(guò) execute 函數(shù)封裝了通過(guò) JDBC 獲取數(shù)據(jù)過(guò)程中不變的執(zhí)行邏輯，主要是獲取到操作數(shù)據(jù)庫(kù)的 Statement 對(duì)象，并通過(guò)StatementCallback<T>接口將 Statement 對(duì)象傳遞給用戶自己去做業(yè)務(wù)邏輯。上面代碼中 QueryStatementCallback 回調(diào)實(shí)現(xiàn)中，進(jìn)行了數(shù)據(jù)查詢的操作。并通過(guò)實(shí)現(xiàn)ResultSetExtractor<T> 接口，完成數(shù)據(jù)到對(duì)象的轉(zhuǎn)換工作。

簡(jiǎn)單來(lái)說(shuō)，就是通過(guò)一個(gè)回調(diào)嵌套來(lái)完成了數(shù)據(jù)的查詢操作，同時(shí)，完成了數(shù)據(jù)到對(duì)象的轉(zhuǎn)換操作。StatementCallback<T>接口實(shí)現(xiàn)中持有了ResultSetExtractor<T> 接口的實(shí)現(xiàn)。 然后將StatementCallback<T>中接口的實(shí)現(xiàn)傳進(jìn) excute 方法中，通過(guò)在 excute 方法中回調(diào)StatementCallback<T> 接口，接著在StatementCallback<T>實(shí)現(xiàn)中回調(diào)ResultSetExtractor<T> 接口，來(lái)完成整個(gè)查詢數(shù)據(jù)到數(shù)據(jù)轉(zhuǎn)換到對(duì)象的操作。

應(yīng)用二：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 點(diǎn)擊事件，從代碼實(shí)現(xiàn)來(lái)看，點(diǎn)擊事件監(jiān)聽(tīng)器就是一個(gè)回調(diào)接口；而從業(yè)務(wù)實(shí)現(xiàn)來(lái)看，當(dāng)用戶點(diǎn)擊了按鈕后，監(jiān)聽(tīng)器就會(huì)接收到響應(yīng)，就是一個(gè)注冊(cè)了點(diǎn)擊事件的觀察者。

這里的 setOnclickListener 是一個(gè)異步回調(diào)。當(dāng)注冊(cè)好回調(diào)函數(shù)后，并不需要等待回調(diào)函數(shù)執(zhí)行，而是直接執(zhí)行后面的業(yè)務(wù)注冊(cè)后面的業(yè)務(wù)邏輯。這也再一次驗(yàn)證了異步回調(diào)比較像觀察者模式。

應(yīng)用三：addShutdownHook

Hook 和 Callback 的關(guān)系：Callback 更側(cè)重于語(yǔ)法機(jī)制的描述，而 Hook 更側(cè)重于應(yīng)用場(chǎng)景的描述。Hook 是 Callback 的一種應(yīng)用。

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");
}

上面的代碼中，當(dāng) main 方法中的I'm dying打印后，該程序就執(zhí)行完成，程序關(guān)閉。在關(guān)閉之間會(huì)回調(diào) ShutdownThread 中的方法。

模板方法和回調(diào)的區(qū)別

在應(yīng)用場(chǎng)景上，模板方法和同步回調(diào)基本上沒(méi)有什么差別，都是在一個(gè)大的算法骨架中，自由替換某些步驟，起到代碼復(fù)用和擴(kuò)展的目的。而異步回調(diào)跟模塊模式有較大差異，異步回調(diào)更像觀察者模式。

在代碼實(shí)現(xiàn)上，回調(diào)基于組合來(lái)實(shí)現(xiàn)，把一個(gè)對(duì)象傳遞到另一個(gè)對(duì)象，是一種對(duì)象之間的關(guān)系。而模板方法基于繼承實(shí)現(xiàn)，子類重寫父類的抽象方法，是一種類之間的關(guān)系。

回調(diào)相比模板方法實(shí)現(xiàn)的好處

  1. Java 只支持單繼承，如果使用模板方法實(shí)現(xiàn)后，該類就不在具有繼承能力。
  2. 回調(diào)可以使用匿名對(duì)象，可以不用事先定義類，而模板方法針對(duì)不同的實(shí)現(xiàn)，都要?jiǎng)?chuàng)建不同的子類來(lái)實(shí)現(xiàn)。
  3. 如果某個(gè)類中實(shí)現(xiàn)了多個(gè)模板方法，每個(gè)模板方法都有抽象方法，需要子類來(lái)實(shí)現(xiàn)。即便子類只用到了其中的一個(gè)模板方法都需要實(shí)現(xiàn)所有模板方法中的所有抽象方法。而如果是使用回調(diào)就更加靈活，只需要向用到的模板方法中注入對(duì)應(yīng)的回調(diào)對(duì)象即可。

3. 策略模式

3.1 定義

定義一簇算法類，將每個(gè)算法分別封裝起來(lái)，讓它們可以相互替換。策略模式可以使算法的變化獨(dú)立于使用它們的客戶端（使用算法的代碼）。

3.2 作用

  1. 解耦算法的定義、創(chuàng)建和使用，降低算法的復(fù)雜度。同時(shí)，滿足單一職責(zé)，避免由于算法的切換帶來(lái)的算法代碼的個(gè)性。
  2. 通過(guò)動(dòng)態(tài)指定算法策略，提高程序切換算法的靈活性。
  3. 基于接口實(shí)現(xiàn)，向客戶端屏蔽算法實(shí)現(xiàn)細(xì)節(jié)，易擴(kuò)展。
  4. 將多個(gè)算法獨(dú)立成類，提高了代碼的復(fù)用性。

3.3 類結(jié)構(gòu)圖

image

3.4 經(jīng)典實(shí)現(xiàn)

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. 策略的創(chuàng)建

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. 運(yùn)行時(shí)動(dòng)態(tài)指定策略：根據(jù)配置、用戶輸入或計(jì)算結(jié)果等這些不確定性因素，動(dòng)態(tài)決定使用哪種策略。
// 運(yùn)行時(shí)動(dòng)態(tài)確定，根據(jù)配置文件的配置決定使用哪種策略
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);
    //...
  }
}

// 非運(yùn)行時(shí)動(dòng)態(tài)確定，在代碼中指定使用哪種策略
public class Application {
  public static void main(String[] args) {
    //...
    EvictionStrategy evictionStrategy = new LruEvictionStrategy();
    UserCache userCache = new UserCache(evictionStrategy);
    //...
  }
}

非運(yùn)行時(shí)動(dòng)態(tài)確定，并沒(méi)有發(fā)揮策略模式的優(yōu)勢(shì)。在這種場(chǎng)景下，策略模式就退化成了“面向?qū)ο蠖鄳B(tài)編程”或者“基于接口而非實(shí)現(xiàn)編程原則”。

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

常見(jiàn)多個(gè)算法耦合在一起的例子

public class OrderService {
  public double discount(Order order) {
    double discount = 0.0;
    OrderType type = order.getType();
    if (type.equals(OrderType.NORMAL)) { // 普通訂單
      //...省略折扣計(jì)算算法代碼
    } else if (type.equals(OrderType.GROUPON)) { // 團(tuán)購(gòu)訂單
      //...省略折扣計(jì)算算法代碼
    } else if (type.equals(OrderType.PROMOTION)) { // 促銷訂單
      //...省略折扣計(jì)算算法代碼
    }
    return discount;
  }
}

改造流程

  1. 將不同訂單的打折策略設(shè)計(jì)成獨(dú)立的類
  2. 使用工廠類來(lái)對(duì)不同的策略進(jìn)行統(tǒng)一管理

改造后代碼

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

// 策略的創(chuàng)建
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);
  }
}

對(duì)分支判斷的改造本質(zhì)上是對(duì)借助“查表”法替代了根據(jù) type 的分支判斷。

3.6 應(yīng)用場(chǎng)景

給文件中數(shù)字排序

根據(jù)數(shù)據(jù)的規(guī)模將使用 4 種不同的排序算法：

  1. 針對(duì)一次性讀取到內(nèi)存的數(shù)據(jù)，可以直接使用快排或者其它算法
  2. 針對(duì)文件較大，比如：10 G，無(wú)法一次性讀取到內(nèi)存中，可以使用外部排序算法（如：桶排序、計(jì)數(shù)排序）
  3. 針對(duì)文件更大，比如：100G，可以在外部排序的基礎(chǔ)上使用多線程，實(shí)現(xiàn)一個(gè)單機(jī)版的 MapReduce
  4. 針對(duì)文件巨大，比如：1T，這時(shí)可以通過(guò)使用真正的 MapReduce 框架來(lái)實(shí)現(xiàn)

代碼實(shí)現(xiàn)

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) {
    // 省略校驗(yàn)邏輯
    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);
  }
}

對(duì)上面代碼通過(guò)引入工廠類，使用“查表”法來(lái)緩存這些無(wú)狀態(tài)的算法類。

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) {
    // 省略校驗(yàn)邏輯
    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);
  }
}

再次優(yōu)化，移除 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) {
    // 省略校驗(yàn)邏輯
    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;
    }
  }
}

目前這種實(shí)現(xiàn)，在添加新的策略類時(shí)，需要同時(shí)在 Sorter 類和 SortAlgFactory 類中添加對(duì)應(yīng)的邏輯，并不完全符合開(kāi)閉原則。有什么辦法讓上面的代碼完全符合開(kāi)閉原則呢？

對(duì)于工廠類的修改，可以通過(guò)反射 + 注解的方式。這里有兩種實(shí)現(xiàn)方式：

  1. 通過(guò)配置文件配置對(duì)應(yīng)的策略類，程序啟動(dòng)時(shí)，讀取配置文件，并通過(guò)反射將所有的策略類對(duì)象添加到工廠類中。
  2. 為每個(gè)策略類設(shè)置注解，程序啟動(dòng)時(shí)，會(huì)通過(guò)掃描所有的注解，并通過(guò)反射將所有的策略類對(duì)象添加到工廠類中。

對(duì)于 Sorter 類的修改，可以通過(guò)配置文件的方式，將文件區(qū)間大小和算法之間的對(duì)應(yīng)關(guān)系放到配置文件中。當(dāng)添加新算法時(shí)，只需要改動(dòng)區(qū)間與算法的對(duì)應(yīng)關(guān)系即可。

4. 責(zé)任鏈模式

其實(shí)現(xiàn)可以參考我的另一篇博客。里面做了更加詳細(xì)的說(shuō)明，點(diǎn)擊跳轉(zhuǎn)。

5. 狀態(tài)模式

5.1 定義

允許對(duì)象在其內(nèi)部狀態(tài)改變時(shí)，更改其對(duì)應(yīng)的行為。和有限狀態(tài)機(jī)的概念非常相似。

什么是有限狀態(tài)機(jī)

有限狀態(tài)機(jī)簡(jiǎn)稱狀態(tài)機(jī)，由狀態(tài)（State）、事件（Event）、和動(dòng)作(Action)三部分組成。其中，事情也稱為狀態(tài)轉(zhuǎn)移條件。事件觸發(fā)狀態(tài)的轉(zhuǎn)移及動(dòng)作的執(zhí)行，當(dāng)然，動(dòng)作不是必須的，也可以是發(fā)生狀態(tài)的轉(zhuǎn)移。

5.2 作用

5.3 類結(jié)構(gòu)圖

image

5.4 狀態(tài)機(jī)的實(shí)現(xiàn)方式

1. 狀態(tài)模式實(shí)現(xiàn)

2. 分支邏輯法

3. 查表法

5.5 應(yīng)用場(chǎng)景

超級(jí)瑪麗奧

馬里奧有多種形態(tài)：小巴里奧、超級(jí)馬里奧、火焰馬里奧和斗篷馬里奧。

在不同的游戲情節(jié)下，各種形態(tài)會(huì)相互轉(zhuǎn)化，并相應(yīng)的增減積分。比如：小馬里奧吃了一個(gè)蘑菇后，變成超級(jí)巴里奧，并增加 100 積分。

吃了一個(gè)蘑菇對(duì)應(yīng)事件（Event）,變成超級(jí)馬里奧對(duì)應(yīng)狀態(tài)的變化，增加 100 積分對(duì)應(yīng)狀態(tài)變化后的動(dòng)作執(zhí)行。

各狀態(tài)之間的轉(zhuǎn)換如下圖：

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;
  }
}

如果分支邏輯比較簡(jiǎn)單，是可以接受的。但如果對(duì)于復(fù)雜的狀態(tài)機(jī)來(lái)說(shuō)，這種情況極有可能漏寫代碼，同時(shí)，每個(gè)事件中所對(duì)應(yīng)狀態(tài)改變及動(dòng)作執(zhí)行會(huì)包含大量的 if-else 邏輯，可讀性和可維護(hù)性非常差。而且，當(dāng)要新增加一種狀態(tài)的話，每個(gè)事件里里的代碼都會(huì)被修改，代碼將非常難以維護(hù)。

查表法

image

在上面的二維表中，第一維表示當(dāng)前狀態(tài)，第二維表示事件，值表示當(dāng)前狀態(tài)經(jīng)過(guò)事件之后，轉(zhuǎn)移到新的狀態(tài)及要執(zhí)行的動(dòng)作。

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;
  }

}

上面使用兩個(gè)二維數(shù)組非常巧妙的將觸發(fā)事件后所對(duì)應(yīng)的狀態(tài)和對(duì)應(yīng)狀態(tài)所需要執(zhí)行的動(dòng)作都表示了出來(lái)。在具體實(shí)現(xiàn)的時(shí)候，只需要通過(guò)當(dāng)前事件去這兩個(gè)二維數(shù)組中獲取對(duì)應(yīng)的狀態(tài)和需要執(zhí)行的動(dòng)作即可，非常的簡(jiǎn)單，代碼實(shí)現(xiàn)也非常的簡(jiǎn)潔。

但也存在問(wèn)題，就是這里的動(dòng)作只是簡(jiǎn)單的加減積分，如果是一系列的操作，這種實(shí)現(xiàn)有無(wú)法滿足需求了。

狀態(tài)模式實(shí)現(xiàn)

狀態(tài)模式實(shí)際上是對(duì)分支邏輯法的一種優(yōu)化處理。狀態(tài)模式是將事件觸發(fā)的狀態(tài)轉(zhuǎn)移和動(dòng)作執(zhí)行，拆分到了不同的狀態(tài)類中，來(lái)避免分支判斷邏輯的。

public interface IMario { //所有狀態(tài)類的接口
  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; // 不再使用枚舉來(lái)表示狀態(tài)

  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 是一個(gè)狀態(tài)維護(hù)類，所有狀態(tài)的變更都是通過(guò)這里維護(hù)的。而實(shí)現(xiàn)了 IMario 接口的這些類，主要是負(fù)責(zé)維護(hù)在當(dāng)前狀態(tài)下，事件觸發(fā)后的動(dòng)作的執(zhí)行。

兩者是雙向依賴關(guān)系，當(dāng)事件觸發(fā)后，會(huì)先 MarioStateMachine 中對(duì)應(yīng)事件的方法，這些方法會(huì)調(diào)用到對(duì)應(yīng)狀態(tài)實(shí)現(xiàn)類中對(duì)應(yīng)的動(dòng)作的執(zhí)行。而動(dòng)作執(zhí)行的過(guò)程中，又需要反過(guò)來(lái)更新 MarioStateMachine 中的狀態(tài)。

由于狀態(tài)類中不包含任何的成員變量（狀態(tài)），所以，可以將其設(shè)計(jì)成單例對(duì)象。優(yōu)化后的代碼如下：

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;
  }
}

查表法和狀態(tài)模式的應(yīng)用場(chǎng)景

  1. 查表法：像游戲這種比較復(fù)雜的狀態(tài)機(jī)，包含的狀態(tài)比較多，優(yōu)先推薦查表法，而如果使用狀態(tài)模式的話，會(huì)引入非常多的狀態(tài)類，會(huì)導(dǎo)致代碼比較難維護(hù)。
  2. 狀態(tài)模式：像電商下單、外賣下單這種類型的狀態(tài)機(jī)，狀態(tài)相對(duì)有限，而事件觸發(fā)執(zhí)行的動(dòng)作包含的業(yè)務(wù)邏輯可能比較復(fù)雜的情況下，使用狀態(tài)模式更合適。

6. 迭代器模式

6.1 定義

提供一種方法訪問(wèn)一個(gè)容器（container）對(duì)象中各個(gè)元素，而又不需暴露該對(duì)象的內(nèi)部細(xì)節(jié)。

6.2 作用

  1. 迭代器模式封裝集合內(nèi)部的復(fù)雜數(shù)據(jù)結(jié)構(gòu)，開(kāi)發(fā)者不需要了解如何遍歷，直接使用窗口提供的迭代器即可，提供容器的易用性
  2. 迭代器模式將對(duì)集合的遍歷操作從集合類中拆分出來(lái)，放到迭代器中，讓兩者的職責(zé)更加單一
  3. 迭代器讓新增新的遍歷算法非常的容易，只需要實(shí)現(xiàn)迭代器接口，并在容器接口中提供對(duì)應(yīng)的創(chuàng)建方法即可，更加符合開(kāi)閉原則

6.3 類結(jié)構(gòu)圖

image

6.4 經(jīng)典實(shí)現(xiàn)

// 接口定義方式一
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在指向最后一個(gè)元素的時(shí)候，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();
    }
  }
}

上面的實(shí)現(xiàn)是將容器對(duì)象通過(guò)構(gòu)造函數(shù)直接傳遞給了迭代器對(duì)象，而為了封裝迭代器的創(chuàng)建細(xì)節(jié)，我們可以在容器對(duì)象中定義一個(gè) iterator 方法，來(lái)創(chuàng)建對(duì)應(yīng)的迭代器。改造代碼如下：

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

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();
    }
  }
}

下圖是容器對(duì)象和迭代器對(duì)象的依賴關(guān)系圖：

image

6.5 迭代器遍歷集合的優(yōu)勢(shì)

遍歷集合的3種方式

  1. for
  2. foreach
  3. iterator

而 foreach 是基于 iterator 實(shí)現(xiàn)的，也就是說(shuō)，本質(zhì)上只有 2 種遍歷集合的方式。

迭代器優(yōu)勢(shì)

  1. 迭代器模式封裝集合內(nèi)部的復(fù)雜數(shù)據(jù)結(jié)構(gòu)，開(kāi)發(fā)者不需要了解如何遍歷，直接使用窗口提供的迭代器即可
  2. 迭代器模式將對(duì)集合的遍歷操作從集合類中拆分出來(lái)，放到迭代器中，讓兩者的職責(zé)更加單一
  3. 迭代器讓新增新的遍歷算法非常的容易，只需要實(shí)現(xiàn)迭代器接口，并在容器接口中提供對(duì)應(yīng)的創(chuàng)建方法即可，更加符合開(kāi)閉原則

6.6 遍歷集合的時(shí)候，為什么不能增刪集合中元素

主要是由于集合底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，當(dāng)刪除元素時(shí)，會(huì)將數(shù)組向前移動(dòng)一位，而再去遍歷元素的時(shí)候，就有可能出現(xiàn)有些數(shù)據(jù)被漏掉的情況。

而增加一個(gè)新的元素，插入位置之后的元素都會(huì)向后移動(dòng)一位，就有可能出現(xiàn)某個(gè)元素會(huì)被重復(fù)遍歷的情況。

ArrayList 的解決思路

在遍歷的過(guò)程中，出現(xiàn)增刪元素之后，直接報(bào)錯(cuò)。

如何確定是否有增刪元素

ArrayList 定義了一個(gè) modCount 變量，集合每次調(diào)用增刪都會(huì)將 modCount 加 1。然后，將每次通過(guò) ArrayList 的 iterator 函數(shù)創(chuàng)建迭代器的時(shí)候，會(huì)將 modCount 的值賦值給 expectedModCount 變量（expectedModCount 是 Iterator 對(duì)象中的變量）。之后，每次調(diào)用當(dāng)前 Iterator 迭代器對(duì)象的 hasNext()、next()函數(shù)，都會(huì)檢查 modCount 和 exceptedModCount 值是否相等。如果不相等，則說(shuō)明迭代器在遍歷過(guò)程中，元素進(jìn)行了增刪的操作。此時(shí)，遵循 fail-fast 原則，會(huì)拋出 ConcurrentModificationException 異常。

什么是 fail-fast 原則

fail-fast 是一種系統(tǒng)的設(shè)計(jì)思想，當(dāng)程序有可能出現(xiàn)異常的時(shí)候，應(yīng)該盡可能的上報(bào)其錯(cuò)誤信息，讓程序終止運(yùn)行，而讓程序設(shè)計(jì)者盡早知道問(wèn)題，并解決問(wèn)題。

6.7 如果在遍歷的同時(shí)，安全地刪除元素

Iterator 迭代器中提供了 remove() 的方法來(lái)支持在遍歷過(guò)程中，刪除元素的操作。但這個(gè) remove 的操作的作用是有限的，它只能刪除當(dāng)前 遍歷游標(biāo) cursor 所在位置的前一個(gè)元素，而且只能執(zhí)行一次刪除操作，連續(xù)調(diào)用兩次操作，直接會(huì)報(bào)錯(cuò)。

具體的刪除操作是：在 Iterator 中定義了 lastRet 變量，每次調(diào)用 next() 方法后，會(huì)將當(dāng)前游標(biāo)所指定的位置賦值給 lastRet，然后游標(biāo)自加 1 并指向下一個(gè)位置。當(dāng)調(diào)用了 remove() 方法后，會(huì)刪除 lastRet 所指向位置的元素，并將 lastRet 賦值給當(dāng)前的 cursor 游標(biāo)，也就是將游標(biāo)的位置向前移動(dòng)了一位。

cursor = lastRet 賦值操作完成后，會(huì)將 lastRet 賦值為 -1，當(dāng)再次調(diào)用 remove() 方法時(shí)，如果沒(méi)有調(diào)用 next() 方法給 lastRet 重新賦值的話，由于 lastRet 仍然等于 -1，則會(huì)拋出異常。

6.8. 實(shí)現(xiàn)帶“快照”功能的迭代器，徹底解決增刪問(wèn)題

方案一：直接拷貝集合數(shù)據(jù)

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;
  }
}

直接在創(chuàng)建迭代器的時(shí)候，將原有集合中的元素拷貝一份。簡(jiǎn)單直接，但代價(jià)較高。

方案二：添加時(shí)間戳標(biāo)記每個(gè)元素

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

  private int actualSize; //不包含標(biāo)記刪除元素
  private int totalSize; //包含標(biāo)記刪除元素

  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; // 在整個(gè)容器中的下標(biāo)，而非快照中的下標(biāo)
  private int leftCount; // 快照中還有幾個(gè)元素未被遍歷
  private ArrayList<E> arrayList;

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

    justNext(); // 先跳到這個(gè)迭代器快照的第一個(gè)元素
  }

  @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++;
    }
  }
}

添加三個(gè)時(shí)間戳，分別是元素添加時(shí)間戳 addTimestamp、元素刪除時(shí)間戳 delTimestamp 和迭代器創(chuàng)建時(shí)時(shí)間戳 snapshotTimestamp。當(dāng)滿足 addTimestamp < snapshotTimestamp < delTimestamp 時(shí)，說(shuō)明當(dāng)前元素是創(chuàng)建 Iterator 迭代器時(shí)，快照的元素，需要被遍歷到。

而當(dāng) addTimestamp > snapshotTimestamp 時(shí)，說(shuō)明當(dāng)前元素是快照生成之后添加到集合的，不屬于快照中的元素；當(dāng) snapshotTimestamp > delTimestamp 時(shí)，說(shuō)明當(dāng)前元素在創(chuàng)建快照之前就已經(jīng)被刪除了，同樣的，也不屬于快照中的元素。這兩種情況下，對(duì)應(yīng)的元素都不應(yīng)該被 遍歷到。

方案二存在問(wèn)題：

由于刪除元素只是標(biāo)記而非刪除，這樣就導(dǎo)致隨機(jī)訪問(wèn)失效。相當(dāng)于為了修復(fù)一個(gè)問(wèn)題，引入了另一個(gè)問(wèn)題。而本來(lái)隨機(jī)訪問(wèn)特性是以數(shù)組為底層數(shù)據(jù)結(jié)構(gòu)的一個(gè)優(yōu)勢(shì)，通過(guò)標(biāo)記而非刪除的方式實(shí)現(xiàn)后，這種優(yōu)勢(shì)就被丟棄了，得不償失。

解決方案二中存在的問(wèn)題：讓容器既支持快照，又支持隨機(jī)訪問(wèn)

可以在 ArrayList 中創(chuàng)建兩個(gè)數(shù)組，一個(gè)用來(lái)支持標(biāo)記清除的，用來(lái)實(shí)現(xiàn)快照功能。另一個(gè)不支持標(biāo)記清除的，用來(lái)支持隨機(jī)訪問(wèn)。

說(shuō)明

此文是根據(jù)王爭(zhēng)設(shè)計(jì)模式之美相關(guān)專欄內(nèi)容整理而來(lái)，非原創(chuàng)。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容