🎓 Do your best and obey the destiny. The blogger is studying for a master’s degree in Southeast University. He loves fitness and basketball, and is willing to share what he sees and gains related to technology. He pays close attention to the public account @flying Veal, and gets the update of the article as soon as possible

🎁 This article has been included in the “CS-Wiki” Gitee official recommended project, has accumulated 1.5K + STAR, is committed to creating a perfect back-end knowledge system, in the road of technology to avoid detours, welcome friends to come to exchange and study

🍉 If you have no outstanding projects, you can refer to a project I wrote “Open source community system Echo” Gitee official recommended project, so far has accumulated 500+ star, SpringBoot + MyBatis + Redis + Kafka + Elasticsearch + Spring Security +… And provide detailed development documents and supporting tutorials. Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo

There is no need to say more about the importance of the collection knowledge, coupled with the multithreading problem of stable interview will ask the overlord, in-depth understanding of the overall structure of the collection framework and the implementation principle of each collection class is very necessary.

As different sets adopt different data structures in implementation, there are certain differences in performance, underlying implementation and usage mode of each set, so there are a lot of knowledge points in collection, but fortunately its overall learning framework is relatively clear. This paper only introduces the knowledge system of set framework in general to help you clear your mind. After detailed analysis of key set classes, it will be divided into several articles separately.

The mind map of the whole text is as follows:

1. Why collections

When we are learning something, it is better to understand why we are using it, not just for the sake of using it.

Collection, hence the name, is used to store elements, and array also has this function, so since the emergence of collection, must be because of the use of array there are certain defects.

As mentioned briefly in the previous article, once an array is defined, its storage size cannot be changed. For example, suppose we have a class with 50 students in it. We define an array that can store information about 50 students:

1) If there are 10 transfer students in this class, the size of the array is fixed, so it is obvious that the storage capacity of the array cannot support 60 students; For example, if 20 students in this class drop out, the array actually only holds 30 students, resulting in a waste of memory space. In summary, arrays cannot dynamically adapt to changes in the number of elements because they cannot change their length once they are defined.

2) The array has the length property, which can be used to check the storage capacity of the array, that is, the length of the array, but cannot be used to directly obtain the actual number of elements stored in the array.

3) Because the array uses the storage mode of continuous space allocation in memory, we can quickly obtain the corresponding student information according to the subscript. For example, if we store a student’s student number 111 at subscript 2 in the array, we can obviously get the student number 111 by subscript 2. But what if we go the other way and want to find the subscript of student number 111? You can’t do that with an array native, which requires a variety of lookup algorithms.

4) In addition, if we want to store a one-to-one correspondence between a student’s name and home address, arrays obviously cannot do the same.

5) If we want to store some teacher information in the array used to store student information, the array will not be able to meet this requirement, it can only store elements of the same type.

In order to solve the pain points of using these arrays, the collection framework was developed. In simple terms, the main functions of collections are as follows:

  • Store an indefinite amount of data (can dynamically change the collection length)
  • Store mapped data
  • Store different types of data

Note, however, that collections can only store reference types (objects), and if you store int data (primitives), it will be automatically boxed to Integer. Arrays can store both primitive data types and reference types.

2. Overview of collection framework system

As is common with modern data structure libraries, Java collection classes separate the interface from the implementation, which resides under the java.util package. According to its storage structure set, it can be divided into two categories:

  • Single-column Collection Collection
  • Bicolumn set Map

The Collection interface

Single-column Collection Java.util. Collection: Elements exist in isolation and are stored element by element in a Collection.

Look at the inheritance architecture of the Collection interface:

The Collection interface defines some common methods for single-column collections:

public boolean add(E e); // Add the given object to the current collection
public void clear(a); // Clear all elements of the collection
public boolean remove(E e); // Delete the given object from the current collection
public boolean contains(E e); // Determine whether the current collection contains the given object
public boolean isEmpty(a); // Check whether the current collection is empty
public int size(a); // Returns the number of elements in the collection
public Object[] toArray(); // Store the elements of the collection into an array
Copy the code

Collection has two important subinterfaces, List and Set, which represent ordered and unordered collections, respectively:

1) List is characterized by orderly and repeatable elements. The so-called order here means that the order of the elements is the same as the order of the elements. For example, if we store elements in the order 11, 22, 33, we will retrieve them from the List in the order 11, 22, 33. Common implementation classes for the List interface are:

  • ArrayList: The underlying data structure is an array, which is not thread safe
  • LinkedList: the underlying data structure is a LinkedList, which is not thread safe

In addition to including all the methods of the Collection interface, the List interface also adds some special methods to manipulate collections based on element indexes:

public void add(int index, E element); // Adds the specified element to the specified position in the collection
public E get(int index); // Returns the element at the specified position in the collection
public E remove(int index); // Remove the element at the specified position in the list, return the removed element
public E set(int index, E element); // Replace the element at the specified position in the collection with the specified element
Copy the code

2) Set interface is exactly the same as Collection interface in method signature, but it has more strict definition in method description. The most important feature is that it refuses to add repeated elements, cannot be accessed by integer index, and elements are out of order. Disorder is when elements are stored in a different order than they are retrieved. Its common implementation classes are:

  • HashSet: Bottom basedHashMapImplement, adoptHashMapTo save the element
  • LinkedHashSet:LinkedHashSet 是 HashSetSubclass, and its underlying is passedLinkedHashMapTo achieve.

As for why we define an interface with identical method signatures, my understanding is to make the structure of the collection framework clearer, distinguishing single-column collections from the following two points:

  • You can add duplicate elements (List) and you can’t add duplicate elements (Set)
  • Accessible through integer indexes (List) and not accessible through integer indexes (Set)

This allows us to more accurately inherit the corresponding interface when we declare a single-column collection.

The Map interface

Two-column collection java.util.Map: Elements exist in pairs. Each element is composed of a key and a value. You can find the corresponding value by the key. Obviously, this two-column collection solves the pain of arrays not being able to store mappings. Also, it is important to note that the Map cannot contain duplicate keys; values can be repeated; And each key can only correspond to one value.

Look at the Map interface inheritance architecture diagram:

The Map interface defines some common methods for two-column collections:

public V put(K key, V value); // Add the specified key and the specified value to the Map collection.
public V remove(Object key); // Return the value of the deleted element from the Map.
public V get(Object key); // Retrieves the corresponding value in the Map collection based on the specified key.
boolean containsKey(Object key); // Determine whether the collection contains the specified key.
public Set<K> keySet(a); // Get all the keys in Map and store them in Set.
Copy the code

Map has two important implementation classes, HashMap and LinkedHashMap:

① HashMap: It can be said that HashMap does not dare to go to an interview until it is thoroughly memorized. Here is a brief introduction of its underlying structure, which will be explained in detail later. Prior to JDK 1.8, the underlying implementation of a HashMap was an array, the body of a HashMap, plus a linked list, which was primarily used to resolve hash conflicts (” zip “conflict resolution). JDK1.8 later in solving the hash conflict with the larger changes, when the chain length of the table is greater than the threshold value (the default is 8), the list into the red-black tree, in order to reduce the search time (note: the list into the red-black tree before judgment, if the current is less than 64 the length of the array, so choose to array capacity, rather than into a red and black tree).

② LinkedHashMap: a subclass of HashMap, which ensures that elements are stored in the same order as they are retrieved.

LinkedHashMap inherits from HashMap, so its underlying structure is still based on a pulled hash structure, consisting of arrays and linked lists or red-black trees. In addition, LinkedHashMap adds a two-way linked list to the above structure, allowing the above structure to maintain the insertion order of key-value pairs. At the same time, the related logic of access order is realized by the operation of linked list.

OK, we already know that a Map stores two types of objects, one is called a key and the other is called a value. There is a one-to-one correspondence between the two objects in a Map. This pair of objects is also called an Entry in a Map. Entry encapsulates the key-value pair mapping into an object, that is, a key-value pair object. The Map also provides methods for getting all Entry objects:

public Set<Map.Entry<K,V>> entrySet(); // Get a collection of all entries in the Map.
Copy the code

In the same way, Map provides a method to get the corresponding key and value of each Entry, so that we can get the corresponding key and value of each Entry as we traverse the Map collection:

public K getKey(a); // Get the key in an Entry object.
public V getValue(a); // Get the value in an Entry object.
Copy the code

Let’s take a look at two traversal modes of Map based on what we’ve learned above:

1) Traversal method 1: find the value according to the key

  • Retrieves all keys in the Map, and since keys are unique, returns a Set to store all keys. Keyset ()

  • Iterate through the Set of keys to get each key.

  • Gets the value corresponding to the key based on the key. Get (K key)

public static void main(String[] args) {
    // Create a Map collection object
    HashMap<Integer, String> map = new HashMap<Integer,String>();
    // Add elements to the collection
    map.put(1."Small five");
    map.put(2."Little red");
    map.put(3."Zhang");

    // Get all the keys get the keyset
    Set<Integer> keys = map.keySet();
    // Iterate over the key set to get each key
    for (Integer key : keys) {
        // Get the corresponding value
        String value = map.get(key);
        System.out.println(key + "："+ value); }}Copy the code

I don’t know if you noticed one detail here, but the keySet method returns Set. Maps do not implement the Iterable interface, so they cannot be iterated directly using iterators or for each loops, but they can be used when converted to sets. Read on to find out what an iterator is.

2) Traversal mode 2: key value pair mode

  • Gets all Entry pairs in the Map Set and returns them as a Set. Method tip: entrySet().

  • Iterating through the Set that contains the key-value objects yields each Entry object.

  • Gets the keys and values in each Entry object. Getkey (), getValue()

// Get all entry objects
Set<Entry<Integer,String>> entrySet = map.entrySet();

// Iterate to get each entry object
for (Entry<Integer, String> entry : entrySet) {
    Integer key = entry.getKey();
    String value = entry.getValue();  
    System.out.println(key + ":" + value);
}
Copy the code

3. Iterator

What is the Iterator

We looked at the for each loop in the previous chapter on arrays:

for(variable : collection) {
    // todo
}
Copy the code

The expression collection must be either an array or a class object that implements the Iterable interface. As you can see, the Collection interface inherits the Itreable interface, so any Collection that implements the Collection interface can use the for each loop.

Let’s click on Iterable and have a look:

It has an iterator method that returns type iterator.

Let’s go to the implementation class of the Collection and see if it implements Itreator. Open one of these, like ArrayList:

The Iterator interface is implemented as an internal class in ArrayList. And Iterator is essentially iterating over collections.

So to summarize: we can iterate through Collection elements through the Iterator interface, which is implemented as an inner class in a concrete subclass.

❓ Here’s a question. Why is the iterator not wrapped as a class, but as an interface? Let’s say the iterator is a class, so we can create objects of that class and call methods of that class to iterate through the Collection.

In fact, the Collection interface has many different implementation classes. As we mentioned at the beginning of this article, the underlying data structures of these classes are mostly different. Therefore, their storage and traversal methods are also different, so we cannot use a single class to specify the method of dead traversal. We extract the general method required for traversal, encapsulate it into the interface, and let the subclasses of Collection implement it according to their own characteristics.

After this analysis, let’s verify that the Itreator interface implemented by LinkedList and ArrayList are different:

Obviously, although these two implementation classes of Collection are the same, their internal procedures for implementing the Itreator interface are different.

Iterator is basically used

OK, now that we know that Iterator is used to iterate over collections, how does that work?

A: Iterate over!

To explain the concept of iteration: determine if there is an element in the set before fetching an element, if there is, extract the element, determine again, if there is, extract again. All the way to the point where I’ve taken everything out of my set. This method of extraction is called iteration. Hence Iterator objects are also called iterators.

That is, to iterate through the Collection, we need to get the iterator corresponding to the Collection. How do you get it? The Collection implementation Iterable contains a method called iterator

Here are some common methods used in Iterator interfaces:

public E next(a); // Returns the next element of the iteration.
public boolean hasNext(a); // Returns true if there are still elements to iterate over
Copy the code

Here’s an example:

public static void main(String[] args) {
    Collection<String> coll = new ArrayList<String>();

    // Add elements to the collection
    coll.add("A");
    coll.add("B");
    coll.add("C");
    // Get the coll iterator
    Iterator<String> it = coll.iterator();
    while(it.hasNext()){ // Determine if there are iteration elements
        String s = it.next(); // Get the iterated elementSystem.out.println(s); }}Copy the code

Of course, the same loop operation can be expressed much more simply with the for each loop:

Collection<String> coll = newArrayList<String>(); .for(String element : coll){
    System.out.println(element);
}
Copy the code

References

  • Java Core Technologies – Volume 1 Basics – 10th Edition
  • Java3y – Collection Overview: juejin.cn/post/684490…

| flying veal 🎉 pay close attention to the public, get updates immediately

  • The blogger is a master student in Southeast University. In her spare time, she runs a public account “Flying Veal”, which was opened on December 29, 2020/29. Focus on sharing computer basics (data structure + algorithm + computer network + database + operating system + Linux), Java basics and interview guide related original technical good articles. The purpose of this public account is to let you can quickly grasp the key knowledge, targeted. I hope you can support me and grow with veal 😃
  • And recommend personal maintenance of open source tutorial project: CS-Wiki (Gitee recommended project, has accumulated 1.5K + STAR), is committed to creating a perfect back-end knowledge system, in the road of technology to avoid detours, welcome friends to come to exchange learning ~ 😊
  • If you don’t have any outstanding projects, you can refer to the Gitee official recommended project of “Open Source Community System Echo” written by me, which has accumulated 500+ star so far. SpringBoot + MyBatis + Redis + Kafka + Elasticsearch + Spring Security +… And provide detailed development documents and supporting tutorials. Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo