Virtual DOM && DIFF算法简单实现

写在前面

在线演示：http://wonghan.cn/Diff-demo/
Github链接：https://github.com/wonghan/Diff-demo

一、什么是Virtual DOM

1.DOM是树型结构，一般需要修改某个DOM节点时，先使用innerHTML=null清空DOM树，再重新插入新的DOM树，过于浪费(若只需修改一个li，却需要删掉100个li后重新插入99个li)
2.JS可以用JS对象结构表示DOM树型结构，这就是虚拟DOM
3.每次文档状态变化，会新建一颗虚拟DOM树，并将新树与旧树进行对比，记录两棵树的差异
4.将对比后的差异修改到真实的DOM树上

二、为什么使用Virtual DOM

1. DOM十分复杂，DOM操作十分昂贵，应尽量减少DOM操作。例如以下例子可以看出DOM节点的复杂：

var div = document.createElement('div');
var result = '';
for(let item in div){
  result += ' | ' + item;
}
console.log(result)；
//  | align | title | lang | translate | dir | dataset | hidden | tabIndex | accessKey | draggable | spellcheck | autocapitalize | contentEditable | isContentEditable | inputMode | offsetParent | offsetTop | offsetLeft | offsetWidth | offsetHeight | style | innerText | outerText | onabort | onblur | oncancel | oncanplay | oncanplaythrough | onchange | onclick | onclose | oncontextmenu | oncuechange | ondblclick | ondrag | ondragend | ondragenter | ondragleave | ondragover | ondragstart | ondrop | ondurationchange | onemptied | onended | onerror | onfocus | oninput | oninvalid | onkeydown | onkeypress | onkeyup | onload | onloadeddata | onloadedmetadata | onloadstart | onmousedown | onmouseenter | onmouseleave | onmousemove | onmouseout | onmouseover | onmouseup | onmousewheel | onpause | onplay | onplaying | onprogress | onratechange | onreset | onresize | onscroll | onseeked | onseeking | onselect | onstalled | onsubmit | onsuspend | ontimeupdate | ontoggle | onvolumechange | onwaiting | onwheel | onauxclick | ongotpointercapture | onlostpointercapture | onpointerdown | onpointermove | onpointerup | onpointercancel | onpointerover | onpointerout | onpointerenter | onpointerleave | nonce | click | focus | blur | namespaceURI | prefix | localName | tagName | id | className | classList | slot | attributes | shadowRoot | assignedSlot | innerHTML | outerHTML | scrollTop | scrollLeft | scrollWidth | scrollHeight | clientTop | clientLeft | clientWidth | clientHeight | onbeforecopy | onbeforecut | onbeforepaste | oncopy | oncut | onpaste | onsearch | onselectstart | previousElementSibling | nextElementSibling | children | firstElementChild | lastElementChild | childElementCount | onwebkitfullscreenchange | onwebkitfullscreenerror | setPointerCapture | releasePointerCapture | hasPointerCapture | hasAttributes | getAttributeNames | getAttribute | getAttributeNS | setAttribute | setAttributeNS | removeAttribute | removeAttributeNS | hasAttribute | hasAttributeNS | getAttributeNode | getAttributeNodeNS | setAttributeNode | setAttributeNodeNS | removeAttributeNode | closest | matches | webkitMatchesSelector | attachShadow | getElementsByTagName | getElementsByTagNameNS | getElementsByClassName | insertAdjacentElement | insertAdjacentText | insertAdjacentHTML | requestPointerLock | getClientRects | getBoundingClientRect | scrollIntoView | scrollIntoViewIfNeeded | animate | before | after | replaceWith | remove | prepend | append | querySelector | querySelectorAll | webkitRequestFullScreen | webkitRequestFullscreen | attributeStyleMap | scroll | scrollTo | scrollBy | createShadowRoot | getDestinationInsertionPoints | computedStyleMap | ELEMENT_NODE | ATTRIBUTE_NODE | TEXT_NODE | CDATA_SECTION_NODE | ENTITY_REFERENCE_NODE | ENTITY_NODE | PROCESSING_INSTRUCTION_NODE | COMMENT_NODE | DOCUMENT_NODE | DOCUMENT_TYPE_NODE | DOCUMENT_FRAGMENT_NODE | NOTATION_NODE | DOCUMENT_POSITION_DISCONNECTED | DOCUMENT_POSITION_PRECEDING | DOCUMENT_POSITION_FOLLOWING | DOCUMENT_POSITION_CONTAINS | DOCUMENT_POSITION_CONTAINED_BY | DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | nodeType | nodeName | baseURI | isConnected | ownerDocument | parentNode | parentElement | childNodes | firstChild | lastChild | previousSibling | nextSibling | nodeValue | textContent | hasChildNodes | getRootNode | normalize | cloneNode | isEqualNode | isSameNode | compareDocumentPosition | contains | lookupPrefix | lookupNamespaceURI | isDefaultNamespace | insertBefore | appendChild | replaceChild | removeChild | addEventListener | removeEventListener | dispatchEvent

2. JS运行效率高，可以通过JS模拟DOM结构，找出本地DOM必须更新的节点来更新，其他的不更新，以此减少DOM操作。例如，虚拟DOM如下：

<!--真实DOM-->
<ul id="list">
    <li class="item">Item 1</li>
    <li class="item">Item 2</li>
</ul>

// 虚拟DOM
{
  tag: 'ul',
  attrs: {
    id: 'list'
  },
  text: '',
  children: [
    {
      tag: 'li',
      attrs: {className: 'item'},
      children: [],
      text: 'Item 1'
    },
    {
      tag: 'li',
      attrs: {className: 'item'},
      children: [],
      text: 'Item 2'
    }
  ]
}
三、Virtual DOM如何应用，核心API是什么
  • 参考代码库：
    • snabbdom 库：https://github.com/snabbdom/snabbdom
    • 核心API：
      h()：生成虚拟DOM
      patch()：对比前后DOM差异进行渲染（分为第一次插入空容器的操作与之后进行前后vnode对比后进行更新的操作）
四、Diff算法（伪代码，可执行的代码在第五点）
  1. 使用h()方法生成vnode
  2. 获取container容器，将vnode转化成真实dom节点，通过patch()方法进行插入到容器中
  3. 生成新的vnode2，调用patch()方法递归对比前后虚拟DOM差异后，更新对应的真实DOM节点
// vnode生成函数
function h(tag='',attrs={},children=[],text=''){
  return {
    tag: tag,
    attrs: attrs,
    children: children,
    text: text
  }
}
// 插入 || diff DOM函数
function patch(vnode, newVnode){
  if(vnode instanceof HTMLElement){ // 若第一个参数是DOM节点，插入到容器里
    let node = createElement(newVnode);
    vnode.appendChild(node);
  }else{ // 两个都为vnode,执行diff算法
    updateChildren(vnode, newVnode); // diff
  }
}

// 由 虚拟DOM 生成 真实DOM 的函数
function createElement(vnode) {
    var tag = vnode.tag  // 'ul'
    var attrs = vnode.attrs || {}
    var children = vnode.children || []
    if (!tag) {
        return null
    }

    // 创建真实的 DOM 元素
    var elem = document.createElement(tag)
    if(text){
      elem.innerText = text;
    }
    // 属性
    for (let attrName in attrs) {
        if (attrs.hasOwnProperty(attrName)) {
            // 给 elem 添加属性
            elem.setAttribute(attrName, attrs[attrName])
        }
    }
    // 子元素
    children.forEach(function (childVnode) {
        // 给 elem 添加子元素
        elem.appendChild(createElement(childVnode))  // 递归
    })
    // 绑定真实DOM节点到vnode上
    vnode.elem = elem
    // 返回真实的 DOM 元素
    return elem
}

// diff算法对比前后差异
function updateChildren(vnode, newVnode) {
    var children = vnode.children || []
    var newChildren = newVnode.children || []

    children.forEach(function (childVnode, index) {
        var newChildVnode = newChildren[index]
        if (childVnode.tag === newChildVnode.tag) {
            // 深层次对比，递归
            updateChildren(childVnode, newChildVnode)
        } else {
            // 替换
            replaceNode(childVnode, newChildVnode)
        }
    })
}
// 替换真实DOM节点
function replaceNode(vnode, newVnode) {
    var elem = vnode.elem  // 真实的 DOM 节点
    var newElem = createElement(newVnode)
    // 替换
    elem.parentNode.replaceChild(newElem,elem);
}


五、Diff算法简单实现（github代码，可执行）
<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>diff-demo</title>
</head>
<body>
  <div id="container">
  </div>
  <button id="btn">
    change
  </button>
  <button id="btn2">
    change2
  </button>
</body>
<script src="./index.js"></script>
<script>
  // 第一次插入
  let container = document.getElementById('container');
  let vnode1 = h('ul',{id: 'list'},[
    h('li',{class: 'item'},[],'Item 1'),
    h('li',{class: 'item'},[],'Item 2'),
    h('li',{class: 'item'},[],'Item 3')
  ])
  
  patch(container,vnode1);
  console.log(vnode1)

  // 修改vnode,查看diff效果
  let btn = document.getElementById('btn');
  btn.addEventListener('click',function(e){
    let vnode2 = h('ul',{id:'list'},[
      h('li',{class: 'item'},[],'Item B'),
      h('li',{class: 'item'},[],'Item 2'),
      h('li',{class: 'item'},[],'Item 3'),
      h('li',{class: 'item'},[],'Item 3'),
      h('li',{class: 'item'},[],'Item 3')
    ])
    patch(vnode1,vnode2);
    console.log(vnode1)
  })

  // 修改vnode,查看diff效果
  let btn2 = document.getElementById('btn2');
  btn2.addEventListener('click',function(e){
    let vnode2 = h('ul',{id:'list'},[
      h('li',{class: 'item'},[],'Item 1'),
      h('li',{class: 'item'},[],'Item 2'),
      h('li',{class: 'item'},[],'Item 3')
    ])
    patch(vnode1,vnode2);
    console.log(vnode1)
  })
</script>
</html>

/**
 * 插入 || diff DOM函数
 * @param {HTMLElement || Object} vnode container容器 || vnode节点
 * @param {object} newVnode newVnode节点
 */
function patch(vnode, newVnode){
  if(vnode instanceof HTMLElement){ // 若第一个参数是DOM节点，插入到容器里
    let node = createElement(newVnode);
    vnode.appendChild(node);
  }else{ // 两个都为vnode,执行diff算法
    createElement(newVnode); // 绑定DOM节点到newVnode上
    updateChildren(vnode, newVnode); // diff
  }
}
/**
 * vnode生成函数
 * @param {String} tag 标签名
 * @param {object} attrs 属性
 * @param {Array} children 子节点
 * @param {String} text 文本节点
 */
function h(tag='',attrs={},children=[],text=''){
  return {
    tag: tag,
    attrs: attrs,
    children: children,
    text: text
  }
}
/**
 * 真实 DOM 生成函数
 * @param {Object} vnode vnode节点
 */
function createElement(vnode){
  let tag = vnode.tag;
  let children = vnode.children || [];
  let attrs = vnode.attrs || {};
  let text = vnode.text || '';
  if(!tag){
    return null
  }
  // 创建真实的 DOM 元素
  let elem = document.createElement(tag);
  if(text){
    elem.innerText = text;
  }
  // 设置属性
  for(let key in attrs){
    if(attrs.hasOwnProperty(key)){
      elem.setAttribute(key,attrs[key])
    }
  }
  // 添加子元素节点
  children.forEach((childVnode)=>{
    elem.appendChild(createElement(childVnode))
  })
  // 真实 DOM 绑定到vnode上
  vnode.elem = elem;
  
  // 返回真实的 DOM 元素
  return elem
}

/**
 * Diff 函数
 * @param {Object} vnode vnode节点
 * @param {Object} newVnode newVnode节点
 */
function updateChildren(vnode, newVnode){
  // 保存父节点，方便之后DOM节点的删除
  let currentNode = vnode.elem;
  // 对比当前节点是否相同
  if(vnode.tag === newVnode.tag && vnode.text === newVnode.text && vnode.attrs.toString() === newVnode.attrs.toString()){
    // 若节点相同，深层次对比，递归(根据vnode & newVnode的数量,决定是增加节点还是删除节点)
    if(vnode.children.length >= newVnode.children.length){
      let childrenArray = vnode.children; // 保存children数组，方便之后修改原vnode
      for(let i=vnode.children.length-1;i>=0;i--){
        let childVnode = vnode.children[i];
        let newChildVnode = newVnode.children[i];
        if(newChildVnode && childVnode.tag === newChildVnode.tag){ // 防止newChildVnode===undefined导致报错
          updateChildren(childVnode, newChildVnode) // 递归
        }else{
          replaceNode(childVnode, newChildVnode,currentNode,childrenArray,i)
        }
      }
    }else{
      let childrenArray = vnode.children; // 保存children数组，方便之后修改原vnode
      for(let i=0;i<newVnode.children.length;i++){
        let childVnode = vnode.children[i];
        let newChildVnode = newVnode.children[i];
        if(childVnode && childVnode.tag === newChildVnode.tag){ // 防止childVnode===undefined导致报错
          updateChildren(childVnode, newChildVnode) // 递归
        }else{
          replaceNode(childVnode, newChildVnode,currentNode,childrenArray)
        }
      }
    }
  }else{
    replaceNode(vnode, newVnode)
  }
}
/**
 * 替换真实DOM节点 & 替换虚拟DOM节点
 * @param {Object} vnode 
 * @param {Object} newVnode 
 * @param {HTMLElement} parentNode 
 * @param {Array} childrenArray 
 * @param {Number} index 
 */
function replaceNode(vnode, newVnode,parentNode=null,childrenArray=[],index=0){
  if(vnode&&newVnode){ // 若两者都是vnode,应替换节点
    let elem = vnode.elem;
    let newElem = newVnode.elem;
    replaceVNode(vnode, newVnode)
    elem.parentNode.replaceChild(newElem,elem);
  }else if(vnode){ // 若newVnode===undefined,应删除节点
    let elem = vnode.elem;
    childrenArray.splice(index,1);
    elem.parentNode.removeChild(elem)
  }else{ // 若vnode===undefined,应添加节点
    let newElem = newVnode.elem;
    childrenArray.push(newVnode);
    parentNode.appendChild(newElem);
  }
}
/**
 * 替换虚拟DOM节点
 * @param {Object} vnode 
 * @param {Object} newVnode 
 */
function replaceVNode(vnode, newVnode){
  vnode.tag = newVnode.tag;
  vnode.elem = newVnode.elem;
  vnode.text = newVnode.text;
  vnode.attrs = newVnode.attrs;
  vnode.children = newVnode.children;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,921评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,635评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,393评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,836评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,833评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,685评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,043评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,694评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 42,671评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,670评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,779评论 1赞 332
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,424评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,027评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,984评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,214评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,108评论 2赞 351
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,517评论 2赞 343

推荐阅读更多精彩内容