降维打击！为什么我认为数据结构与算法很重要

从一个需求谈起

在我之前的项目中，曾经遇到过这样一个需求，编写一个级联选择器，大概是这样：

图中的示例使用的是 Ant-Design 的 Cascader 组件。

要实现这一功能，我需要类似这样的数据结构：

var data = [{
  "value": "浙江",
  "children": [{
    "value": "杭州",
    "children": [{
      "value": "西湖"
    }]
  }]
}, {
  "value": "四川",
  "children": [{
    "value": "成都",
    "children": [{
      "value": "锦里"
    }, {
      "value": "方所"
    }]
  }, {
    "value": "阿坝",
    "children": [{
      "value": "九寨沟"
    }]
  }]
}]

一个具有层级结构的数据，实现这个功能非常容易，因为这个结构和组件的结构是一致的，递归遍历就可以了。

但是，由于后端通常采用的是关系型数据库，所以返回的数据通常会是这个样子：

var data = [{
  "province": "浙江",
  "city": "杭州",
  "name": "西湖"
}, {
  "province": "四川",
  "city": "成都",
  "name": "锦里"
}, {
  "province": "四川",
  "city": "成都",
  "name": "方所"
}, {
  "province": "四川",
  "city": "阿坝",
  "name": "九寨沟"
}]

前端这边想要将数据转换一下其实也不难，因为要合并重复项，可以参考数据去重的方法来做，于是我写了这样一个版本。

'use strict'

/**
 * 将一个没有层级的扁平对象,转换为树形结构({value, children})结构的对象
 * @param {array} tableData - 一个由对象构成的数组,里面的对象都是扁平的
 * @param {array} route - 一个由字符串构成的数组,字符串为前一数组中对象的key,最终
 * 输出的对象层级顺序为keys中字符串key的顺序
 * @return {array} 保存具有树形结构的对象
 */

var transObject = function(tableData, keys) {
  let hashTable = {}, res = []
  for( let i = 0; i < tableData.length; i++ ) {
    if(!hashTable[tableData[i][keys[0]]]) {
      let len = res.push({
        value: tableData[i][keys[0]],
        children: []
      })
      // 在这里要保存key对应的数组序号,不然还要涉及到查找
      hashTable[tableData[i][keys[0]]] = { $$pos: len - 1 }
    }
    if(!hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]]) {
      let len = res[hashTable[tableData[i][keys[0]]].$$pos].children.push({
        value: tableData[i][keys[1]],
        children: []
      })
      hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]] = { $$pos: len - 1 }
    }
    res[hashTable[tableData[i][keys[0]]].$$pos].children[hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]].$$pos].children.push({
      value: tableData[i][keys[2]]
    })
  }
  return res
}

var data = [{
  "province": "浙江",
  "city": "杭州",
  "name": "西湖"
}, {
  "province": "四川",
  "city": "成都",
  "name": "锦里"
}, {
  "province": "四川",
  "city": "成都",
  "name": "方所"
}, {
  "province": "四川",
  "city": "阿坝",
  "name": "九寨沟"
}]

var keys = ['province', 'city', 'name']

console.log(transObject(data, keys))

还好 keys 的长度只有 3 ，这种东西长了根本没办法写，很明显可以看出来这里面有重复的部分，可以通过循环搞定，但是想了很久都没有思路，就搁置了。

后来，有一天晚饭后不是很忙，就跟旁边做数据的同事聊了一下这个需求，请教一下该怎么用循环来处理。他看了一下，就问我：“你知道 trie 树吗？”。我头一次听到这个概念，他简单的给我讲了一下，然后说感觉处理的问题有些类似，让我可以研究一下 trie 树的原理并试着优化一下。

讲道理， trie 树这个数据结构网上确实有很多资料，但很少有使用 JavaScript 实现的，不过原理倒是不难。尝试之后，我就将 transObject 的代码优化成了这样。（关于 trie 树，还请读者自己阅读相关材料）

var transObject = function(tableData, keys) {
  let hashTable = {}, res = []
  for (let i = 0; i < tableData.length; i++) {
    let arr = res, cur = hashTable
    for (let j = 0; j < keys.length; j++) {
      let key = keys[j], filed = tableData[i][key]
      if (!cur[filed]) {
        let pusher = {
          value: filed
        }, tmp
        if (j !== (keys.length - 1)) {
          tmp = []
          pusher.children = tmp
        }
        cur[filed] = { $$pos: arr.push(pusher) - 1 }
        cur = cur[filed]
        arr = tmp
      } else {
        cur = cur[filed]
        arr = arr[cur.$$pos].children
      }
    }
  }
  return res
}

这样，解决方案就和 keys 的长短无关了。

这种解决方案正如《三体》里面使用「二向箔」对宇宙文明进行降维打击一般干净利落！