Collection framework summary of Java review

As the saying goes: review the old and know the new. Think about the knowledge you have learned. Even if you have learned well before, you will forget it after a long time. Therefore, I think it is very necessary to review the knowledge you have learned before. This document reviews the collection framework in Java foundation.

Why is there a collection framework?

Usually, we use arrays to store some basic data types or reference data types, but the length of the array is fixed. When the added elements exceed the length of the array, we need to redefine the array, which will make it too troublesome to write programs. Therefore, for our convenience, Java provides collection classes that can store any object, The length can be changed, increasing with the increase of elements and decreasing with the decrease of elements.

Arrays can store basic data types or reference data types. Basic data types store values, reference data types store addresses, and collections can only store reference data types (that is, objects). In fact, basic data types can also be stored in collections, but they will be automatically boxed into objects when stored.

Having a set does not mean that we should abandon the array. If the number of elements to be stored is fixed, we can use the array. When the number of elements to be stored is not fixed, we use the set.

Type of collection

Sets are divided into single column sets and double column sets. The root interface of single column collection is collection, and the root interface of double column combination is map. Both sets have set classes based on hash algorithm (HashMap and HashSet). Now we may have questions about whether double column collection is based on single column collection or single column collection is based on double column collection. Let's look at the source code of adding elements to HashMap and HashSet:

From the above source code, we can see that the add method does not appear in the put method source code of the double column set, while the add source code of the single column set can only blame the put method; We can know that single column set is based on double column set. In fact, the reason is very simple. Every time an element is added to a single column set, only a key can be added, and the key is also the unique identifier of a double column set element, and its value value is replaced and hidden by an object object. Every time it is added, the output element hides the value of the combination of single columns. The underlying layer is based on a double column set, and hiding a column is easy to achieve, If it is a single column set, it is estimated that it will be very difficult to turn it into a double column set. It is like a magician doing magic. The magician must prepare what he wants to change in advance and just hide it. However, if the magician does magic from scratch, I guess he is an immortal. He can change what he wants.

Single column set

First, let's look at the inheritance diagram of single column combination. The root interface of single column collection is collection, while the implementation classes of list are ArrayList, LinkedList and vector, and the implementation classes of set interface are HashSet and TreeSet.

Next, let's look at the functions of each set

Overview of the unique functions of the list collection

*Void add (int index, e element) / / add the element * e remove (int index) / / delete the element at the index position * e get (int index) / / get the element at the index position * e set (int index, e element) in the set and replace the element at the index position with element

Unique functions of vector class

*Public void addelement (e obj) add an element * public e elementat (int index) / / get the element * public enumeration elements() / / get the enumeration of elements (used in iterative traversal)

LinkedList class specific functions

*Public void addfirst (e e e) and addlast (e e e) / / add elements to the collection header or collection tail * public e getfirst() and getlast() / / get the header elements and get the tail elements * public e removefirst() and public e removelast() / / delete the header elements and delete the tail elements * public e get (int index)// Get index element

According to the above LinkedList functions, we can simulate the stack to obtain the data structure of the queue. The stack is first in first out and the queue is first in first out.

Next, let's look at the set set. We know that the set set storage is disordered, has no index, and cannot store duplicate objects; We need to remove the duplicate elements when using the set. If we compare equals () one by one during storage, the efficiency is low. The hash algorithm improves the efficiency of de duplication and reduces the number of times of using the equals () method. The bottom layer of HashSet is based on the hash algorithm. When HashSet calls the add method to store the object, first call the hashcode () method of the object to get a hash value, Then find out whether there are objects with the same hash value in the collection. If there are no objects with the same hash value, they will be directly stored in the collection. If there are objects with the same hash value, they will be compared with the objects with the same hash value one by one. If the comparison result is false, they will be stored, and if true, they will not be stored. The following is an example of a HashSet storing a custom object. The custom object needs to override the hashcode () and equals () methods.

The running results are shown in the figure, which achieves the purpose of not storing duplicate custom objects. In fact, there is also a linkedhashset under the HashSet. The bottom layer is implemented by a linked list. It is the only set object in the set that can guarantee how to save and how to get. It is a subclass of the HashSet to ensure the uniqueness of elements. It is the same as the HashSet principle. I won't say more here.

Finally, the TreeSet set is used for sorting. It can also ensure the uniqueness of elements. You can specify an order. After the objects are stored, they will be arranged in the specified order.

There are two implementations for specifying sorting:

Comparable: when adding custom objects to the collection, the custom objects need to implement the comparable interface,

Comparator:

Principle:

Here are some examples:

The following is a screenshot of the operation. The implementation method of CompareTo implements several conditional sorting. For details, you can see the implementation in the person user-defined class.

That's all for the single column review.

Two column set

Similarly, before reviewing the two column combination, let's look at the inheritance diagram of the two column set.

Functions of map collection:

Add function

Delete function

Judgment function

Get function

Length function

The map class collection also has three traversal methods:

Let's see how to implement the above three traversal methods

Linkhashmap is the same as linkhashset. How to save and how to get it ensures that the element is unique (key is the unique judgment value). Because the element is unique, its performance will be lower. I won't elaborate here.

Treemap is a two column set. In fact, it is very similar to TreeSet, but the key of the two column set is the unique identification, so treemap sorts the key of each element. For storing custom object sorting, it also has comparable and comparator. Let's take a look at the example below

Here, the review of the Java collection framework is basically completed. Finally, an example of landlords is given to make a comprehensive application of the collection framework, which only realizes the shuffling and licensing of landlords. As for how to play cards, the logic is complex, so there is no implementation here.

Operation screenshot:

Write at the end:

If you see here, it is estimated that you have reviewed the old and learned the new. That's it. That's all for this smelly and long article. I hope it will help you in your study, and I also hope you can support programming tips.