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

[vision1900]

那么问题来了。用 JS 实现的链表还有意义吗？

既然 JS 中数组本质是哈希表，那么用链表和数组进行插入删除效率对比，感觉应该没优势啊。

各位在 Code Review 时碰上自己动手用 JS 写链表的会怎么 Comment?

[Cbdy]

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

[vision1900]

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

[gyf304]

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

[renmu123]

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

[Zhuzhuchenyan]

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

[no1xsyzy]

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

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

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

[laminux29]

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

[laminux29]

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

[dfzj]

确实没啥意思

[aaronlam]

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

[ArcherD]

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

[vision1900]

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

[vision1900]

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

[wangbenjun5]

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

[no1xsyzy]

@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 比较像。

[autogen]

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

[myqoo]

TypedArray 表示不服

[meteor957]

假的数组

[xcstream]

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

[namelosw]

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

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