Relearn JS | to read an array from the underlying design!

This is the fourth day of my participation in Gwen Challenge

Relearn JavaScript in a series of articles…

Array in daily development, nowhere to see, this article sorted out the daily use of array, troubleshooting, and array common algorithm types. And by writing polyfill, you understand the internal implementation of common methods for arrays. Let’s start by looking at the underlying implementation of arrays and see how chrome V8 implements them.

The outline of this paper is as follows:

1. An underlying implementation of arrays

2. Array type determination

3. Array static properties

4. Array static methods

5. Common algorithms for arrays

1. The low-level implementation of arrays

An array is a special object. The underlying implementation is JSArray extends JSObject. Internally, it stores data as a key-value.

JS arrays come in two forms: fast and slow

1.1 FAST ELEMENTS

A fast array is a linear storage structure. The default storage mode of the newly created empty array is fast array. The length of the fast array is variable. The size of the storage space can be dynamically adjusted according to the increase and deletion of elements.

capacity

The expansion algorithm is as follows. After the expansion, the array is copied to the new memory space.

new_capacity = old_capicity/2+old_capicity + 16
Copy the code

shrinkage

Shrink condition :(capacity) >= length*2 + 16, then shrink capacity adjustment, otherwise use holes to fill the empty position.Copy the code

Shrinkage algorithm:

elements_to_trim = length+1 == old_length? (capacity-length)/ 2 : capacity-lengthCopy the code

Hodes: Void, object refers to the location in the array where space is allocated but no element is stored.

Convert to slow array

1. New capacity >= 3 Expanded capacity 2

2. Index – Current capacity >= 1024 indicates that there are more than 1024 holes

Fast array is in the way of space for time, the application of large contiguous memory, improve efficiency.

1.2 Slow Array (DICTIONARY ELEMENTS)

A slow array is an in-memory form of a dictionary. You save memory by not having to carve out large chunks of contiguous storage, but because you need to maintain such a HashTable, it’s less efficient than fast arrays.

Convert to fast array:

An array in a hash table implementation whose space usage is checked by V8’s heuristic algorithm each time the space grows. A slow array is converted to a fast array when the elements of the slow array can be stored in a fast array with a length between SMI and a space savings of only 50%

Slow array in time for space, do not need to apply for continuous space, saving memory, but need to pay the cost of efficiency.

2. Determine the array type

2.1 Why typeof cannot be determined?

When you think of data type judgment, you usually think of Typeof, but in reality this operator is only useful for determining basic data types, not reference types.

typeof {} // object
typeof [] // object
Copy the code

Why is that? Here’s how the js variable’s data type is implemented at the bottom.

Important: When JS processes variables, it stores their type information in the lowest 1-3 bits of the variable machine code.

000: Object 001: Int 010: Double 100: String 110: Boolean Represents a null pointer. The median value on most platforms is 0x00, so null's type label becomes 0, so typeof NULL returns 'object' undefined: a -2^30 integerCopy the code

2.2 The instanceof operator

Principle: Detects whether a variable is an instance of a type by looking up a prototype chain.

[] instanceof Array // true [] instanceof Object // true {} instanceof Array // false // [ [].__proto__ = Array.prototype Array.prototype.__proto__ === Object.prototypeCopy the code

You can determine the type of an Array instance by first determining whether the type is Array instance.

function isArray(obj){ if(obj instanceof Array){ return true }else if(obj instanceof Object){ return false }else{ return 'Parameter non-object type'}}Copy the code

2.3 Judge the constructor

To determine whether a variable is an Array or an Object, in other words, whether the variable’s constructor is of type Array or Object. This is because instances of objects are generated through constructors.

Why do variables have a constructor attribute?

Each variable has a __proto__ attribute, which represents the implicit stereotype. The implicit stereotype of an object refers to the stereotype of the constructor that constructed the object.

[].constructor === Array  // true
[].constructor === Object // false
[].__proto__ === Array.prototype  // true
[].__proto__ === [].constructor.prototype // true

[].__proto__.constructor == Array // true
Copy the code

Through the above analysis of the prototype chain, the encapsulation judgment method is as follows:

The function isArray (obj) {/ / get the constructor let constructor = obj. __proto__. Constructor | | obj. Constructor if (constructor = = = Constructor === Object){return false}else{return 'non-object type'}}Copy the code

2.4 the toString () function

Each reference type directly or indirectly inherits an Object property, so there is a toString method, and different data types toString returns different values, so it can be used to determine whether they are arrays or objects.

Object.prototype.toString.call([])  // "[object Array]"
Object.prototype.toString.call({})  // "[object Object]"
Object.prototype.toString.call(1)   // "[object Number]"
Copy the code

The encapsulation method is as follows:

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 'non-object type'}}Copy the code

2.5 Array. IsArray () function

You can only determine whether it is an array, not an object.

Array.isArray([])  // true
Array.isArray({})  // false
Array.isArray(0)   // false
Copy the code

3. Array static properties

3.1 Array. The from ()

Creates a new, shallow-copied Array instance from an array-like or iterable object.

What is an array-like object?

An object is not created by the Array constructor; it still behaves like an Array. In the ECMAScript 5 standard, the string is a read-only array-like object.

/* * syntax: * mapFn: Map function can call each element of Array */ array. from(arrayLike [, mapFn [, ThisArg]]) / / = = = = = = = = = = = = use = = = = = = = = = = = = = = = = = = = = / / string Array. The from (' ab ') / / / 'a', 'b'/Set/Array. The from (new ,2,1,2 Set ([1])) / / [1, 2] / / Map const Map = new Map ([[1, 2]]) Array. The from (map) / / [[1, 3]] Array. The from (map) values ()) / / [2] Array. The from (map. The keys ()) / / [1] / / NodeList const imgs = Document. GetElementsByTagName (' img) const sources = Array. The from (imgs, img = >. Img SRC) / / / / returns the img tags SRC attribute value of the arguments Function fun(){return array. from(arguments) // [1,2]} fun(1,2) // object array. from({a:1,b:2}) // [] Array. The from ({a: 1, length: 2}) / / [undefined undefined] Array. The from ({1-0, 1:2, length: 2}) / / / / mapping function [1, 2] Array. The from ([1, 2, 3], I = > I * 2) / / minus [2]Copy the code

3.2 Array. IsArray ()

Check whether the argument is an array, not an object.

Array.isArray([])  // true
Array.isArray({})  // false
Array.isArray(1)  // false
Copy the code

3.3 Array) of ()

Create a new Array instance with a variable number of parameters, regardless of the number or type of parameters

Array.of(1,2) // [1,2] Array(2) // create an Array of empty slots of specified length [empty, empty] // polyfill Array.of = function(){ return Array.prototype.slice.call(arguments); }Copy the code

4. Array static methods

4.1 the concat ()

Merges two or more arrays. This method does not change an existing array, but returns a new array.

[] concat (1, 2, 3], [4]) / / [1, 2, 3, 4]Copy the code

4.2 entries ()

Returns a new Array Iterator containing key/value pairs for each index in the Array.

Const arr = [1,2,3] const itea = arr.entries() // iterator const [index,value] = itea.next().valuem  for(const [index,value] of arr.entries()){ console.log(index,value) }Copy the code

4.3 the fill ()

Changes all elements in the array to static values, from the start index (default 0) to the end index (default array.length). It returns the modified array.

Let array = array (1, 2, 3, 4]. The fill (0, 4-trichlorobenzene) / /,2,0,0 [1] -- > array array. The fill (5, 1) / /,5,5,5 [1]Copy the code

4.4 findIndex ()

Returns the index of the first element that meets the condition, otherwise -1, indicating no element that meets the condition.

Const index = [1,2,3,4,5]. FindIndex (function(ele,idx,array){return ele>3}) // 3Copy the code

4.5 flat ()

Creates a new array in which all subarray elements are recursively concatenated until the specified depth is reached.

const arr2 = [0, 1, 2, [[[3, 4]]]]; Arr2. Flat (2) // 2 depth: [0, 1, 2, [3, 4]]Copy the code

4.6 includes ()

Determines whether an entry in the array contains a value and returns true or false as required.

[1, 2, 3]. Includes (2) / / true [1, 2, 3]. Includes (4) / / falseCopy the code

4.7 indexOf ()

Returns the first index where the given element can be found in the array; If none exists, -1 is returned.

[1, 2, 3, 4] indexOf (3) / / 2 [1, 2, 3, 4] indexOf (3, 2) / / from index 2, begin to search back 3 - - > 2 (from the index value of back) [1, 2, 3, 4] indexOf (3, 3) / / from index 3, Start searching 3 --> -1Copy the code

4.8 Other Uses of arrays

// Create and return a new string by concatenating all the elements in an array (or array-like object). [1,2,3].join() // 1,2,3 // returns a new Array Iterator containing the keys for each index in the Array. Let itea = [1,2,3].keys() // Iterator itea.next() // {value:0,done:false} // returns a new Array Iterator containing the value of each index in the Array. 1 let itea = [1,2,3].values() itEa.next () // {value:1,done:false} // Remove the last element from the array and return the element. This method changes the length of the array [1,2,3].pop() // 3, returning the undeleted array length // adds one or more elements to the end of the array and returns the new array length. [1, 2, 3]. Push (4) / / 4 / turn/array [1, 2, 3, 4]. Reverse () / / [4, 3, 2, 1] / / removes the first element from an array and then return to delete elements. This method changes the length of the array [1,2,3,4].shift() // 1 // adds one or more elements to the beginning of the array and returns the new length of the array. [1,2]. Unshift (3,4) // 4 // cut array from start to end, without end, Return to the new array [6]. Slice (2, 4) / / [3, 4] / / array sort let Numbers = [4, 2, 5, 1, 3]. numbers.sort(function(a, b) { return a - b; }); // [1,2,3,4,5] // Change the contents of the array by deleting or replacing existing elements and/or adding new elements in appropriate places let arr = [1,2] arr.splice(1,0,'a') // arr -> [1,'a',2] let arr1 = [1,2,3] let removed = arr1.splice(2,1) // removed:[3] arr1:[1,2,3]Copy the code

4.9 Array traversal 7 methods

for

forEach

map

filter

some

every

reduce

find
Copy the code

Polyfill: array traversal, array traversal, array traversal

Seven methods of Array traversal and Compatibility Processing (Polyfill)

5. Common algorithms for arrays

1. Find the maximum and minimum values of the array

1. Extend the min() and Max () functions by extending the Prototype attribute.

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},4,1,4 [2]. Min () / / 1,4,1,4 [2]. Max () / / 4Copy the code

2. Use the min() and Max () functions of the Math object

// static array. min = function(Array){return math.min. apply(Math, Array)} array. Max = function(Array){return Array.prototype.min = function(){return math.min. Apply (null,this)} Array.prototype.max = function(){ return Math.max.apply(null,this) }Copy the code

3. Use the reduce() function

Array.prototype.min = function(){ return this.reduce(function(preVal,curVal){ return preVal>curVal? CurVal :preVal})} // Same for maximum valueCopy the code

4. By sort()

Let arr = [2,1,3,4] let sortArr = arr.sort(function(a,b){return a-b}) sortArr[0] // minCopy the code

5. With es6 extension operators

Let arr = [2,1,4,3] Math. Min (... Arr) // Minimum math.max (... Arr) // Maximum valueCopy the code

2. 7 algorithms for array deduplication

7 algorithms for array de-duplication

3. Find the four algorithms with the most elements in the array

4 algorithms for finding the most frequently occurring elements in an array (more on later)

8. To summarize

So far we have summed up the array of knowledge, worth collecting, job interview essential!