Without further ado, let’s go directly to the picture:
Java collections, also called containers, Mainly derived from two major interfaces (Interface): Collection and Map
As the name suggests, containers are used to store data.
The difference between these two interfaces is:
Collection stores a single element;
Map stores key- value key-value pair.
That is, singles are placed in the Collection, and couples are placed in the Map. (So where do you belong?
Learning these collection frameworks, I think there are 4 goals:
Clear the corresponding relationship between each interface and class;
Be familiar with commonly used APIs for each interface and class;
Be able to choose appropriate data structures and analyze the advantages and disadvantages for different scenarios;
Learn source code design and be able to answer interviews.
Regarding Map, the previous HashMap article has been very thorough and detailed. So I won’t go into details in this article. If you haven’t read that article yet, please go to the official account and reply “HashMap” to read the article~
Collection
Let’s first look at the top-level Collection.
Collection also defines many methods, which will also be inherited into each sub-interface and implementation class. The use of these APIs is also a common test in daily work and interviews, so Let’s look at these methods first.
The collection of operations is nothing more than the four categories of "Add, Delete, Modify and Check", also called CRUD:
Create, Read, Update, and Delete.
Then I also divide these APIs into these four categories:
Function
Method
Add
add()/addAll()
Delete
remove()/ removeAll( )
Change
There is no
in Collection Interface#check
contains()/ containsAll()
Others
isEmpty()/size()/toArray()
Let’s look at it in detail below:
Added:
boolean add(E e);
add() The data type passed in by the method It must be Object, so when writing basic data types, auto-boxing and unboxing will be performed.
There is another method addAll(), which can add elements from another collection to this collection.
boolean addAll(Collection<? extends E> c);
Delete:
boolean remove(Object o);
remove() is the specified element to be deleted.
That corresponds to addAll(), naturally has removeAll(), which is to delete all elements in set B.
boolean removeAll(Collection<?> c);
Change:
There is no direct operation to change elements in Collection Interface. Anyway, deletion and addition can complete the change!
查：
查下集合中有没有某个特定的元素：
boolean contains(Object o);
查集合 A 是否包含了集合 B：
boolean containsAll(Collection<?> c);
还有一些对集合整体的操作：
判断集合是否为空：
boolean isEmpty();
集合的大小：
int size();
把集合转成数组：
Object[] toArray();
以上就是 Collection 中常用的 API 了。
在接口里都定义好了，子类不要也得要。
当然子类也会做一些自己的实现，这样就有了不同的数据结构。
那我们一个个来看。
List
List 最大的特点就是：有序，可重复。
看官网说的：
An ordered collection (also known as a sequence).
Unlike sets, lists typically allow duplicate elements.
This time I also mentioned the characteristics of Set. It is completely opposite to List. Set is unordered and does not repeat.
List can be implemented in two ways: LinkedList and ArrayList. The most common question asked during interviews is how to choose between these two data structures.
For this type of selection problem: The first is to consider whether the data structure can complete the required functions; If both can be completed, the second is to consider which is more Efficient.
(Everything is like this.
Let’s look specifically at the APIs of these two classes and their time complexity:
Function
Method
ArrayList
LinkedList
increase
add(E e)
O(1)
O(1)
Add
add(int index, E e)
O(n)
O(n)
Delete
remove(int index)
O(n)
O(n)
Delete
remove(E e)
O(n)
O(n)
Change
set(int index, E e)
O(1)
O(n)
Check
get(int index)
O(1)
O(n)
A few explanations:
add(E e) is to add elements to the tail. Although the ArrayList may expand, the amortized time complexity ) is still O(1).
add(int index, E e) is to add an element at a specific position. LinkedList needs to find this position first and then add this element. Although it is a simple "add" action It's O(1), but finding this position is still O(n). (Some people think this is O(1). Just explain it clearly to the interviewer and refuse to take the blame.
remove(int index) is the element on the index of remove. So
The process of finding this element in ArrayList is O(1), but after remove, subsequent elements must be moved forward by one position, so the amortized complexity is O(n);
LinkedList also needs to find the index first. This process is O(n), so the overall process is also O(n).
remove(E e) is the first element seen by remove, then
ArrayList must first find this element. This process is O(n), and then move After division, you have to move one position forward, which is O(n), and the total is still O(n);
LinkedList also needs to be searched first, and this process is O(n) ), and then removed, this process is O(1), and the total is O(n).
What is the reason for the difference in time complexity?
Answer:
Because ArrayList is implemented using arrays.
The biggest difference between arrays and linked lists is that arrays can be accessed randomly (random access).
This feature causes You can get the number at any position in O(1) time through subscripting, but you can't do that with a linked list. You can only traverse it one by one from the beginning.
That is to say, in the two functions of "Change and Check" Because the array can be accessed randomly, ArrayList is highly efficient.
What about "addition and deletion"?
If you do not consider the time to find this element,
Because of the physical continuity of the array, when you want to add or delete elements, it is fine at the tail, but other places will cause subsequent elements to be deleted. Movement, so the efficiency is lower; while a linked list can easily disconnect from the next element, directly insert new elements or remove old elements.
But, in fact, you have to consider the time to find the element. . . And if it is operated at the tail, ArrayList will be faster when the amount of data is large.
So:
Change the search and select ArrayList;
Choose ArrayList for additions and deletions at the end;
In other cases, if the time complexity is the same, it is recommended to choose ArrayList because the overhead is smaller, or the memory Use more efficiently.
Vector
As the last knowledge point about List, let’s talk about Vector. This is also an age-revealing post, used by all the big guys.
The Vector, like the ArrayList, also inherits from java.util.AbstractList, and the bottom layer is also implemented using an array.
But it has been deprecated now because...it adds too many synchronized!
Every benefit comes at a cost. The cost of thread safety is low efficiency, which can easily become a bottleneck in some systems. Therefore, now we no longer add synchronized at the data structure level, but instead Transfer to our programmers==
So the common interview question: What is the difference between Vector and ArrayList? Just answering this is not very comprehensive.
Let’s take a look at the high-voted answers on stack overflow:
The first is the thread safety issue just mentioned; The second is the difference in how much expansion is required during expansion.
You have to look at the source code for this:
This is the expansion implementation of ArrayList. This arithmetic right shift operation is to The binary number of this number is moved one bit to the right, and the leftmost complements the sign bit , but because the capacity does not have a negative number, it still adds 0.
The effect of shifting one bit to the right is to divide by 2 , then the new capacity defined is 1.5 times of the original capacity.
Let’s look at Vector again:
Because usually we do not define capacityIncrement, so by default it is expanded twice.
If you answer these two points, there will definitely be no problem.
Queue & Deque
Queue is a linear data structure with one end in and the other out; and Deque is both ends. All can be entered and exited.
Queue
The Queue interface in Java is a little bit confusing. Generally speaking, the semantics of queues They are all first in, first out (FIFO).
But there is an exception here, that is, PriorityQueue, also called heap, does not come out in the order of the time it enters, but goes out according to the specified priority, and its operation is not O(1), time The calculation of complexity is a bit complicated, and we will discuss it in a separate article later.
The Queue methodOfficial website[1]It’s all summarized. It has two sets of APIs, and the basic functions are the same, but:
One group will throw an exception;
The other group will return a special value.
Function
Throw exception
Return value
Add
add(e)
offer(e)
##Delete
remove()
poll()
Look
element()
peek()
Why does it throw an exception?
For example, if the queue is empty, remove() will throw an exception, but poll() will return null; element() will throw an exception, and peek() will Just return null.
How come add(e) throws an exception?
Some Queues have capacity limits, such as BlockingQueue. If it has reached its maximum capacity and will not be expanded, an exception will be thrown; but if the offer (e), it will return false.
So how to choose? ：
First of all, if you want to use it, use the same set of API, and the front and back must be unified;
Secondly, according to needs. If you need it to throw exceptions, use the one that throws exceptions; but it is basically not used when doing algorithm problems, so just choose the one that returns special values.
Deque
Deque can be entered and exited from both ends, so it is naturally targeted at the First end. Operations and operations on the Last side, each side has two groups, one group throws an exception, and the other group returns a special value:
Function
Throws an exception
Return value
##increase
addFirst(e)/ addLast(e)
offerFirst( e)/ offerLast(e)
Delete
removeFirst()/ removeLast()
pollFirst()/ pollLast()
Look
getFirst()/ getLast()
peekFirst()/ peekLast()
The same applies when used. If you want to use it, use the same group.
These APIs of Queue and Deque have a time complexity of O(1), to be precise, it is an amortized time complexity.
Implementation classes
Their implementation classes have these three:
So,
If you want to implement the semantics of "ordinary queue - first in, first out", use LinkedList or ArrayDeque to achieve it;
If If you want to realize the semantics of "priority queue", use PriorityQueue;
If you want to realize the semantics of "stack", use ArrayDeque.
Let’s look at them one by one.
When implementing a common queue, How to choose between LinkedList or ArrayDeque?
Let’s take a look at the top-voted answer on StackOverflow[2]:
Summary It is recommended to use ArrayDeque because of its high efficiency, while LinkedList will have other additional overhead.
What are the differences between ArrayDeque and LinkedList?
Still with the same question just now, this is the best summary I think:
ArrayDeque It is an expandable array, and LinkedList is a linked list structure;
ArrayDeque cannot store null values, but LinkedList can;
ArrayDeque in It is more efficient to operate the addition and deletion operations at the head and tail, but the removal of LinkedList is O(1) only when an element in the middle is to be removed and the element has been found;
ArrayDeque is more efficient in terms of memory usage.
So, as long as you don’t have to store null values, choose ArrayDeque!
So if a very senior interviewer asks you, under what circumstances should you choose to use LinkedList?
The value is placed on the key in the map, and a PRESENT is placed on the value. It is a static Object, equivalent to a place holder, and each key points to this object.
So the specific implementation principle, add, delete, modify, check four operations, and hash conflict, hashCode( )/equals() and other issues have been discussed in the HashMap article, so I won’t go into details here. Friends who haven’t seen it can reply “HashMap” in the background of the official account to get the article~
Summary
Go back to the picture at the beginning, is it clearer? Woolen cloth?
There is actually a lot of content under each data structure, such as PriorityQueue. This article does not go into details, because it will take a long time for this guy to talk about it. .
If you think the article is good, the likes at the end of the article are back again, Remember to give me "like" and "reading"~
Finally, there are many Readers have been asking me about the communication group, but I haven’t done it because I have a jet lag and it’s difficult to manage it.
But now I have found a professional administrator to manage it with me, so "Sister Qi's Secret Base" is under preparation, and I will invite some big guys at home and abroad to come and bring it to everyone A different perspective.
The first phase of the exchange group is planned to be opened in mid-to-early July. I will send invitations in Moments then, so stay tuned!
The above is the detailed content of It's enough to read this article about Java collection framework. For more information, please follow other related articles on the PHP Chinese website!
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
The key to writing PHP comments is to clarify the purpose and specifications. Comments should explain "why" rather than "what was done", avoiding redundancy or too simplicity. 1. Use a unified format, such as docblock (/*/) for class and method descriptions to improve readability and tool compatibility; 2. Emphasize the reasons behind the logic, such as why JS jumps need to be output manually; 3. Add an overview description before complex code, describe the process in steps, and help understand the overall idea; 4. Use TODO and FIXME rationally to mark to-do items and problems to facilitate subsequent tracking and collaboration. Good annotations can reduce communication costs and improve code maintenance efficiency.
Comments cannot be careless because they want to explain the reasons for the existence of the code rather than the functions, such as compatibility with old interfaces or third-party restrictions, otherwise people who read the code can only rely on guessing. The areas that must be commented include complex conditional judgments, special error handling logic, and temporary bypass restrictions. A more practical way to write comments is to select single-line comments or block comments based on the scene. Use document block comments to explain parameters and return values at the beginning of functions, classes, and files, and keep comments updated. For complex logic, you can add a line to the previous one to summarize the overall intention. At the same time, do not use comments to seal code, but use version control tools.
The key to writing good comments is to explain "why" rather than just "what was done" to improve the readability of the code. 1. Comments should explain logical reasons, such as considerations behind value selection or processing; 2. Use paragraph annotations for complex logic to summarize the overall idea of functions or algorithms; 3. Regularly maintain comments to ensure consistency with the code, avoid misleading, and delete outdated content if necessary; 4. Synchronously check comments when reviewing the code, and record public logic through documents to reduce the burden of code comments.
The key to writing PHP comments is clear, useful and concise. 1. Comments should explain the intention behind the code rather than just describing the code itself, such as explaining the logical purpose of complex conditional judgments; 2. Add comments to key scenarios such as magic values, old code compatibility, API interfaces, etc. to improve readability; 3. Avoid duplicate code content, keep it concise and specific, and use standard formats such as PHPDoc; 4. Comments should be updated synchronously with the code to ensure accuracy. Good comments should be thought from the perspective of others, reduce the cost of understanding, and become a code understanding navigation device.
The first step is to select the integrated environment package XAMPP or MAMP to build a local server; the second step is to select the appropriate PHP version according to the project needs and configure multiple version switching; the third step is to select VSCode or PhpStorm as the editor and debug with Xdebug; in addition, you need to install Composer, PHP_CodeSniffer, PHPUnit and other tools to assist in development.
There are three common ways to use PHP comments: single-line comments are suitable for briefly explaining code logic, such as // or # for the explanation of the current line; multi-line comments /*...*/ are suitable for detailed description of the functions or classes; document comments DocBlock start with /** to provide prompt information for the IDE. When using it, you should avoid nonsense, keep updating synchronously, and do not use comments to block codes for a long time.
PHP comparison operators need to pay attention to type conversion issues. 1. Use == to compare values only, and type conversion will be performed, such as 1=="1" is true; 2. Use === to require the same value as the type, such as 1==="1" is false; 3. Size comparison can be used on values and strings, such as "apple"
PHP comments are parts of the code that are used to interpret logic, tag tasks, or temporarily block code and are not executed by the server. Its core functions include: 1. Improve the readability of the code, which facilitates quick understanding of others and future self; 2. Supports two formats: single-line comments (// or #) and multi-line comments (//); 3. Common uses cover function descriptions, complex logic explanations, TODO markings and disable code during debugging; 4. Effective comments should avoid duplicate code, explain the reasons rather than operations, keep it concise and add version records where necessary, thereby significantly improving code maintenance efficiency.
