重学 JS | 从底层设计到应用读懂数组！-一一网

这是我参与更文挑战的第4天，活动详情查看：更文挑战

[重学JavaScript系列文章连载中…]

数组在日常开发中，无处不见，本篇文章整理了数组的日常用法、疑难点解析，以及数组常用算法类型。并通过编写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 {} // object
typeof [] // object
复制代码

为什么呢？这里就要看看，js变量在底层中，它的数据类型是怎么实现的了。

重点：JS底层处理变量时，会在变量机器码的低位1-3位存储其类型信息。

000 ： Object
001 ： Int
010 ： Double
100 ： String
110 ： 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.prototype
Array.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([])  // true
Array.isArray({})  // false
Array.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]
// NodeList
const imgs = document.getElementsByTagName('img')
const sources = Array.from(imgs,img=>img.src) // 返回img标签的src属性值
// arguments
function fun(){
  return Array.from(arguments)  // [1,2]
}
fun(1,2)
// object
Array.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([])  // true
Array.isArray({})  // false
Array.isArray(1)  // false
复制代码

3.3 Array.of()

创建新的具有可变数量参数的Array实例，而不考虑参数的数量或类型

Array.of(1，2)  // [1，2]
Array(2)   // 创建指定长度的空槽数组[empty，empty]  

// polyfill
Array.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]--> array
array.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对象，该对象包含数组中每个索引的值。1
let 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
  })
}

// 最大值同理
复制代码

通过sort()函数

let arr = [2,1,3,4]
let sortArr = arr.sort(function(a,b){
	return a-b
})
sortArr[0]  // 最小值
复制代码

借助es6的扩展运算符

let arr = [2,1,4,3]
Math.min(...arr)  // 最小值
Math.max(...arr)  // 最大值
复制代码

2. 数组去重的7种算法

数组去重的 7 种算法

3. 找出数组中出现最多元素的4种算法

找出数组中出现次数最多元素的 4 种算法(后续更)

8. 总结

至此我们总结了数组的知识点，值得收藏，工作面试必备！

文章版权归作者所有，未经允许请勿转载。

THE END

前端

【PC】超级监控软件无限试用版

铃声多多v8.7.74.0最新vip破解版海量手机铃声

CGIScript.net CSFAQ脚本的路径泄露漏洞 CGIScript.net CSFAQ脚本泄露路径漏洞

智能展示技术在淘宝封面图的应用

VDR 未明远程文件访问漏洞

VTK显示像素图

重学 JS | 从底层设计到应用读懂数组！

1. 数组的底层实现

1.1 快数组（FAST ELEMENTS）

1.2 慢数组（DICTIONARY ELEMENTS）

2. 数组类型判断

2.1 typeof为啥判断不了？

2.2 instanceof运算符

2.3 判断构造函数

2.4 toString()函数

2.5 Array.isArray()函数

3. 数组静态属性

3.1 Array.from()

3.2 Array.isArray()

3.3 Array.of()

4. 数组静态方法

4.1 concat()

4.2 entries()

4.3 fill()

4.4 findIndex()

4.5 flat()

4.6 includes()

4.7 indexOf()

4.8 数组其他用法

4.9 数组遍历7种方法

5. 数组常见算法

1. 求数组的最大值和最小值

2. 数组去重的7种算法

3. 找出数组中出现最多元素的4种算法

8. 总结

【PC】超级监控软件无限试用版

铃声多多v8.7.74.0最新vip破解版 海量手机铃声

CGIScript.net CSFAQ脚本的路径泄露漏洞 CGIScript.net CSFAQ脚本泄露路径漏洞

智能展示技术在淘宝封面图的应用

VDR 未明远程文件访问漏洞

VTK显示像素图

重学 JS | 从底层设计到应用读懂数组！

1. 数组的底层实现

1.1 快数组（FAST ELEMENTS）

1.2 慢数组（DICTIONARY ELEMENTS）

2. 数组类型判断

2.1 typeof为啥判断不了？

2.2 instanceof运算符

2.3 判断构造函数

2.4 toString()函数

2.5 Array.isArray()函数

3. 数组静态属性

3.1 Array.from()

3.2 Array.isArray()

3.3 Array.of()

4. 数组静态方法

4.1 concat()

4.2 entries()

4.3 fill()

4.4 findIndex()

4.5 flat()

4.6 includes()

4.7 indexOf()

4.8 数组其他用法

4.9 数组遍历7种方法

5. 数组常见算法

1. 求数组的最大值和最小值

2. 数组去重的7种算法

3. 找出数组中出现最多元素的4种算法

8. 总结

铃声多多v8.7.74.0最新vip破解版海量手机铃声