[TODO]Immutable-js 数据结构介绍之List

[zmmbreeze]

可以说Facebook开源的Immutable库是市面上前端领域内用来实现不可变数据的最佳工具。也一直是React的最佳搭档。据说Lee Byron花了3年时间开发了它。很早就想深入了解下Immutable的实现原理，不过时间有限。最近正好空出一段时间，可以详细阅读源码学习下实现。

Immutable的核心结构是所谓的Persistent data structor。其数据结构的实现借鉴了Clojure和Scala的hash maps tries和vector tries。PS：有另一个库mori，它桥接了Clojure的数据结构到Javascript中。Immutable的数据结构主要有两个特点：

1. 数据不可变（immutable），任何更新都会生成新的数据（引用），原有的旧数据保持不变依旧可以访问
2. 实现了结构共享（Structral sharing）的机制，达到最大限度的内存复用

接下来的文章里面，我们会主要介绍一下其实现原理。

有向无环图（DAG）

本文主要讲List所以我们以数组为例。如果不采用Immutable我们要自己实现修改数组但是不改变，那么我们一般采用拷贝一份新数组并修改新数组的方式实现。示例代码如下：

var oldArray = [1, 2, 3, 4];
var newArray = oldArray.concat();
newArray[3] = '3';
oldArray === newArray;   // false

可以看到数组本身（不包括数组中各项的值）基本没有共享任何东西，如果数组的元素不算多那直接拷贝一次还好。如果数组比较大，那么就不合算了。因此为了实现结构共享这个目标，最大限度的复用内存，我们需要另一种数据结构。

Directed Acyclic Graph（DAG）即所谓的有向无环图是更为理想的实现结构共享的数据结构。下图是Lee Byron在React.js Conf 2015的分享中所使用的动态图，完美解释了DAG实现内存共享的方式：

DAG虽然可以实现最大程度上的结构共享，但是我们实际开发中用到的还是数组、对象（key-value结构）这些常见的数据结构。Immutable采用的方式就是对外提供类似数组和对象的接口，但是底层采用DAG的数据结构。

Tires

DAG是非常灵活的一种数据结构，Immutable采用的则是DAG的子集Tries（其发音和Trees一样，也有人读作try）来实现。Tries又可以成为字典树或者前缀树。说定义可能比较难以理解，看下图比较容易理解一下：

上图所描述的就是如下所示的对象被改成Tries形式的数据格式之后的结果。

var data = {
    to: 7,
    tea: 3,
    A: 15,
    ted: 4,
    ten: 12,
    i: 11,
    inn: 9,
    in: 5
};

如果按照Javascript的写法来写这个Tries数据结构，大概如下：

var tries = {
    subTries: {
        t: {
            subTries: {
                o: {value: 7},
                e: {
                    subTries: {
                        a: {value: 3},
                        d: {value: 4},
                        n: {value: 12}
                    }
                }
            }
        },
        A: {value: 15},
        i: {
            value: 11,
            subTries: {
                n: {
                    value: 5,
                    subTries: {
                        n: {value: 9}
                    }
                }
            }
        }
    }
};

可以看到数据结构一下复杂了很多。通过牺牲空间，获得了一个鲜明的优点：一个节点的所有子孙节点都有相同的前缀。利用这个特点我们可以用来做字符串联想、搜索提示等等。

Tries也并不一定要用字符串来作为键值，也可以使用其他结构。

TODO

---

• JS Array == Vector

• JS Object == Hash map == Hash table

• Tries 字典树/前缀树

• Directed Acyclic Graph (DAG) 有向无环图

• Index Trie == Bitmap Vector Trie

• Hash Trie == Hash Array Mapped Trie