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

This article mainly introduces "what are the Java collection frameworks". In daily operation, I believe many people have doubts about what Java collection frameworks there are. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful for you to answer the questions of "what Java collection frameworks are there?" Next, please follow the editor to study!

Without saying much, go straight to the picture above:

Java collections, also known as containers, are mainly derived from two major interfaces (Interface):

Collection and Map

As the name implies, containers are used to store data.

So the difference between the two interfaces is:

Collection stores a single element

Map stores key-value key-value pairs.

That is, single dogs are put in Collection, couple is put in Map. So where do you belong?

To learn these collective frameworks, I think there are four goals:

Make clear the correspondence between each interface and class

Familiar with common API for each interface and class

For different scenarios, you can choose the appropriate data structure and analyze the advantages and disadvantages.

Learn the design of the source code and be able to answer the interview.

The previous HashMap article on Map has been very thorough and detailed, so I won't repeat it in this article. If you haven't read the article, go to the official account and reply to "HashMap" to read the article.

Collection

Let's first take a look at the top Collection.

Collection also defines a lot of methods, which are inherited into various subinterfaces and implementation classes, and the use of these API is also common in daily work and interviews, so let's take a look at these methods first.

The collection of operations is nothing more than four categories of "add, delete, modify and query", also known as CRUD:

Create, Read, Update, and Delete.

Then I will also divide these API into these four categories:

Functional method add add () / addAll () delete remove () / removeAll () change the Collection Interface did not look up contains () / containsAll () other isEmpty () / size () / toArray ()

Let's look at it in detail:

Increase:

Boolean add (E e)

The data type passed in by the add () method must be Object, so auto-boxing auto-boxing and auto-unboxing unboxing are done when the basic data type is written.

There is another method, addAll (), that adds elements from another collection to this collection.

Boolean addAll (Collection c)

Change:

There is no direct operation to change the element in Collection Interface, anyway, delete and add can complete the change!

Check:

Check to see if there is a particular element in the collection:

Boolean contains (Object o)

Check whether set A contains set B:

Boolean containsAll (Collection c)

There are also some operations on the collection as a whole:

Determine whether the collection is empty:

Boolean isEmpty ()

Size of the collection:

Int size ()

To convert a collection into an array:

Object [] toArray ()

The above is the API commonly used in Collection.

It's all defined in the interface, and the subclasses don't have to be.

Of course, subclasses will also do some of their own implementation, so that there are different data structures.

Let's take a look at it one by one.

List

The biggest feature of List is that it is orderly and repeatable.

Look at the official website:

An ordered collection (also known as a sequence).

Unlike sets, lists typically allow duplicate elements.

This also speaks out the characteristics of Set. In contrast to List, Set is disordered and does not repeat.

There are two ways to implement List: LinkedList and ArrayList, so the most common question in the interview is how to choose these two data structures.

For this type of selection question:

One is to consider whether the data structure can perform the required functions.

If all can be done, the second is to consider which is more efficient.

It's the same with everything.

Specifically, look at the API of these two classes and their time complexity:

Functional method ArrayListLinkedList add add (E e) O (1) O (1) add add (int index, E e) O (n) O (n) remove (int index) O (n) O (n) 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)

Explain a few things:

Add (E e) is to add elements to the tail, although ArrayList may be expanded, but the average sharing complexity (amortized time complexity) is still O (1).

Add (int index, E e) is to add elements to a specific location. LinkedList needs to find this location first, and then add this element. Although the simple "add" action is O (1), it is still O (n) to find this location. (some people just think it's O (1). Just explain it to the interviewer and refuse to carry the essence.

Remove (int index) is an element on the index of remove, so

The process for ArrayList to find this element is O (1), but after remove, the subsequent elements have to move forward one bit, so the average complexity is O (n).

LinkedList also has to find the index first, and the process is O (n), so the whole is O (n).

Remove (E e) is the first element seen by remove, so

ArrayList needs to find this element first, the process is O (n), then remove it and move forward one bit, this is O (n), the total is O (n).

LinkedList also needs to be found first, this process is O (n), and then removed, this process is O (1), the total is O (n).

So what is the reason for the difference in time complexity?

A:

Because ArrayList is implemented in arrays.

The biggest difference between an array and a linked list is that the array is random access.

This feature makes it possible to get anywhere in the array with the time of the subscript O (1), while the linked list cannot and can only be traversed one by one from the beginning.

In other words, in the "change check" these two functions, because the array can be accessed randomly, so ArrayList is efficient.

What about "adding and deleting"?

If you don't consider the time it takes to find this element,

Because of the physical continuity, the array is fine at the tail when you want to add or delete elements, but elsewhere will cause the subsequent elements to move, so it is less efficient, while the linked list can easily disconnect from the next element. insert a new element or remove an old element directly.

But, in fact, you can't ignore the time it takes to find the element. And if it is operated in the tail, the ArrayList will be faster when the amount of data is large.

So say:

Recheck and select ArrayList

Add or delete the selection ArrayList at the tail

In other cases, if the time complexity is the same, ArrayList is recommended because the overhead is smaller, or memory usage is more efficient.

Vector

As the last point of List, let's talk about Vector. This is also an age exposure post, and all those who have used it are bosses.

Vector, like ArrayList, is inherited from java.util.AbstractList, and the underlying layer is also implemented in arrays.

But it has been abandoned now, because. It adds too much synchronized!

Any benefit comes at a price. The cost of thread safety is inefficiency, which can easily become a bottleneck in some systems, so now we no longer add synchronized at the data structure level, but transfer this task to us programmers.

So the interview frequently asked question: what is the difference between Vector and ArrayList? only this is not a comprehensive answer.

Let's take a look at the high ticket on stack overflow and answer:

One is the thread safety problem that I have just mentioned.

The second is the difference of how much to expand when expanding capacity.

This depends on the source code:

This is the expansion implementation of ArrayList. The arithmetic shift to the right is to move the binary of this number one bit to the right and fill the left symbol bit, but because the capacity is not negative, it is still 0. 0.

The effect of moving one bit to the right is to divide by 2, so the new capacity defined is 1.5 times the original capacity.

Let's take a look at Vector's:

Because we don't usually define capacityIncrement, it is twice as large by default.

If you answer these two points, there will certainly be no problem.

Queue & Deque

Queue is a linear data structure that goes in and out of one end; Deque is accessible at both ends.

Queue

The Queue interface in Java is a bit crappy, and generally speaking, the semantics of queues are first in, first out (FIFO).

But there is an exception here, that is, PriorityQueue, also known as heap, does not come out according to the chronological order in which it goes in, but goes out according to the specified priority, and its operation is not O (1), and the calculation of time complexity is a little complicated. We will talk about it separately later.

Well, the Queue method website [1] has been summarized. It has two sets of API, and the basic functions are the same, but:

One group will throw an exception.

The other group returns a special value.

Function throw exception return value increase add (e) offer (e) delete remove () poll () look at element () peek ()

Why would an exception be thrown?

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 return null.

So why would add (e) throw an exception?

Some Queue will have a capacity limit, such as BlockingQueue, so if it has reached its maximum capacity and will not expand, it will throw an exception; but if offer (e), it will return false.

Then how to choose?

First of all, if you want to use it, use the same group of API and unify it before and after.

Secondly, according to the demand. If you need it to throw an exception, use it to throw an exception; but you don't need to do an algorithm problem, so just choose the group that returns a special value.

Deque

Deque can be accessed at both ends. Naturally, there are operations for First and Last. There are two sets for each end. One group throws an exception and the other returns special values:

Function throws exception return value to increase addFirst (e) / addLast (e) offerFirst (e) / offerLast (e) delete removeFirst () / removeLast () pollFirst () / pollLast () see getFirst () / getLast () peekFirst () / peekLast ()

Use the same principle, if you want to use, use the same group.

These API of Queue and Deque are O (1) time complexity, exactly sharing time complexity.

Implementation class

Their implementation classes are as follows:

So,

If you want to implement the semantics of "normal queue-first-in, first-out", use LinkedList or ArrayDeque to implement

If you want to implement the semantics of "priority queue", use PriorityQueue

If you want to implement the semantics of "stack", use ArrayDeque.

Let's look at it one by one.

When implementing a normal queue, how do you choose to use LinkedList or ArrayDeque?

Let's take a look at the high ticket answer on StackOverflow [2]:

To sum up, ArrayDeque is recommended because it is efficient and LinkedList has other overhead.

So what's the difference between ArrayDeque and LinkedList?

Under the same question just now, this is what I think is the best summary:

ArrayDeque is an expandable array and LinkedList is a linked list structure.

Null values cannot be stored in ArrayDeque, but LinkedList can

ArrayDeque is more efficient in adding and deleting headers and tails, but LinkedList is O (1) only if you want to remove an element in the middle and have found it.

ArrayDeque is more efficient in terms of memory usage.

So, as long as you don't have to save the null value, choose ArrayDeque!

So if a very senior interviewer asks you, under what circumstances do you choose to use LinkedList?

A: before Java 6. Because ArrayDeque is available only after Java 6.

For the sake of version compatibility, we have to make some compromises in practical work.

Then the last question is about Stack.

Stack

Stack is semantically a linear data structure of last-in, first-out (LIFO).

There are many high-frequency interview questions are to use the stack, such as the water problem, although the optimal solution is to use double pointers, but the stack is the most intuitive solution is also need to understand, and then have the opportunity to write it.

So how do you implement the stack in Java?

Although there is a Stack class in Java, official documents say that it is not allowed to use it!

The reason is also simple, because Vector has been deprecated, and Stack inherits Vector.

So if you want to implement the semantics of Stack, use ArrayDeque:

Deque stack = new ArrayDeque ()

Set

The last Set has just said that the specificity of Set is unordered and not repeated.

It is consistent with the concept of "set" in mathematics.

There are three common implementation classes for Set:

HashSet: use Hashmap's key to store elements, the main feature is disorder, the basic operation is O (1) time complexity, very fast.

LinkedHashSet: this is a HashSet + LinkedList structure characterized by the time complexity of O (1) and the ability to retain the order of insertion.

TreeSet: uses the red-black tree structure, the characteristic is can be ordered, can use the natural sort or the custom comparator to sort; the disadvantage is that the query speed is not as fast as HashSet.

Then the underlying implementation of each Set is actually the corresponding Map:

The value is placed on the key in map, and a PRESENT is placed on the value, which is a static Object, which is equivalent to place holder, and each key points to this object.

Then the specific implementation principle, the four operations of addition, deletion, modification and search, as well as hash conflicts, hashCode () / equals () and other issues have been mentioned in the HashMap article, so I will not repeat them here. Friends who have not seen it can reply to "HashMap" in the official account background to get the article.

Summary

At this point, the study on "what are the Java collection frameworks" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.