从TreeMap到红黑树

TreeMap and Red-Black Tree

Posted by S.L on October 4, 2019

Java中常用的TreeMap类是基于红黑树Red-Black Tree实现的,本文大量参考了CarpenterLee的《史上最清晰的红黑树讲解》。

红黑树简介

红黑树又称红-黑二叉树,它首先是一颗二叉树,它具体二叉树所有的特性。同时红黑树更是一棵 自平衡二叉查找树

我们知道一颗基本的二叉排序树都需要满足一个基本性质————即 树中的任何节点的值大于它的左子节点,且小于它的右子节点 。 按照这个基本性质使得树的检索效率大大提高。我们知道在生成二叉树的过程是非常容易 失衡 的,最坏的情况就是一边倒(只有右/左子树),这样势必会导致二叉树的检索效率大大降低 (O(n) ),所以为了维持二叉树的平衡,大牛们提出了各种实现的算法,如: AVLSBT伸展树TREAP红黑树等等。

红黑树的特点

红黑树顾名思义就是节点是红色或者黑色的「平衡二叉树」(并不完全是),它通过颜色的约束来维持着二叉树的「平衡」。对于一棵有效的红黑树二叉树而言有如下规则:

  • 1.每个节点要么是红色,要么是黑色。
  • 2.根节点必须是黑色。
  • 3.红色节点不能连续(也即是,红色节点的孩子和父亲都不能是红色)。
  • 4.对于每个节点,从该点至null(树尾端)的任何路径,都含有相同个数的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的,是近似平衡的二叉搜索树。 因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的。 所以红黑树是复杂而高效的,其检索效率 O(logn) ,最大深度为 2log(n+1)

红黑树有两个重要性质:

  • 1、红节点的孩子节点不能是红节点;
  • 2、从根到前端节点的任意一条路径上的黑节点数目一样多。

这两条性质确保该树的高度为 logN ,所以是平衡树。

与AVL的区别

  • 1、红黑树放弃了追求完全平衡,追求大致平衡。 对于AVL树,任何一个节点的两个子树高度差不会超过1;对于红黑树,则是不会相差两倍以上。 在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多两次、删除最多三次旋转就能达到平衡,实现起来也更为简单。
  • 2、平衡二叉树追求「绝对平衡」,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知(这个有争议)。
  • 3、平衡二叉树适合用于插入与删除次数比较少,但查找多的情况。红黑树在二叉查找树的基础上增加了着色和相关的性质使得红黑树「相对平衡」, 从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(logn)。所以红黑树适用于搜索、插入、删除操作较多的情况。

下面引用知乎帖子信陵君魏无忌的回答:

红黑树中红节点的父亲和孩子必须是黑节点,且从根到叶子节点经过的黑节点个数相同,因此红黑树最小深度是路径上只有黑节点, 最大深度是路径上红黑节点相互间隔,因此最大深度≤最小深度的两倍,最大深度是2*log2(n+1)。因此,红黑树的查询效率比avl树低, 但是红黑树的删除效率比avl树高,更适合大量数据增加删除的场景,而且红黑树在增加删除数据的时候只需要常数次旋转操作, 更适合数据持久化的场景。

关于二叉查找树和二叉平衡树请参考这篇博文

红黑树的应用

红黑树的应用:

  • 1、在C++的STL中,地图和集都是用红黑树实现的;
  • 2、著名的Linux的进程调度完全公平调度程序,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上, 每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间;
  • 3、IO多路复用的 epoll 的的实现采用红黑树组织管理的 sockfd ,以支持快速的增删改查;
  • 4、Nginx的中用红黑树管理定时器,因为红黑树是有序的,可以很快的得到距离当前最小的定时器;
  • 5、Java中的 TreeMap 中的实现,如可以实现一致性哈希的环

    TreeMap基础

    TreeMap 底层通过红黑树(Red-Black Tree)实现,也就意味着 containsKey()get()put()remove() 都有着 log(n) 的时间复杂度。 brt

TreeMap 的定义如下:

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap继承 AbstractMap ,实现 NavigableMapCloneableSerializable 三个接口。

其中 AbstractMap 表明 TreeMap 为一个 Map 即支持 key-value 的集合, NavigableMap 则意味着它支持一系列的「导航」方法,具备 针对给定搜索目标返回最接近匹配项 的导航方法 。

前文说到当查找树的结构发生改变时,红黑树的条件可能被破坏,需要通过调整使得查找树重新满足红黑树的条件。调整可以分为两类:

  • 一类是颜色调整,即改变某个节点的颜色;
  • 另一类是结构调整,即改变检索树的结构关系。

结构调整过程包含两个基本操作:左旋(RotateLeft)和右旋(RotateRight)。

基本结构

它包含了如下几个重要的属性:

    //比较器,因为TreeMap是有序的,通过Comparator接口我们可以对TreeMap的内部排序进行精密的控制
    private final Comparator<? super K> comparator;
    //TreeMap红-黑节点,为TreeMap的内部类
    private transient Entry<K,V> root = null;
    //容器大小
    private transient int size = 0;
    //TreeMap修改次数
    private transient int modCount = 0;
    //红黑树的节点颜色--红色
    private static final boolean RED = false;
    //红黑树的节点颜色--黑色
    private static final boolean BLACK = true;

对于叶子节点 Entry 是TreeMap的内部类,可见默认的颜色是黑色:

/**
 * Node in the Tree.  Doubles as a means to pass key-value pairs back to
 * user (see Map.Entry).
 */

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;

    /**
     * Make a new cell with given key, value, and parent, and with
     * {@code null} child links, and BLACK color.
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
    .....

左旋

左旋的过程是将x的右子树绕x逆时针旋转,使得x的右子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。 left_rotate

private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        // 获取P的右子节点
        Entry<K,V> r = p.right;
        // 将R的左子树设置为P的右子树
        p.right = r.left;
        // 若R的左子树不为空,则将P设置为R左子树的父亲
        if (r.left != null)
            r.left.parent = p;
        // 将P的父亲设置R的父亲
        r.parent = p.parent;
        // 如果P的父亲为空,则将R设置为跟节点
        if (p.parent == null)
            root = r;
        // 如果P为其父节点的左子树,则将R设置为P父节点左子树
        else if (p.parent.left == p)
            p.parent.left = r;
        // 否则R设置为P的父节点的右子树
        else
            p.parent.right = r;
        // 将P设置为R的左子树
        r.left = p;
        // 将R设置为P的父节点
        p.parent = r;
    }
}

左旋就是将节点的右支往左拉,右子节点变成父节点,并把晋升之后多余的左子节点出让给降级节点的右子节点

右旋

右旋的过程是将x的左子树绕x顺时针旋转,使得x的左子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

right_rotate TreeMap中右旋代码如下:

private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        // 将L设置为P的左子树
        Entry<K,V> l = p.left;
        // 将L的右子树设置为P的左子树
        p.left = l.right;
        // 若L的右子树不为空,则将P设置L的右子树的父节点
        if (l.right != null) 
            l.right.parent = p;
        // 将P的父节点设置为L的父节点
        l.parent = p.parent;
        // 如果P的父节点为空,则将L设置根节点
        if (p.parent == null)
            root = l;
        // 若P为其父节点的右子树,则将L设置为P的父节点的右子树
        else if (p.parent.right == p)
            p.parent.right = l;
        // 否则将L设置为P的父节点的左子树
        else 
            p.parent.left = l;
        // 将P设置为L的右子树
        l.right = p;
        // 将L设置为P的父节点
        p.parent = l;
    }
}

右旋就是反过来,将节点的左支往右拉,左子节点变成了父节点,并把晋升之后多余的右子节点出让给降级节点的左子节点。

着色

private static <K,V> void setColor(Entry<K,V> p, boolean c) {
    if (p != null)
        p.color = c;
}

TreeMap方法剖析

get方法

get(Object key) 方法根据指定的key值返回对应的value,该方法调用了 getEntry(Object key) 得到相应的entry,然后返回entry .value。因此 getEntry() 是算法的核心。 算法思想是根据key的自然顺序或者比较器顺序对二叉查找树进行查找,直到找到满足 k.compareTo(p.key) == 0 的entry。 TreeMap.getEntry

具体代码如下:

//getEntry()方法
final Entry<K,V> getEntry(Object key) {
    ......
    if (key == null)//不允许key值为null
        throw new NullPointerException();
    Comparable<? super K> k = (Comparable<? super K>) key; // 使用元素的自然顺序
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0) // 向左找
            p = p.left;
        else if (cmp > 0) // 向右找
            p = p.right;
        else
            return p;
    }
    return null;
}

put方法

put(K key, V value) 方法是将指定的key-value对添加到map里。该方法首先会对map做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于 ` getEntry()` 方法;如果没有找到则会在红黑树中插入新的entry,如果插入之后破坏了红黑树的约束,还需要进行调整(旋转&改变某些节点的颜色)。

具体代码如下:

public V put(K key, V value) {
   // 用t表示二叉树的当前节点
    Entry<K,V> t = root;
    // t为null表示一个空树,即TreeMap中没有任何元素,直接插入
    if (t == null) {
        // 比较key值
        compare(key, key); // type (and possibly null) check
        // 将新的key-value键值对创建为一个Entry节点,并将该节点赋予给root
        root = new Entry<>(key, value, null);
        // 容器的size = 1,表示TreeMap集合中存在一个元素
        size = 1;
        // 修改次数 + 1
        modCount++;
        return null;
    }
    int cmp;     // cmp表示key排序的返回结果
    Entry<K,V> parent;   // 父节点,第一次赋值为root
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;    //指定的排序算法
    // 如果cpr不为空,则采用既定的排序算法进行创建TreeMap集合
    if (cpr != null) {
        do {
            parent = t;      // parent指向上次循环后的t
            // 用比较器比较新增节点的key和当前节点key的大小
            cmp = cpr.compare(key, t.key);
            // cmp返回值小于0,表示新增节点的key小于当前节点的key,则以当前节点的左子节点作为新的当前节点
            if (cmp < 0)
                t = t.left;
            // cmp返回值大于0,表示新增节点的key大于当前节点的key,则以当前节点的右子节点作为新的当前节点
            else if (cmp > 0)
                t = t.right;
            // cmp返回值等于0,表示两个key值相等,则新值覆盖旧值,并返回新值
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 如果cpr为空,则采用默认的排序算法进行创建TreeMap集合
    else {
        if (key == null)     //key值为空抛出异常
            throw new NullPointerException();
        // 下面处理过程和上面一样
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key); // 使用key自身的比较器完成比较
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // t为null
    // 将新增节点当做parent的子节点
    Entry<K,V> e = new Entry<>(key, value, parent);
    // 如果新增节点的key小于parent的key,则当做左子节点
    if (cmp < 0)
        parent.left = e;
    // 如果新增节点的key大于parent的key,则当做右子节点
    else
        parent.right = e;
    
    // 上面已经完成了排序二叉树的的构建,将新增节点插入该树中的合适位置
    // 下面fixAfterInsertion()方法就是对这棵树进行调整、平衡
    fixAfterInsertion(e);
    // TreeMap元素数量 + 1
    size++;
    // TreeMap容器修改次数 + 1
    modCount++;
    return null;
}

上述代码的插入部分并不难理解:首先在红黑树上找到合适的位置,然后创建新的entry并插入(当然,新插入的节点一定是树的叶子)。 难点是调整函数 fixAfterInsertion() ,前面已经说过,调整往往需要:1.改变某些节点的颜色;2.对某些节点进行旋转。

调整函数 fixAfterInsertion() 的具体代码如下,其中用到了上文中提到的 rotateLeft()rotateRight() 函数。通过代码我们能够看到,情况2其实是落在情况3内的。情况4~情况6跟前三种情况是对称的,因此图解中并没有画出后三种情况,读者可以参考代码自行理解。

//红黑树调整函数fixAfterInsertion()
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED; //新增节点的颜色为红色
    //循环 直到 x不是根节点,且x的父节点不为红色
    while (x != null && x != root && x.parent.color == RED) {
        // 如果X的父节点(P)是其父节点的父节点(G)的左节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // 获取X的叔节点(U)
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) { // 如果y为null,则视为BLACK
                setColor(parentOf(x), BLACK);              // 情况1
                setColor(y, BLACK);                        // 情况1
                setColor(parentOf(parentOf(x)), RED);      // 情况1
                x = parentOf(parentOf(x));                 // 情况1
                // 因为父亲和叔父都是黑色,保证从爷爷向下的路径此时满足路径上的黑色数目相同
                // 可能G节点的父节点也是红色,这个时候我们需要将G节点当做新增节点递归处理
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);                       // 情况2
                    rotateLeft(x);                         // 情况2
                    // 将父节点左旋,注意旋转后父节点x变成了之前右孩子的左孩子
                }
                // 这里的x的父节点其实是上面旋转前的x
                setColor(parentOf(x), BLACK);              // 情况3
                setColor(parentOf(parentOf(x)), RED);      // 情况3
                rotateRight(parentOf(parentOf(x)));        // 情况3
                // 将爷爷几点进行右旋转,因为它为红色,而它的左孩子为黑色,是旋转后的根节点
            }
        } else { // 和if中的逻辑对称
            // 获取X的叔节点(U)
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);              // 情况4
                setColor(y, BLACK);                        // 情况4
                setColor(parentOf(parentOf(x)), RED);      // 情况4
                x = parentOf(parentOf(x));                 // 情况4
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);                       // 情况5
                    rotateRight(x);                        // 情况5
                }
                setColor(parentOf(x), BLACK);              // 情况6
                setColor(parentOf(parentOf(x)), RED);      // 情况6
                rotateLeft(parentOf(parentOf(x)));         // 情况6
            }
        }
    }
    // 将根节点强制设置为黑色
    root.color = BLACK; 
}

它的思想是把「多出来」的红色往上一层推,确保下面层的红黑性质,最后推到根以后,如果依然违反性质1,则可以直接把根由红改黑即可,就相当于把这「多出来」的红色推到树以外的节点去了。

put

successor方法

对于一棵二叉查找树,给定节点t,其后继(树中比大于t的元素中最小的那个元素)可以通过如下方式找到:

  • t的右子树不空,则t的后继是其右子树中最小的那个元素。
  • t的右孩子为空,则t的后继是其第一个向左走的节点的祖先。 successor TreeMap 中寻找节点后继的代码如下:
    // 寻找节点后继函数successor()
    static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
      if (t == null)
          return null;
      else if (t.right != null) {// 1. t的右子树不空,则t的后继是其右子树中最小的那个元素
          Entry<K,V> p = t.right;
          while (p.left != null)
              p = p.left;
          return p;
      } else {// 2. t的右孩子为空,则t的后继是其第一个向左走的祖先
          Entry<K,V> p = t.parent;
          Entry<K,V> ch = t;
          while (p != null && ch == p.right) { // 向上遍历,直到ch为p的左孩子
              ch = p;
              p = p.parent;
          }
          return p; // 返回parent
      }
    }
    

    predecessor方法

    对于一棵二叉查找树,给定节点t,其前驱(树中比小于t的元素中最大的那个元素)可以通过如下方式找到:

  • t的左子树不空,则t的前驱是其左子树中最大的那个元素。
  • t的左孩子为空,则t的前驱是其第一个向右走的节点的祖先。

对应的图可以对比successor部分的图看,分别找45的前驱和35的前驱。

TreeMap 中寻找节点前驱的代码如下:

// 寻找节点前驱函数successor()
static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.left != null) {// 1. t的左子树不空,则t的前驱是其有子树中最大的那个元素
        Entry<K,V> p = t.left;
        while (p.right != null)
            p = p.right;
        return p;
    } else {// 2. t的左孩子为空,则t的前驱是其第一个向右走的祖先
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.left) { // 向上遍历,直到ch为p的右孩子
            ch = p;
            p = p.parent;
        }
        return p; // 返回parent
    }
}

remove方法

remove(Object key)的作用是删除key值对应的entry,该方法首先通过上文中提到的getEntry(Object key)方法找到key值对应的entry,然后调用deleteEntry(Entry<K,V> entry)删除对应的entry。由于删除操作会改变红黑树的结构,有可能破坏红黑树的约束条件,因此有可能要进行调整。

getEntry()函数前面已经讲解过,这里重点放deleteEntry()上,该函数删除指定的entry并在红黑树的约束被破坏时进行调用fixAfterDeletion(Entry<K,V> x)进行调整。

由于红黑树是一棵增强版的二叉查找树,红黑树的删除操作跟普通二叉查找树的删除操作也就非常相似,唯一的区别是红黑树在节点删除之后可能需要进行调整。现在考虑一棵普通二叉查找树的删除过程,可以简单分为两种情况:

  • 删除点p的左右子树都为空,或者只有一棵子树非空。
  • 删除点p的左右子树都非空。

对于上述情况1,处理起来比较简单,直接将p删除(左右子树都为空时),或者用非空子树替代p(只有一棵子树非空时); 对于情况2,可以用p的后继s(树中大于x的最小的那个元素)代替p,然后使用情况1删除s(此时s一定满足情况1,可以画画看)。

基于以上逻辑,红黑树的节点删除函数deleteEntry()代码如下:

// 红黑树entry删除函数deleteEntry()
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;
    if (p.left != null && p.right != null) {// 2. 删除点p的左右子树都非空。
        Entry<K,V> s = successor(p);// 后继
        p.key = s.key;
        p.value = s.value;
        p = s;
    }
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {// 1. 删除点p只有一棵子树非空。
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;
        p.left = p.right = p.parent = null;
        if (p.color == BLACK)
            fixAfterDeletion(replacement);// 调整
    } else if (p.parent == null) {
        root = null;
    } else { // 1. 删除点p的左右子树都为空
        if (p.color == BLACK)
            fixAfterDeletion(p);// 调整
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

上述代码中占据大量代码行的,是用来修改父子节点间引用关系的代码,其逻辑并不难理解。下面着重讲解删除后调整函数 fixAfterDeletion() 。首先请思考一下,删除了哪些点才会导致调整?只有删除点是 BLACK 的时候,才会触发调整函数,因为删除 RED 节点不会破坏红黑树的任何约束,而删除 BLACK 节点会破坏规则4。

跟上文中讲过的 fixAfterInsertion() 函数一样,这里也要分成若干种情况。记住,无论有多少情况,具体的调整操作只有两种:1.改变某些节点的颜色,2.对某些节点进行旋转。

remove

删除节点时先要找到顶替的节点,如果删去的节点是黑色则破坏了性质2,也需要调整。调整的思想也同前面类似,把这个黑色赋予顶替节点,则顶替节点相当于有两重黑色,然后将它的两重黑色向上推,一直推到根,再从根推到外面去了。

private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);                   // 情况1
                setColor(parentOf(x), RED);             // 情况1
                rotateLeft(parentOf(x));                // 情况1
                sib = rightOf(parentOf(x));             // 情况1
            }
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);                     // 情况2
                x = parentOf(x);                        // 情况2
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);       // 情况3
                    setColor(sib, RED);                 // 情况3
                    rotateRight(sib);                   // 情况3
                    sib = rightOf(parentOf(x));         // 情况3
                }
                setColor(sib, colorOf(parentOf(x)));    // 情况4
                setColor(parentOf(x), BLACK);           // 情况4
                setColor(rightOf(sib), BLACK);          // 情况4
                rotateLeft(parentOf(x));                // 情况4
                x = root;                               // 情况4
            }
        } else { // 跟前四种情况对称
            Entry<K,V> sib = leftOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);                   // 情况5
                setColor(parentOf(x), RED);             // 情况5
                rotateRight(parentOf(x));               // 情况5
                sib = leftOf(parentOf(x));              // 情况5
            }
            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);                     // 情况6
                x = parentOf(x);                        // 情况6
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);      // 情况7
                    setColor(sib, RED);                 // 情况7
                    rotateLeft(sib);                    // 情况7
                    sib = leftOf(parentOf(x));          // 情况7
                }
                setColor(sib, colorOf(parentOf(x)));    // 情况8
                setColor(parentOf(x), BLACK);           // 情况8
                setColor(leftOf(sib), BLACK);           // 情况8
                rotateRight(parentOf(x));               // 情况8
                x = root;                               // 情况8
            }
        }
    }
    setColor(x, BLACK);
}

References

  • https://www.cnblogs.com/chenssy/p/3746600.html
  • https://www.cnblogs.com/CarpenterLee/p/5503882.html
  • https://www.cnblogs.com/CarpenterLee/p/5525688.html
  • https://blog.csdn.net/qq_25940921/article/details/82183093
  • https://zhuanlan.zhihu.com/p/31805309
  • https://www.zhihu.com/question/30527705

本文首次发布于 S.L’s Blog, 作者 @stuartlau , 转载请保留原文链接.