文章結(jié)構(gòu)：
- React中的虛擬DOM是什么虹曙？
- 虛擬DOM的簡單實(shí)現(xiàn)（diff算法）
- 虛擬DOM的內(nèi)部工作原理
- React中的虛擬DOM與Vue中的虛擬DOM比較
React中的虛擬DOM是什么祠锣？
雖然React中的虛擬DOM很好用坠狡，但是這是一個(gè)無心插柳的結(jié)果。
React的核心思想：一個(gè)Component拯救世界口猜，忘掉煩惱负溪，從此不再操心界面。
1. Virtual Dom快济炎，有兩個(gè)前提
1.1 Javascript很快
Chrome剛出來的時(shí)候川抡，在Chrome里跑Javascript非常快须尚，給了其它瀏覽器很大壓力崖堤。而現(xiàn)在經(jīng)過幾輪你追我趕，各主流瀏覽器的Javascript執(zhí)行速度都很快了耐床。
在 https://julialang.org/benchmarks/ 這個(gè)網(wǎng)站上密幔，我們可以看到，JavaScript語言已經(jīng)非沉煤洌快了胯甩，和C就是幾倍的關(guān)系，和java在同一個(gè)量級(jí)堪嫂。所以說蜡豹，單純的JavaScript還是還是很快的。
1.2 Dom很慢
當(dāng)創(chuàng)建一個(gè)元素比如div溉苛，有以下幾項(xiàng)內(nèi)容需要實(shí)現(xiàn)： HTML element镜廉、Element、GlobalEventHandler愚战。簡單的說娇唯，就是插入一個(gè)Dom元素的時(shí)候，這個(gè)元素上本身或者繼承很多屬性如 width寂玲、height塔插、offsetHeight、style拓哟、title想许，另外還需要注冊(cè)這個(gè)元素的諸多方法，比如onfucos断序、onclick等等流纹。 這還只是一個(gè)元素，如果元素比較多的時(shí)候违诗，還涉及到嵌套漱凝，那么元素的屬性和方法等等就會(huì)很多，效率很低诸迟。
比如茸炒，我們?cè)谝粋€(gè)空白網(wǎng)頁的body中添加一個(gè)div元素愕乎，如下所示：
這個(gè)元素會(huì)掛載默認(rèn)的styles、得到這個(gè)元素的computed屬性壁公、注冊(cè)相應(yīng)的Event Listener感论、DOM Breakpoints以及大量的properties，這些屬性紊册、方法的注冊(cè)肯定是需要h耗費(fèi)大量時(shí)間的笛粘。
尤其是在js操作DOM的過程中，不僅有dom本身的繁重湿硝，js的操作也需要浪費(fèi)時(shí)間，我們認(rèn)為js和DOM之間有一座橋润努，如果你頻繁的在橋兩邊走動(dòng)关斜，顯然效率是很低的，**如果你的JavaScript操作DOM的方式還非常不合理铺浇，那么顯然就會(huì)更糟糕了痢畜。 **
而 React的虛擬DOM就是解決這個(gè)問題的！ 雖然它解決不了DOM自身的繁重鳍侣，但是虛擬DOM可以對(duì)JavaScript操作DOM這一部分內(nèi)容進(jìn)行優(yōu)化丁稀。
比如說，現(xiàn)在你的list是這樣：
<ul>
<li>0</li>
<li>1</li>
<li>2</li>
<li>3</li>
</ul>
你希望把它變成下面這樣：
<ul>
<li>6</li>
<li>7</li>
<li>8</li>
<li>9</li>
<li>10</li>
</ul>
通常的操作是什么倚聚？
先把0线衫， 1，2惑折，3這些Element刪掉授账，然后加幾個(gè)新的Element 6，7惨驶，8白热，9，10進(jìn)去粗卜，這里面就有4次Element刪除屋确，5次Element添加。共計(jì)9次DOM操作续扔。
那React的虛擬DOM可以怎么做呢攻臀？
而React會(huì)把這兩個(gè)做一下Diff，然后發(fā)現(xiàn)其實(shí)不用刪除0纱昧，1茵烈，2，3砌些，而是可以直接改innerHTML呜投，然后只需要添加一個(gè)Element（10）就行了加匈，這樣就是4次innerHTML操作加1個(gè)Element添加。共計(jì)5此操作仑荐，這樣效率的提升是非车衿矗可觀的。
2粘招、 關(guān)于React
2.1 接口和設(shè)計(jì)
在React的設(shè)計(jì)中啥寇，是完全不需要你來操作DOM的。 我們也可以認(rèn)為洒扎，在React中根本就沒有DOM這個(gè)概念辑甜，有的只是Component。
當(dāng)你寫好一個(gè)Component以后袍冷，Component會(huì)完全負(fù)責(zé)UI磷醋，你不需要也不應(yīng)該去也不能夠指揮Component怎么顯示，你只能告訴它你想要顯示一個(gè)香蕉還是兩個(gè)梨胡诗。
隔離DOM并不僅僅是因?yàn)镈OM慢邓线，而也是為了把界面和業(yè)務(wù)完全隔離，操作數(shù)據(jù)的只關(guān)心數(shù)據(jù)煌恢，操作界面的只關(guān)心界面骇陈。比如在websocket聊天室的創(chuàng)建房間時(shí)，我們可以首先Component寫好瑰抵，然后當(dāng)獲取到數(shù)據(jù)的時(shí)候你雌，只要把數(shù)據(jù)放在redux中就好，然后Component就動(dòng)把房間添加到頁面中去二汛，而不是你先拿到數(shù)據(jù)匪蝙，然后使用js操作DOM把數(shù)據(jù)顯示在頁面上。
即我提供一個(gè)Component习贫，然后你只管給我數(shù)據(jù)逛球，界面的事情完全不用你操心，我保證會(huì)把界面變成你想要的樣子苫昌。所以說React的著力點(diǎn)就在于View層颤绕，即React專注于View層。你可以把一個(gè)React的Component想象成一個(gè)Pure Function祟身，只要你給的數(shù)據(jù)是[1, 2, 3]奥务，我保證顯示的是[1, 2, 3]。沒有什么刪除一個(gè)Element袜硫，添加一個(gè)Element這樣的事情氯葬。NO。你要我顯示什么就給我一個(gè)完整的列表婉陷。
另外帚称，F(xiàn)lux雖然說的是單向的Data Flow(redux也是)官研，但是實(shí)際上就是單向的Observer，Store->View->Action->Store（箭頭是數(shù)據(jù)流向闯睹，實(shí)現(xiàn)上可以理解為View監(jiān)聽Store戏羽，View直接trigger action，然后Store監(jiān)聽Action）楼吃。
2.2 實(shí)現(xiàn)
那么react如何實(shí)現(xiàn)呢始花？ 最簡單的方法就是當(dāng)數(shù)據(jù)變化時(shí)，我直接把原先的DOM卸載孩锡，然后把最新數(shù)據(jù)的DOM替換上去酷宵。 但是，虛擬DOM哪去了躬窜？ 這樣做的效率顯然是極低的浇垦。
所以虛擬DOM就來救場了。
那么虛擬DOM和DOM之間的關(guān)系是什么呢斩披？
首先，Virtual DOM并沒有完全實(shí)現(xiàn)DOM讹俊，即虛擬DOM和真正地DOM是不一樣的垦沉，Virtual DOM最主要的還是保留了Element之間的層次關(guān)系和一些基本屬性。因?yàn)?strong>真實(shí)DOM實(shí)在是太復(fù)雜仍劈，一個(gè)空的Element都復(fù)雜得能讓你崩潰厕倍，并且?guī)缀跛袃?nèi)容我根本不關(guān)心好嗎。所以Virtual DOM里每一個(gè)Element實(shí)際上只有幾個(gè)屬性贩疙，即最重要的讹弯，最為有用的，并且沒有那么多亂七八糟的引用这溅，比如一些注冊(cè)的屬性和函數(shù)啊组民，這些都是默認(rèn)的，創(chuàng)建虛擬DOM進(jìn)行diff的過程中大家都一致悲靴，是不需要進(jìn)行比對(duì)的臭胜。所以哪怕是直接把Virtual DOM刪了，根據(jù)新傳進(jìn)來的數(shù)據(jù)重新創(chuàng)建一個(gè)新的Virtual DOM出來都非常非常非绸校快耸三。（每一個(gè)component的render函數(shù)就是在做這個(gè)事情，給新的virtual dom提供input）浇揩。
所以仪壮，引入了Virtual DOM之后，React是這么干的：你給我一個(gè)數(shù)據(jù)胳徽，我根據(jù)這個(gè)數(shù)據(jù)生成一個(gè)全新的Virtual DOM积锅，然后跟我上一次生成的Virtual DOM去 diff爽彤，得到一個(gè)Patch，然后把這個(gè)Patch打到瀏覽器的DOM上去乏沸。完事淫茵。并且這里的patch顯然不是完整的虛擬DOM，而是新的虛擬DOM和上一次的虛擬DOM經(jīng)過diff后的差異化的部分蹬跃。
假設(shè)在任意時(shí)候有匙瘪，VirtualDom1 == DOM1 （組織結(jié)構(gòu)相同, 顯然虛擬DOM和真實(shí)DOM是不可能完全相等的，這里的==是js中非完全相等）蝶缀。當(dāng)有新數(shù)據(jù)來的時(shí)候丹喻，我生成VirtualDom2，然后去和VirtualDom1做diff翁都，得到一個(gè)Patch（差異化的結(jié)果）碍论。然后將這個(gè)Patch去應(yīng)用到DOM1上，得到DOM2柄慰。如果一切正常鳍悠，那么有VirtualDom2 == DOM2（同樣是結(jié)構(gòu)上的相等）。
這里你可以做一些小實(shí)驗(yàn)坐搔，去破壞VirtualDom1 == DOM1這個(gè)假設(shè)（手動(dòng)在DOM里刪除一些Element藏研，這時(shí)候VirtualDom里的Element沒有被刪除，所以兩邊不一樣了）概行。
然后給新的數(shù)據(jù)蠢挡，你會(huì)發(fā)現(xiàn)生成的界面就不是你想要的那個(gè)界面了。
最后凳忙，回到為什么Virtual Dom快這個(gè)問題上业踏。
其實(shí)是由于每次生成virtual dom很快，diff生成patch也比較快涧卵，而在對(duì)DOM進(jìn)行patch的時(shí)候勤家，雖然DOM的變更比較慢诚撵，但是React能夠根據(jù)Patch的內(nèi)容锅必，優(yōu)化一部分DOM操作，比如之前的那個(gè)例子惨撇。
重點(diǎn)就在最后胎撤，哪怕是我生成了virtual dom(需要耗費(fèi)時(shí)間)晓殊，哪怕是我跑了diff（還需要花時(shí)間），但是我根據(jù)patch簡化了那些DOM操作省下來的時(shí)間依然很可觀（這個(gè)就是時(shí)間差的問題了伤提，即節(jié)省下來的時(shí)間 > 生成 virtual dom的時(shí)間 + diff時(shí)間）巫俺。所以總體上來說，還是比較快肿男。
簡單發(fā)散一下思路介汹，如果哪一天却嗡，DOM本身的已經(jīng)操作非常非常非常快了嘹承，并且我們手動(dòng)對(duì)于DOM的操作都是精心設(shè)計(jì)優(yōu)化過后的窗价，那么加上了VirtualDom還會(huì)快嗎？
當(dāng)然不行了叹卷，畢竟你多做了這么多額外的工作撼港。
但是那一天會(huì)來到嗎？
誒骤竹，大不了到時(shí)候不用Virtual DOM帝牡。
注： 此部分內(nèi)容整理自：https://www.zhihu.com/question/29504639/answer/44680878
虛擬DOM的簡單實(shí)現(xiàn)（diff算法）
目錄
- 1 前言
- 2 對(duì)前端應(yīng)用狀態(tài)管理思考
- 3 Virtual DOM 算法
- 4 算法實(shí)現(xiàn)
- 4.1 步驟一：用JS對(duì)象模擬DOM樹
- 4.2 步驟二：比較兩棵虛擬DOM樹的差異
- 4.3 步驟三：把差異應(yīng)用到真正的DOM樹上
- 5 結(jié)語
前言
在上面一部分中，我們已經(jīng)簡單介紹了虛擬DOM的答題思路和好處蒙揣，這里我們將通過自己寫一個(gè)虛擬DOM來加深對(duì)其的理解靶溜，有一些自己的思考。
對(duì)前端應(yīng)用狀態(tài)管理思考
維護(hù)狀態(tài)懒震，更新視圖罩息。
虛擬DOM算法
DOM是很慢的，如果我們創(chuàng)建一個(gè)簡單的div个扰，然后把他的所有的屬性都打印出來瓷炮，你會(huì)看到：
var div = document.createElement('div'),
str = '';
for (var key in div) {
str = str + ' ' + key;
}
console.log(str);
可以看到，這些屬性還是非常驚人的锨匆，包括樣式的修飾特性崭别、一般的特性冬筒、方法等等恐锣，如果我們打印出其長度，可以得到驚人的227個(gè)舞痰。
而這僅僅是一層土榴，真正的DOM元素是非常龐大的，這是因?yàn)闃?biāo)準(zhǔn)就是這么設(shè)計(jì)的响牛，而且操作他們的時(shí)候你要小心翼翼玷禽，輕微的觸碰就有可能導(dǎo)致頁面發(fā)生重排，這是殺死性能的罪魁禍?zhǔn)住?/strong>
而相對(duì)于DOM對(duì)象呀打，原生的JavaScript對(duì)象處理起來更快矢赁，而且更簡單，DOM樹上的結(jié)構(gòu)信息我們都可以使用JavaScript對(duì)象很容易的表示出來贬丛。
var element = {
tagName: 'ul',
props: {
id: 'list' },
children: {
{
tagName: 'li',
props: { class: 'item' },
children: ['Item1']
},
{
tagName: 'li',
props: { class: 'item' },
children: ['Item1']
},
{
tagName: 'li',
props: { class: 'item' },
children: ['Item1']
}
}
}
如上所示撩银，對(duì)于一個(gè)元素，我們只需要一個(gè)JavaScript對(duì)象就可以很容易的表示出來豺憔，這個(gè)對(duì)象中有三個(gè)屬性:
- tagName: 用來表示這個(gè)元素的標(biāo)簽名额获。
- props: 用來表示這元素所包含的屬性够庙。
- children: 用來表示這元素的children。
而上面的這個(gè)對(duì)象使用HTML表示就是：
<ul id='list'>
<li class='item'>Item 1</li>
<li class='item'>Item 2</li>
<li class='item'>Item 3</li>
</ul>
OK! 既然原來的DOM信息可以使用JavaScript來表示抄邀，那么反過來耘眨，我們就可以用這個(gè)JavaScript對(duì)象來構(gòu)建一個(gè)真正的DOM樹。
所以之前所說的狀態(tài)變更的時(shí)候會(huì)從新構(gòu)建這個(gè)JavaScript對(duì)象境肾，然后呢剔难，用新渲染的對(duì)象和舊的對(duì)象去對(duì)比， 記錄兩棵樹的差異准夷，記錄下來的就是我們需要改變的地方钥飞。 這就是所謂的虛擬DOM，包括下面的幾個(gè)步驟：
- 用JavaScript對(duì)象來表示DOM樹的結(jié)構(gòu)衫嵌； 然后用這個(gè)樹構(gòu)建一個(gè)真正的DOM樹读宙，插入到文檔中。
- 當(dāng)狀態(tài)變更的時(shí)候楔绞，重新構(gòu)造一個(gè)新的對(duì)象樹结闸，然后用這個(gè)新的樹和舊的樹作對(duì)比，記錄兩個(gè)樹的差異酒朵。
- 把2所記錄的差異應(yīng)用在步驟一所構(gòu)建的真正的DOM樹上桦锄，視圖就更新了。
Virtual DOM的本質(zhì)就是在JS和DOM之間做一個(gè)緩存蔫耽，可以類比CPU和硬盤结耀，既然硬盤這么慢，我們就也在他們之間添加一個(gè)緩存匙铡； 既然DOM這么慢图甜，我們就可以在JS和DOM之間添加一個(gè)緩存。 CPU（JS）只操作內(nèi)存（虛擬DOM）鳖眼，最后的時(shí)候在把變更寫入硬盤（DOM）黑毅。
算法實(shí)現(xiàn)
1、 用JavaScript對(duì)象模擬DOM樹
用JavaScript對(duì)象來模擬一個(gè)DOM節(jié)點(diǎn)并不難钦讳，你只需要記錄他的節(jié)點(diǎn)類型（tagName）矿瘦、屬性（props）、子節(jié)點(diǎn)（children）愿卒。
element.js
function Element(tagName, props, children) {
this.tagName = tagName;
this.props = props;
this.children = children;
}
module.exports = function (tagName, props, children) {
return new Element(tagName, props, children);
}
通過這個(gè)構(gòu)造函數(shù)缚去，我們就可以傳入標(biāo)簽名、屬性以及子節(jié)點(diǎn)了琼开，tagName可以在我們r(jià)ender的時(shí)候直接根據(jù)它來創(chuàng)建真實(shí)的元素易结，這里的props使用一個(gè)對(duì)象傳入，可以方便我們遍歷。
基本使用方法如下：
var el = require('./element');
var ul = el('ul', {id: 'list'}, [
el('li', {class: 'item'}, ['item1']),
el('li', {class: 'item'}, ['item2']),
el('li', {class: 'item'}, ['item3'])
]);
然而衬衬，現(xiàn)在的ul只是JavaScript表示的一個(gè)DOM結(jié)構(gòu)买猖，頁面上并沒有這個(gè)結(jié)構(gòu)，所有我們可以根據(jù)ul構(gòu)建一個(gè)真正的<ul>：
Element.prototype.render = function () {
// 根據(jù)tagName創(chuàng)建一個(gè)真實(shí)的元素
var el = document.createElement(this.tagName);
// 得到這個(gè)元素的屬性對(duì)象滋尉，方便我們遍歷玉控。
var props = this.props; for (var propName in props) {
// 獲取到這個(gè)元素值
var propValue = props[propName];
// 通過setAttribute設(shè)置元素屬性。
el.setAttribute(propName, propValue);
}
// 注意： 這里的children狮惜，傳入的是一個(gè)數(shù)組高诺，所以，children不存在時(shí)我們用[]來替代碾篡。
var children = this.children || [];
//遍歷children
children.forEach(function (child) {
var childEl = (child instanceof Element) ? child.render()
: document.createTextNode(child);
// 無論childEl是元素還是文字節(jié)點(diǎn)虱而，都需要添加到這個(gè)元素中。
el.appendChild(childEl);
});
return el;
}
所以开泽，render方法會(huì)根據(jù)tagName構(gòu)建一個(gè)真正的DOM節(jié)點(diǎn)牡拇，然后設(shè)置這個(gè)節(jié)點(diǎn)的屬性，最后遞歸的把自己的子節(jié)點(diǎn)也構(gòu)建起來穆律，所以只需要調(diào)用ul的render方法惠呼，通過document.body.appendChild就可以掛載到真實(shí)的頁面了。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>div</title>
</head>
<body>
<script>
function Element(tagName, props, children) {
this.tagName = tagName;
this.props = props;
this.children = children;
}
var ul = new Element(
'ul',
{id: 'list'},
[ new Element(
'li',
{class: 'item'},
['item1']),
new Element(
'li',
{class: 'item'},
['item2']),
new Element(
'li',
{class: 'item'},
['item3'])]
);
Element.prototype.render = function () {
// 根據(jù)tagName創(chuàng)建一個(gè)真實(shí)的元素
var el = document.createElement(this.tagName);
// 得到這個(gè)元素的屬性對(duì)象峦耘，方便我們遍歷剔蹋。
var props = this.props; for (var propName in props) {
// 獲取到這個(gè)元素值
var propValue = props[propName];
// 通過setAttribute設(shè)置元素屬性。
el.setAttribute(propName, propValue);
}
// 注意：這里的children辅髓，傳入的是一個(gè)數(shù)組泣崩，所以洛口，children不存在時(shí)我們用[]來替代矫付。
var children = this.children || []; //遍歷children
children.forEach(function (child) {
var childEl = (child instanceof Element)
? child.render()
: document.createTextNode(child);
// 無論childEl是元素還是文字節(jié)點(diǎn)，都需要添加到這個(gè)元素中绍弟。
el.appendChild(childEl);
});
return el;
}
var ulRoot = ul.render();
document.body.appendChild(ulRoot);
</script>
</body>
</html>
上面的這段代碼豹悬，就可以渲染出下面的結(jié)果了：
2绊困、比較兩顆虛擬DOM樹的差異
比較兩顆DOM數(shù)的差異是Virtual DOM算法中最為核心的部分常挚，這也就是所謂的Virtual DOM的diff算法作谭。 兩個(gè)樹的完全的diff算法是一個(gè)時(shí)間復(fù)雜度為 O(n3) 的問題。 但是在前端中奄毡，你會(huì)很少跨層地移動(dòng)DOM元素折欠，所以真實(shí)的DOM算法會(huì)對(duì)同一個(gè)層級(jí)的元素進(jìn)行對(duì)比。
上圖中吼过，div只會(huì)和同一層級(jí)的div對(duì)比怨酝，第二層級(jí)的只會(huì)和第二層級(jí)對(duì)比。 這樣算法復(fù)雜度就可以達(dá)到O(n)那先。
（1）深度遍歷優(yōu)先农猬，記錄差異
在實(shí)際的代碼中，會(huì)對(duì)新舊兩棵樹進(jìn)行一個(gè)深度優(yōu)先的遍歷售淡，這樣每一個(gè)節(jié)點(diǎn)就會(huì)有一個(gè)唯一的標(biāo)記：
上面的這個(gè)遍歷過程就是深度優(yōu)先斤葱，即深度完全完成之后，再轉(zhuǎn)移位置揖闸。 在深度優(yōu)先遍歷的時(shí)候揍堕，每遍歷到一個(gè)節(jié)點(diǎn)就把該節(jié)點(diǎn)和新的樹進(jìn)行對(duì)比，如果有差異的話就記錄到一個(gè)對(duì)象里面汤纸。
// diff函數(shù)衩茸，對(duì)比兩顆樹
function diff(oldTree, newTree) {
// 當(dāng)前的節(jié)點(diǎn)的標(biāo)志。因?yàn)樵谏疃葍?yōu)先遍歷的過程中贮泞，每個(gè)節(jié)點(diǎn)都有一個(gè)index楞慈。
var index = 0;
// 在遍歷到每個(gè)節(jié)點(diǎn)的時(shí)候，都需要進(jìn)行對(duì)比啃擦，找到差異囊蓝，并記錄在下面的對(duì)象中。
var pathches = {};
// 開始進(jìn)行深度優(yōu)先遍歷
dfsWalk(oldTree, newTree, index, pathches);
// 最終diff算法返回的是一個(gè)兩棵樹的差異令蛉。
return pathches;
}
// 對(duì)兩棵樹進(jìn)行深度優(yōu)先遍歷聚霜。
function dfsWalk(oldNode, newNode, index, pathches) {
// 對(duì)比oldNode和newNode的不同，記錄下來
pathches[index] = [...];
diffChildren(oldNode.children, newNode.children, index, pathches);
}
// 遍歷子節(jié)點(diǎn)
function diffChildren(oldChildren, newChildren, index, pathches) {
var leftNode = null;
var currentNodeIndex = index;
oldChildren.forEach(function (child, i) {
var newChild = newChildren[i];
currentNodeIndex = (leftNode && leftNode.count)
? currentNodeIndex + leftNode.count + 1
: currentNodeIndex + 1
// 深度遍歷子節(jié)點(diǎn)
dfsWalk(child, newChild, currentNodeIndex, pathches);
leftNode = child;
});
}
例如，上面的div和新的div有差異蝎宇，當(dāng)前的標(biāo)記是0弟劲， 那么我們可以使用數(shù)組來存儲(chǔ)新舊節(jié)點(diǎn)的不同：
patches[0] = [{difference}, {difference}, ...]
同理使用patches[1]來記錄p，使用patches[3]來記錄ul姥芥，以此類推函卒。
（2）差異類型
上面說的節(jié)點(diǎn)的差異指的是什么呢？ 對(duì)DOM操作可能會(huì)：
- 替換原來的節(jié)點(diǎn)撇眯，如把上面的div換成了section报嵌。
- 移動(dòng)、刪除熊榛、新增子節(jié)點(diǎn)锚国， 例如上面div的子節(jié)點(diǎn)，把p和ul順序互換玄坦。
- 修改了節(jié)點(diǎn)的屬性血筑。
- 對(duì)于文本節(jié)點(diǎn)，文本內(nèi)容可能會(huì)改變煎楣。 例如修改上面的文本內(nèi)容2內(nèi)容為Virtual DOM2.
所以豺总，我們可以定義下面的幾種類型：
var REPLACE = 0;
var REORDER = 1;
var PROPS = 2;
var TEXT = 3;
對(duì)于節(jié)點(diǎn)替換，很簡單择懂，判斷新舊節(jié)點(diǎn)的tagName是不是一樣的喻喳，如果不一樣的說明需要替換掉。 如div換成了section困曙，就記錄下：
patches[0] = [{
type: REPALCE,
node: newNode // el('section', props, children)
}]
除此之外表伦，如果給div新增了屬性id為container，就記錄下：
pathches[0] = [
{
type: REPLACE,
node: newNode
},
{
type: PROPS,
props: {
id: 'container' }
}
]
如果是文本節(jié)點(diǎn)發(fā)生了變化慷丽，那么就記錄下：
pathches[2] = [
{
type: TEXT,
content: 'virtual DOM2' }
]
那么如果我們把div的子節(jié)點(diǎn)重新排序了呢蹦哼？ 比如p、ul要糊、div的順序換成了div纲熏、p、ul锄俄，那么這個(gè)該怎么對(duì)比呢局劲？ 如果按照同級(jí)進(jìn)行順序?qū)Ρ鹊脑挘麄兙蜁?huì)被替換掉珊膜，如p和div的tagName不同容握，p就會(huì)被div所代替宣脉，最終车柠，三個(gè)節(jié)點(diǎn)就都會(huì)被替換，這樣DOM開銷就會(huì)非常大，而實(shí)際上是不需要替換節(jié)點(diǎn)的竹祷，只需要移動(dòng)就可以了谈跛， 我們只需要知道怎么去移動(dòng)。這里牽扯到了兩個(gè)列表的對(duì)比算法塑陵，如下感憾。
（3）列表對(duì)比算法
假設(shè)現(xiàn)在可以英文字母唯一地標(biāo)識(shí)每一個(gè)子節(jié)點(diǎn)：
舊的節(jié)點(diǎn)順序：
a b c d e f g h i
現(xiàn)在對(duì)節(jié)點(diǎn)進(jìn)行了刪除、插入令花、移動(dòng)的操作阻桅。新增j節(jié)點(diǎn)，刪除e節(jié)點(diǎn)兼都，移動(dòng)h節(jié)點(diǎn)：
新的節(jié)點(diǎn)順序：
a b c h d f g i j
現(xiàn)在知道了新舊的順序嫂沉，求最小的插入、刪除操作（移動(dòng)可以看成是刪除和插入操作的結(jié)合）扮碧。這個(gè)問題抽象出來其實(shí)是字符串的最小編輯距離問題（Edition Distance）趟章，最常見的解決算法是 Levenshtein Distance，通過動(dòng)態(tài)規(guī)劃求解慎王，時(shí)間復(fù)雜度為 O(M * N)蚓土。但是我們并不需要真的達(dá)到最小的操作，我們只需要優(yōu)化一些比較常見的移動(dòng)情況赖淤，犧牲一定DOM操作蜀漆，讓算法時(shí)間復(fù)雜度達(dá)到線性的（O(max(M, N))。具體算法細(xì)節(jié)比較多咱旱，這里不累述，有興趣可以參考代碼莽龟。
我們能夠獲取到某個(gè)父節(jié)點(diǎn)的子節(jié)點(diǎn)的操作，就可以記錄下來：
patches[0] = [{
type: REORDER,
moves: [{remove or insert}, {remove or insert}, ...]
}]
但是要注意的是剃毒，因?yàn)?code>tagName是可重復(fù)的，不能用這個(gè)來進(jìn)行對(duì)比搂赋。所以需要給子節(jié)點(diǎn)加上唯一標(biāo)識(shí)key赘阀，列表對(duì)比的時(shí)候脑奠，使用key進(jìn)行對(duì)比，這樣才能復(fù)用老的 DOM 樹上的節(jié)點(diǎn)宋欺。
這樣轰豆，我們就可以通過深度優(yōu)先遍歷兩棵樹胰伍，每層的節(jié)點(diǎn)進(jìn)行對(duì)比，記錄下每個(gè)節(jié)點(diǎn)的差異了骂租。完整 diff 算法代碼可見 diff.js斑司。
3渗饮、把差異引用到真正的DOM樹上
因?yàn)椴襟E一所構(gòu)建的 JavaScript 對(duì)象樹和render出來真正的DOM樹的信息宿刮、結(jié)構(gòu)是一樣的。所以我們可以對(duì)那棵DOM樹也進(jìn)行深度優(yōu)先的遍歷云茸，遍歷的時(shí)候從步驟二生成的patches對(duì)象中找出當(dāng)前遍歷的節(jié)點(diǎn)差異，然后進(jìn)行 DOM 操作标捺。
function patch (node, patches) {
var walker = {index: 0}
dfsWalk(node, walker, patches)
}
function dfsWalk (node, walker, patches) {
var currentPatches = patches[walker.index]
// 從patches拿出當(dāng)前節(jié)點(diǎn)的差異
var len = node.childNodes ? node.childNodes.length
: 0
for (var i = 0; i < len; i++) {
// 深度遍歷子節(jié)點(diǎn)
var child = node.childNodes[i]
walker.index++
dfsWalk(child, walker, patches)
}
if (currentPatches) {
applyPatches(node, currentPatches)
// 對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行DOM操作
}
}
// applyPatches揉抵，根據(jù)不同類型的差異對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行 DOM 操作：
function applyPatches (node, currentPatches) {
currentPatches.forEach(function (currentPatch) {
switch (currentPatch.type) {
case REPLACE:
node.parentNode.replaceChild(currentPatch.node.render(), node) break
case REORDER:
reorderChildren(node, currentPatch.moves) break
case PROPS:
setProps(node, currentPatch.props) break
case TEXT:
node.textContent = currentPatch.content break
default: throw new Error('Unknown patch type ' + currentPatch.type)
}
})
}
5、結(jié)語
virtual DOM算法主要實(shí)現(xiàn)上面步驟的三個(gè)函數(shù)： element冤今、diff、patch屋谭，然后就可以實(shí)際的進(jìn)行使用了龟糕。
// 1. 構(gòu)建虛擬DOM
var tree = el('div', {'id': 'container'}, [
el('h1', {style: 'color: blue'}, ['simple virtal dom']),
el('p', ['Hello, virtual-dom']),
el('ul', [el('li')])
])
// 2. 通過虛擬DOM構(gòu)建真正的DOM
var root = tree.render()
document.body.appendChild(root)
// 3. 生成新的虛擬DOM
var newTree = el('div', {'id': 'container'}, [
el('h1', {style: 'color: red'}, ['simple virtal dom']),
el('p', ['Hello, virtual-dom']),
el('ul', [el('li'), el('li')])
])
// 4. 比較兩棵虛擬DOM樹的不同
var patches = diff(tree, newTree)
// 5. 在真正的DOM元素上應(yīng)用變更
patch(root, patches)
當(dāng)然這是非常粗糙的實(shí)踐，實(shí)際中還需要處理事件監(jiān)聽等讲岁；生成虛擬 DOM 的時(shí)候也可以加入 JSX 語法。這些事情都做了的話缓艳，就可以構(gòu)造一個(gè)簡單的ReactJS了。
