Shulou(Shulou.com)06/03 Report--

This article is about how to compare arrays of data structures in JavaScript with objects. The editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.

In programming, if you want to go further, the data structure is an area that we must understand, and the motivation to learn / understand the data structure may be different, on the one hand, for the interview. On the other hand, it may be simply to improve your skills or the needs of the project. No matter what the motivation is, learning data structures is a tedious and boring process if you don't know what array structures are and when to use them.

The Big O notation large zero symbol is generally used to describe the complexity of the algorithm, such as the time of execution or the space occupied by memory (disk), especially in the worst-case scenario.

Array

Array is one of the most widely used data structures. The data in the array is structured in an orderly manner, that is, the first element in the array is stored in index 0, the second element in index 1, and so on. JavaScript provides us with some built-in data structures, and array is one of them?

In JavaScript, the easiest way to define an array is:

Let arr = []

The above line of code creates a dynamic array of unknown length. To learn how to store the elements of the array in memory, let's look at an example:

Let arr = ['John',' Lily', 'William',' Cindy']

In the above example, we create an array containing some people's names. Names in memory are stored in the following ways:

To understand how arrays work, we need to do some things:

Add elements:

In the JavaScript array, we have different ways to add elements at the end of the array, at switches, and at specific indexes.

Add an element to the end of the array:

The array in JavaScript has a default property, length, which represents the length of the array. In addition to the length property, JS also provides a push () method. Using this method, we can add an element directly at the end.

Arr.push ('Jake')

So what is the complexity of this command? We know that by default, JS provides the length attribute, and push () is equivalent to using the following command:

Arr [arr.length-1] = 'Jake'

Because we can always access the length attribute of an array, no matter how large the array is, the complexity of adding an element at the end is always O (1)?

Add an element at 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']

The complexity of the unshift method seems to be the same as that of the push method: O (1), because we just add an element in front of it. This is not the case, let's take a look at what happens when you 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 relatively 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 a delay because we have to move the index of each element in the array. Therefore, the complexity of unshift operation is O (n)?

If you are dealing with large-length arrays, use the unshift method wisely. To add an element at a specific index, we can splice () method, which has the following syntax:

Splice (startingIndex, deleteCount, elementToBeInserted)

Because we are going to add an element, deleteCount will be 0. For example, if we want to add a new element where the array index is 2, we can use this:

Let arr = ['John',' Lily', 'William',' Cindy'] arr.splice (2,0, 'Janice') console.log (arr) / / [' John', 'Lily',' Janice', 'William',' Cindy']

What do you think is the complexity of this operation? In the above operation, we added elements at index 2, so all subsequent elements after index 2 must be added or moved by 1 (including those previously at index 2).

As you can observe, we are not moving or incrementing the indexes of all elements, but incrementing the indexes of elements after index 2. Does this mean that the complexity of the operation is `O (nplink 2)? No?. According to Big O rules, constants can be removed from complexity, and we should consider the worst-case scenario. Therefore, the complexity of the operation is O (n)?

Delete the element:

Just like adding elements, deleting elements can be done at different locations, at the end, at the beginning, and at a specific index.

Delete an element at the end of the array:

Like push (), JavaScript provides a default method, pop (), to delete / delete 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']

The complexity of this operation is O (1). Because, no matter how large the array is, deleting the last element does not need to change the index of any element in the array.

Delete an element at the beginning of the array:

JavaScript provides a default method, shift (), which deletes the first element of the array.

Let arr = ['John',' Lily','William','Cindy'] arr.shift () console.log (arr) / / ['Lily','William','Cindy'] arr.shift () console.log (arr); / / [' William','Cindy']

From the above, we can easily see that the complexity of the shift () operation is O (n), because after deleting the first element, we have to 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 parameters, because we are not going to add a new element at the index.

Let arr = ['Apple',' Orange', 'Pear',' Banana','Watermelon'] arr.splice (2) console.log (arr) / / ['Apple',' Orange', 'Banana','Watermelon']

Similar to the add element operation with splice, in this operation, we will decrement or move the element index after index 2, so the complexity is O (n).

Find elements:

Lookup is just an element of the access array, which we can access by using square brackets (for example: arr [4]).

What do you think is the complexity of this operation? Let's demonstrate it with an example:

Let fruits = ['Apple',' Orange', 'Pear']

As we saw earlier, all the elements of the array are stored sequentially and are always grouped together. Therefore, if you execute fruits [1], it will tell the computer to find an array named fruits and get the second element (the array starts with index 0).

Because they are stored sequentially, the computer does not have to look at the entire memory to find the element, because all the elements are grouped together sequentially, so it can be viewed 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 operation of the array, let's summarize when the array can be used:

Arrays are appropriate when you want to perform operations such as push () (adding elements at the end) and pop () (removing elements from the end), because the complexity of these operations is O (1).

In addition, lookup operations can be performed very quickly in an array.

When using arrays, operations such as adding / removing elements at a specific index or at the beginning can be very slow because of their complexity of O (n).

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 instead of storing values at the numbered index as we can see in the array.

The easiest way to define an object is:

Let obj1 = {}

Examples:

Let student = {name: 'Vivek', age: 13, class: 8}

Take a look at how the above objects are stored in memory:

As you can see, the key-value pairs of objects are stored randomly, unlike all the elements in the array stored together. This is also the main difference between arrays and objects, where key-value pairs are randomly stored in memory.

We also see a hash function (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 the hash value into an address space, where the key-value pair is stored.

For example, if we add the following key-value pair to the student object:

Student.rollNumber = 322

The rollNumber key passes through the hash function and is then converted to the address space where the key and value are stored. Now that we have a basic understanding of how objects are stored in memory, let's do something.

Add

For objects, we have no separate way to add elements to the front or back, because all key-value pairs are stored randomly. Only one operation is to add a new key-value pair to the object.

Examples:

Student.parentName = 'Narendra Singh Bisht'

We can conclude from the figure above that the complexity of this operation is always O (1), because we do not need to change any indexes or operands themselves, we can directly add a key-value pair, which is stored in a random address space.

Delete

Like adding elements, the deletion of an object is very simple, with a complexity of O (1). Because we don't have to change or manipulate objects when we delete them.

Delete student.parentName

Find

The complexity of the lookup is O (1), because here, we only use the key to access the value. A way to access values in an object:

Student.class

The complexity of adding, deleting and searching in an object 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 are some small cases to consider when working with objects, which is Hash Collisions. When using objects, this situation should not always be dealt with, but understanding the situation will help us to better understand the objects.

So what is a hash collision?

When we define an object, our computer allocates some space for the object in memory. We need to keep in mind that the space in our memory is limited, so it is possible that two or more key-value pairs may have the same address space, a situation called hash collisions. To better understand it, let's look at an example:

Suppose 5 blocks of space are allocated to the following objects

We observe that the two key-value pairs are stored in the same address space. How did this happen? This occurs when the hash function returns a hash value that is converted to the same address space for multiple keys. Therefore, multiple key are mapped to the same address space. Because of hash collisions, the complexity of adding and accessing object values is O (n), because to access specific values, we may have to traverse various key-value pairs.

Hash collisions are not something we need to deal with every time we use an object. This is just a special case, which also shows that the object is not a perfect data structure.

In addition to * hash collisions, there is another situation that you must be aware of when using objects. JS provides us with a built-in keys () method for traversing the keys of an object.

We can apply this method to any object, such as object1.keys (). The keys () method iterates through the object and returns all the keys. Although this method looks simple, we need to understand that the key-value pairs in the object are randomly stored in memory, so the process of traversing the object becomes slower, unlike traversing the arrays that group them together in order.

To sum up, we can use objects when we want to perform operations such as adding, deleting, and accessing elements, but when using objects, we need to traverse objects carefully because it can be time-consuming. In addition to traversing, we should also understand that sometimes the complexity of accessing objects can become O (n) because of hash collisions.

The above is how to compare the array of data structures in JavaScript with objects. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.