第 75 题：数组里面有 10 万个数据，取第一个元素和第 10 万个元素的时间相差多少？

Question

问题

数组里面有10万个数据，取第一个元素和第10万个元素的时间相差多少？

答案

JavaScript 没有真正意义上的数组，所有的数组其实是对象，其 索引 看起来是数字，其实会被转换成字符串，作为属性名（对象的 key）来使用。所以无论是取第 1 个还是取第 10 万个元素，都是用 key 精确查找哈希表的过程，其消耗时间大致相同。

为了更加清楚一点还是使用js来一段代码比较清晰

var arr = new Array(100000).fill(null)
console.time('first')
arr[0]
console.timeEnd('first')
console.time('end')
arr[99999]
console.timeEnd('end')
/*
first: 0.00390625ms
end: 0.0029296875ms
*/

上面测试代码打印结果时间基本可以忽略不计

Answer 1

数组里面有10万个数据，取第一个元素和第10万个元素的时间相差多少？

• JS里数组的存储方式是哈希表，可以通过键名key直接获取到对应的值，时间复杂度就是O（1）
• 所以取第一个和第十万个，看起来是数字，但是会被转换成字符串作为属性名，通过key去查找哈希表取值，所以时间是差不多的

Answer 2

06-js中的数组

前言

数组、链表、栈、队列都是线性表，它表示的结构都是一段线性的结构，与之对应的就是非线性表，例如树、图、堆等，它表示的结构都非线性。

思考

• JavaScript 中，数组为什么可以保存不同类型？
• JavaScript 中，数组是如何存储的喃？

什么 是数组

数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储.

以上是js数组在内存中大致位置 ，或者

Chrome 浏览器JS引擎 V8中，数组有两种存储模式，一种是类似C语言中的线性结构存储（索引值连续，且都是正整数的情况下），一种是采用Hash结构存储（索引值为负数，数组稀疏，间隔比较大）

为什么这么说，因为在js 中 数组的存储

// The JSArray describes JavaScript Arrays
//  Such an array can be in one of two modes:
//    - fast, backing storage is a FixedArray and length <= elements.length();
// 存储结构是 FixedArray ，并且数组长度 <= elements.length() ，push 或 pop 时可能会伴随着动态扩容或减容

//       Please note: push and pop can be used to grow and shrink the array.
//    - slow, backing storage is a HashTable with numbers as keys
// 存储结构是 HashTable（哈希表），并且数组下标作为 key
class JSArray: public JSObject {
 public:
  // [length]: The length property.
  DECL_ACCESSORS(length, Object)
    
  // ...
   
  // Number of element slots to pre-allocate for an empty array.
  static const int kPreallocatedArrayElements = 4;
};

意思是说，我们可以看到 JSArray 是继承自 JSObject 的，所以在 JavaScript 中，数组可以是一个特殊的对象，内部也是以 key-value 形式存储数据，所以 JavaScript 中的数组可以存放不同类型的值

数组的优点

• 随机访问：可以通过下标随机访问数组中的任意位置上的数据

根据下标随机访问的时间复杂度为 O(1)

数组特性

• 数组插入

我们已经知道数组是一段连续储存的内存，当我们要将新元素插入到数组k的位置时呢?这个时候需要将k索引处之后的所有元素往后挪一位,并将k索引的位置插入新元素.

• 删除

删除操作其实与插入很类似,同样我要删除数组之内的k索引位置的元素,我们就需要将其删除后,为了保持内存的连续性,需要将k之后的元素通通向前移动一位,这个情况的时间复杂度也是O(n).

• 查找

比如我们要查找一个数组中是否存在一个为2的元素,那么计算机需要如何操作呢?

如果是人的话,在少量数据的情况下我们自然可以一眼找到是否有2的元素,而计算机不是,计算机需要从索引0开始往下匹配,直到匹配到2的元素为止

• 读取

我们已经强调过数组的特点是拥有相同的数据类型和一块连续的线性内存,那么正是基于以上的特点,数组的读取性能非常的卓越,时间复杂度为O(1),相比于链表、二叉树等数据结构,它的优势非常明显.

那么数组是如何做到这么低的时间复杂度呢?

假设我们的数组内存起始地址为start,而元素类型的长度为size,数组索引为i,那么我们很容易得到这个数组内存地址的寻址公式:

arr[i]_address = start + size * i

比如我们要读取arr[3]的值,那么只需要把3代入寻址公式,计算机就可以一步查询到对应的元素,因此数组读取的时间复杂度只有O(1).

总结

JavaScript 中， JSArray 继承自 JSObject ，或者说它就是一个特殊的对象，内部是以 key-value 形式存储数据，所以 JavaScript 中的数组可以存放不同类型的值。它有两种存储方式，快数组与慢数组，初始化空数组时，使用快数组，快数组使用连续的内存空间，当数组长度达到最大时，JSArray 会进行动态的扩容，以存储更多的元素，相对慢数组，性能要好得多。当数组中 hole 太多时，会转变成慢数组，即以哈希表的方式（ key-value 的形式）存储数据，以节省内存空间。

let res = new Array(100000).fill(10)
console.log(res)
var arr=new Array(100000).fill(100);
console.time('timer')
arr[0];
console.timeEnd('timer')

console.time('timer')
arr[100000-1];
console.timeEnd('timer')

参考

• 从Chrome V8源码看JavaScript数组
• 面试官: 100万个成员的数组取第一个和最后一个有性能差距吗?
  性能测试

https://jsperf.com/

Answer 3

1. 脚本里面的数组不是真正的数组，用的Hash算法，所以读取时间是一致的；
2. 即便真正的数组，读取时间也是一致的，连续内存直接读就好了；
3. 只有对单向链表才有差异；

Answer 4

我竟然去真的去做了实验:

var arr=new Array(100000).fill(100);
console.time('index_0')
arr[0];
console.timeEnd('index_0')

console.time('index_100000')
arr[100000-1];
console.timeEnd('index_100000')

index_0: 0.01708984375ms
index_100000: 0.006103515625ms

index_0: 0.01611328125ms
index_100000: 0.04296875ms

index_0: 0.011962890625ms
index_100000: 0.005859375ms

index_0: 0.012939453125ms
index_100000: 0.0078125ms

index_0: 0.01171875ms
index_100000: 0.0068359375ms

index_0: 0.011962890625ms
index_100000: 0.01904296875ms

index_0: 0.0126953125ms
index_100000: 0.008056640625ms

Answer 5

如果是传统数组的方式，应该是没区别的。
如果是哈希的方式，得看具体的哈希情况，所以是无法预估的，只能说时间复杂度相等。
不过10万条数据的数组在JS里面多半变成哈希了吧。

Answer 6

没多大区别，都是比较短的

var arr = new Array(100000).fill(null)
console.time('first')
arr[0]
console.timeEnd('first')
console.time('end')
arr[99999]
console.timeEnd('end')
first: 0.010009765625ms
end: 0.003662109375ms

Answer 7

用下标是瞬间，链表也瞬间

Answer 8

js 中数组元素的存储方式并不是连续的，而是哈希映射关系。哈希映射关系，可以通过键名 key，直接计算出值存储的位置，所以查找起来很快。推荐一下这篇文章：深究 JavaScript 数组

大佬推荐的这篇文章里，链式哈希查找元素要从第一个去追溯，那index的不同应该是有差距的呀，是我对这篇文章的什么地方理解错了么

Answer 9

js 中数组元素的存储方式并不是连续的，而是哈希映射关系。哈希映射关系，可以通过键名 key，直接计算出值存储的位置，所以查找起来很快。推荐一下这篇文章：深究 JavaScript 数组

Answer 10

正常来说取数组元素应该没差才对，都是按下标取的，也不是像链表那样要逐个查找。

Answer 11

Chrome 浏览器JS引擎 V8中，数组有两种存储模式，一种是类似C语言中的线性结构存储（索引值连续，且都是正整数的情况下），一种是采用Hash结构存储（索引值为负数，数组稀疏，间隔比较大）；

结论：以上说明对这个问题都没啥影响，同一个数组，在索引取值的时候，取第一个和最后一个效率没什么差别

Answer 12

JavaScript 没有真正意义上的数组，所有的数组其实是对象，其“索引”看起来是数字，其实会被转换成字符串，作为属性名（对象的 key）来使用。所以无论是取第 1 个还是取第 10 万个元素，都是用 key 精确查找哈希表的过程，其消耗时间大致相同。
@lvtraveler 请帮忙测试下稀松数组。

Answer 13

数组可以直接根据索引取的对应的元素，所以不管取哪个位置的元素的时间复杂度都是 O(1)

得出结论：消耗时间几乎一致，差异可以忽略不计