JS 中没有传统意义上的数组，数组其实是哈希表

链表

哈希表

中数组

comment

45 条回复 • 2020-12-12 15:11:25 +08:00

1

Cbdy

2020-12-05 19:39:05 +08:00 via Android

先问是不是吧，“数组是哈希表”这句话是值得商榷的

2

vision1900

OP

2020-12-05 19:45:49 +08:00

@Cbdy 你是说不同引擎可能以不同方式实现数组吗

3

gyf304

2020-12-05 19:48:22 +08:00

大部分 JS 引擎包括 V8，甚至轻量化的 Duktape 都是有对 array 的支持 /优化的。

4

renmu123

2020-12-05 20:04:54 +08:00 via Android

我好像没听过这个说法，在哈希表中找到一个元素的复杂度是 O1，建议试一下数组到底是不是哈希

5

Zhuzhuchenyan

2020-12-05 20:08:22 +08:00

先不提数组的实现，
在评审中遇到手写基本数据结构的，不限于链表这种
一般我都会建议提交者详细阐述一下这里的需求以及为什么标准库自带数据结构在此处不能胜任，以及是否有良好的开源库的实现等
说实话以上足以排除 99%的情况，工作这么久了还真没遇到需要手写基本数据结构的。

6

no1xsyzy

2020-12-05 20:29:17 +08:00

@renmu123 数组难道是 O(n) ……？不过你提醒我了……

@vision1900 优化 #3 从实例上说明了不再多言。
即使实现上保持一致的哈希，你觉得哈希表实现的数组，插入删除难道是 O(1) 的吗？不需要改 key 的吗？
虽然我给不出证明，但我直觉上认为：在不具有先验知识的情况下，不可能同时做到 O(1) 增删和 O(1) 定位。
因为见过 O(log n) 增删 O(log n) 定位的超复杂结构，并且这玩意儿还几乎每台电脑上都有。

Code Review 的话，首先封装成单独 module，复用 + 关注点分离 + 单测；既然封装了，那不如找一个现成的。
有理有据地不让别人自己写，也不用想方设法委婉地表达怀疑对方写的代码基础库会不会有 bug 。

7

laminux29

2020-12-05 20:29:50 +08:00

现代软件工程项目，有些东西非常复杂，比如 OS 、浏览器、Office 类办公软件。

8

laminux29

2020-12-05 20:30:14 +08:00

browser 能给你提供一个运行代码的地方已经很不错了，免费的玩意，要啥自行车。

9

dfzj

2020-12-05 20:32:13 +08:00

确实没啥意思

10

aaronlam

2020-12-05 20:40:19 +08:00 via iPhone

1

默认的话引擎是会有优化的，但是如果你修改了数组，那引擎就只能转为哈希了。

11

ArcherD

2020-12-05 20:43:24 +08:00

1 数组可以组成哈希表的组成部分，不是哈希表的本质
2 链表是一种 immuable 的数据结构，多个链表可以共享空间，用的地方不一样啊。
array 和 list
Hash table 和 map
本来就是用在不同的地方的数据结构，并不是只有一种就够了。

12

vision1900

OP

2020-12-05 20:47:43 +08:00

@ArcherD JS 里的数组和其他语言不一样，它只是叫数组而已；如果 10 楼老哥说的没错，一旦开始扩展数组，大多数引擎底层会把它转为哈希表

13

vision1900

OP

2020-12-05 20:50:05 +08:00

@no1xsyzy 即使遇到碰撞需要处理，也不会影响大 O 吧。除非 Load factor 太高和哈希算法太烂，要不这应该是极少情况，可以忽略不计

14

wangbenjun5

2020-12-05 21:01:24 +08:00

小兄弟，如果你多学几门语言你会发现，PHP 里面的所谓“数组”也是哈希表，实际上，很多语言里面的数组都不是很准确，真正的数组一般是指 C 里面的数组。

15

no1xsyzy

2020-12-05 21:01:34 +08:00

1

@vision1900 不是说碰撞
你想象一下这个 array [1, 2, 3, 5, 6, 7]
写成 hash {0:1, 1:2, 2:3, 3:5,4:6, 5:7}
然后第四位添加一个 4 得 [1,2,3,4,5,6,7]
写成 hash {0:1, 1:2, 2:3, 3:4, 4:5, 5:6, 6:7}
5 、6 、7 三个元素的 key 都变了，你得改吧——
所以就算完全不优化就是个哈希，也是跟 array 比较像而不是跟 list 比较像。

16

autogen

2020-12-05 21:56:33 +08:00

哈希表可以 for (i=0 to 100) cons.log(arr[i]) 吗？

17

myqoo

2020-12-05 22:07:03 +08:00

1

TypedArray 表示不服

18

meteor957

2020-12-05 23:43:29 +08:00

假的数组

19

xcstream

2020-12-05 23:50:33 +08:00

2

如果一个东西看起来像鸭子，走起来像鸭子，叫起来像鸭子。那他就是鸭子。

20

namelosw

2020-12-06 01:02:42 +08:00

1

感觉你这个问题不成立啊…… 其他语言也有 hash table, 难道也不用链表了?

很多语言 hash 分区下面还是要用链表的. 链表存的是地址, 保证一步到位. 我记得 React 里面有很多链表.

21

IamYourDad

2020-12-06 03:51:31 +08:00 via Android

楼主不对了，高中课本就有 js 入门教程了，js 的数组默认就是数组 arr[0]=fuc arr[1]=k

直到，你开启上帝模式，arr["key"]=value
arr 就变成了哈希表，而且所有数组访问失效，不能通过 arr[1]拿到 k

22

dartabe

2020-12-06 05:21:06 +08:00

1

插入数据的话 hash 你要改 key 吧像 15 楼说的

话说 React hook 底层就是链表啊

23

dartabe

2020-12-06 05:24:11 +08:00

Map 底层貌似就是链表 LRU cache 这道 leetcode 可以不用 Map 做一下

24

muzuiget

2020-12-06 08:59:28 +08:00

模糊概念，“数组”就一抽象概念，只要你看起来“元素一个接着一个”就行了，数字类型都能当数组用(位操作)。硬要想象成具体的“操作系统连续内存”就是想得太多了。

25

zjffun

2020-12-06 10:09:34 +08:00

1

可以试下这个例子，和链表完全不一样。

```javascript
var array = [];
for(var i = 0;i< 1000000;i++){
array.push(i)
}
var start = new Date().getTime()
for(var i = 0; i< 100000; i++){
array.splice(1000000,0,1);
}
var end = new Date().getTime();
console.log(`Add 10^5 numbers to the head of array: ${end - start} ms`);

var array = [];
for(var i = 0;i< 1000000;i++){
array.push(i)
}
var start = new Date().getTime()
for(var i = 0; i< 100000; i++){
array.push(1000000,0,1);
}
var end = new Date().getTime();
console.log(`Add 10^5 numbers to the rear of array: ${end - start} ms`);

// Add 10^5 numbers to the head of array: 4555 ms
// Add 10^5 numbers to the rear of array: 56 ms
```

另外，之前用 JS 做题测试 Set 和 Map 的时间查询复杂度是 O(n) 也是挺难受的。
https://tc39.es/ecma262/#sec-set.prototype.has

26

jsun

2020-12-06 10:57:44 +08:00

哈希表不是本质，本质是内存分配和寻址。寻址肯定是不一样的，内存分配上如果数组的 keys 不是增量数字的话可能一样

27

dartabe

2020-12-06 11:18:53 +08:00

@zjffun O(1)吧是 Hash 链表啊

28

mxT52CRuqR6o5

2020-12-06 11:23:37 +08:00

@zjffun 不对吧，我刚用 chrome 简单试了下，set 的去重时间复杂度是 o(n)，array 去重时间复杂度是 o(n^2)
如果是在不原生支持 set 、map 的旧版浏览器，polyfill 出来的 set 和 map 是用 array 模拟的，那 Set 和 Map 的时间查询复杂度确实是 o(n)

29

seth19960929

2020-12-06 11:27:47 +08:00

@no1xsyzy 好像就没见过有哪几种语言提供数组插入这个操作吧?
我只听说过链表插入.

30

charlie21

2020-12-06 11:50:42 +08:00 via iPhone

那么哪些语言的数组是真的链表呢？ python 是吗

31

charlie21

2020-12-06 12:20:37 +08:00 via iPhone

在哈希表中找到一个元素的复杂度是 O(1) ，比如 C# Dictionary<TKey,TValue> 、Java HashMap
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2
https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

32

vision1900

OP

2020-12-06 12:42:55 +08:00

@no1xsyzy 感谢大佬。数组和普通对象不一样，插入会改变右边元素的 key 值。如果哈希表是类 C 数组实现的话，需要对右边的所有元素做 shift 操作。

33

vision1900

OP

2020-12-06 12:53:51 +08:00

@autogen 有趣的问题，知道哈希算法就可以吧。假设哈希算法是简单的二次方，比如 0 => 0, 1 => 1, 2 => 4 ... 100 => 10,000 。那么实际循环的时候，就取第 1，2，5 ... 1,0001 个元素就好了。当然这是简化的情况，实际中可能记录了 key => index 这个表，当然我是猜的，不过理论可行哈。。。

34

vision1900

OP

2020-12-06 13:01:42 +08:00

@IamYourDad "直到，你开启上帝模式，arr["key"]=value
arr 就变成了哈希表，而且所有数组访问失效，不能通过 arr[1]拿到 k". 这个我试了，不对啊。

```javascript
const friends = ["Mike", "Peter", "Jones", "Alex"];
friends["count"] = 4;
friends instanceof Array; // true
friends[0]; // Mike
friends["0"] = "Kate";
friends[0]; // "Kate";
```

35

no1xsyzy

2020-12-06 14:09:04 +08:00

@IamYourDad “是数组” 是显性性状（借用下术语），“不是数组”是隐性性状。只要有 length 就可以当 array 用。
而且 arr[1] 和 arr["1"] 是等价的，原因是弱类型。
@vision1900 #34 instanceof 原型链是另外的设施

@seth19960929 首先你要能够动态扩充数组，这个就杀掉一大批（手动分配内存的），但需求在，也会有相关设施的。JS 姑且是有 splice 可以做这事。

@charlie21 Python 的 [1,2,3] 形式就是 list，数组是另外的 import array （或者 import numpy，如果你高兴的话）。
这两个似乎一直分辨得很明确，但具体语言以 list 为主还是以 array 为主是设计思路的问题。

实际上放弃纠结细节，看看 #26 说的也挺清楚。
实际上数组和哈希表就是寻址算法分别为 x=>head+x 和 x=>head+hash(x) 罢了。
然而链表的寻址是 x=>x(p=>p.next)(head) 注意此处我顺手把 x 当邱奇数了。

36

seth19960929

2020-12-06 14:56:06 +08:00

@no1xsyzy JS 动态扩容和 splice 有什么相关吗? JS 的数组本来就是动态扩容的.

37

dobelee

2020-12-06 15:05:42 +08:00 via iPhone

狭义的数组必须在内存地址连续，一般的数组都说广义的，即一个业务相关对象的线性存储。

38

mxT52CRuqR6o5

2020-12-06 15:05:56 +08:00

@seth19960929
像 c++的 array 是固定程度不可变的，你要想长度可变的需要用 vector
我们在这和楼主纠结概念命名其实没啥意思

39

no1xsyzy

2020-12-06 18:42:49 +08:00

@seth19960929 没有相关。JS 自带 splice 的插入设施。

40

bruce0

2020-12-07 09:57:07 +08:00

php 的数组好像也是基于 hash table 实现的

41

libook

2020-12-07 13:28:29 +08:00

1

用 JS 写链表，就好比是在手枪上装了个高倍狙击镜，并不能达到预期的效果，所以如果团队内有人这样写，我会让他要么改回原生数据结构，要么拿 Rust/C++重写。

JS 跑在引擎上，引擎给 JS 语言提供给的内存空间是抽象的，真实反映在操作系统内存管理上可能是连续的也可能是不连续的。像 JS 的 Array 底层引擎实现可能是多种模式动态切换的。
操作系统给引擎提供的内存也是抽象的，真实反映在物理内存上可能是连续的也可能是不连续的。

在如此高级抽象的语言上考虑算法性能是不可能有定论的，因为可能每次运行的时候情况都会不一样，控制器芯片、操作系统、引擎也都会对一些常见情况做优化，这个是在语言层面无法把控的。要是真的在项目上要考虑性能问题，可以做宏观的压力测试，有问题要解决大多也都是在系统架构上优化，语法算法上的优化余地不多。

用 JS 不看性能，看性能不用 JS 。WebAssembly 以及 Node.js 的 N-API 主要就是用来解决这个问题的。

42

libook

2020-12-07 13:29:52 +08:00

JS 不只有 Array 一种数组，还有很多，比如 ArrayBuffer，虽然不一定满足你的需求，但是很多特殊场景都可以覆盖到了。

43

wxsm

2020-12-07 13:31:39 +08:00

> The JavaScript Array class is a global object that is used in the construction of arrays; which are high-level, list-like objects.

MDN 是这么说的，可以这么认为吧。

44

wxsm

2020-12-07 13:35:39 +08:00

不过，怎么说呢，纠结 JS 的 Array 到底是链表还是哈希表，有什么意义吗？ JS 本身是高级语言，具体是怎么实现的完全看 runtime 怎么写，语言也没有提供指针和寻址的能力。换句话说，标准提供了 Array，你用就行了，效率什么的，引擎帮你考虑了，别管那么多。

45

zjffun

2020-12-12 15:11:25 +08:00

@mxT52CRuqR6o5 @dartabe 刚才又去试了下 Set 确实很快，可能当初别的原因导致很慢一看 ES 规范写了遍历就就误解了