Collection framework details and code examples

brief introduction

Differences between sets and arrays:

Arrays store basic data types, and each array can only store data of one data type, and the space is immutable.

Collections store objects. Multiple types of objects can be stored in a collection. Variable space.

Strictly speaking, a collection is a reference to stored objects, and each object is called an element of the collection. According to the different data structures during storage, it is divided into several types of sets. However, no matter what type of collection objects are stored in, since the collection can store objects of any type, these objects must be transformed upward to object type during storage, that is, the elements in the collection are objects of object type.

Since it is a set, no matter how it is divided into several categories, it has the commonality of sets, that is to say, although the data structure is different during storage, there must be some set methods. In Java, the collection interface is the root interface of the collection framework. All collection types implement this interface or inherit from its sub interfaces.

Collection interface

Depending on the data structure, some collections allow duplicate elements, while others do not. Some collections are ordered, while others are disordered.

The Java SDK does not provide classes directly inherited from collection. The classes provided by the Java SDK are all "sub interfaces" inherited from collection, such as list and set. In other words, you cannot directly new a collection object, but only a new object that implements the sub interface of the collection class, such as new arraylist();.

All collection classes must provide at least two constructors: a parameterless constructor constructs an empty collection; The constructor with the collection parameter constructs a collection containing the content of the collection. For example, ArrayList has three construction methods, two of which meet the requirements of these two construction methods.

Collection is Java Util package, so to implement the concept of collection, you need to import the package first.

ArrayList inherits from the list interface, which in turn inherits from the collection interface. In the collection stored by the ArrayList class, the elements are orderly and repeatable.

import java. util.*; Collection coll = new ArrayList();

Because the collection interface does not allow direct implementation, the collection concept needs to be implemented by implementing its subclasses. The ArrayList object created here uses the parent class reference, which has the advantage of good scalability.

Collection has some general operation methods for collections, which are divided into two categories: one is common methods; One is the method with all, which operates on collections.

Add(): inserts an element into the tail of the collection. The return value type is Boolean. If the insertion is successful, true is returned. Note that collections can only store objects (actually references to objects).

The "ABCD" and "123" inserted above are stored in the collection after being converted into objects through automatic boxing. Two of these add (123) are duplicate object elements, because the only way to determine whether the elements in the collection are duplicate is whether the equals method returns 0. Integer has overridden equals(). The latter two student objects are different objects. Because the equals () method is not overridden in the student class, they are non repeating elements.

Remove (): deletes the first element in the collection. The only way to determine whether an element can be deleted is to determine whether the objects are equal through the equals () method. True is returned only when the objects are equal.

Clear (): clear all elements in the collection. Contains (object): whether an object element is included. The judgment is still based on the equals () method.

Isempty(): whether the collection contains no elements. Size (): returns the number of elements in the collection. Equals (object obj): compares whether two sets are exactly equal. The basis is that all elements in the set can get equal comparison through their respective equals. Addall (collection C): adds the elements in the entire collection C to the collection. Containsall (collection C): whether the collection contains all elements in the C collection, that is, whether the collection C is a subset of the collection. Remove all (collection C): delete the elements in the collection that are also included in the C collection. That is, delete the intersection elements of the set and C set. Retain all (collection C): in contrast to removeAll (), only the elements in the intersection of the collection and collection C are retained. Iterator (collection C): returns the iterator in this collection. Note that the return value type is iterator. Iterators are used to traverse collections. See below.

Iterator general iterator

Because different types of collections have different data structures when storing data, it is unrealistic to write a general method of traversing collections. However, no matter what type of collection, only the collection itself knows the elements in the collection best. Therefore, when implementing the collection interface, different collection classes implement their own unique traversal methods, which is called the iterator of the collection. In fact, collection inherits Java Lang. Iterable interface, which only provides one method: iterator (). As long as the class that implements this interface has the ability of iteration, it also has the ability of foreach to enhance traversal.

The iterator itself is an interface, and the iterator of the corresponding collection type can be obtained through the iterator () method of the collection object. For example:

Collection coll = new ArrayList(); Iterator it = coll. iterator(); // Gets the iterator of the collection of the corresponding type

The iterator interface provides three methods:

Hasnext(): judge whether there is a next element. Next (): get the next element. Note that it returns an object (generic type is not considered for the time being). Remove (): removes the last element returned by the iterator. This method is the only safe way to modify elements during collection iterations.

Although there are different types of sets, the iterative method of iterators is general. For example, you want to traverse the elements in the coll collection.

But generally speaking, although the above traversal method is correct, the following traversal method is better. Because the IT object is only used for collection traversal and should disappear after traversal, it is placed inside the for loop. Since the third expression of the for loop is missing, it can continuously loop the second expression.

for (Iterator it = coll.iterator(); it. hasNext();) { System.out.println(it.next()); }

The element traversed by iterator is an object in the collection, and the object also has attributes. How do I reference these properties? You only need to use the traversed elements as objects, but because the elements returned by next () are object objects, you can't obtain the unique attributes in the corresponding elements by directly operating this element object. Therefore, you must first force object type conversion.

For example, get the name attribute of the student object element in coll, and delete the element of the non Student object.

Because there are some non Student object elements in the collection, you need to judge it Whether next() meets the requirements of instanceof, but cannot be directly written as the following code:

Because every time you execute it Next (), the cursor pointer of the element slides down 1. In this writing, it is used once in the if judgment expression Next (), it is called again in the code block of if next()。 So it should be Save next() to the object variable. And it The type returned by next() is object type, so object obj = it is defined next()。

Only the remove () method is safe to modify collection elements during iteration of the iterator iterator. Take add () during iteration as an example. When the iteration starts, the iterator thread obtains the number of elements in the collection. When add () is executed during the iteration, it will use another thread to execute (because the add () method is not provided by the iterator interface). As a result, the number of elements increases, and the newly added elements cannot be determined whether they should be used as an element of the iteration. This is unsafe behavior, so a concurrentmodificationexception will be thrown. The remove () method is the iterator's own method. It uses the iterator thread to execute, so it is safe.

For the list class collection, the sub interface listiterator of iterator can be used to realize safe iteration. This interface provides many methods to add, delete, modify and query the list class collection.

List interface

The list interface implements the collection interface.

The data structure characteristics of the list interface are:

1. Ordered list with index. The so-called order refers to the order of insertion, that is, the order determined by index. Inserting data into the set will be disrupted 2 Variable size. 3. The data can be repeated. 4. Because of its order and variable size, it not only has the characteristics of collection, but also has the ability to accurately add, delete, modify and query an element according to the index. 5. The two common classes that implement the list interface are: (1) ArrayList: an ordered list of array structures; 1). The length is variable because some subscripts are reduced by one or increased by one when reducing or adding elements. If the allocated array space is not enough, create a new larger array and copy the memory of the original array (the direct memory copy speed is very fast); 2). Fast query speed and slow addition and deletion speed. The fast query is because the memory space is continuous, and the slow addition and deletion is because the subscript moves. 3). Except that ArrayList is an asynchronous list, it almost replaces the vector class. (2). LinkedList: an ordered list of linked list structures; 1). Out of synchronization; 2). Fast addition and deletion speed and slow query speed. The reason for the fast addition and deletion is that you only need to modify the index points of the front and rear elements in the linked list; 3). Stack (LIFO, last in first out), queue (usually FIFO, first in first out) and double ends queue can be realized.

The methods of the ArrayList class are basically the same as those of the list method, so it is not necessary to introduce ArrayList since the general methods of list and listiterator are introduced below. However, LinkedList is special, so it is introduced independently.

List interface general method

In addition to the general methods inherited from collection, the list interface also has its own general methods. These general methods of general list are aimed at the concept of sequence. With sequence and subscript index values, you can accurately manipulate elements at a certain position, including addition, deletion, modification and query.

(1). Add: add (index, element) (2) Delete: remove (index), remove (obj) deletes the first obj element (3) in the list Change: set (index, element) (4) Check: get (index) (5) Indexof (obj): returns the index value of the obj element in the list for the first time. If it does not exist, it returns - 1 (6) lastIndexOf(obj) (7). Sublist (start, end): returns the list of elements from start to end (excluding the end boundary) in the list. Note that the list type is returned. (8). Listiterator(): returns the iterator listiterator of the list class collection traversed from the beginning. (9). Listiterator (index): returns the list traversed from the index position, combined with the iterator listiterator. Because of the get () method, in addition to iterator iteration, you can also use the get () method to traverse the collection:

But note that this method is not safe, because L. size () changes immediately. If you add or delete elements, size () will also change.

Example:

In the above code, if ls add(new Student("Malong4",24)); If the annotation of is cancelled, an exception will be thrown because the method of the only safe operation element in the iterator iterator is remove() provided by the iterator interface, and the add() method is provided by the list interface, not the iterator interface. However, for the list collection class, you can use the listiterator iterator, which provides more methods for manipulating elements. Because it is the method provided by the iterator, they are safe when manipulating elements.

Iterator listiterator for the list collection

The listiterator iterator can be obtained through the listiterator () method. The iterator interface provides the following methods:

Hasnext(): whether there is a next element hasprevious(): whether there is a previous element for backward traversal. Next(): get the next element previour(): get the previous element for backward traversal. Add (element): insert an element. Note: This is add () provided by iterator, not add () provided by list. Remove (): remove the elements obtained by next () or previous (). Note: This is the remove() provided by the iterator instead of the remove() set (element) provided by the list: set the element obtained by next() or previour(). Note: This is set () provided by iterator, not set () provided by list

For example, the previous example threw an exception when adding elements using add() of list during iterator iteration. Here, use listiterator iteration instead and add elements using the add() method provided by listiterator.

LinkedList collection

The data structure of the LinkedList class is a collection of linked list classes. It can realize the data structure of stack, queue and double ended queue. In fact, these data structures are implemented according to different logic through the methods provided by LinkedList.

Several of the methods provided are as follows: because the list interface is implemented, in addition to the following methods, the methods of the list interface are available.

Addfirst (element): insert an element into the head of the linked list. Addlast (element): insert an element into the tail of the linked list. Getfirst(): get the first element of the linked list. Getlast(): get the last element of the linked list. Removefirst(): remove and return the first element. Note that the returned element is removelast(): remove and return the last element, Note that the element LinkedList is returned to simulate the queue data structure

Queue is the data structure of FIFO. The encapsulated queue class myqueue code is as follows:

The program code for operating the queue data structure is as follows:

Set interface

The set interface also implements the collection interface. Since it can be classified separately, its data structure must be very different from that of the list set.

The data structure characteristics of the set interface are:

1. The elements in the set are out of order. The disorder here is relative to list. The order of list indicates the order with subscript index, while set does not need to mean that there is no order without index. 2. The elements in the set cannot be repeated. 3. Because of disorder, there is only one method to get elements from the set: iteration. 4. The two common classes that implement the set interface are: (1) HashSet: hash table data structure; 1). Out of synchronization; 2). Fast query speed; 3). The only way to judge whether the elements are repeated is to call hashcode () to judge whether the objects are the same, and then call the equals () method to judge whether the contents are the same. Therefore, to store elements in the collection of this data structure, hashcode () and equals () must be overridden. (2). TreeSet: binary tree data structure; 1). Binary tree is used to sort, so the elements in the set are ordered. This order is different from the order concept of list. The order here refers to sorting the elements during storage, such as alphabetical order, number size order, etc., rather than index order. 2). Since you want to sort, the equals () method can only judge whether it is equal. Therefore, you need to be able to judge the size when storing data in the TreeSet set. 3). There are two methods to construct an ordered TreeSet set: a. the class of the object to be stored implements the comparable interface and rewrites its CompareTo () method; b. Specify a comparator when constructing the TreeSet collection. The comparator needs to implement the comparator interface and override the compare () method. (3). Linkedhashset: a HashSet in the form of a linked list. Only the linked list index is added to the HashSet. Therefore, such collections are linked and HashSet. However, this collection type is rarely used.

HashSet collection

There is nothing to explain the usage of HashSet. Methods are inherited from set and then from collection. What needs to be explained is its disorder, non repeatability, the method of calculating hash value and the method of judging repeatability.

The result is unordered and the elements are not repeatable:

Here, the method to judge whether a string object is repeated is to call hashcode () of string to judge. If it is the same, then call the equals () method of string. The hashcode () method of string calculates the hash value according to each character, and the operation results of the same character at the same character position are the same.

Therefore, among the above string objects, the hash operation results of the substring part of the prefix "ABCD" are the same, and the last character determines whether these string objects are the same. There are two "ABCD1" during insertion, so the equals () method of string is called once in total.

If you are storing custom objects, such as student objects, the object is defined as follows:

Even if equals () is overridden, it will be considered not to be repeated when inserting a student object with the same attribute into the HashSet.

result:

This is because the bottom layer of the hastset set set first calls the student's hashcode () method, and the student does not override this method, but inherits from the object. Therefore, the hashcode () of each object is different and is directly inserted into the set.

Therefore, you need to override student's hashcode () method. The following is an override method:

If "age * 31" is not added, the hash value of the name part may be the same, but it is likely that it is not the same student object, so the age attribute should be added as a part of the element for calculating the hash value. However, you cannot add age directly, because it will cause the hashcode of "new student (" lisi3 ", 23)" and "new student (" lisi2 ", 24)" to be the same (3 + 23 = 2 + 24). Therefore, you need to make some modifications for age, such as multiplying an integer other than 0 and 1.

After rewriting hashcode () in student and inserting the following student objects, you can judge whether it is the same student element relatively accurately.

result:

Linkedhashset collection

Compared with HashSet, a HashSet set with linked list order only needs to record one more linked list index, which ensures that the storage order and insertion order are the same. The implementation method is the same everywhere except that the new object is different from HashSet.

result:

TreeSet set

The TreeSet collection stores elements in a binary tree data structure. Binary tree ensures that elements are ordered and unique to each other. Therefore, the core of implementing TreeSet set lies in the comparison between objects.

There are two ways to compare objects: one is to implement the comparable interface in the object class and rewrite the CompareTo () method; The second is to define a comparator for object comparison. The way to implement this comparator is to implement the comparator interface and rewrite the compare () method. The comparison method provided by the comparable interface is called natural order. For example, letters are in dictionary order and values are in numerical order.

Either way, each element to be inserted needs to be transformed into comparable. After determining the node location to be stored in the binary tree, it needs to be transformed into object and stored in the collection.

Insert a string class object.

Since string has overridden CompareTo (), there is no problem inserting string objects into the TreeSet collection.

However, the above "t.add (23)" cannot be uncommented. Although the integer class also rewrites compareto(), when inserting these integer class elements, the elements of string class already exist in the collection. The comparison methods of compareto() of string class and compareto() of integer are different, making it impossible to compare the sizes between the two types of elements, It is impossible to determine which node of the binary tree the elements of the numerical class are inserted into.

Insert a custom object that implements the comparable interface and overrides compareto(). For example, if the CompareTo () method of Student object is not overridden, an exception will be thrown, indicating that it cannot be transformed into comparable.

t.add(new Student("Malongshuai1",23));

result:

Therefore, when modifying student to override CompareTo (), you should consider which is the primary sorting attribute and which is the secondary sorting attribute. For example, name is the primary sorting attribute and age is the secondary sorting attribute. If compareto() returns a positive number, it means greater than; if it returns a negative number, it means less than; if it returns 0, it means equal to. As follows:

Therefore, when inserting students, they will be based on the alphabetical order in name. If they are the same, they will be based on the size order of age. Finally, if they are the same, the elements are considered to be repeated and should not be inserted into the collection.

result:

Sorting is implemented using the comparator comparator. At this time, the construction method of TreeSet is TreeSet (comparator COMP). When a comparator is used, the comparator is used by default to compare elements when inserting data.

The comparator is an implementation of Java util. Comparator interface and rewrite the class of compare () method. You can create different comparators according to different comparison requirements. For example, create a comparator sortbyage with age as the primary sorting attribute and name as the secondary sorting attribute. Since this comparator is used to compare the size of student objects, it must be transformed into student first.

Specify the comparator of TreeSet as sortbyage, and insert some student objects:

When a comparator is specified for the TreeSet collection, the results will be sorted first by age and then by name, although the compareto() method is still overridden in the student class:

summary

The above is all about the detailed explanation of the Collections Framework and code examples in this article. I hope it will be helpful to you. Interested friends can continue to refer to this website:

Detailed explanation of list in Java collection

Explain the thread safety of various collections of Java in detail

LinkedHashMap of Java collection framework source code analysis