天天看點
傳回

資料結構與算法 - 線性結構

本期主要内容：

  • 棧
  • 隊列
    • 隊列在HTTP1.1 / Http 2.0 中的運用
  • 連結清單
    • 連結清單在React Fiber 中的運用
  • 題目練習
    • Set， Map, 棧， 隊列

首先，這篇文章不是講解資料結構的文章，而是結合現實的場景幫助大家

了解和複習

資料結構與算法 。

如果你的資料結構基礎很差，建議先去看一些基礎教程，再轉過來看。

本篇文章的定位是側重于前端的，通過學習前端中實際場景的資料結構，進而加深大家對資料結構的了解和認識。

線性結構

資料結構我們可以從邏輯上分為線性結構和非線性結構。

線性結構有：數組，棧，連結清單等，

非線性結構有樹，圖等。

其實我們可以稱樹為一種半線性結構。

需要注意的是，線性和非線性不代表存儲結構是線性的還是非線性的，這兩者沒有任何關系，它隻是一種邏輯上的劃分。比如我們可以用數組去存儲二叉樹。

一般而言，有前驅和後繼的就是線性資料結構。

比如數組和連結清單。其實一叉樹就是連結清單。

數組

數組是最簡單的資料結構了，很多地方都用到它。

比如有一個資料清單等，用它是再合适不過了。

我們之後要講的棧和隊列其實都可以看成是一種

受限

的數組, 怎麼個受限法呢？

我們後面讨論。

我們來講幾個有趣的例子來加深大家對數組這種資料結構的了解。

React Hooks

Hooks的本質就是一個數組， 僞代碼：

資料結構與算法 - 線性結構

那麼為什麼hooks要用數組？我們可以換個角度來解釋，如果不用數組會怎麼樣？

function Form() {
  // 1. Use the name state variable
  const [name, setName] = useState('Mary');

  // 2. Use an effect for persisting the form
  useEffect(function persistForm() {
    localStorage.setItem('formData', name);
  });

  // 3. Use the surname state variable
  const [surname, setSurname] = useState('Poppins');

  // 4. Use an effect for updating the title
  useEffect(function updateTitle() {
    document.title = name + ' ' + surname;
  });

  // ...
}

複制

基于數組的方式，Form的hooks就是 [hook1, hook2, hook3, hook4], 我們可以得出這樣的關系， hook1就是[name, setName] 這一對， hook2就是persistForm這個。

如果不用數組實作，比如對象，Form的hooks就是

{
  'key1': hook1,
  'key2': hook2,
  'key3': hook3,
  'key4': hook4,
}

複制

那麼問題是key1，key2，key3，key4怎麼取呢？

關于React hooks 的本質研究，更多請檢視React hooks: not magic, just arrays

React 将

如何確定元件内部hooks儲存的狀态之間的對應關系

這個工作交給了 開發人員去保證，即你必須保證HOOKS的順序嚴格一緻，具體可以看React 官網關于 Hooks Rule 部分。

隊列

隊列是一種受限的序列，它隻能夠操作隊尾和隊首，并且隻能隻能在隊尾添加元素，在隊首删除元素。

隊列作為一種最常見的資料結構同樣有着非常廣泛的應用， 比如消息隊列

"隊列"這個名稱,可類比為現實生活中排隊（不插隊的那種）

在計算機科學中, 一個 隊列(queue) 是一種特殊類型的抽象資料類型或集合。集合中的實體按順序儲存。

隊列基本操作有兩種:

  • 向隊列的後端位置添加實體，稱為入隊
  • 從隊列的前端位置移除實體，稱為出隊。

隊列中元素先進先出 FIFO (first in, first out)的示意：

資料結構與算法 - 線性結構

(圖檔來自 https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/queue/README.zh-CN.md)

我們前端在做性能優化的時候，很多時候會提到的一點就是“HTTP 1.1 的隊頭阻塞問題”。

具體來說，就是HTTP2 解決了 HTTP1.1 中的隊頭阻塞問題，但是為什麼HTTP1.1有隊頭阻塞問題，HTTP2究竟怎麼解決的很多人都不清楚。

其實“隊頭阻塞”是一個專有名詞，不僅僅這裡有，交換器等其他都有這個問題，引起這個問題的根本原因是使用了

隊列

這種資料結構。

對于同一個tcp連接配接，所有的http1.0請求放入隊列中，隻有前一個

請求的響應

收到了，然後才能發送下一個請求，這個阻塞主要發生在用戶端。

這就好像我們在等紅綠燈，即使旁邊綠燈亮了，你的這個車道是紅燈，你還是不能走，還是要等着。

資料結構與算法 - 線性結構

HTTP/1.0

和

HTTP/1.1

: 在

HTTP/1.0

中每一次請求都需要建立一個TCP連接配接，請求結束後立即斷開連接配接。在

HTTP/1.1

中，每一個連接配接都預設是長連接配接(persistent connection)。

對于同一個tcp連接配接，允許一次發送多個http1.1請求，也就是說，不必等前一個響應收到，就可以發送下一個請求。這樣就解決了http1.0的用戶端的隊頭阻塞，而這也就是

HTTP/1.1

中

管道(Pipeline)

的概念了。

但是，

http1.1規定，伺服器端的響應的發送要根據請求被接收的順序排隊

，也就是說，先接收到的請求的響應也要先發送。這樣造成的問題是，如果最先收到的請求的處理時間長的話，響應生成也慢，就會阻塞已經生成了的響應的發送。也會造成隊頭阻塞。

可見，http1.1的隊首阻塞發生在伺服器端。

如果用圖來表示的話，過程大概是：

資料結構與算法 - 線性結構

HTTP/2

和

HTTP/1.1

:

為了解決

HTTP/1.1

中的服務端隊首阻塞，

HTTP/2

采用了

二進制分幀

和

多路複用

等方法。

二進制分幀

中，幀是

HTTP/2

資料通信的最小機關。

在

HTTP/1.1

資料包是文本格式，而

HTTP/2

的資料包是二進制格式的，也就是二進制幀。采用幀可以将請求和響應的資料分割得更小，且二進制協定可以更高效解析。

H

TTP/2

中，同域名下所有通信都在單個連接配接上完成，該連接配接可以承載任意數量的雙向資料流。

每個資料流都以消息的形式發送，而消息又由一個或多個幀組成。

多個幀之間可以亂序發送，根據幀首部的流辨別可以重新組裝。

多路複用

用以替代原來的序列和擁塞機制。

在

HTTP/1.1

中，并發多個請求需要多個TCP連結，且單個域名有6-8個TCP連結請求限制。

在

HHTP/2中，同一域名下的所有通信在單個連結完成，僅占用一個TCP連結，且在這一個連結上可以并行請求和響應，互不幹擾。

此網站可以直覺感受

HTTP/1.1

 和

HTTP/2

 的性能對比。

棧

棧也是一種受限的序列，它隻能夠操作棧頂，不管入棧還是出棧，都是在棧頂操作。

在計算機科學中, 一個 棧(stack) 是一種抽象資料類型,用作表示元素的集合,具有兩種主要操作:

push, 添加元素到棧的頂端(末尾); pop, 移除棧最頂端(末尾)的元素. 以上兩種操作可以簡單概括為“後進先出(LIFO = last in, first out)”。

此外,應有一個 peek 操作用于通路棧目前頂端(末尾)的元素。（隻傳回不彈出）

"棧"這個名稱,可類比于一組物體的堆疊(一摞書,一摞盤子之類的)。

棧的 push 和 pop 操作的示意:

資料結構與算法 - 線性結構

(圖檔來自 https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/stack/README.zh-CN.md)

棧在很多地方都有着應用，比如大家熟悉的浏覽器就有很多棧，其實浏覽器的執行棧就是一個基本的棧結構，從資料結構上說，它就是一個棧。這也就解釋了，我們用遞歸的解法和用循環+棧的解法本質上是差不多。

比如如下JS代碼：

function bar() {
  const a = 1
  const b = 2;
  console.log(a, b)
}

function foo() {
  const a = 1;
  bar();
}

foo();

複制

真正執行的時候，内部大概是這樣的：

我畫的圖沒有畫出執行上下文中其他部分（this和scope等）， 這部分是閉包的關鍵，而我這裡不是将閉包的，是為了講解棧的。 社群中有很多“執行上下文中的scope指的是執行棧中父級聲明的變量”說法，這是完全錯誤的， JS是詞法作用域，scope指的是函數定義時候的父級，和執行沒關系

棧常見的應用有進制轉換，括号比對，棧混洗，中綴表達式（用的很少），字尾表達式（逆波蘭表達式）等。

合法的棧混洗操作，其實和合法的括号比對表達式之間存在着一一對應的關系， 也就是說n個元素的棧混洗有多少種，n對括号的合法表達式就有多少種。感興趣的可以查找相關資料

連結清單

連結清單是一種最基本資料結構，熟練掌握連結清單的結構和常見操作是基礎中的基礎。

資料結構與算法 - 線性結構

(圖檔來自：https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/linked-list/traversal)

React Fiber

很多人都說 fiber 是基于連結清單實作的，但是為什麼要基于連結清單呢，可能很多人并沒有答案，那麼我覺得可以把這兩個點（fiber 和連結清單）放到一起來講下。

fiber 出現的目的其實是為了解決 react 在執行的時候是無法停下來的，需要一口氣執行完的問題的。

資料結構與算法 - 線性結構

圖檔來自 Lin Clark 在 ReactConf 2017 分享

上面已經指出了引入 fiber 之前的問題，就是 react 會阻止優先級高的代碼（比如使用者輸入）執行。是以 fiber 打算自己自建一個

虛拟執行棧

來解決這個問題，這個虛拟執行棧的實作是連結清單。

Fiber 的基本原理是将協調過程分成小塊，一次執行一塊，然乎将運算結果儲存起來，并判斷是否有時間（react 自己實作了一個類似 requestIdleCallback 的功能）繼續執行下一塊。如果有時間，則繼續。否則跳出，讓浏覽器主線程歇一會，執行别的優先級高的代碼。

當協調過程完成（所有的小塊都運算完畢）， 那麼就會進入送出階段， 真正的進行副作用（side effect）操作，比如更新DOM，這個過程是沒有辦法取消的，原因就是這部分有副作用。

問題的關鍵就是将協調的過程劃分為一塊塊的，最後還可以合并到一起，有點像Map／Reduce。

React 必須重新實作周遊樹的算法，從依賴于

内置堆棧的同步遞歸模型

，變為

具有連結清單和指針的異步模型

。

Andrew 是這麼說的：如果你隻依賴于[内置]調用堆棧，它将繼續工作直到堆棧為空。。。

如果我們可以随意中斷調用堆棧并手動操作堆棧幀，那不是很好嗎？這就是 React Fiber 的目的。

Fiber是堆棧的重新實作，專門用于React元件

。你可以将單個 Fiber 視為一個

虛拟堆棧幀

。

react fiber 大概是這樣的：

let fiber = {
  tag: HOST_COMPONENT,
  type: "div",
  return: parentFiber,
  children: childFiber,
  sibling: childFiber,
  alternate: currentFiber,
  stateNode: document.createElement("div"),
  props: { children: [], className: "foo"},
  partialState: null,
  effectTag: PLACEMENT,
  effects: []
};

複制

從這裡可以看出fiber本質上是個對象，使用parent，child，sibling屬性去建構fiber樹來表示元件的結構樹， return, children, sibling也都是一個fiber，是以fiber看起來就是一個連結清單。

細心的朋友可能已經發現了， alternate也是一個fiber， 那麼它是用來做什麼的呢？它其實原理有點像git， 可以用來執行git revert ,git commit等操作，這部分挺有意思，我會在我的《從零開發git》中講解

想要了解更多的朋友可以看這個文章

如果可以通路外國網站， 可以看英文原文.

上一篇: [第14期] [長文預警] 深入了解React 渲染原理及性能優化 二、性能優化
下一篇: Python腳本統計AndroidMainfest.xml中Activity的相關資料