直观感受
在nodejs中很少去关注每一种数据结构的性能和特点，今天正好遇到了这个问题就简单对比了一下，顺便做一个笔记，不一定正确，nodejs代码下得贼慢，还没下下来。
下面是结构体(对象)和map在nodejs中的例子
let some_state_map = new Map();
setInterval(()=>{
some_state_map.set(`element${Math.ceil(Math.random()*1000)}`,Math.random());
},1000);
let some_state = {};
setInterval(()=>{setInterval(()=> {
some_state_map[`element${Math.ceil(Math.random() * 1000)}`] = Math.random();
},1000);
上述代码的作用就是每一秒中向一个结构体里或者一个对象里插入一个元素。看起来并没有任何区别，实际上在99%的场景下二者完全可以互相替换。
但是从二者的实现上来看，他们还是有一定的差别的，下面来分析二者的数据结构。
数据结构
结构体
在c语言中，struct和数组的存储方式并没有本质的区别，二者都是都是顺序存储（不考虑对其之类的 特殊处理）。这也就 意味着struct的读取时间复杂度是O(n)，而不是想像中的O(1)，当然不排除nodejs等语言在 实现的时候做了调整。可以猜想如果struct的成员变量很多的时候性能会变差，不过一般情况下结构体的成员并不会很多，所以一般不用担心这个问题。
Map
基本所有的算法书中都会把Map(Set)的读取复杂度定为1，但是这是理想的情况。Map的思想很简单，就是做一个映射，一般会是一个hash函数，输入一个key，可以输出一个地址或者偏移量，然后把数据放到对应位置即可。在读取的时候只需要再通过映射找到偏移量就能直接取到该值了。
但是，在实际实现中一方面不可能找到完全不碰撞而有能保证结果在一定区间的函数（毕竟存储空间是有限的），所以实际上的实现方案并不一致。
通常的做法是利用链表来避免冲突同时保证所需空间相对能够接受，具体做法这里不再说明，这种做法的 读写时间复杂度介于O(1)和O(n)之间，主要是由链表长度和数据的分布有关。另一种做法是直接采用树结构，这种做法的读写复杂度是O(lgn)。
二者对比
在nodejs中大部分情况二者完全可以互相替换，不过对于数据较多的情况下，比如打点信息或者用户信息，最好还是使用Map。当然，这里的分析只是简单针对性能和易用性上来说明的。
下面是一个简单的测试：
结构体
//test-struct.js
const num = 1000000;
let a = {};
for(let i = 0;i<num;i++){
a[`element${i}`]=i;
}
let start_time = new Date();
for(let key in a){
a[key]+=1;
}
let end_time = new Date();
console.log("time cost:",end_time-start_time);
Map
//test-map.js
const num = 1000000;
let a = new Map();
for(let i = 0;i<num;i++){
a.set(`element${i}`,i);
}
let start_time = new Date();
for(let key of a.keys()){
a.set(key,a.get(key)+1);
}
let end_time = new Date();
console.log("time cost:",end_time-start_time);
测试结果
node test-struct.js && node test-map.js
//=>
time cost: 735
time cost: 365
网友评论