数组在日常开发中，无处不见，本篇文章整理了数组的日常用法、疑难点解析，以及数组常用算法类型。并通过编写 polyfill，理解数组常用方法的内部实现。首先从了解数组的底层实现开始，看看 chrome V8 引擎是如何实现。
本文大纲如下：
数组的底层实现
数组的类型判断
数组静态属性
数组静态方法
数组常见算法
1. 数组的底层实现
数组是一个特殊的对象，底层实现是JSArray extends JSObject，内部也是通过key-value的形式存储数据，这也就可以理解 JS 的数组可以存放不同的数据结构。
JS 数组存在两种表现形式：快数组和慢数组
1.1 快数组（FAST ELEMENTS）
快数组是一种线性的存储结构。新创建的空数组，默认存储方式是快数组，快数组长度是可变的，可以根据元素的增加和删除来动态调整存储空间的大小，内部是通过扩容和收缩机制实现。
扩容
扩容算法如下，扩容后会将数组拷贝到新的内存空间。
new_capacity = old_capicity/2+old_capicity + 16
复制代码
收缩
收缩条件：(容量) >= length*2 + 16，则收缩容量调整，否则用holes对象填充空位置。
收缩算法：
elements_to_trim = length+1 == old_length?(capacity-length)/ 2 : capacity-length
复制代码
hodes：空洞，对象指的是数组中分配了空间，但是没有存储元素的位置。
转为慢数组
新容量 >= 3*扩容后的容量*2
加入的 index-当前 capacity >= 1024，即存在超过 1024 个空洞
快数组就是以空间换时间的方式，申请了大块连续内存，提高效率。
1.2 慢数组（DICTIONARY ELEMENTS）
慢数组是一种字典的内存形式。不用开辟大块连续的存储空间，节省了内存，但是由于需要维护这样一个 HashTable，其效率会比快数组低。
转为快数组：
处于哈希表实现的数组，在每次空间增长时， V8 的启发式算法会检查其空间占用量。当慢数组的元素可存放在快数组中且长度在 smi 之间且仅节省了 50%的空间，则会转变为快数组
慢数组以时间换空间，不必申请连续的空间，节省了内存，但需要付出效率变差的代价。
2. 数组类型判断
2.1 typeof 为啥判断不了？
谈到数据类型判断，通常会想到typeof，但实际上这运算符只在判断基本数据类型有用，对于引用类型乏力。
typeof {} // objecttypeof [] // object
复制代码
为什么呢？这里就要看看，js 变量在底层中，它的数据类型是怎么实现的了。
重点：JS 底层处理变量时，会在变量机器码的低位 1-3 位存储其类型信息。
000 ： Object001 ： Int010 ： Double100 ： String110 ： Boolean
特殊点：null：代表空指针，大多数平台中值为0x00,因此null的类型标签就成了0，所以typeof null返回'object'undefined：用-2^30 整数来表示
复制代码
2. 2 instanceof 运算符
原理：通过查找原型链来检测变量是否为某个类型的实例。
[] instanceof Array // true[] instanceof Object // true{} instanceof Array // false
// []的原型链如下,因此为Array / Object 的实例[].__proto__ = Array.prototypeArray.prototype.__proto__ === Object.prototype
复制代码
可以通过优先判断类型是否为 Array 的实例的来判断类型，封装如下：
function isArray(obj){ if(obj instanceof Array){ return true }else if(obj instanceof Object){ return false }else{ return '参数非对象类型' }}
复制代码
2.3 判断构造函数
判断变量是否为数组还是对象，另一角度讲，即是判断变量的构造函数是 Array 类型还是 Object 类型。因为对象的实例都是通过构造函数生成的。
为什么变量会有 constructor 属性呢？
每个变量都会有个__proto__属性，表示的是隐式原型。一个对象的隐式原型指向的是构造该对象的构造函数的原型。
[].constructor === Array // true[].constructor === Object // false[].__proto__ === Array.prototype // true[].__proto__ === [].constructor.prototype // true
[].__proto__.constructor == Array // true
复制代码
通过如上对原型链的分析，封装判断方法：
function isArray(obj){ // 获取构造函数 let constructor = obj.__proto__.constructor || obj.constructor if(constructor === Array){ return true }else if(constructor === Object){ return false }else{ return '参数非对象类型' }}
复制代码
2.4 toString()函数
每种引用类型都会直接或间接继承 Object 的属性，因此都存在toString方法，并且不同数据类型toString返回的值不一样，因此可用于判断是数组还是对象。
Object.prototype.toString.call([]) // "[object Array]"Object.prototype.toString.call({}) // "[object Object]"Object.prototype.toString.call(1) // "[object Number]"
复制代码
封装方法如下：
function isArray(obj){ let type = Object.prototype.toString.call(obj) if(type === "[object Array]"){ return true }else if(type === "[object Object]"){ return false }else{ return '参数非对象类型' }}
复制代码
2.5 Array.isArray()函数
只能判断是否为数组，不能判断是否为对象。
Array.isArray([]) // trueArray.isArray({}) // falseArray.isArray(0) // false
复制代码
3. 数组静态属性
3.1 Array.from()
从类似数组或可迭代的对象中创建一个新的，浅表复制的 Array 实例。
什么是类数组对象？
一个对象并不是由 Array 构造函数所创建的,它依然呈现出数组的行为。在 ECMAScript 5 标准中，字符串 string 就是一个只读的类数组对象。
/* * 语法： * mapFn: 映射函数可调用数组的每个元素 */ Array.from(arrayLike [, mapFn [, thisArg]])
// ============ 用法 ==================== // 字符串Array.from('ab') // ['a','b']// Set Array.from(new Set([1,2,1,2])) // [1,2]// Map const map = new Map([[1, 2]])Array.from(map) // [[1,3]]Array.from(map.values()) // [2]Array.from(map.keys()) // [1]// NodeListconst imgs = document.getElementsByTagName('img')const sources = Array.from(imgs,img=>img.src) // 返回img标签的src属性值// argumentsfunction fun(){ return Array.from(arguments) // [1,2]}fun(1,2)// objectArray.from({a:1,b:2}) // []Array.from({a:1,length:2}) // [undefined,undefined]Array.from({0:1,1:2,length:2}) // [1,2]
// 映射函数Array.from([1,2,3],i=>i*2) // [2,4,6]
复制代码
3.2 Array.isArray()
判断参数是否为数组，无法判断是否是对象。
Array.isArray([]) // trueArray.isArray({}) // falseArray.isArray(1) // false
复制代码
3.3 Array.of()
创建新的具有可变数量参数的 Array 实例，而不考虑参数的数量或类型
Array.of(1，2) // [1，2]Array(2) // 创建指定长度的空槽数组[empty，empty]
// polyfillArray.of = function(){ return Array.prototype.slice.call(arguments);}
复制代码
4. 数组静态方法
4.1 concat()
合并两个或多个数组。此方法不更改现有数组，而是返回一个新数组。
[].concat(1,[2,3],[4]) // [1,2,3,4]
复制代码
4.2 entries()
返回一个新的 Array Iterator 对象，该对象包含数组中每个索引的键/值对。
const arr = [1,2,3]const itea = arr.entries() // 迭代器const [index,value] = itea.next().valuem
// 循环const arr = [1,2,3]for(const [index,value] of arr.entries()){ console.log(index,value)}
复制代码
4.3 fill()
将数组中的所有元素更改为静态值，从开始索引（默认为 0）到结束索引（默认为 array.length）。它返回修改后的数组。
let array = [1,2,3,4]array.fill(0,2,4) // [1,2,0,0]--> arrayarray.fill(5,1) // [1,5,5,5]
复制代码
4.4 findIndex()
返回满足条件的第一个元素的索引，否则返回-1，表示没有满足的元素。
const index = [1,2,3,4,5].findIndex(function(ele,idx,array){ return ele>3}) // 3
复制代码
4.5 flat()
创建一个新数组，其中所有子数组元素都以递归方式连接到该数组中，直到达到指定的深度。
const arr2 = [0, 1, 2, [[[3, 4]]]];arr2.flat(2) // 2级深度： [0, 1, 2, [3, 4]]
复制代码
4.6 includes()
确定数组的条目中是否包含某个值，并根据需要返回 true 或 false。
[1,2,3].includes(2) // true[1,2,3].includes(4) // false
复制代码
4.7 indexOf()
返回可以在数组中找到给定元素的第一个索引；如果不存在，则返回-1。
[1,2,3,4].indexOf(3) // 2[1,2,3,4].indexOf(3,2) // 从索引2，开始往后搜索3 --> 2(从头往后的索引值)[1,2,3,4].indexOf(3,3) // 从索引3，开始往后搜索3 --> -1
复制代码
4.8 数组其他用法
// 通过连接数组（或类似数组的对象）中的所有元素来创建并返回新字符串。[1,2,3].join() // 1,2,3
// 返回一个新的Array Iterator对象，该对象包含数组中每个索引的键。let itea = [1,2,3].keys() // 迭代器itea.next() // {value:0,done:false}
// 返回一个新的Array Iterator对象，该对象包含数组中每个索引的值。1let itea = [1,2,3].values()itea.next() // {value:1,done:false}
// 从数组中删除最后一个元素，然后返回该元素。此方法更改数组的长度[1,2,3].pop() // 3,返回未删除前的数组长度
// 将一个或多个元素添加到数组的末尾，并返回该数组的新长度。[1,2,3].push(4) // 4
// 数组翻转[1,2,3,4].reverse() // [4, 3, 2, 1]
// 从数组中删除第一个元素，然后返回删除的元素。此方法更改数组的长度[1,2,3,4].shift() // 1
// 将一个或多个元素添加到数组的开头，并返回数组的新长度。[1,2].unshift(3,4) // 4
// 从start到end切割数组，不包含end，返回新数组[1,2,3,4,5,6].slice(2,4) // [3,4]
// 数组排序let numbers = [4, 2, 5, 1, 3];numbers.sort(function(a, b) { return a - b;}); // [1,2,3,4,5]
// 通过删除或替换现有元素和/或在适当位置添加新元素来更改数组的内容let arr = [1,2]arr.splice(1,0,'a') // arr -> [1,'a',2]let arr1 = [1,2,3,4]let removed = arr1.splice(2,1) // removed:[3] arr1:[1,2,3]
复制代码
4.9 数组遍历 7 种方法
for
forEach
map
filter
some
every
reduce
find
以上数组遍历的 7 种方法详解，以及polyfill，详看文章：
数组遍历的 7 种方法及兼容性处理 (polyfill)
5. 数组常见算法
1. 求数组的最大值和最小值
通过给 prototype 属性扩展 min()和 max()函数。
Array.prototype.min = function(){ let min = this[0] for(let i=0,l = this.length;i<l;i++){ if(this[i]<min){ min = this[i] } } return min}
Array.prototype.max = function(){ let max = this[0] for(let i=0,l = this.length;i<l;i++){ if(this[i]>max){ max = this[i] } } return max}
[2,4,1,4].min() // 1[2,4,1,4].max() // 4
复制代码
借助 Math 对象的 min()函数和 max()函数
// 静态方式Array.min = function(array){ return Math.min.apply(Math,array)}Array.max = function(array){ return Math.max.apply(Math,array)}
// prototype属性扩展Array.prototype.min = function(){ return Math.min.apply(null,this)}
Array.prototype.max = function(){ return Math.max.apply(null,this)}
复制代码
借助 reduce()函数
Array.prototype.min = function(){ return this.reduce(function(preVal,curVal){ return preVal>curVal?curVal:preVal })}
// 最大值同理
复制代码
4. 通过 sort()函数
let arr = [2,1,3,4]let sortArr = arr.sort(function(a,b){ return a-b})sortArr[0] // 最小值
复制代码
5. 借助 es6 的扩展运算符
let arr = [2,1,4,3]Math.min(...arr) // 最小值Math.max(...arr) // 最大值
复制代码
2. 数组去重的 7 种算法
数组去重的 7 种算法
3. 找出数组中出现最多元素的 4 种算法
找出数组中出现次数最多元素的 4 种算法
8. 总结
至此我们总结了数组的知识点，值得收藏，工作面试必备！
评论