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

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

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

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

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

1. 觀察者模式

1.1 定義

在對象之間定義一個一對多的依賴考榨，當一個對象狀態(tài)改變的時候蚊逢，所有依賴的對象都會自動收到通知悯仙。

1.2 作用

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

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

image

1.4 經(jīng)典實現(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è)計模式的本質(zhì)

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

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

1.6 觀察都模式的種類

1. 同步阻塞

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

2. 異步非阻塞

最簡單的實現(xiàn)是在每個 update 方法中開啟一個線程來執(zhí)行更新鞭莽。另外一種方式是直接在被觀察者中使用一個線程池來執(zhí)行對各觀察者的調(diào)用。當然麸祷，可以使用事件總線 EventBus 來實現(xiàn)異步非阻塞的澎怒。

3. 進程內(nèi)實現(xiàn)

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

4. 跨進程實現(xiàn)

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

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

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

1.7 應(yīng)用場景

EventBus

框架的作用

  1. 隱藏實現(xiàn)細節(jié)
  2. 降低開發(fā)難度
  3. 代碼復(fù)用
  4. 解耦業(yè)務(wù)與非業(yè)務(wù)代碼
  5. 讓程序員聚焦功能的開發(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ù)的校驗代碼
    //省略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. 通過調(diào)用 EventBus 的 register 方法進行注冊工作
  2. 通過 @Subscribe 來注冊哪些方法用來接收更新
  3. 通過 @Subscribe 所注冊方法中的參數(shù)來判斷 EventBus 發(fā)送的數(shù)據(jù)哪些注冊了 EventBus 的哪些方法可以接收到此更新

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

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

EventBus 的注冊過程

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

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

image

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

異步非阻塞是通過線程池來完成的芒澜。為了統(tǒng)一邏輯處理仰剿，同步阻塞也可以依賴線程池，只不過這個線程池里只有一個線程痴晦。

2. 模板方法模式

2.1 定義

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

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

2.2 作用

  1. 通過繼承的實現(xiàn)方式，復(fù)用邏輯箱锐，提高復(fù)用性
  2. 通過提供抽象方法由子類來實現(xiàn)比勉，提高擴展性

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

image

2.4. 經(jīng)典實現(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)用場景

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) 是需要子類實現(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() 是需要子類進行實現(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() 則是需要子類選擇性進行擴展的方法。

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

Callback 回調(diào)機制

比如：A 類事先注冊了 F 函數(shù)到了 B 類闸与，然后毙替，A 類調(diào)用了 B 類的 P 函數(shù)，B 類返過來調(diào)用 A 類的 F 函數(shù)践樱。這里的 F 函數(shù)就是“回調(diào)函數(shù)”厂画。A 調(diào)用 B，B 反過來又調(diào)用 A拷邢，這種機制稱為“回調(diào)”袱院。

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

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

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)看起來更像模板模式欲虚。
異步回調(diào)看起來更像觀察者模式。

應(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 所實現(xiàn)的mapRow(ResultSet rs, int rowNum) 就是一個回調(diào)函數(shù)悔雹，負責(zé)將通過 JDBC 查詢到的數(shù)據(jù)轉(zhuǎn)換為對象复哆，并返回。

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

簡單來說牙咏，就是通過一個回調(diào)嵌套來完成了數(shù)據(jù)的查詢操作，同時嘹裂，完成了數(shù)據(jù)到對象的轉(zhuǎn)換操作妄壶。StatementCallback<T>接口實現(xiàn)中持有了ResultSetExtractor<T> 接口的實現(xiàn)。 然后將StatementCallback<T>中接口的實現(xiàn)傳進 excute 方法中寄狼，通過在 excute 方法中回調(diào)StatementCallback<T> 接口丁寄，接著在StatementCallback<T>實現(xiàn)中回調(diào)ResultSetExtractor<T> 接口氨淌，來完成整個查詢數(shù)據(jù)到數(shù)據(jù)轉(zhuǎn)換到對象的操作。

應(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 點擊事件伊磺，從代碼實現(xiàn)來看盛正，點擊事件監(jiān)聽器就是一個回調(diào)接口；而從業(yè)務(wù)實現(xiàn)來看屑埋，當用戶點擊了按鈕后豪筝，監(jiān)聽器就會接收到響應(yīng)，就是一個注冊了點擊事件的觀察者摘能。

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

應(yīng)用三：addShutdownHook

Hook 和 Callback 的關(guān)系：Callback 更側(cè)重于語法機制的描述逻恐，而 Hook 更側(cè)重于應(yī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");
}

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

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

在應(yīng)用場景上阵面，模板方法和同步回調(diào)基本上沒有什么差別轻局，都是在一個大的算法骨架中，自由替換某些步驟样刷，起到代碼復(fù)用和擴展的目的仑扑。而異步回調(diào)跟模塊模式有較大差異，異步回調(diào)更像觀察者模式置鼻。

在代碼實現(xiàn)上镇饮，回調(diào)基于組合來實現(xiàn)，把一個對象傳遞到另一個對象箕母，是一種對象之間的關(guān)系储藐。而模板方法基于繼承實現(xiàn)，子類重寫父類的抽象方法嘶是，是一種類之間的關(guān)系钙勃。

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

  1. Java 只支持單繼承，如果使用模板方法實現(xiàn)后聂喇，該類就不在具有繼承能力辖源。
  2. 回調(diào)可以使用匿名對象，可以不用事先定義類，而模板方法針對不同的實現(xiàn)克饶，都要創(chuàng)建不同的子類來實現(xiàn)酝蜒。
  3. 如果某個類中實現(xiàn)了多個模板方法，每個模板方法都有抽象方法矾湃，需要子類來實現(xiàn)亡脑。即便子類只用到了其中的一個模板方法都需要實現(xiàn)所有模板方法中的所有抽象方法。而如果是使用回調(diào)就更加靈活洲尊，只需要向用到的模板方法中注入對應(yīng)的回調(diào)對象即可远豺。

3. 策略模式

3.1 定義

定義一簇算法類，將每個算法分別封裝起來坞嘀，讓它們可以相互替換躯护。策略模式可以使算法的變化獨立于使用它們的客戶端（使用算法的代碼）。

3.2 作用

  1. 解耦算法的定義丽涩、創(chuàng)建和使用棺滞，降低算法的復(fù)雜度。同時矢渊，滿足單一職責(zé)继准，避免由于算法的切換帶來的算法代碼的個性。
  2. 通過動態(tài)指定算法策略矮男，提高程序切換算法的靈活性移必。
  3. 基于接口實現(xiàn)，向客戶端屏蔽算法實現(xiàn)細節(jié)毡鉴，易擴展崔泵。
  4. 將多個算法獨立成類，提高了代碼的復(fù)用性猪瞬。

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

image

3.4 經(jīng)典實現(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. 運行時動態(tài)指定策略：根據(jù)配置憎瘸、用戶輸入或計算結(jié)果等這些不確定性因素，動態(tài)決定使用哪種策略陈瘦。
// 運行時動態(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);
    //...
  }
}

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

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

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. 將不同訂單的打折策略設(shè)計成獨立的類
  2. 使用工廠類來對不同的策略進行統(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);
  }
}

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

3.6 應(yīng)用場景

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

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

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

代碼實現(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) {
    // 省略校驗邏輯
    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);
  }
}

對上面代碼通過引入工廠類枣宫，使用“查表”法來緩存這些無狀態(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) {
    // 省略校驗邏輯
    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) {
    // 省略校驗邏輯
    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;
    }
  }
}

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

對于工廠類的修改竭沫，可以通過反射 + 注解的方式燥翅。這里有兩種實現(xiàn)方式：

  1. 通過配置文件配置對應(yīng)的策略類，程序啟動時蜕提，讀取配置文件森书，并通過反射將所有的策略類對象添加到工廠類中。
  2. 為每個策略類設(shè)置注解谎势，程序啟動時拄氯，會通過掃描所有的注解，并通過反射將所有的策略類對象添加到工廠類中它浅。

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

4. 責(zé)任鏈模式

其實現(xiàn)可以參考我的另一篇博客镊折。里面做了更加詳細的說明，點擊跳轉(zhuǎn)介衔。

5. 狀態(tài)模式

5.1 定義

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

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

有限狀態(tài)機簡稱狀態(tài)機赃泡，由狀態(tài)（State）寒波、事件（Event）、和動作(Action)三部分組成升熊。其中俄烁，事情也稱為狀態(tài)轉(zhuǎn)移條件。事件觸發(fā)狀態(tài)的轉(zhuǎn)移及動作的執(zhí)行级野，當然页屠，動作不是必須的，也可以是發(fā)生狀態(tài)的轉(zhuǎn)移蓖柔。

5.2 作用

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

image

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

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

2. 分支邏輯法

3. 查表法

5.5 應(yīng)用場景

超級瑪麗奧

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

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

吃了一個蘑菇對應(yīng)事件（Event）,變成超級馬里奧對應(yīng)狀態(tài)的變化帮辟，增加 100 積分對應(yīng)狀態(tài)變化后的動作執(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;
  }
}

如果分支邏輯比較簡單玩焰，是可以接受的由驹。但如果對于復(fù)雜的狀態(tài)機來說，這種情況極有可能漏寫代碼昔园，同時蔓榄，每個事件中所對應(yīng)狀態(tài)改變及動作執(zhí)行會包含大量的 if-else 邏輯，可讀性和可維護性非常差默刚。而且甥郑，當要新增加一種狀態(tài)的話，每個事件里里的代碼都會被修改荤西，代碼將非常難以維護澜搅。

查表法

image

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

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

}

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

但也存在問題，就是這里的動作只是簡單的加減積分糖赔，如果是一系列的操作萍丐，這種實現(xiàn)有無法滿足需求了。

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

狀態(tài)模式實際上是對分支邏輯法的一種優(yōu)化處理放典。狀態(tài)模式是將事件觸發(fā)的狀態(tài)轉(zhuǎn)移和動作執(zhí)行逝变，拆分到了不同的狀態(tà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; // 不再使用枚舉來表示狀態(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 是一個狀態(tài)維護類，所有狀態(tài)的變更都是通過這里維護的弥臼。而實現(xiàn)了 IMario 接口的這些類宴咧，主要是負責(zé)維護在當前狀態(tài)下，事件觸發(fā)后的動作的執(zhí)行径缅。

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

由于狀態(tài)類中不包含任何的成員變量（狀態(tài)）沙绝，所以，可以將其設(shè)計成單例對象鼠锈。優(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)用場景

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

6. 迭代器模式

6.1 定義

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

6.2 作用

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

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

image

6.4 經(jīng)典實現(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在指向最后一個元素的時候肩杈，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();
    }
  }
}

上面的實現(xiàn)是將容器對象通過構(gòu)造函數(shù)直接傳遞給了迭代器對象解寝，而為了封裝迭代器的創(chuàng)建細節(jié)扩然，我們可以在容器對象中定義一個 iterator 方法，來創(chuàng)建對應(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();
    }
  }
}

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

image

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

遍歷集合的3種方式

  1. for
  2. foreach
  3. iterator

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

迭代器優(yōu)勢

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

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

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

而增加一個新的元素，插入位置之后的元素都會向后移動一位济锄，就有可能出現(xiàn)某個元素會被重復(fù)遍歷的情況暑椰。

ArrayList 的解決思路

在遍歷的過程中，出現(xiàn)增刪元素之后荐绝，直接報錯一汽。

如何確定是否有增刪元素

ArrayList 定義了一個 modCount 變量，集合每次調(diào)用增刪都會將 modCount 加 1低滩。然后召夹，將每次通過 ArrayList 的 iterator 函數(shù)創(chuàng)建迭代器的時候岩喷，會將 modCount 的值賦值給 expectedModCount 變量（expectedModCount 是 Iterator 對象中的變量）。之后监憎，每次調(diào)用當前 Iterator 迭代器對象的 hasNext()纱意、next()函數(shù)，都會檢查 modCount 和 exceptedModCount 值是否相等鲸阔。如果不相等偷霉，則說明迭代器在遍歷過程中，元素進行了增刪的操作隶债。此時腾它，遵循 fail-fast 原則，會拋出 ConcurrentModificationException 異常死讹。

什么是 fail-fast 原則

fail-fast 是一種系統(tǒng)的設(shè)計思想瞒滴，當程序有可能出現(xiàn)異常的時候，應(yīng)該盡可能的上報其錯誤信息赞警，讓程序終止運行妓忍，而讓程序設(shè)計者盡早知道問題，并解決問題愧旦。

6.7 如果在遍歷的同時世剖，安全地刪除元素

Iterator 迭代器中提供了 remove() 的方法來支持在遍歷過程中，刪除元素的操作笤虫。但這個 remove 的操作的作用是有限的旁瘫，它只能刪除當前 遍歷游標 cursor 所在位置的前一個元素，而且只能執(zhí)行一次刪除操作琼蚯，連續(xù)調(diào)用兩次操作酬凳，直接會報錯。

具體的刪除操作是：在 Iterator 中定義了 lastRet 變量遭庶，每次調(diào)用 next() 方法后宁仔，會將當前游標所指定的位置賦值給 lastRet，然后游標自加 1 并指向下一個位置峦睡。當調(diào)用了 remove() 方法后翎苫，會刪除 lastRet 所指向位置的元素，并將 lastRet 賦值給當前的 cursor 游標榨了，也就是將游標的位置向前移動了一位煎谍。

cursor = lastRet 賦值操作完成后，會將 lastRet 賦值為 -1龙屉，當再次調(diào)用 remove() 方法時呐粘，如果沒有調(diào)用 next() 方法給 lastRet 重新賦值的話，由于 lastRet 仍然等于 -1，則會拋出異常事哭。

6.8. 實現(xià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)建迭代器的時候瓜富，將原有集合中的元素拷貝一份鳍咱。簡單直接，但代價較高与柑。

方案二：添加時間戳標記每個元素

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 和迭代器創(chuàng)建時時間戳 snapshotTimestamp丑念。當滿足 addTimestamp < snapshotTimestamp < delTimestamp 時，說明當前元素是創(chuàng)建 Iterator 迭代器時结蟋，快照的元素脯倚，需要被遍歷到。

而當 addTimestamp > snapshotTimestamp 時嵌屎，說明當前元素是快照生成之后添加到集合的推正，不屬于快照中的元素；當 snapshotTimestamp > delTimestamp 時宝惰，說明當前元素在創(chuàng)建快照之前就已經(jīng)被刪除了植榕，同樣的，也不屬于快照中的元素尼夺。這兩種情況下尊残，對應(yīng)的元素都不應(yīng)該被 遍歷到。

方案二存在問題：

由于刪除元素只是標記而非刪除淤堵，這樣就導(dǎo)致隨機訪問失效寝衫。相當于為了修復(fù)一個問題，引入了另一個問題粘勒。而本來隨機訪問特性是以數(shù)組為底層數(shù)據(jù)結(jié)構(gòu)的一個優(yōu)勢竞端，通過標記而非刪除的方式實現(xiàn)后，這種優(yōu)勢就被丟棄了庙睡，得不償失事富。

解決方案二中存在的問題：讓容器既支持快照，又支持隨機訪問

可以在 ArrayList 中創(chuàng)建兩個數(shù)組乘陪，一個用來支持標記清除的统台，用來實現(xiàn)快照功能。另一個不支持標記清除的啡邑，用來支持隨機訪問贱勃。

說明

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

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末贵扰，一起剝皮案震驚了整個濱河市仇穗，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌戚绕，老刑警劉巖纹坐，帶你破解...
    沈念sama閱讀 216,470評論 6贊 501
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異舞丛，居然都是意外死亡耘子，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,393評論 3贊 392
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門球切，熙熙樓的掌柜王于貴愁眉苦臉地迎上來谷誓，“玉大人，你說我怎么就攤上這事吨凑『赐幔” “怎么了？”我有些...
    開封第一講書人閱讀 162,577評論 0贊 353
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵鸵钝，是天一觀的道長费封。 經(jīng)常有香客問我，道長蒋伦，這世上最難降的妖魔是什么弓摘？ 我笑而不...
    開封第一講書人閱讀 58,176評論 1贊 292
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮痕届，結(jié)果婚禮上韧献，老公的妹妹穿的比我還像新娘。我一直安慰自己研叫，他們只是感情好锤窑，可當我...
    茶點故事閱讀 67,189評論 6贊 388
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布。 她就那樣靜靜地躺著嚷炉，像睡著了一般渊啰。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上申屹，一...
    開封第一講書人閱讀 51,155評論 1贊 299
  • 城市分裂傳說
    那天绘证，我揣著相機與錄音，去河邊找鬼哗讥。 笑死嚷那，一個胖子當著我的面吹牛，可吹牛的內(nèi)容都是我干的杆煞。 我是一名探鬼主播魏宽，決...
    沈念sama閱讀 40,041評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼腐泻，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了队询？” 一聲冷哼從身側(cè)響起派桩，我...
    開封第一講書人閱讀 38,903評論 0贊 274
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎蚌斩，沒想到半個月后窄坦，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 45,319評論 1贊 310
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡凳寺，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,539評論 2贊 332
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了彤侍。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片肠缨。...
    茶點故事閱讀 39,703評論 1贊 348
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖盏阶，靈堂內(nèi)的尸體忽然破棺而出晒奕，到底是詐尸還是另有隱情，我是刑警寧澤名斟，帶...
    沈念sama閱讀 35,417評論 5贊 343
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布脑慧，位于F島的核電站，受9級特大地震影響砰盐，放射性物質(zhì)發(fā)生泄漏闷袒。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點故事閱讀 41,013評論 3贊 325
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一岩梳、第九天 我趴在偏房一處隱蔽的房頂上張望囊骤。 院中可真熱鬧，春花似錦冀值、人聲如沸也物。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,664評論 0贊 22
  • 一樁弒父案列疗，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽滑蚯。三九已至，卻和暖如春抵栈，著一層夾襖步出監(jiān)牢的瞬間告材，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,818評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工古劲， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留创葡，地道東北人。 一個月前我還...
    沈念sama閱讀 47,711評論 2贊 368
  • 代替公主和親
    正文 我出身青樓绢慢，卻偏偏與公主長得像灿渴，于是被迫代替她去往敵國和親洛波。 傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
    茶點故事閱讀 44,601評論 2贊 353