虽然测速的例子很多了,但是有时候会很困惑,总之实践出真知,自己试试才能说服自己

直接上测试结果

测试代码在下面

这里设了个常量ROOP_TIME作为循环次数
不同样本跑三次取平均值后三位小数(再多也没意义),没有测删除,因为跟插入是差不多的不重复测了

PS:这里的access指的是通过下标直接访问,search通过Array.prototype.indexOf来查询值
PSS:这里的access做了一次完整的循环,以便观察

当ROOP_TIME为1*106

数组类型buildaccesssearchinsert
fastElement26.615ms2.799ms0.738ms129.776ms
dictionaryElement129.426ms2.904ms0.734ms28.326ms

当ROOP_TIME为1*107

数组类型buildaccesssearchinsert
fastElement261.872ms8.843ms7.740ms143.573ms
dictionaryElement1871.067ms8.881ms7.213ms95.931ms

当ROOP_TIME为5*107

这里数据可能有较大误差,有空再测几组

数组类型buildaccesssearchinsert
fastElement874.869ms33.9ms41.097ms140.460ms
dictionaryElement8591.274ms33.474ms52.502ms743.913ms

当ROOP_TIME为8*107

数组类型buildaccesssearchinsert
fastElement2050.828ms102.259ms113.977ms222.230ms
dictionaryElement14885.168ms52.909ms66.380ms437.229ms

当ROOP_TIME为1*108

微信截图_20200901150736.png

在这里慢数组的insert操作爆内存了,因为懒得改node内存,加上以上的测试已经很明显比较出快慢数组insert效率的差别,所以这里不再加上insert了
至于为什么会爆内存,下面会说到

数组类型buildaccesssearch
fastElement2185.586ms116.534ms148.188ms
dictionaryElement19518.572ms68.448ms76.459

在讨论快慢数组的效率之前需要了解V8底层实现数组的方式有两种

具体可以看这里V8 引擎中的 JavaScript 数组实现分析与性能优化

该文讲述了

  • 快数组Fast Element由C++的数组实现

至于为什么JavaScript的数组可以支持多类型,我只能做一个猜想(不要信不要信不要信):在C++数组中存放的都是指针,每个指针可以指向堆内存中不同类型的对象,至于指针类型这里不太懂C++,也没有太多的想法,只能猜想至此

  • 慢数组Dictionary Element由C++基于HashTable类实现

这里我请教了Java的同事,他说HashTable是多线程安全的,HashMap简单来说是不加锁的HashTable,按理说JavaScript单线程应该HashMap足矣,于是这里我再次给自己留一个疑问。。。(可能是原文错了,也可能V8出于某种考虑用了HashTable,亦或者C++的HashTable和Java的HashTable功能不一样)

C++的数组就不用说了,重点要说一下相比HashTable类更简单的HashMap是怎么实现的

先上个图

hashMap

上图紫色部分是数组,绿色部分是解决哈希冲突用的链表(也可能是红黑树,比如Java中链表长度大于8时会转换成红黑树)

然后摘抄一段深入理解哈希表

在讨论哈希表之前,先规范几个接下来会用到的概念。哈希表的本质是一个数组,数组中每一个元素称为一个箱子(bin),箱子中存放的是键值对。

哈希表的存储过程如下:

  1. 根据 key 计算出它的哈希值 h。
  2. 假设箱子的个数为 n,那么这个键值对应该放在第 (h % n) 个箱子中。
  3. 如果该箱子中已经有了键值对,就使用开放寻址法或者拉链法解决冲突。

在使用拉链法解决哈希冲突时,每个箱子其实是一个链表,属于同一个箱子的所有键值对都会排列在链表中。

哈希表还有一个重要的属性: 负载因子(load factor),它用来衡量哈希表的 空/满 程度,一定程度上也可以体现查询的效率,计算公式为:

> 负载因子 = 总键值对数 / 箱子个数

负载因子越大,意味着哈希表越满,越容易导致冲突,性能也就越低。因此,一般来说,当负载因子大于某个常数(可能是 1,或者 0.75 等)时,哈希表将自动扩容。

哈希表在自动扩容时,一般会创建两倍于原来个数的箱子,因此即使 key 的哈希值不变,对箱子个数取余的结果也会发生改变,因此所有键值对的存放位置都有可能发生改变,这个过程也称为重哈希(rehash)。

哈希表的扩容并不总是能够有效解决负载因子过大的问题。假设所有 key 的哈希值都一样,那么即使扩容以后他们的位置也不会变化。虽然负载因子会降低,但实际存储在每个箱子中的链表长度并不发生改变,因此也就不能提高哈希表的查询性能。

基于以上总结,细心的读者可能会发现哈希表的两个问题:

  1. 如果哈希表中本来箱子就比较多,扩容时需要重新哈希并移动数据,性能影响较大。
  2. 如果哈希函数设计不合理,哈希表在极端情况下会变成线性表,性能极低。

先解释下,为什么哈希表构建的时候比数组慢那么多

数组构建的时候只需直接从内存中申请一段连续的空间
而哈希表需要计算哈希、维持哈希表,为了后面的效率,牺牲了构建时的速度和空间(在同数据量数组没有空洞的情况下,维持哈希表所需的内存更多)

再来解释下,为什么一开始慢数组(哈希表)插入比快数组(数组)更快,而后面数据量大了反而变慢了吧

这题我会!
首先,哈希表初始化时会给定一个大小,所以在这个大小足以使用不需要扩容的前提下,插入是非常简单且方便的,而数组需要把插入下标后的所有元素往后挪一位,所以效率比哈希表低
到了后面数据量变大,哈希表需要扩容,就会发生重哈希(rehash)过程,这个过程性能影响比较大,在数据量变大的时候,哈希表不停地扩容扩容,累积下来效率相比数组低很多

再解释下为什么测试后面内存溢出的原因:

内存溢出发生在哈希表insert的时候,HashMap和HashTable底层原理以及常见面试题一文可以看到二倍扩容时,峰值内存应该是旧哈希表+新哈希表占用的内存,这或许就是造成内存溢出的原因
但是按理说构建的时候也会有扩容的情况,为什么不是在构建的时候内存溢出呢,这里我再次给自己留下一个疑问。。。

最后解释下为什么数据量越大,慢数组(哈希表)查询比快数组(数组)更快吧

Blablabla,好了这题我不会,容我去学习学习。。。
这里我的认知是数组通过下标访问是通过第一个元素和元素大小进行内存地址偏移量的计算,应该是比哈希表用key通过哈希函数一系列计算找到value的内存地址更快的,然而事实与我现有的知识相违背,又是一个疑问。。。
问了群上大佬,我的认知应该是没问题的,可能是V8的奇技淫巧干了什么事情,下次再用其他语言验证下我的认知。。。

结论

所以日常写JavaScript时(假设是V8引擎),应该避免快数组转换成慢数组
理由如下:

  1. JavaScript应用场景有前端,数据量不大且应该避免内存使用过多的情况
  2. 慢数组构建耗费的时间换取查询的时间是不值得的,更多是用于很稀疏的数组来节省内存(不需要开辟无用的连续内存)
  3. 如果是很稀疏的数组,或许一开始就使用JavaScript对象来存储(比如ObjectMap)更合适

如何避免快数组转换成慢数组,答案在这:V8 引擎中的 JavaScript 数组实现分析与性能优化

测试代码:
/**
 * FastElement
 */
let arr1 = [];
// BUILD
console.time("fastElement-build");
for (let i = 0; i < ROOP_TIME; i++) {
    arr1[i] = i;
}
console.timeEnd("fastElement-build");

// ACCESS
console.time("fastElement-access");
for (let i = 0; i < ROOP_TIME; i++) {
    temp = arr1[i];
}
console.timeEnd("fastElement-search");

// SEARCH
console.time("fastElement-search");
arr1.indexOf(ROOP_TIME / 2);
console.timeEnd("fastElement-search");

// INSERT
console.time("fastElement-insert");
for (let i = ROOP_TIME - 10000; i < ROOP_TIME; i++) {
    arr1.splice(i, 0, 1);
}
console.timeEnd("fastElement-insert");

/**
 * DictionaryElement
 */
let arr2 = [];
temp = 0;

// BUILD
console.time("dictionaryElement-build");
for (let i = ROOP_TIME; i >= 0; i--) {
    arr2[i] = i;
}
console.timeEnd("dictionaryElement-build");

// ACCESS
console.time("dictionaryElement-access");
for (let i = 0; i < ROOP_TIME; i++) {
    temp = arr2[i];
}
console.timeEnd("dictionaryElement-access");

// SEARCH
console.time("dictionaryElement-search");
arr2.indexOf(ROOP_TIME / 2);
console.timeEnd("dictionaryElement-search");

// INSERT
console.time("dictionaryElement-insert");
for (let i = ROOP_TIME - 10000; i < ROOP_TIME; i++) {
    arr2.splice(i, 0, 1);
}
console.timeEnd("dictionaryElement-insert");