JavaScript 数据结构之用 Object 做索引实现快速检索

随着Web前端技术的不断发展，技术团队的不断壮大，越来越多的数据需要放在前端用JavaScript做处理。本篇我就来介绍一下，如何使用 Object 对象做索引，从而实现信息的快速检索。

场景一：根据ID找到学生信息

拿学生信息管理举例说明吧，其实公司里的员工管理，药店里的药品管理及分类管理都是类似的。

场景说明

在学生列表页面，后端把20名学生（每页20条数据）的所有信息都给到了Web前端；前端根据情况选择比较重要的信息在列表中显示。如果需要查看学生的详细信息，则需要点击“学生名”，或该点击对应列的“查看详情”按钮。

一般情况下在列表中，可点击部分都会绑定该第信息的“唯一标识码”（ID）。所以前端需要根据这个“唯一标识码”检索出对应学生的信息并显示出来。

在列表页面学生信息的结构如下面的代码段所示：

var students = [
    {id:1,name:"仵士杰",gender:"男",birthday:"1990-02-03",……},
    {id:2,name:"张珍珍",gender:"女",birthday:"1989-02-08",……},
     ……
];

需要强调以下几点：

在列表页面，学生的所有信息都已经加载到Web前端；
在列表页面仅显示了比较重要的学生信息，如：姓名、性别，班级；
详细信息页面包含列表页面所没有的信息，如：入学时间，年龄，证件照、学费金额、学费缴纳状态等；

一般做法

可能有人会想到，每次“查看详细信息”时就向后端发起一次请求。如果在列表页面仅是加载了学生的部分信息，而详情页面中显示的很多信息在列表页面中没有加载的情况下，只能用这种方式。当然我们例举的这个场景下这种做法也可以，但是对于一个在程序优化方面有强迫症且有些偏执的人来说，是绝对不会这么做的。

还有人想到了可以使用循环，代码如下：

function getStudentById(id){
  for(var i=0; i<students.length;i++){
    if(students[i].id == id){
      return students[i];
    }
  }
}

或者有人觉得循环的效率太低，于是想先对 students 数组排序，然后用二分查找。这是一个好的想法，但必须保证所选择的排序算法有较高的效率。否则还不如使用上面的循环。

以上这些方法中，最优的应该是二分查找；但门槛较高，需要写一个高效率的排序，然后还需要写二分查找的算法。

用 Object 做索引

在JavaScript中，Object 对象可以动态增加属性，对属性的访问速度是非常快的（可暂且认为与平衡二叉树的叶子结点的访问速度相同）。所以可以利用Object对象的这一特点构造快速检索的数据结构。

针对此场景生成可快速检索的 Object 对象的代码如下：

var stuObj = {};
for(var i=0; i<students.length;i++){
  stuObj["_"+students[i].id] = students[i];
}

上面的代码生成了一个 stuObj 对象，这个对象中的属性与 students 数组中元素的id一一对应。可使用如下代码完成快速检索：

function getStudentById(id){
  return stuObj["_"+id];
}

小结

每次“查看详细信息”都向服务端发起一次请求的方案是最差的，这一点应该不会有异议。

使用循环的方式进行查找的时间复杂度是 O(n)。

排序后进行二分查找时，假设使用了效率较高的排序算法（如快排，n*logn）。二分查找的时间复杂度是 logn 。则总体时间复杂度为：n*logn /n+logn = 2logn。但这种方式需要我们写复杂的排序和二分查找算法，有些得不尝失。

最后分析用Object 做索引的方案。每次向Object中增加属性的时间复杂度是 logn（n是Object中当前属性的数量），外面有个for循环时间复杂度为n。而检索时的时间复杂度是 logn（n是Object中当前属性的数量）。所以总体时间复杂度约为： n*logn/n +logn = 2logn。

虽然我们用 Object 做索引时，在时间复杂度上与“快速排序+二分查找”相同，但是这种方案容易实现。不用写复杂的快排和二分查找算法。

场景二：多级联动时查找下一级select元素应该需要显示的option。

简单点，举一个“省、市、县”三级联动的例子吧。

场景说明

后端一次性把全国所有的省、市、县信息及它们之间的所属关系都发送到前端了。后面的事全部交给前端处理。原始数据结构如下面的代码段所示：

// 省
var province=[{name:"北京",id:1},{name:"河北",id:2},{name:"河南",id:3},……];

// 市
var city=[{name:"郑州市",id:1,province_id:3},{name:"周口",id:2,province_id:3},……];

// 县
var county=[{name:"郸城县",id:1,city_id:2},{name:"西化县",id:2,city_id:2},……];

当我选中一个省的时候，在第二级的select上元素需要显示该省下面所有的市以供选择。当我选择一个市时，在第三级的select元素上需要显示对应市下面所有的县以供选择。

一般做法

循环方式，当选中一个省时的示例代码如下：

function getCitysByProvinceId(province_id){
  var results = [];
  for(var i=0;i<city.length;i++){
    if(province_id == city[i].province_id){
      results.push(city[i]);
    }
  }
  return results;
}

当选中一个市时，获取市下面所有县的代码与上面的代码类似。

用 Object 做索引

首先需要创建索引，代码如下：

var cityByProvinceId = {};
for(var i=0;i<city.length;i++){
  if(!cityByProvinceId["_"+city[i].province_id]){
    cityByProvinceId["_"+city[i].province_id] = [];
  }
  cityByProvinceId["_"+city[i].province_id].push(city[i]);
}

索引完成后，检索就容易了，并且效率会非常之高：

function getCityByProvinceId(province_id){
  return cityByProvinceId["_"+province_id];
}

选择市时对县的处理方式，与选择省时对市的处理方式完全相同，在此不再赘述。

总结

在Web前端，需要用到快速检索的地方，用 Object 做索引的方式来完成是一个非常好的方案。首先，Object 中属性的检索效率是由JavaScript引擎优化过的，值得信赖。其次，没有复杂的算法和逻辑，代码清晰易读。即提高了效率又简化了代码，何乐而不为呢。