The ArrayList section introduces the time complexity of the analysis. It is strongly recommended that you read it in order. The first two articles are:
ArrayList initialization – Java things column
2, ArrayList basic array expansion principle – Java those things column
In order to fully understand the internal implementation of HashMap, we still need some basic knowledge. With this basic knowledge, we can better understand HashMap. In fact, we have unknowingly entered the door of data structure. In order to give you a better understanding of the following articles, we will first introduce the concept of time complexity.
The same Person object, added an attribute age
Create an array and place 10 Person objects in the array.
If we had a requirement, and we wanted to know the age of The group, we would write code to find it:
You need to loop through it six times to get the Person object from the array.
At this time, Xiao Ming came and said, oh, I know Zhou Ba is in the fifth position of the group (array subscript 5), no cycle, we directly look for him
Without looping, the Person object is fetched once:
No matter how many elements in the array, each time to read the elements and and compare the time is always the same, assuming that the time for K, in the above example loop search a user in the array, we cycle 6 times to search to the user, time of 6 * K, on the efficiency, the former way 6 times faster than the latter, but the meaning of this statement is not big, because in real life, The array may have 100 elements, and the “eight” may be in the first or last position of the array.
In the real world, we measure the length of time in hours, minutes, seconds, etc. We also need a metric to calculate the efficiency of the algorithm in this example. In computer science, this metric is known as the “big O” notation.
When we know the location of the element, we can access the element in one step. This time is K, and the time complexity is marked by O(1) in big O notation, with the K omitted. If we look for an element in the array, we don’t know where it is in the array. If the array is of length N, we might find the element at position 0 (the first position) in one loop, and the time is O(1). It’s also possible that at n minus 1, the last position in the array, we’re going to have to loop n times to match that value, which is O(n), which is n/2 on average, which is O(n/2) on average, but we shouldn’t just think about the average, we should think about the worst case, That is, we’re assuming that every time we match the element is the last bit of the array, because the worst case is a kind of running time guarantee, the running time can’t get any longer, and if we don’t specify it, we’re talking about the worst case running time, which is to find something in the array, order n;
In an array of length n:
Access elements directly by subscript, O(1) time.
When you need to loop to find an element, the time is order n.
In the next chapter, we will analyze the source code of the deleted elements of ArrayList to analyze the time complexity of ArrayList, and then understand the advantages and disadvantages of ArrayList.
ArrayList basic array expansion principle – Java those things column
Next: To be continued
Note: This column was first published on the public account saysayJava. All sample codes have been uploaded to the public account, please pay attention to download.
If you liked this series, please give me a thumbs up or share it with me. Your support is what keeps me going, and leave a comment in the comments section where you can find out what you want to know about this column.
Reprint unlimited welcome, but please indicate “author” and “original address”. Please keep this paragraph in the article, thank you for your respect for the author’s copyright. For commercial reprint or publication, please contact the author for authorization.