Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

1. Introduction to collection framework

A collection can be thought of as a container for storing object information. All collection classes are located under the java.util package.

The Java Collections Framework (JCF) is a unified and standard architecture for representing and manipulating Collections. Any collection framework consists of three big pieces: the external interface, the implementation of the interface, and the algorithm to operate on the collection.

  • Interface: Is an abstract data type that represents a collection. For example, Collection, List, Set, and Map. Multiple interfaces are defined to manipulate collection objects in different ways
  • Implementation (class) : Is a concrete implementation of the collection interface. In essence, they are reusable data structures, such as ArrayList, LinkedList, HashSet, HashMap.
  • Algorithms: Useful calculations performed by methods in objects that implement the collection interface, such as searching and sorting. These algorithms are called polymorphic because the same method can have different implementations on similar interfaces.

The entire collection framework is designed around a set of standard interfaces. You can directly use the standard implementations of these interfaces (implementation classes), such as LinkedList, HashSet, and TreeSet, or you can implement your own collections through these interfaces.

The set framework system is shown in the figure:

The Java Collections framework consists of two main types of interfaces: collections, which store a Collection of elements, and Maps, which store key/value pair mappings.

2. Apis involved in the collection framework

Java collections can be divided into two systems: Collection and Map.

The Collection interface: Collection is the most basic Collection interface. A Collection represents a group of objects, that is, the elements of a Collection. Java does not provide classes that directly inherit from a Collection, but only subinterfaces (such as List and set) that inherit from a Collection.

  • List interface: The List interface is an ordered Collection with precise control over where each element is inserted. Elements in the List can be accessed by index (element position in the List, similar to the subscript of an array). The index of the first element is 0, and the same element is allowed. The List interface stores a List of repeatable, ordered (insert order) objects.
  • Set interface: A Set has exactly the same interface as a Collection, except that the behavior is different. Sets do not hold duplicate elements. The Set interface stores an unrepeatable, unordered Set of objects.

Map interface: The Map interface stores a set of key-value objects and provides mapping from key to value.

Collection interface inheritance tree: Solid lines represent inheritance and dotted lines represent implementation classes

Map interface inheritance tree: Solid line indicates inheritance, dotted line indicates implementation

3. Use of Collection interface

3.1 common methods in Collection interface

Method description and test code are as follows:

Add (Object e) to add element e to the collection

AddAll (Collection,coll1) moves elements from coll1 to the current Collection. Coll1 is empty after the move

Size (), gets the number of elements in the collection

IsEmpty () to determine whether the current collection isEmpty

Clear () to clear the elements in the collection

// Take ArrayList, the implementation class of the Collection interface
Collection coll = new ArrayList();
 //add(Object e) to add element e to the collection
 coll.add("AA");
 coll.add(123);
 coll.add(new Date());

 //size(), gets the number of elements in the collection
 System.out.println(coll.size());/ / 3

 Collection coll1 = new ArrayList();
 coll.add(456);
 coll.add("CC");
 //addAll(Collection,coll1), add elements from coll1 to the current coll1,coll1 will be empty
 coll.addAll(coll1);/ / 5

 System.out.println(coll.size());
 System.out.println(coll);//[AA, 123, Tue Oct 05 21:20:16 CST 2021, 456, CC]
 System.out.println(coll1);/ / []

 //isEmpty() to determine whether the current collection isEmpty
 System.out.println(coll.isEmpty());//false

//clear() to clear the elements in the collection
 coll.clear();
 System.out.println(coll.isEmpty());//true
Copy the code

Contains (Object obj), determines whether the Object obj is in the current collection. Equals () of the Object obj class is called to determine this

ContainsAll (Collection<> coll1) checks whether all the elements in coll1 are in the current Collection

Custom classes:

package collection;

import java.util.Objects;

public class Person {
    private String name;
    private int age;

    public Person(a) {}public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName(a) {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge(a) {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString(a) {
        return "Person{" +
                "name='" + name + '\' ' +
                ", age=" + age +
                '} ';
    }


    // Override equals
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null|| getClass() ! = o.getClass())return false;
        Person person = (Person) o;
        returnage == person.age && Objects.equals(name, person.name); }}Copy the code

Test code:

Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
// Add obj objects to the collection, requiring the obj class to override equals()
coll.add(new Person("wanli".3));


//contains(Object obj), checks whether the Object obj is in the current collection. Equals () of the Object obj class is called when checking
System.out.println(coll.contains("DD"));//true
System.out.println(coll.contains(new String("EE")));//true
System.out.println(coll.contains(new Person("wanli".3)));//true


Collection coll1 = Arrays.asList(123.456);
//containsAll(Collection<> coll1) checks whether all the elements in coll1 are in the current Collection
System.out.println(coll.containsAll(coll1));
Copy the code

Remove (Object obj), removes the obj element from the current collection

RemoveAll (Collection<> coll1) removes elements from the coll1 Collection from the current Collection

Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
coll.add(new Person("wanli".3));

//remove(Object obj) to remove the obj element from the current collection
System.out.println(coll.remove(456));//true
System.out.println(coll.remove(789));//false
System.out.println(coll.remove(new Person("wanli".3)));//true
System.out.println(coll);//[123, false, EE, DD]
//removeAll(Collection<> coll1) to remove elements from coll1 from the current Collection
Collection coll2 = new ArrayList();
coll2.add("DD");
System.out.println(coll.removeAll(coll2));//true
System.out.println(coll);//[123, false, EE]
Copy the code

RetainAll (Collection<> coll1), gets the intersection of the current Collection and coll1 and returns it to the current Collection

Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
// Add obj objects to the collection, requiring the obj class to override equals()
coll.add(new Person("wanli".3));

Collection coll1 = Arrays.asList(123.456);
//retainAll(Collection<> coll1), retrieves the intersection of the current Collection and coll1 and returns it to the current Collection
System.out.println(coll.retainAll(coll1));//true
System.out.println(coll);/ / [123, 456]
Copy the code

Equals (Object obj) compares the equality of the specified Object to the collection

    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add(false);
    coll.add(new String("EE"));
    coll.add("DD");
    coll.add(new Person("wanli".3));

    Collection coll1 = new ArrayList();
    coll1.add(123);
    coll1.add(456);
    coll1.add(false);
    coll1.add(new String("EE"));
    coll1.add("DD");
    coll1.add(new Person("wanli".3));
    //equals(Object obj) compares the specified objects to the collection
    System.out.println(coll.equals(coll1));//true
Copy the code

HashCode (), which prints the hash value of the current object

ToArray () converts the current collection to an array

Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
coll.add(new Person("wanli".3));

//hashCode(), which prints the hash value of the current object
System.out.println(coll.hashCode());

//toArray(), which converts the current collection to an array
Object[] arr = coll.toArray();
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}
// An array is converted to a collection
List<String> strings = Arrays.asList(new String[]{"AA"."BB"."CC"});
System.out.println(strings);//[AA, BB, CC]
Copy the code

3.2 Traversing the Collection

3.2.1. Use Iterator to iterate over the Collection

Iterator Indicates an Iterator interface

Lterator objects are called iterators (a type of design pattern) and are used primarily to iterate over elements in a Collection. GOF defines the iterator pattern as providing a way to access elements of a container object without exposing the inner details of the object. The iterator pattern is built for containers.

The Collection interface inherits the java.lang.ilterable interface, which has an iterator() method. All Collection classes that implement the Collection interface have an iterator() method that returns an object that implements the Lterator interface.

The Lterator is only used to traverse collections. The Lterator body does not provide the ability to load objects. If you need to create an Lterator object, you must have an iterated collection.

Each call to the iterator() method results in a new iterator object. The default cursor precedes the first element of the collection.

Methods of the Iterator interface

HasNext (), returns true if the iteration has more elements.

Next (), returns the next element in the iteration.

HasNext () must be called to check before calling the next() method. If not called and the next record is invalid, calling next() directly throws NoSuchElementException.

Remove () to remove the last element returned by this iterator from the underlying collection (optional operation).

Iterator Iterator through the Collection code instance

Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
coll.add(new Person("wanli".3));

// Create an iterator object
Iterator iterator = coll.iterator();

while (iterator.hasNext()){
    System.out.println(iterator.next());
}
Copy the code

Test the remove() method

Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
coll.add(new Person("wanli".3));

Iterator iterator = coll.iterator();
while (iterator.hasNext()){
    Object next = iterator.next();
    if ("EE".equals(next)){
        // Remove the elementiterator.remove(); }}// iterate over the collection
iterator = coll.iterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
}
Copy the code

Note:

  • The lterator can remove elements of a collection, but only through the iterator object’s remove method during traversal, not the collection object’s remove method.

  • If next() has not been called yet or if the remove method has been called since the last time next was called, a call to remove is reported as llegalStateException.

3.2.2 forEach loops through the collection

Java 5.0 provides foreach loops to iteratively access collections and arrays.

Traversal does not need to get the length of the Collection or array, and does not need to use indexes to access elements.

The underlying call to Iterator to iterate through the collection completes the operation.

Foreach can also be used to iterate over groups of numbers.

ForEach loop through the collection code example:

Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
coll.add(new Person("wanli".3));

for (Object obj : coll) {
    System.out.println(obj);
}
Copy the code

4. List interface

List Interface Overview

Given the limitations of arrays in Java for storing data, we often use lists instead.

The elements of the List collection class are ordered and repeatable, and each element in the collection has its corresponding sequential index.

List Each element in the container corresponds to an integer sequence number to record its position in the container. You can access the elements in the container according to the sequence number.

The List implementation classes in JDKAPI are ArrayList, LinkedList, and Vector.

4.1. The List interface is commonly used to achieve class comparison

ArrayList, LinkedList, and Vector:

  • Same: The three classes all implement the List interface and store data in the same way: store ordered and repeatable data.

  • Vision:

    • ArrayList: is the main implementation class of List interface. It is not thread safe and efficient. The bottom layer uses Object[] storage
    • LinkedList: if you want to insert and delete frequently, it is efficient to use this type, and the underlying storage is two-way LinkedList
    • Vector: is an older implementation of the List interface. It is thread-safe and inefficient and uses Object[] storage at the bottom

4.2 ArrayList source code analysis (JDK1.8)

// The initial capacity of the default array element
private static final int DEFAULT_CAPACITY = 10;

// A shared empty array instance for the empty instance
private static final Object[] EMPTY_ELEMENTDATA = {};

// A shared empty array instance of an empty instance of default size. We separate this from EMPTY_ELEMENTDATA to see how much expansion is required when the first element is added
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//ArrayList is the array buffer in which the elements are stored. The capacity of the ArrayList is the length of the array buffer. When the first element is added, any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY.
transient Object[] elementData;
Copy the code

No-parameter structure:

public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

The no-argument construct initializes an empty array, and the array size is initialized to 10 only after the first add.

The add () method:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Check the list capacity. If it is insufficient, increase the capacity by 1. The first time add size is 0
    // place the element e at size and size++
    elementData[size++] = e;
    return true;
}
Copy the code

EnsureCapacityInternal (int minCapacity) : minCapacity: minimum capacity required

// Add minCapacity to 1 for the first time.
private void ensureCapacityInternal(int minCapacity) {
    // Check whether the array needs to be expanded
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
Copy the code

CalculateCapacity (Object[] elementData, int minCapacity) :

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // If it is the first time to add, elementData and DEFAULTCAPACITY_EMPTY_ELEMENTDATA are empty
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // return the maximum number, DEFAULT_CAPACITY = 10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // The minCapacity is 10
    return minCapacity;
}
Copy the code

EnsureExplicitCapacity (int minCapacity) :

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // When you add for the first time, minCapacity is 10 and elementData.length is 0
    if (minCapacity - elementData.length > 0)
        // Enter the capacity expansion method
        grow(minCapacity);
}
Copy the code

Grow (int minCapacity) : a key method for automatic capacity expansion

private void grow(int minCapacity) {
    // Get the capacity of the current array
    int oldCapacity = elementData.length;
    // Get the capacity of the expanded array. The new array is 1.5 times the size of the previous one
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // If the capacity after expansion is still smaller than the required minimum capacity
    if (newCapacity - minCapacity < 0)
        // Expand the capacity again to the minimum size required. When the first add is made, the initial capacity of the array is defined here
        newCapacity = minCapacity;
    // If the capacity after expansion exceeds the threshold, the system allocates large capacity
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // The size of the new array is determined, copy the array, copyof(original array, new array length)
    elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code

4.3 Common methods of List interface

Method description:

Void add(int index, object ele): Insert ele at index position

Boolean addAll(int index,Collection eles): Adds all elements from eles starting at index

Object get(int index): Gets the element at the specified index position

Int indexOf(Object obj): Returns the position where obj first appears in the set, or -1 if not

Int lastIndexOf(object obj): Returns the position of the last occurrence of obj in the current set, or -1 if not

Object remove(int index): Removes the element at the specified index position and returns the element

Object set(int index, Object ele): Sets the element at the specified index position to ele

List subList(int fromIndex, int toIndex): Returns a subset of positions from fromIndex to toIndex, fromIndex closed and toIndex open.

Code test:

ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("wanli".3));

System.out.println(list);//[123, 456, AA, Person{name='wanli', age=3}]


//void add(int index, object ele
list.add(2."BB");
System.out.println(list);// [123, 456, BB, AA, Person{name='wanli', age=3}]


// Boolean addAll(int index,Collection eles): addAll elements from eles starting at index
List<Integer> list1 = Arrays.asList(1.2.3);
list.addAll(3,list1);
System.out.println(list);//[123, 456, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]


//object get(int index): Gets the element at the specified index position
System.out.println(list.get(2));//BB



list.add(2."AA");
System.out.println(list);//[123, 456, AA, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]
//int indexOf(Object obj): Returns the position where obj first appears in the set
System.out.println(list.indexOf("AA"));/ / 2
//int lastIndexOf(object obj): Returns the last occurrence of obj in the current set
System.out.println(list.lastIndexOf("AA"));/ / 7


//Object remove(int index): Removes the element at the specified index position and returns the element
System.out.println(list);[123, 456, AA, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]
System.out.println(list.remove(1));/ / 456
System.out.println(list);[123, AA, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]
//System.out.println(list.remove(789)); / / if the element is not present, the abnormal IndexOutOfBoundsException


//Object set(int index, Object ele): set the element at the specified index position to ele, return the original element at the specified index position
list.set(0.333);
System.out.println(list);//[333, AA, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]


//List subList(int fromIndex, int toIndex) subList(int fromIndex, int toIndex)
System.out.println(list);//[333, AA, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]
System.out.println(list.subList(1.4));//[AA, BB, 1]
Copy the code

Go through the List

ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");

Iterator iterator = list.iterator();

// Iterator: Iterator
while(iterator.hasNext()){
    System.out.println(iterator.next());
}

// forEach
for (Object obj: list) {
    System.out.println(obj);
}

// For loop
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));

Copy the code

5. Set interface

Set Interface Overview

The Set interface is a subinterface of Collection, and the Set interface provides no additional methods.

A Set cannot contain identical elements. If you try to add two identical elements to the same Set, the addition fails.

Set determines whether two objects are the same not by using the == operator, but by equals().

The difference between Set and List

1. The Set interface instance stores unordered, non-repeating data. The List interface instance stores ordered, repeatable elements.

2, Set retrieval efficiency is low, delete and insert efficiency is high, insert and delete will not cause element position change < implementation class has HashSet,TreeSet>.

3. Lists, like arrays, can grow dynamically, depending on the actual size of the stored data. Find the elements with high efficiency, low insert removing efficiency, because can lead to other elements position change < ArrayList implementation class, LinkedList, the Vector >.

5.1 Commonly used Set interface implementation class comparison

Set implementation class HashSet introduction

HashSet is a typical implementation of the Set interface, and is used most of the time when working with sets. A HashSet uses the Hash algorithm to store the elements of a collection, so it has good access, find, and delete performance.

HashSet has the following characteristics:

  • The order of elements cannot be guaranteed
  • Hashsets are not thread-safe
  • Collection elements can be null

A HashSet is unordered, that is, the order of the inserts is not recorded.

The criteria for determining the equality of two elements in a HashSet is that two objects are compared to each other using the hashCode() method and that their equals() method returns equal values.

For objects stored in a Set, the corresponding class must override the equals() and hashCode(Objectobj) methods to implement the object equality rule. That is, “Equal objects must have equal hash codes”.

Set implementation class LinkedHashSet introduction

LinkedHashSet is a subclass of HashSet

LinkedHashSet determines where elements are stored based on their hashCode value, but it also maintains the order of elements using a two-way linked list, which makes them appear to be stored in insertion order.

LinkedHashSet has slightly lower insert performance than HashSet, but good performance when iteratively accessing all elements in a Set.

LinkedHashSet does not allow collection elements to be repeated.

TreeSet introduction to the Set implementation class

TreeSet is an implementation class of the SortedSet interface. TreeSet ensures that collection elements are in sorted state.

The underlying TreeSet uses a red-black tree structure to store data

TreeSet can sort by the specified properties of the added objects

TreeSet has two sorting methods: natural sorting and custom sorting. By default, TreeSet uses natural sorting.

5.2 Understand the disorder and unrepeatability of Set

Take HashSet as an example.

disorder

        HashSet set = new HashSet();
        set.add(123);
        set.add(798);
        set.add(new Person("wanli".3));
        set.add(456);

        Iterator iterator = set.iterator();

        while (iterator.hasNext()){
            System.out.println(iterator.next());
Person{name='wanli', age=3} 123 798 */
        }
Copy the code

Unordered: Data stored in the underlying array is not added in the order of the array index, but is determined by the hash value of the data.

nonrepeatability

Create an entity class

public class User {
    private String name;
    private int age;
    
    public User(a){}public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName(a) {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge(a) {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString(a) {
        return "User{" +
                "name='" + name + '\' ' +
                ", age=" + age +
                '} '; }}Copy the code

Example code:

    @Test
    public void test1(a){

        HashSet set = new HashSet();
        set.add(123);
        set.add(798);
        set.add(new User("wanli".3));
        set.add(new User("wanli".3));
        set.add(456);

        Iterator iterator = set.iterator();

        while(iterator.hasNext()){ System.out.println(iterator.next()); }}Copy the code

In the above code, we add two User objects to the HashSet to see the result:

Both User objects are printed because the Set can only store non-repeatable elements, indicating that the two User objects are not duplicated.

The criteria for determining the equality of two elements in a HashSet is that two objects are compared to each other using the hashCode() method and that their equals() method returns equal values.

The User implementation overrides the equals() and hashCode(Object obj) methods:

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null|| getClass() ! = o.getClass())return false;

    User user = (User) o;

    if(age ! = user.age)return false;
    returnname ! =null ? name.equals(user.name) : user.name == null;
}

@Override
public int hashCode(a) {
    intresult = name ! =null ? name.hashCode() : 0;
    result = 31 * result + age;
    return result;
}
Copy the code

Note: For objects stored in a Set, the corresponding class must override the equals() and hashCode(Object obj) methods to implement the Object equality rule.

To see the results again:

Non-repeatability: Ensure that added elements cannot return true when checked by equals(). That is, only one of the same elements can be added to the Set.

The process of adding elements to a HashSet

When we add element A to a HashSet, we first call the hashCode() method of element A’s class to calculate the hash value of element A. The hash value then uses some algorithm to calculate the location in the underlying array of the HashSet (i.e. the index position).

Check if there are already elements at this position:

  • If there are no other elements at this location, element A is added successfully.

  • If there are other elements B (or multiple elements in a linked list) in this position, then compare the hash value of element A to element B:

    • If the hash value is different, element A is added successfully.
    • If the hash value is the same, then call the equLas() method of element A’s class: return true, add failed, return false, add succeeded

    When element A is successfully added to the array index of an existing element, element A is stored in a linked list with the data that already exists at the specified index location. Storage mode: JDK7 head plug method, JDK8 tail plug method

5.3 Natural and customized ordering of TreeSet

Adding an element to a TreeSet requires that the object to which the element is added be of the same type.

The default implementation of natural sorting:

@Test
public void test(a){
    // Add an Integer object
    TreeSet set = new TreeSet();
    set.add(23);
    set.add(12);
    set.add(5);
    set.add(62);
    set.add(45);
    Iterator iterator = set.iterator();
    while (iterator.hasNext()){
        System.out.println(iterator.next());
    }

    // Add a String object
    TreeSet set1 = new TreeSet();
    set1.add("CC");
    set1.add("BB");
    set1.add("TT");
    set1.add("EE");
    set1.add("AA");

    Iterator iterator1 = set1.iterator();
    while(iterator1.hasNext()){ System.out.println(iterator1.next()); }}Copy the code

View the run result:

By default, TreeSet uses natural sorting.

Natural sorting of custom class implementations

Inherit the Comparable interface in the User entity class and rewrite the compareTo method:

package collection;

public class User implements Comparable{
    private String name;
    private int age;

    public User(a){}public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName(a) {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge(a) {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString(a) {
        return "User{" +
                "name='" + name + '\' ' +
                ", age=" + age +
                '} ';
    }


    // Sort by name from smallest to largest
    @Override
    public int compareTo(Object o) {
        if (o instanceof User){
            User user = (User) o;
            return this.name.compareTo(user.name);
        }else {
            throw new RuntimeException("Type exception cannot be compared"); }}}Copy the code

Test code: Add the User object to the TreeSet collection

    @Test
    public void test(a){

        TreeSet set = new TreeSet();
        set.add(new User("wanli".23));
        set.add(new User("shengming".14));
        set.add(new User("taoxian".36));
        set.add(new User("bimo".12));
        set.add(new User("neihan".35));

        Iterator iterator = set.iterator();
        while(iterator.hasNext()){ System.out.println(iterator.next()); }}Copy the code

View the run result:

Put two User objects of the same name and different ages into the TreeSet collection of the test code:

@Test
public void test(a){

    TreeSet set = new TreeSet();
    set.add(new User("wanli".23));
    set.add(new User("shengming".14));
    set.add(new User("taoxian".36));
    set.add(new User("bimo".12));
    set.add(new User("neihan".35));
    set.add(new User("neihan".46));

    Iterator iterator = set.iterator();
    while(iterator.hasNext()){ System.out.println(iterator.next()); }}Copy the code

Look at the results again: two User objects with the same name and different ages output only one

This is because in the natural ordering of TreeSet collections, two objects are determined not by equals(), but by compareTo(). If compareTo() returns 0, the two objects are determined to be the same.

Adding a secondary judgment to the rewritten compareTo() method solves the above problem:

    @Override
    public int compareTo(Object o) {
        if (o instanceof User){
            User user = (User) o;
            // Sort the names from largest to smallest
            int compare = -this.name.compareTo(user.name);
            // If the name is different, return it directly
            if(compare ! =0) {return compare;
                // If the names are the same, then sort by age from youngest to oldest
            }else {
                return Integer.compare(this.age, user.age); }}else {
            throw new RuntimeException("Type exception cannot be compared"); }}Copy the code

In the case of two User objects with the same name and different ages, look at the run result: two User objects with the same name and different ages are output.

TreeSet custom sorting

@Test
public void test1(a){

    Comparator comparator = new Comparator() {


        // Sort by age from youngest to oldest
        @Override
        public int compare(Object o1, Object o2) {
            if (o1 instanceof User && o2 instanceof User){
                User user1 = (User) o1;
                User user2 = (User) o2;
                return Integer.compare(user1.getAge(),user2.getAge());
            }else {
                throw new RuntimeException("Type exception cannot be compared"); }}};// Select custom sort. If there is no comparator, natural sort is default
    TreeSet set = new TreeSet(comparator);
    set.add(new User("wanli".23));
    set.add(new User("shengming".14));
    set.add(new User("taoxian".36));
    set.add(new User("bimo".12));
    set.add(new User("neihan".12));
    set.add(new User("neihan".46));

    Iterator iterator = set.iterator();
    while(iterator.hasNext()){ System.out.println(iterator.next()); }}Copy the code

In a custom sort of TreeSet collection, compare() is used instead of equals() to determine whether two objects are the same. If compare() returns 0, the two objects are the same.

6. Map interface

Map interface: The Map interface stores a set of key-value objects and provides mapping from key to value.

6.1 comparison of commonly used Map interface implementation classes

HashMap: As the main implementation class of Map, it is not thread safe and efficient, and can store null keys and values.

LinkedHashMap: A subclass of HashMap that ensures that map elements can be traversed in the order they were added to. This is suitable for frequent traversal.

TreeMap: Sorts the key and value according to the added key and value. In this case, both natural and custom sorts only consider the key, not the value.

Hashtable: is an ancient implementation of Map, thread-safe, inefficient, cannot store null keys and values.

Properties: a subclass of Hashtable, used to handle configuration files where keys and values are strings.

Difference between HashMap and Hashtable

Compared to HashMap, Hashtable is thread-safe and does not allow null keys and values.

The default size of Hashtable is 11.

Hashtable is a hash value that uses the hashCode(key.hashcode ()) of the key directly. Unlike the static final int hash(Object key) function inside a HashMap, the key’s hashCode is disturbed as a hash value.

Hash bucket subscript for Hashtable is modular %. (because its default capacity is not 2 ^ n.). So you can’t replace modular operations with bitwise operations.)

During capacity expansion, the new capacity is twice the original capacity +1. int newCapacity = (oldCapacity << 1) + 1;

Hashtable is a subclass of Dictionary that implements the Map interface.

6.2 Key-value characteristics stored in HashMap

HashMap is the most frequently used implementation class of the Map interface. It allows null keys and null values and, like HashSet, does not guarantee the order of the mapping.

The Set of all keys in a HashMap is Set: unordered and non-repeatable. So, the classes for keys need to be overridden :equals() and lhashCode().

All values of a HashMap form a Collection: unordered and repeatable. So, the value class is overridden :equals()

HashMap A key-value pair constitutes an entry

The Set of all the entries in a HashMap is a Set: unordered and non-repeatable

A HashMap determines that two keys are equal when they return true via equals() and the hashCode values are equal.

The HashMap criterion for determining the equality of two values is that they return true via equals().

6.3 HashMap Source Code Analysis (JDK 8)

6.3.1 Underlying structure of HashMap

In JDK1.8, HashMap is composed of array + linked list + red-black tree. With the addition of red-black tree as the underlying data structure, the structure becomes more complex, but the use efficiency also becomes more efficient.

6.3.2 Data structures involved in HashMap

Linked list (single linked list)

Node is an inner class of HashMap that implements the Map.Entry interface, which is essentially a mapping (key-value pair).

Specific source code:

static class Node<K.V> implements Map.Entry<K.V> {
    final int hash;/ / hash value
    final K key;/ / key the key
    V value;/ / value the value
    Node<K,V> next;// A reference to the next key-value pair

    // constructor
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey(a)        { return key; }
    public final V getValue(a)      { return value; }
    public final String toString(a) { return key + "=" + value; }

    // The hash value of each node is xor of the key hashCode and the value hashCode.
    public final int hashCode(a) {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    // Set the new value and return the old value
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    // Check whether two nodes are equal. If both key and value are equal, return true. You can compare it with yourself
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceofMap.Entry) { Map.Entry<? ,? > e = (Map.Entry<? ,? >)o;if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false; }}Copy the code

One of the data structures involved in HashMap is an array

// An array of stored elements. The transient keyword indicates that the attribute cannot be serialized
transient Node<K,V>[] table;
Copy the code

Red-black tree, the data structure involved in HashMap

About the characteristics of red-black trees:

Property 1. The node is red or black.

Property 2. The root node is black.

Property 3 Each leaf node (NIL node, empty node) is black.

Property 4 Two children of each red node are black. (No two consecutive red nodes on all paths from each leaf to the root)

Property 5. The path from any node to each of its leaves contains the same number of black nodes.

static final class TreeNode<K.V> extends LinkedHashMap.Entry<K.V> {
    TreeNode<K,V> parent;  / / the parent node
    TreeNode<K,V> left;// Left child node
    TreeNode<K,V> right;// Right child node
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red; // Color attributes
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    /** * returns the root of the tree containing this node */
    final TreeNode<K,V> root(a) {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                returnr; r = p; }}Copy the code

6.3.3 Basic attributes of HashMap

// Default initial capacity is 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 


// The maximum size of the array is 2 to the 30th
static final int MAXIMUM_CAPACITY = 1 << 30;


// Default load factor 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75 f;


// Threshold for list nodes to be converted to red black tree nodes. When the list exceeds 8 nodes, it is converted to red black tree nodes
static final int TREEIFY_THRESHOLD = 8;


// The threshold of the red-black tree node to convert the list node. If the list node is less than or equal to 6, the red-black tree will be converted to a normal list
static final int UNTREEIFY_THRESHOLD = 6;


// If the internal array length is less than 64, the list will not be converted to a red-black tree, but the array will be expanded first. 64 is the minimum length of a table when turning a red-black tree
static final int MIN_TREEIFY_CAPACITY = 64;


// An array that stores elements, always a power of 2
transient Node<k,v>[] table;


// Store a set of specific elements
transient Set<map.entry<k,v>> entrySet;


// The number of key-value mappings stored
transient int size;


// Expand and change the map counter each time
transient int modCount; 


// Threshold When the actual size (capacity x fill factor) exceeds the threshold, the system expands the capacity
int threshold;


// Load factor
final float loadFactor;
Copy the code

6.3.4 constructors

Construct an empty HashMap with a default initial capacity (16) and a default load factor (0.75)
public HashMap(a) {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}


Construct an empty HashMap with the specified initial capacity and default load factor (0.75)
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


   // Construct an empty HashMap with the specified initial capacity and load factor
    public HashMap(int initialCapacity, float loadFactor) {
        // If the specified initial capacity is less than 0, an exception is thrown
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // If the specified initial capacity is greater than the array maximum capacity, set the specified capacity to the maximum capacity 2 ^ 30
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // If the specified load factor is less than 0, an exception is thrown
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        // Returns the minimum quadratic value greater than initialCapacity as the threshold
        this.threshold = tableSizeFor(initialCapacity);
    }


   // Create a hash table and add all the elements from the other map m to the table
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
Copy the code

TableSizeFor method

// Return the smallest quadratic value greater than initialCapacity, since the array capacity must be raised to the power of 2,
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // Check whether n is out of bounds, return 2 to the n as the table threshold
    return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Copy the code

6.3.5, put() and putVal() method source analysis

Put () method source code analysis

// Associate the specified value with the specified key in this mapping. If you map a map that previously contained a key, the old value is replaced.
public V put(K key, V value) {
    // Get the hash value of the key,
    return putVal(hash(key), key, value, false.true);
}
Copy the code

Hash () algorithm source code analysis

static final int hash(Object key) {
    int h;
    return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code

We first get the hash of the key, then move the hash 16 bits to the right, then xor the hash to the original hashCode, and return the result.

The purpose of the hash method is to further obfuscate hashCode, increase its “randomness,” try to reduce hash collisions when inserting a HashMap, or in more technical terms, improve discretization performance. This method is called the “perturbation function” when someone answers.

PutVal () source code analysis

The put method inserts an element by putting val ().

// Arguments: processed hash value, key, value value
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; 
    Node<K,V> p; 
    int n, i;
    // Table is an array of elements, and the following resize() method is used only if the table is uninitialized or has a length of 0
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // Calculate the index of the hash value of key in the array, and assign the element corresponding to the index to p,
    if ((p = tab[i = (n - 1) & hash]) == null)
        // If p is null, there is no element at that location, and it is added directly to the array
        tab[i] = newNode(hash, key, value, null);
    // If there are already elements in that position
    else {
        Node<K,V> e; K k;
        // Determine whether the key and hash values of p node (stored in a linked list at this time) are equal to the key-value to be added. If they are equal, then p node is the target node to be searched, and assign p node to e node
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            e = p;
        // If the p node is a node of the red-black tree (i.e. the hash value is not equal, i.e. the key is not equal), add the key-value pair to the red-black tree
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // Check whether the node behind the p node conflicts with the node to be added.
        else {
            //binCount Counts the number of nodes in the linked list
            for (int binCount = 0; ; ++binCount) {
                // If there are no nodes after the p node, place the node to be added after the p node.
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // Check if the number of nodes exceeds 8. If so, call the treeifyBin method to turn the list node into a red-black tree node. -1 is because the loop starts at the next node of the P node
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // If the next node e of node P is not null, check whether the key and hash values of node E are equal to the key-value to be added. If they are equal, node E is the target node to be searched, exit the loop, no longer compare, and perform the operation of overwriting the old value with new value
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    break;
                // Point p to the next node, which is equivalent to moving p down to the next elementp = e; }}// If e is not empty, the target node exists, overwrites its value with the value passed in, and returns oldValue
        if(e ! =null) { // existing mapping for key
            V oldValue = e.value;
            // If onlyIfAbsent is false or the old value is null
            if(! onlyIfAbsent || oldValue ==null)
                // The new value overwrites the old value
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // If the actual size is greater than the threshold, expand the capacity
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Copy the code

6.3.6 Resize () source code analysis

Resize () source code analysis

final Node<K,V>[] resize() {
    // Assign the original array to oldTab, which is the capacity of the old table
    Node<K,V>[] oldTab = table;
    // If the expansion method is called for the first time, table is null and oldTab is also null, so oldCap is 0
    int oldCap = (oldTab == null)?0 : oldTab.length;
    // Threshold is assigned to oldThr. The initial value is 0. OldThr is the threshold of the old table
    int oldThr = threshold;
    // Define the new table capacity and the new table threshold, starting with 0
    int newCap, newThr = 0;
    // If the capacity of the old table is greater than 0
    if (oldCap > 0) {
        // If the capacity of the old table is greater than the maximum capacity (2 ^ 30), then the maximum integer is assigned to the threshold
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // If the current hash bucket array is still smaller than the maximum size after being doubled and oldCap is greater than the default value of 16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // Double the expansion threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // If the capacity of the old table and the threshold of the old table are not greater than 0, the table is not initialized
    else {               // zero initial threshold signifies using defaults
        // assign the default initial capacity DEFAULT_INITIAL_CAPACITY = 16 to the new table capacity newCap
        newCap = DEFAULT_INITIAL_CAPACITY;
        // Then calculate the new table threshold assigned to newThr, threshold = load factor 0.75x default initial capacity 16 = 12
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // Assign the threshold newThr calculated above to threshold
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // Create a new hash bucket array of 16 lengths
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // Assign the newly created array to the table, so when put for the first time, the size of the Node array is defined as 16
    table = newTab;
    // If the old table is not null, expand the capacity and copy the Node object value to the new hash bucket array
    if(oldTab ! =null) {
        // go through the old watch
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // If there is a node at the index, set the node on that index to null
            if((e = oldTab[j]) ! =null) {
                oldTab[j] = null;
                // If there is only one node at the index, then the index is recalculated into the new array.
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // If the node type is a red-black tree, perform red-black tree expansion
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // If the node type is a linked list node
                else { // preserve order
                    //loHead, loTail are the nodes of the original list with the same index
                    Node<K,V> loHead = null, loTail = null;
                    //hiHeadm, hiTail is new list node, old index + old array length
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // Start traversing the list
                    do {
                        // Assign the current node's reference to the next node to the current node
                        next = e.next;
                        // If the hash value of node E and the length of the original hash bucket array is 0
                        if ((e.hash & oldCap) == 0) {
                            // If loTail is null
                            if (loTail == null)
                                // Assign e to loHead
                                loHead = e;
                            // If loTail is not null
                            else
                                // Assign node e to the next loTail node
                                loTail.next = e;
                            // Then assign the node e to loTail
                            loTail = e;
                        }
                        // If the hash value of node E and the length of the original hash bucket array is not 0
                        else {
                            // If hiTail is null
                            if (hiTail == null)
                                // Assign e to hiHead
                                hiHead = e;
                            // If hiTail is not null
                            else
                                // Assign e to the next node in hiTail
                                hiTail.next = e;
                            // Then assign e to hiTail
                            hiTail = e;
                        }
                        // Exit traversal condition: traversal has reached the last element
                    } while((e = next) ! =null);
                    // If loTail is not equal to null after completion of the loop
                    if(loTail ! =null) {
                        // Set lotail.next to null
                        loTail.next = null;
                        // Put the loHead in the new Hash bucket array [j]
                        newTab[j] = loHead;
                    }
                    // If hiTail is not null
                    if(hiTail ! =null) {
                        // Set hitail.next to null
                        hiTail.next = null;
                        // Put the hiHead in the new Hash bucket array [j+ the old hash bucket array length]
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // Return the expanded array
    return newTab;
}
Copy the code

6.3.7 treeifyBin() source analysis

TreeifyBin () source code analysis

Converts a linked list node at the given array index to a red-black tree node

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // If the internal array length is less than 64, the list will not be converted to red-black tree, but the array will be expanded first,MIN_TREEIFY_CAPACITY = 64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // Calculate the index of the array based on the hash value and assign the node on the index to e, if e is not null
    else if ((e = tab[index = (n - 1) & hash]) ! =null) {
        //hd represents the head node, tl represents the tail node
        TreeNode<K,V> hd = null, tl = null;
        do {
            // Change e to type TreeNode and assign it to p
            TreeNode<K,V> p = replacementTreeNode(e, null);
            // If the tail node is null
            if (tl == null)
                // set the current node p as the head node
                hd = p;
            else {
                // set tl to the precursor of p
                p.prev = tl;
                // set p to the successor node of tl
                tl.next = p;
            }
            // After the head node is set to p, p is assigned to the tail node tl, and then the next node in the linked list is set to TreeNode, and then p is assigned to p
            tl = p;
            // If the next node is empty, the list is traversed
        } while((e = e.next) ! =null);
        // Assign the index position of table to the head node of the newly converted TreeNode. If this node is not empty, the head node (HD) is used as the root node to construct the red-black tree
        if((tab[index] = hd) ! =null)
            // The header calls the treeify method to build a red-black treehd.treeify(tab); }}Copy the code

6.3.8 Source code analysis of Treeify ()

Treeify () source code analysis

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    // Assign the node (this) from which this method is called to x, starting with x, to begin traversal
    for (TreeNode<K,V> x = this, next; x ! =null; x = next) {
        // point the reference to the next node of x to x
        next = (TreeNode<K,V>)x.next;
        // Set the left and right of the x node to null
        x.left = x.right = null;
        // If the root node is null (indicating that the red-black tree has not been built), x is assigned to the root node
        if (root == null) {
            x.parent = null;// The parent of the x node is set to null
            x.red = false;// Set the color of the x node to false
            root = x;
        }
        // If the root node is not null (the red-black tree is already built, and the node is being added to the tree)
        else {
            // Take the key from x and store it in k
            K k = x.key;
            // Get the hash value of x and store it in h
            inth = x.hash; Class<? > kc =null;
            // If the current node x is not the root node, the traversal starts from the root node. This traversal has no bounds and can only be jumped from the inside
            for (TreeNode<K,V> p = root;;) {
                //dir indicates the direction (left and right) and pH indicates the hash value of the current tree node
                int dir, ph;
                // Retrieve the key of the current tree node and store it in pk
                K pk = p.key;
                // If the current tree node's hash value is greater than the hash value of the list node (this) on which the Treeify method was called
                if ((ph = p.hash) > h)
                    // This node will be placed to the left of the current tree node
                    dir = -1;
                // If the current tree node's hash value is less than the hash value of the list node (this) on which the Treeify method was called
                else if (ph < h)
                    // This will be placed to the right of the current tree node
                    dir = 1;
                // If the hash values of the two nodes are equal, compare them using Comparable and tieBreakOrder
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                // Save the current tree node to XP
                TreeNode<K,V> xp = p;
                // If dir is greater than 0, the current list node (this/x) is to the right of the current tree node
                    // If the current tree node is a leaf node, execute x.parent = xp. , treat the current tree node as the parent of the current list node
                    // Case 2: If the current tree node is not a leaf node, start with the right child node of the current tree node
                 // If dir is not greater than 0, the current list node (this/x) is to the left of the current tree node
                    // If the current tree node is a leaf node, execute x.parent = xp. , treat the current tree node as the parent of the current list node
                    // Case 2: If the current tree node is not a leaf node, start with the right child node of the current tree node
                if ((p = (dir <= 0)? p.left : p.right) ==null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;// The current list node is the left child of the current tree node
                    else
                        xp.right = x;// The current list node is the right child of the current tree node
                    //balanceInsertion insertion algorithm is a new method of structuring a red-black tree after a new node is inserted into the tree structure to ensure that the tree retains the red-black tree characteristics. Once balanced, you can move on to the next list node.
                    root = balanceInsertion(root, x);
                    break; }}}}// Make sure that if the element in the HashMap array is of type TreeNode, the TreeNode must be the root of the tree and the first of the list.
    moveRootToFront(tab, root);
}
Copy the code

6.3. Common methods in Map

Add, delete, modify operations:

Object PUT (Object Key,Object value): Adds or modifies the specified key-value to the current map Object

Void putAll(Map M): stores all key-value pairs in M to the current Map

Object remove(): Removes the key-value pair of the specified key and returns value

Void clear(): clears all data in the map

Test code:

Map map = new HashMap<String, Object>();
/ / add
map.put("AA".12);
map.put("BB".13);
map.put("CC".14);
/ / modify
map.put("AA".15);
System.out.println(map);//{AA=15, BB=13, CC=14}

Map map1 = new HashMap<String, Object>();
map.put("DD".16);
map.put("EE".17);
// Put all key-value pairs in map1 into the current map
map.putAll(map1);
System.out.println(map);//{AA=15, BB=13, CC=14, DD=16, EE=17}


// Remove the key-value pair for the specified key and return value
map.remove("AA");
map.remove("BB".13);
System.out.println(map);//{CC=14, DD=16, EE=17}

// Clear all data in the current map
map1.clear();
System.out.println(map1);/ / {}
Copy the code

Element query operations:

Object GET (Object key): Obtains the value corresponding to the specified key

Boolean containsKey(Object Key): Specifies whether to contain the specified key

Boolean containsValue(Object value): Specifies whether to contain the specified value

Int size(): Returns the number of key-value pairs in the map

Boolean isEmpty(): checks whether the current map isEmpty

Boolean equals(Object obj): Checks whether map and Object obj are equal

Test code:

Map map = new HashMap<String, Object>();
Map map1 = new HashMap<String, Object>();
map.put("AA".12);
map.put("BB".13);
map.put("CC".14);
map.put("DD".16);
map.put("EE".17);


// Get the value of the specified key
System.out.println(map.get("BB"));/ / 13
System.out.println(map.get("DD"));/ / 16

// Whether to contain the specified key
System.out.println(map.containsKey("AA"));//true
System.out.println(map.containsKey("FF"));//false


// Whether to include the specified value
System.out.println(map.containsValue(12));//true
System.out.println(map.containsValue(18));//false

// Return the number of key-value pairs in the map
System.out.println(map.size());/ / 5
System.out.println(map1.size());/ / 0


// Check whether the current map is empty
System.out.println(map.isEmpty());//false
System.out.println(map1.isEmpty());//true

// Determine whether map and obj are equal
Map map2 = new HashMap<String, Object>();
map2.put("AA".12);
map2.put("BB".13);
map2.put("CC".14);
map2.put("DD".16);
map2.put("EE".17);
System.out.println(map.equals(map2));//true
Copy the code

To traverse a Map:

Set keySet(): Returns the Set of all keys

Collection Values (): Returns a Collection of all values

Set entrySet(): Returns a Set of all key-value pairs

Test code:

Map map = new HashMap<String, Object>();
map.put("AA".12);
map.put("BB".13);
map.put("CC".14);
map.put("DD".16);
map.put("EE".17);

// Return a Set of all keys
Set set = map.keySet();
// Call the iterator of Set to iterate
Iterator iterator = set.iterator();
// iterate over all keys
while (iterator.hasNext()){
    System.out.println(iterator.next());//AA BB CC DD EE
}

// Return a Collection of all values
Collection values = map.values();
// Call the iterator of the Collection to iterate
Iterator iterator1 = values.iterator();
// Iterate over all values
while (iterator1.hasNext()){
    System.out.println(iterator1.next());//12 13 14 15 16 17
}

// Return the Set of all key-value pairs
Set entrySet = map.entrySet();
// Call the iterator of Set to iterate
Iterator iterator2 = entrySet.iterator();
// Iterate over all key-value pairs
while (iterator2.hasNext()){
    Object next = iterator2.next();
    Map.Entry map1 = (Map.Entry) next;
    System.out.println(map1);//AA=12 BB=13 CC=14 DD=16 EE=17
}
Copy the code

6.4 TreeMap two kinds of sorting implementation

Natural order Comparable

Custom classes:

package map;

public class User implements Comparable{
    private String name;
    private int age;

    public User(a){}public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName(a) {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge(a) {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString(a) {
        return "User{" +
                "name='" + name + '\' ' +
                ", age=" + age +
                '} ';
    }

    @Override
    public int compareTo(Object o) {
        if (o instanceof User){
            User user = (User) o;
            // Sort the names from largest to smallest
            int compare = -this.name.compareTo(user.name);
            // If the name is different, return it directly
            if(compare ! =0) {return compare;
                // If the names are the same, then sort by age from youngest to oldest
            }else {
                return Integer.compare(this.age, user.age); }}else {
            throw new RuntimeException("Type exception cannot be compared"); }}}Copy the code

Test code:

        TreeMap<User, Integer> map = new TreeMap<>();
        User user1 = new User("wanli".11);
        User user2 = new User("shengming".12);
        User user3 = new User("yumo".13);
        map.put(user1,1);
        map.put(user2,2);
        map.put(user3,3);

        Set<Map.Entry<User, Integer>> entrySet = map.entrySet();
        Iterator<Map.Entry<User, Integer>> iterator = entrySet.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
Copy the code

Customize the sort Comparator

Test code:

TreeMap<User, Integer> map = new TreeMap<>(new Comparator<User>() {
    @Override
    public int compare(User o1, User o2) {
        // Sort by age
        return-Integer.compare(o1.getAge(), o2.getAge()); }}); User user1 =new User("wanli".11);
User user2 = new User("shengming".12);
User user3 = new User("yumo".13);
map.put(user1,1);
map.put(user2,2);
map.put(user3,3);

Set<Map.Entry<User, Integer>> entrySet = map.entrySet();
Iterator<Map.Entry<User, Integer>> iterator = entrySet.iterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
}
Copy the code

7. Use of the Collections utility class

Collections is a utility class that operates on Collections of sets, lists, maps, and so on.

Collections provides a series of static methods for sorting, querying, and modifying collection elements, as well as methods for immutability and synchronization control of collection objects.

7.1. Common methods

Sort (static) :

  • Reverse (List): Reverses the order of elements in a List

  • Shuffle (List): Randomly sorts the elements in the List

  • Sort (List): Sort the elements of the specified List collection in ascending order according to their natural order

  • Sort (List, Comparator): Sorts List collection elements in the order produced by the specified Comparator

  • Swap (List, int, int): Swaps the elements at I and j in the specified List

Method test code:

ArrayList list = new ArrayList();
list.add(2);
list.add(12);
list.add(22);
list.add(31);
list.add(6);

//everse(List): reverses the order of the elements in the List
Collections.reverse(list);
System.out.println(list);//[6, 31, 22, 12, 2]

Shuffle (List): Sorts the elements in the List randomly
Collections.shuffle(list);
System.out.println(list);//[12, 6, 22, 31, 2]


//sort(List): Sort the elements of the specified List in ascending order according to their natural order
Collections.sort(list);
System.out.println(list);//[2, 6, 12, 22, 31]

//sort(List, Comparator): Sorts the List collection elements in the order produced by the specified Comparator

ArrayList list1 = new ArrayList();
User user1 = new User("wanli".3);
User user2 = new User("wanli".60);
User user3 = new User("wanli".24);
User user4 = new User("wanli".18);
list1.add(user1);
list1.add(user2);
list1.add(user3);
list1.add(user4);

Collections.sort(list1, new Comparator<User>() {

    @Override
    public int compare(User o1, User o2) {
        // Sort by age from youngest to oldest
        returnInteger.compare(o1.getAge(),o2.getAge()); }}); System.out.println(list1);//swap(List, int, int): swaps the elements at subscript I and j in the specified List
Collections.swap(list,2.3);
System.out.println(list);//[2, 6, 22, 12, 31]
Copy the code

Find and replace

  • Object Max (Collection): Returns the largest element in a given Collection based on the natural order of the elements

  • Object Max (Collection, Comparator): Returns the largest elements in a given set in the order specified by the Comparator

  • Object min(Collection): Returns the smallest element in a given Collection according to the natural order of the elements

  • Object min(Collection, Comparator): Returns the smallest elements in a given set in the order specified by the Comparator

  • Int frequency(Collection, Object): Returns the number of occurrences of the specified element in the specified Collection

  • Void copy(List dest,List SRC): Copies the contents of SRC into dest

  • Boolean replaceAll(List List, Object oldVal, Object newVal): replaceAll old List values with new values

Method test code:

List list = new ArrayList();

list.add(2);
list.add(12);
list.add(22);
list.add(22);
list.add(31);
list.add(6);

//Object Max (Collection): Returns the largest element in a given Collection according to the natural order of the elements
System.out.println(Collections.max(list));/ / 31

//Object min(Collection): Returns the smallest element in a given Collection according to the natural order of the elements
System.out.println(Collections.min(list));/ / 2


ArrayList list1 = new ArrayList();
User user1 = new User("wanli".3);
User user2 = new User("wanli".60);
User user3 = new User("wanli".24);
User user4 = new User("wanli".18);
list1.add(user1);
list1.add(user2);
list1.add(user3);
list1.add(user4);

//Object Max (Collection, Comparator): Returns the largest element in a given set in the order specified by the Comparator
System.out.println(Collections.max(list1, new Comparator<User>() {
    @Override
    public int compare(User o1, User o2) {
        // Sort by age
        return-Integer.compare(o1.getAge(), o2.getAge()); }}));//User{name='wanli', age=3}

//Object min(Collection, Comparator): Returns the smallest elements in a given set in the order specified by the Comparator
System.out.println(Collections.min(list1, new Comparator<User>() {
    @Override
    public int compare(User o1, User o2) {
        // Sort by age
        return-Integer.compare(o1.getAge(), o2.getAge()); }}));//User{name='wanli', age=60}

//int frequency(Collection, Object): returns the frequency of occurrences of the specified element in the specified Collection
System.out.println(Collections.frequency(list, 22));/ / 2


//void copy(List dest,List SRC): copies the contents of SRC into dest
List dest = Arrays.asList(new Object[list.size()]);
System.out.println(dest);//[null, null, null, null, null, null]
Collections.copy(dest,list);
System.out.println(list);//[2, 12, 22, 22, 31, 6]
System.out.println(dest);//[2, 12, 22, 22, 31, 6]

// Boolean replaceAll(List List, Object oldVal, Object newVal): replaceAll old values of List with new values
Collections.replaceAll(list,22.10);
System.out.println(list);//[2, 12, 10, 10, 31, 6]
Copy the code

Synchronization control

The Collections class provides multiple synchronizedXxx() methods that enable a specified collection to be wrapped as a thread-synchronized collection, thereby addressing thread-safety issues when the collection is concurrently accessed by multiple threads.

synchronizedList()

synchronizedSet()

synchronizedMap()

SynchronizedList () Example:

public class ListTest {
    public static void main(String[] args) {
        List<String> list = Collections.synchronizedList(new ArrayList<>());

        for (int i = 1; i < 10; i++) {
            new Thread(() -> {
                list.add(UUID.randomUUID().toString().substring(0.5)); System.out.println(list); }, String.valueOf(i)).start(); }}}Copy the code