By Vivek Bisht translator: Front-end xiaozhi Source: Blog
Click “like” and then look, wechat search [Big Move the world] pay attention to this person without dACHang background, but with a positive attitude upward. In this paper, making github.com/qq449245884… Has been included, the article has been categorized, also organized a lot of my documentation, and tutorial materials.
Everyone said there was no project on your resume, so I found one and gave it away【 Construction tutorial 】.
In programming, data structures are a must-understand area if you want to go further, and the motivation for learning/understanding data structures may vary, whether it’s for an interview, or simply to improve your skills or project needs. Whatever the motivation, learning data structures is a tedious and uninteresting process without knowing what array structures are and when to use application words 😵
This article discusses when to use them. In this article, we’ll learn about arrays and objects. We will try to understand when to select a data structure by using Big O notation.
The Big O notation is used to describe the complexity of an algorithm, such as execution time or memory (disk) footprint, especially in the worst-case scenario.
An array of
Arrays are one of the most widely used data structures. The data in the array is structured in an ordered manner, with the first element in the array stored in index 0, the second in index 1, and so on. JavaScript provides us with some built-in data structures, and arrays are one of them 👌
In JavaScript, the easiest way to define an array is:
let arr = []
Copy the codeThe above line creates a dynamic array (of unknown length). To see how to store the elements of an array in memory, let’s look at an example:
let arr = ['John', 'Lily', 'William', 'Cindy']
Copy the codeIn the example above, we create an array of names. Names in memory are stored as follows:
To understand how arrays work, we need to do a few things:
Add elements:
In JavaScript arrays, we have different ways to add elements at the end of the array, on/off, and at specific indexes.
Add an element to the end of the array:
Arrays in JavaScript have a default property, Length, which represents the length of the array. In addition to the length attribute, JS also provides push() methods. Using this method, we can add an element directly at the end.
arr.push('Jake')
Copy the code
So what is the complexity of this command? As we know, JS provides the length attribute by default, and push() is equivalent to using the following command:
arr[arr.length - 1] = 'Jake'
Copy the codeBecause we always have access to the length property of the array, the complexity of adding an element to the end is always O(1) 👏, no matter how big the array is.
Add an element to the beginning of the array:
For this operation, JavaScript provides a default method called unshift(), which adds elements to the beginning of the array.
let arr = ['John', 'Lily', 'William', 'Cindy']
arr.unshift('Robert')
console.log(arr) // [ 'Robert', 'John', 'Lily', 'William', 'Cindy' ]
Copy the codeThe unshift method seems to have the same complexity as the push method: O(1), because we just add one element in front of it. This is not the case. Let’s look at what happens when we use the unshift method:
In the figure above, when we use the unshift method, the index of all elements should be increased by 1. Here we have a small number of arrays, so we can’t see the problem. Imagine using a fairly long array, and then using a method like unshift causes delay because we have to move the index of every element in the array. Therefore, the complexity of unshift operation is O(n) 😋.
If you are dealing with large arrays, use the unshift method wisely. To add an element at a particular index, we can use the splice() method, which has the following syntax:
splice(startingIndex, deleteCount, elementToBeInserted)
Copy the codeBecause we’re adding an element, deleteCount is going to be 0. For example, if we want to add a new element to an array whose index is 2, we can use:
let arr = ['John', 'Lily', 'William', 'Cindy']
arr.splice(2, 0, 'Janice')
console.log(arr)
// [ 'John', 'Lily', 'Janice', 'William', 'Cindy' ]
Copy the codeWhat do you think is the complexity of this operation? In the above operation, we added elements at index 2, so that all subsequent elements after index 2 must be incremented or moved by 1(including the elements previously at index 2).
You can observe that instead of moving or incrementing the index of all elements, we are incrementing the index of the element after index 2. Does this mean that the operation is O(n/2)? Not 😮. According to the Big O rule, constants can be removed from complexity, and we should consider the worst case. Therefore, the complexity of this operation is O(n) 😳.
Delete element:
Just like adding elements, deleting elements can be done at different places, at the end, at the beginning, and at specific indexes.
Deletes an element at the end of an array:
Like push(), JavaScript provides a default method pop() for removing/deleting elements at the end of an array.
let arr = ['Janice', 'Gillian', 'Harvey', 'Tom']
arr.pop()
console.log(arr)
// [ 'Janice', 'Gillian', 'Harvey' ]
arr.pop()
console.log(arr)
// [ 'Janice', 'Gillian' ]
Copy the codeThe complexity of this operation is O(1). Because, no matter how large the array is, deleting the last element does not require changing the index of any element in the array.
Deletes an element at the beginning of an array:
JavaScript provides a default method for the default shift() method, which deletes the first element of an array.
let arr = ['John', 'Lily','William','Cindy'] arr.shift() console.log(arr) // ['Lily','William','Cindy'] arr.shift() console.log(arr); // ['William','Cindy']Copy the code
We can easily see from the above that the complexity of the shift() operation is O(n), because after deleting the first element, we must shift or decrement the indexes of all elements by 1.
Delete at a specific index:
For this operation, we use the splice() method again, but this time we only use the first two arguments because we don’t intend to add new elements at the index.
Let arr = ['Apple', 'Orange', 'Pear', 'Banana','Watermelon'] arr.splice(2,1) console.log(arr) // ['Apple', 'Orange', 'Banana','Watermelon']Copy the codeSimilar to the add element operation with splice, in this operation we decrement or move the element index after index 2, so the complexity is O(n).
Find elements:
A lookup accesses only one element of an array, which can be accessed by using the square bracket notation (for example: arr[4]).
What do you think is the complexity of this operation? Let’s use an example to demonstrate:
let fruits = ['Apple', 'Orange', 'Pear']
Copy the code
As we saw earlier, all elements of an array are stored sequentially and are always grouped together. So, if fruits1 is executed, it tells the computer to find the array named FRUITS and get the second element (the array starts at index 0).
Because they are stored sequentially, the computer does not have to look through the entire memory to find the element, because all the elements are grouped together sequentially, so it can look directly inside the FRUITS array. Therefore, the complexity of the lookup operation in the array is O(1).
Now that we have completed the basic operations on arrays, let’s summarize when arrays can be used:
Arrays are appropriate when you’re performing operations like push()(adding elements at the end) and POP ()(removing elements from the end), because these operations are O(1) in complexity.
In addition, lookups can be performed very quickly in arrays.
When using arrays, performing operations such as adding/removing elements at a specific index or at the beginning can be very slow because of their O(n) complexity.
object
Like arrays, objects are one of the most commonly used data structures. An object is a hash table that allows us to store key-value pairs rather than storing values at numbered indexes as seen in arrays.
The easiest way to define an object is:
let obj1 = {}
Copy the codeExample:
let student = {
name: 'Vivek',
age: 13,
class: 8
}
Copy the codeLet’s see how the above object is stored in memory:
As you can see, key-value pairs of objects are stored randomly, unlike arrays where all elements are stored together. This is the main difference between arrays and objects, where key-value pairs are stored randomly in memory.
We also see that we have a hash function. So what does this hash function do? The hash function takes each key from the object, generates a hash value, and then converts this hash value into an address space in which key-value pairs are stored.
For example, if we add the following key-value pairs to the student object:
student.rollNumber = 322
Copy the codeThe rollNumber key passes through the hash function and is then converted into an address space that stores the key and value. Now that we have a basic understanding of how objects are stored inside, let’s do some things.
add
For objects, we don’t have a separate way to add elements before or after, because all key-value pairs are stored randomly. Only one operation is to add a new key-value pair to the object.
Example:
student.parentName = 'Narendra Singh Bisht'
Copy the code
We can conclude from the figure above that the complexity of this operation is always O(1), because we don’t need to change any index or the operation object itself, we can simply add a key-value pair, which is stored in a random address space.
delete
Like adding elements, object deletion is a simple O(1) operation. Because we don’t have to change or manipulate objects when we delete them.
delete student.parentName
Copy the codeTo find the
O(1) of look-up, because here, too, we’re just accessing values by keys. One way to access a value in an object:
student.class
Copy the codeAdding, deleting, and finding objects is O(1)?? So can we conclude that we should use objects instead of arrays every time? The answer is no. Although objects are great, there is a small case to consider when using objects, which is Hash Collisions. This is not always the case to deal with when working with objects, but knowing it helps us better understand objects.
So what is a hash collision?
When we define an object, our computer allocates some space in memory for that object. We need to remember that we have a finite amount of space in memory, so it is possible that two or more key-value pairs may have the same address space, a situation called hash collisions. To understand it better, let’s look at an example:
Suppose five blocks of space are allocated for the following objects
We observe that two key-value pairs are stored in the same address space. How did that happen? This occurs when a hash function returns a hash value that is translated into the same address space for multiple keys. Therefore, multiple keys are mapped to the same address space. Adding and accessing object values is O(n) complexity due to hash collisions, since we may have to traverse various key-value pairs to access specific values.
Hash collisions are not something we need to deal with every time we use an object. This is just a special case that illustrates that objects are not perfect data structures.
In addition to * hash collisions, there is another case you must be aware of when using objects. JS provides a built-in keys() method for traversing an object’s keys.
We can apply this method to any object, such as object1.keys(). The keys() method iterates through the object and returns all keys. Although this approach seems simple, we need to understand that the key-value pairs in an object are stored randomly in memory, so the process of traversing an object becomes slower, unlike traversing an array that groups them together in order.
To summarize, objects can be used when we want to perform operations such as adding, deleting, and accessing elements, but we need to be careful to traverse objects when using them, as this can be time-consuming. In addition to traversal, we should also understand that sometimes the complexity of accessing object operations can become O(n) due to hash collisions.
The bugs that may exist after code deployment cannot be known in real time. In order to solve these bugs, I spent a lot of time on log debugging. Incidentally, I recommend a good BUG monitoring tool for youFundebug.
Original text: blog.soshace.com/comparing-d…
communication
This article continues to update every week, you can wechat search “big move the world” the first time to read, reply [welfare] there are many front-end video waiting for you, this article GitHub github.com/qq449245884… Already included, welcome Star.