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

[vision1900]

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

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

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

[IamYourDad]

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

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

[dartabe]

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

话说 React hook 底层就是链表啊

[dartabe]

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

[muzuiget]

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

[zjffun]

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

```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

[jsun]

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

[dartabe]

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

[mxT52CRuqR6o5]

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

[seth19960929]

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

[charlie21]

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

[charlie21]

在哈希表中找到一个元素的复杂度是 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

[vision1900]

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

[vision1900]

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

[vision1900]

@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";
```

[no1xsyzy]

@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 当邱奇数了。

[seth19960929]

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

[dobelee]

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

[mxT52CRuqR6o5]

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

[no1xsyzy]

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

[bruce0]

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