Vue中vfor循环创建DOM时Key的理解之Vue中的diff算法

在Vue开发过程中vfor遍历数组创建Dom是最常见的方式，在vfor时，标签中有一个key值，key值的作用是啥呢？这就不得不提到Vue中的diff算法。

一、什么是diff算法

Vue会用虚拟DOM来表述真实DOM，这样的目的是为了计算出DOM的最小的变化从而更加快速的更新真实DOM

二、diff算法的计算过程

1、遍历老虚拟DOM

2、遍历新虚拟DOM

3、重新排序

这样做会有个问题，就是节点数越多，计算的次数以指数级增长,时间复杂度为O(n³)，这个计算次数是不可接受的，所以在Vue中对diff算法做了优化：

1、只比较同一层级，不做跨级比较

2、标签名不同直接删除，不继续深度比较

3、标签名相同，key相同，就被认为是相同节点，不继续深度比较

所以在vfor创建变量时，不建议使用item.index作为key值，而是以item.id作为key值来保证性能 

 在优化完成后，算法的时间复杂度为O(n)

三、patch函数

vue中的patch函数的逻辑是基于shabbdom，patch函数会在页面首次渲染时执行一次，这一步的目的是将Vnode渲染到一个空的容器中

const vnode = h(
  "div#container.two.classes",
  { on: { click: () => console.log("div clicked") } },
  [
    h("span", { style: { fontWeight: "bold" } }, "This is bold"),
    " and this is just normal text",
    h("a", { props: { href: "/foo" } }, "I'll take you places!")
  ]
);
// Patch into empty DOM element – this modifies the DOM as a side effect
patch(container, vnode);

在页面更新时用新的Vnode来替换老的Vnode。

const newVnode = h(
  "div#container.two.classes",
  { on: { click: () => console.log("updated div clicked") } },
  [
    h(
      "span",
      { style: { fontWeight: "normal", fontStyle: "italic" } },
      "This is now italic type"
    ),
    " and this is still just normal text",
    h("a", { props: { href: "/bar" } }, "I'll take you places!")
  ]
);
// Second `patch` invocation
patch(vnode, newVnode); // Snabbdom efficiently updates the old view to the new state

patch函数是通过init函数创建出来的

const patch = init([
  // Init patch function with chosen modules
  classModule, // makes it easy to toggle classes
  propsModule, // for setting properties on DOM elements
  styleModule, // handles styling on elements with support for animations
  eventListenersModule // attaches event listeners
]);

这里贴上patch实现的逻辑，路径：src>package>init.ts

return function patch(
    oldVnode: VNode | Element | DocumentFragment,
    vnode: VNode
  ): VNode {
    let i: number, elm: Node, parent: Node;
    const insertedVnodeQueue: VNodeQueue = [];
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

    if (isElement(api, oldVnode)) {
      oldVnode = emptyNodeAt(oldVnode);
    } else if (isDocumentFragment(api, oldVnode)) {
      oldVnode = emptyDocumentFragmentAt(oldVnode);
    }

    if (sameVnode(oldVnode, vnode)) {
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } else {
      elm = oldVnode.elm!;
      parent = api.parentNode(elm) as Node;
      //创建新的DOM元素
      createElm(vnode, insertedVnodeQueue);

      if (parent !== null) {
        //插入新的DOM元素
        api.insertBefore(parent, vnode.elm!, api.nextSibling(elm));
        //移除老的DOM元素
        removeVnodes(parent, [oldVnode], 0, 0);
      }
    }

    for (i = 0; i < insertedVnodeQueue.length; ++i) {
      insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i]);
    }
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };

isElement方法用于判断我们传入patch的值是不是一个Dom元素，返回一个布尔值

function isElement(
  api: DOMAPI,
  vnode: Element | DocumentFragment | VNode
): vnode is Element {
  return api.isElement(vnode as any);
}

sameVnode方法判断oldVnode与现有的Vnode是不是同一个Vnode，返回一个布尔值

function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
  const isSameKey = vnode1.key === vnode2.key;
  const isSameIs = vnode1.data?.is === vnode2.data?.is;
  const isSameSel = vnode1.sel === vnode2.sel;
  const isSameTextOrFragment =
    !vnode1.sel && vnode1.sel === vnode2.sel
      ? typeof vnode1.text === typeof vnode2.text
      : true;

  return isSameSel && isSameKey && isSameIs && isSameTextOrFragment;
}

patchVnode用于更新Vnode

  function patchVnode(
    oldVnode: VNode,
    vnode: VNode,
    insertedVnodeQueue: VNodeQueue
  ) {
    const hook = vnode.data?.hook;
    hook?.prepatch?.(oldVnode, vnode);
    const elm = (vnode.elm = oldVnode.elm)!;
    if (oldVnode === vnode) return;
    if (
      vnode.data !== undefined ||
      (vnode.text !== undefined && vnode.text !== oldVnode.text)
    ) {
      vnode.data ??= {};
      oldVnode.data ??= {};
      for (let i = 0; i < cbs.update.length; ++i)
        cbs.update[i](oldVnode, vnode);
      vnode.data?.hook?.update?.(oldVnode, vnode);
    }
    const oldCh = oldVnode.children as VNode[];
    const ch = vnode.children as VNode[];
    if (vnode.text === undefined) {
      if (oldCh !== undefined && ch !== undefined) {
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
      } else if (ch !== undefined) {
        if (oldVnode.text !== undefined) api.setTextContent(elm, "");
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
      } else if (oldCh !== undefined) {
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
      } else if (oldVnode.text !== undefined) {
        api.setTextContent(elm, "");
      }
    } else if (oldVnode.text !== vnode.text) {
      if (oldCh !== undefined) {
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
      }
      api.setTextContent(elm, vnode.text);
    }
    hook?.postpatch?.(oldVnode, vnode);
  }

createElm用于创建新的DOM元素

  function createElm(vnode: VNode, insertedVnodeQueue: VNodeQueue): Node {
    let i: number;
    const data = vnode.data;
    const hook = data?.hook;
    hook?.init?.(vnode);
    const children = vnode.children;
    const sel = vnode.sel;
    if (sel === "!") {
      vnode.text ??= "";
      vnode.elm = api.createComment(vnode.text);
    } else if (sel === "") {
      // textNode has no selector
      vnode.elm = api.createTextNode(vnode.text!);
    } else if (sel !== undefined) {
      // Parse selector
      const hashIdx = sel.indexOf("#");
      const dotIdx = sel.indexOf(".", hashIdx);
      const hash = hashIdx > 0 ? hashIdx : sel.length;
      const dot = dotIdx > 0 ? dotIdx : sel.length;
      const tag =
        hashIdx !== -1 || dotIdx !== -1
          ? sel.slice(0, Math.min(hash, dot))
          : sel;
      const ns = data?.ns;
      const elm =
        ns === undefined
          ? api.createElement(tag, data)
          : api.createElementNS(ns, tag, data);
      vnode.elm = elm;
      if (hash < dot) elm.setAttribute("id", sel.slice(hash + 1, dot));
      if (dotIdx > 0)
        elm.setAttribute("class", sel.slice(dot + 1).replace(/\./g, " "));
      for (i = 0; i < cbs.create.length; ++i) cbs.create[i](emptyNode, vnode);
      if (
        is.primitive(vnode.text) &&
        (!is.array(children) || children.length === 0)
      ) {
        // allow h1 and similar nodes to be created w/ text and empty child list
        api.appendChild(elm, api.createTextNode(vnode.text));
      }
      if (is.array(children)) {
        for (i = 0; i < children.length; ++i) {
          const ch = children[i];
          if (ch != null) {
            api.appendChild(elm, createElm(ch as VNode, insertedVnodeQueue));
          }
        }
      }
      if (hook !== undefined) {
        hook.create?.(emptyNode, vnode);
        if (hook.insert !== undefined) {
          insertedVnodeQueue.push(vnode);
        }
      }
    } else if (options?.experimental?.fragments && vnode.children) {
      vnode.elm = (
        api.createDocumentFragment ?? documentFragmentIsNotSupported
      )();
      for (i = 0; i < cbs.create.length; ++i) cbs.create[i](emptyNode, vnode);
      for (i = 0; i < vnode.children.length; ++i) {
        const ch = vnode.children[i];
        if (ch != null) {
          api.appendChild(
            vnode.elm,
            createElm(ch as VNode, insertedVnodeQueue)
          );
        }
      }
    } else {
      vnode.elm = api.createTextNode(vnode.text!);
    }
    return vnode.elm;
  }

removeVnodes方法用于移除老的DOM元素

  function removeVnodes(
    parentElm: Node,
    vnodes: VNode[],
    startIdx: number,
    endIdx: number
  ): void {
    for (; startIdx <= endIdx; ++startIdx) {
      let listeners: number;
      const ch = vnodes[startIdx];
      if (ch != null) {
        if (ch.sel !== undefined) {
          invokeDestroyHook(ch);
          listeners = cbs.remove.length + 1;
          const rm = createRmCb(ch.elm!, listeners);
          for (let i = 0; i < cbs.remove.length; ++i) cbs.remove[i](ch, rm);
          const removeHook = ch?.data?.hook?.remove;
          if (removeHook !== undefined) {
            removeHook(ch, rm);
          } else {
            rm();
          }
        } else if (ch.children) {
          // Fragment node
          invokeDestroyHook(ch);
          removeVnodes(
            parentElm,
            ch.children as VNode[],
            0,
            ch.children.length - 1
          );
        } else {
          // Text node
          api.removeChild(parentElm, ch.elm!);
        }
      }
    }
  }

这就是整个patch函数的逻辑