1. 认识树结构

什么是树？

在真实生活中的树：

1. 通常有一个根，连着根的是树干
2. 树干到上面之后会进行分叉成树枝，树枝还会分叉成更小的树枝
3. 在树枝的最后是叶子

在数据结构中的树正是由真实生活中的树抽象而来，一个模拟树结构的例子：

在上图中，我们可以把

1. 总经理看成是树干
2. 每一个部门看成树枝
3. 部门下更小的部门可以看成树叶

总结：

树是一种分层数据的抽象模型，js 中没有树，但是我们可以用 Object 来构建树

前言

接下来的几章中我们将要在 mini-vue 中 实现一个自己的编译器，在上一章我们了解了 compiler 的作用和大致流程。

它主要经历了以下三个大的步骤：

1. 解析（ parse ） template 模板，生成 AST
2. 转化（transform）AST，得到 JavaScript AST
3. 生成（generate）render 函数

那么本章我们就先来实现编译器的第一步：依据模板生成 AST 抽象语法树

ps：compiler 是一个非常复杂的概念，我们不会实现一个完善的编译器，而是会像之前一样严格遵循：没有使用就当做不存在 和 最少代码的实现逻辑 这两个标准。只关注 核心 和 当前业务 相关的内容，而忽略其他。

前言

哈希表是一种 非常重要的数据结构，几乎所有的编程语言都有 直接或者间接 的应用这种数据结构。

很多学习编程的人一直搞不懂哈希表到底是如何实现的，在这一章中，我们就一点点来实现一个自己的哈希表。通过实现来理解哈希表背后的原理和它的优势。

1. 哈希表介绍和特性

哈希表通常是基于数组进行实现的，相对于数组，他有很多优势：

1. 他可以提供非常快速的 插入-删除-查找 操作

2. 无论多少数据，插入和删除都接近常量的时间：即 O(1) 的时间复杂度

3. 哈希表的速度比 树还要快，基本可以瞬间查找到想要的元素

4. 哈希表相对于树来说编码要容易很多

PS: 树也是一种基础的数据结构，js 中没有树，我们下一章就会讲树

哈希表相对于数组的一些不足：

1. 哈希表中的数据没有顺序，所以不能以一种固定的方式来遍历其中的元素

2. 通常情况下，哈希表中的 key 是不允许重复的。

那么哈希表到底是什么？

我们上面说了哈希表的优势和不足，似乎还是没说它到底长什么样子？

这也是哈希表不好理解的地方，它不像数组、链表和树等可通过图形的形式表示其结构和原理。

哈希表结构就是数组，但它神奇之处在于对下标值的一种变换，这种变换我们可以称之为哈希函数，通过哈希函数可以获取HashCode。

前言

从这一章开始我们进入到 compiler 编译器模块的实现。

在实现 compiler 编译器模块之前，我们先来了解一下 vue 的编译时核心设计原则

1. 初探 compiler 编译器

编译器是一个非常复杂的概念，在很多语言中均有涉及。不同类型的编译器在实现技术上都会有较大的差异。

比如你要实现一个 java 或者 JavaScript 的编译器，那就是一个非常复杂的过程了。

但是对于我们而言，我们并不需要设计这种复杂的语言编辑器，我们只需要有一个 领域特定语言（DSL） 的编辑器即可。

DSL 并不具备很强的普适性，它是仅为某个适用的领域而设计的，但它也足以用于表示这个领域中的问题以及构建对应的解决方案。

我们这里所谓的特定语言指的就是：把 template 模板，编译成 render 函数。这个就是 vue 中 编译器 compiler 的作用。

而这也是我们本章所要研究的内容，"vue 编译器是如何将 template 编译成 render 函数的？"

明确好以上概念后，我们创建以下实例，以此来看一下 vue 中 compiler 的作用：

html
<script>
const { compile } = Vue
const template = `
  <div>hello world</div>
`
const renderFn = compile(template)

console.log(renderFn);

</script>

查看最终的打印结果可以发现，最终 compile 函数把 template 模板字符串转化为了 render 函数。

那么我们可以借此来观察一下 compile 这个方法的内部实现。我们可以在源码packages/compiler-dom/src/index.ts 中的 第40行 查看到该方法。

从代码中可以发现，compile 方法，其实是触发了 baseCompile 方法，那么我们可以进入到该方法。

该方法的代码比较简单，剔除掉无用的内容之后，我们可以得到上图框框圈出的三块内容

总结这段代码（complie），主要做了三件事情：

1. 通过 parse 方法进行解析，得到 AST
2. 通过 transform 方法对 AST 进行转化，得到 JavaScript AST
3. 通过 generate 方法根据 AST 生成 render 函数

整体的代码解析，虽然比较清晰，但是里面涉及到的一些概念，我们可能并不了解。

比如：什么是 AST？

所以接下来我们先花费一些时间，来了解编译器中的一些基础知识，然后再去阅读对应的源码和实现具体的逻辑。

1. 认识链表

1. 链表是一种通过指针的形式把一组存储单元联系在一起的数据结构。

2. js 中没有链表，但可以用 Object 模拟链表

3. 链表类似于火车：有一个火车头，火车头会连接一个节点，节点上有乘客（类似于数据），并且这个节点会连接下一个节点，以此类推

链表的火车结构：

4. 链表的常见操作：
   1. append(element)：向链表尾部添加一个新的项
   2. insert(value, position)：向链表的特定位置插入一个新的项
   3. get(position)：获取对应位置的元素
   4. indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回 -1
   5. update(position,element)：修改某个位置的元素
   6. removeAt(postion)：从链表的特定位置移除一项
   7. remove(element)：从链表中移除一项
   8. isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于等于0返回false
   9. size()：返回链表包含的元素个数。与数组的length属性类似