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引擎优化过的，值得信赖。其次，没有复杂的算法和逻辑，代码清晰易读。即提高了效率又简化了代码，何乐而不为呢。
