直觀感受
在nodejs中很少去關(guān)注每一種數(shù)據(jù)結(jié)構(gòu)的性能和特點(diǎn)骗随，今天正好遇到了這個(gè)問(wèn)題就簡(jiǎn)單對(duì)比了一下，順便做一個(gè)筆記艺挪，不一定正確不翩，nodejs代碼下得賊慢，還沒(méi)下下來(lái)麻裳。
下面是結(jié)構(gòu)體(對(duì)象)和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);
上述代碼的作用就是每一秒中向一個(gè)結(jié)構(gòu)體里或者一個(gè)對(duì)象里插入一個(gè)元素口蝠。看起來(lái)并沒(méi)有任何區(qū)別津坑，實(shí)際上在99%的場(chǎng)景下二者完全可以互相替換妙蔗。
但是從二者的實(shí)現(xiàn)上來(lái)看，他們還是有一定的差別的疆瑰，下面來(lái)分析二者的數(shù)據(jù)結(jié)構(gòu)眉反。
數(shù)據(jù)結(jié)構(gòu)
結(jié)構(gòu)體
在c語(yǔ)言中昙啄，struct和數(shù)組的存儲(chǔ)方式并沒(méi)有本質(zhì)的區(qū)別，二者都是都是順序存儲(chǔ)（不考慮對(duì)其之類(lèi)的 特殊處理）寸五。這也就 意味著struct的讀取時(shí)間復(fù)雜度是O(n)梳凛，而不是想像中的O(1)，當(dāng)然不排除nodejs等語(yǔ)言在 實(shí)現(xiàn)的時(shí)候做了調(diào)整梳杏∪途埽可以猜想如果struct的成員變量很多的時(shí)候性能會(huì)變差，不過(guò)一般情況下結(jié)構(gòu)體的成員并不會(huì)很多十性，所以一般不用擔(dān)心這個(gè)問(wèn)題叛溢。
Map
基本所有的算法書(shū)中都會(huì)把Map(Set)的讀取復(fù)雜度定為1，但是這是理想的情況烁试。Map的思想很簡(jiǎn)單，就是做一個(gè)映射拢肆，一般會(huì)是一個(gè)hash函數(shù)减响，輸入一個(gè)key，可以輸出一個(gè)地址或者偏移量郭怪，然后把數(shù)據(jù)放到對(duì)應(yīng)位置即可支示。在讀取的時(shí)候只需要再通過(guò)映射找到偏移量就能直接取到該值了。
但是鄙才，在實(shí)際實(shí)現(xiàn)中一方面不可能找到完全不碰撞而有能保證結(jié)果在一定區(qū)間的函數(shù)（畢竟存儲(chǔ)空間是有限的）颂鸿，所以實(shí)際上的實(shí)現(xiàn)方案并不一致。
通常的做法是利用鏈表來(lái)避免沖突同時(shí)保證所需空間相對(duì)能夠接受攒庵，具體做法這里不再說(shuō)明嘴纺，這種做法的 讀寫(xiě)時(shí)間復(fù)雜度介于O(1)和O(n)之間，主要是由鏈表長(zhǎng)度和數(shù)據(jù)的分布有關(guān)浓冒。另一種做法是直接采用樹(shù)結(jié)構(gòu)栽渴，這種做法的讀寫(xiě)復(fù)雜度是O(lgn)。
二者對(duì)比
在nodejs中大部分情況二者完全可以互相替換稳懒，不過(guò)對(duì)于數(shù)據(jù)較多的情況下闲擦，比如打點(diǎn)信息或者用戶(hù)信息，最好還是使用Map场梆。當(dāng)然墅冷，這里的分析只是簡(jiǎn)單針對(duì)性能和易用性上來(lái)說(shuō)明的。
下面是一個(gè)簡(jiǎn)單的測(cè)試：
結(jié)構(gòu)體
//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);
測(cè)試結(jié)果
node test-struct.js && node test-map.js
//=>
time cost: 735
time cost: 365
