1. Data structure

Data structures are how computers store and organize data.

In computer science, the time complexity of an algorithm is a function, which qualitatively describes the running time of the algorithm, often expressed by the O symbol. Time complexity is the same problem can be solved by different algorithms, and the quality of an algorithm will affect the efficiency of the algorithm and even the program. The aim of algorithm analysis is to select suitable algorithm and improve algorithm

1.1. Linear structure

1.1.1, arrays,

We perform performance analysis on CRUD operations on arrays

Add operation

At least one operation is required if saved in the last position of the array

If you save in the first position of the array, then if there are N elements, then all the elements that follow will move back, and you’ll need to do it N times

So the average is (N+1) /2 times, and if you need to expand, the performance is even lower

Delete operation

If the last element is deleted, you need to do it once

If you’re doing the first element, then all the other elements have to move forward, N times

The average is N plus 1 over 2 times

Modify the operating

Given an index, only one operation is performed

Query operation

Once by index, N times by memory

Summing up,

Array-based data structures are very fast to query and modify (high performance), but slow to delete and add, so if you want to ensure the performance of save and delete operations, you need to refer to linked lists

1.1.2, linked list

Linked lists (like trains and train cars) are made up of a series of nodes (each element of the list is called a node) that can be dynamically generated at runtime I. Each node consists of two parts: a data field that stores data elements and a pointer field that stores the address of the next node.

There are two types of linked lists:

  1. Unidirectional linked lists: can only be traversed from beginning to end

  2. Bidirectional linked lists: can be traversed from beginning to end or from end to end

    Performance analysis of linked list operations

Increase the operating

Just do it once, break the chain and add the chain

Delete operation

I’m only going to do it once

Modify the operating

If I’m changing the first element, I need to do it once, and if I’m changing the last element, I need to do it N times, so on average (N+1) /2

Query operation

If you’re looking for the first element, you need to do it once, and if you’re looking for the last element, you need to do it N times, so on average (N+1) /2

conclusion

Linked list query and modify performance is low, while add and delete performance is high

1.1.3, queue

A queue is a special kind of linear table, special in that it allows only delete operations at the front of the table and insert operations at the rear. A queue is a linear table with limited operations.

The end that performs the insertion operation is called the end of the queue, and the end that performs the deletion operation is called the end of the queue. The one-way queue is first-in-first-out, and elements can only be inserted from the end of the queue and deleted from the end of the queue

Single queue

The bidirectional queue

1.1.4, stack

A stack, also known as a stack, is a linear table with limited operations, LIFO, similar to a water bottle, in which water is first filled and then drunk.

The stack structure allows insertion and deletion at only one end of the table, called the top of the stack, and, conversely, the other end, called the bottom of the stack. Adding a new element to a stack, also known as pushing, is the process of placing the new element on top of the top element to make it the new top element. Removing an element from a stack, also known as making a stack, means to remove the top element of the stack so that the adjacent element becomes the new top element.

  • To push: to store elements. That is, the elements are stored at the top of the stack, and the existing elements are moved one position down the stack.
  • Pop stack: is to fetch elements. That is, the top element of the stack is removed, and the existing elements in the stack are moved one position to the top of the stack.

1.2. Nonlinear structure

1.2.1 hash table

The index position of an element in an array is random. There is no definite relationship between the value of an element and its position. Therefore, when searching for a specific value in an array, you need to compare the specific value with the entire array element one by one.

The query efficiency depends on the comparison times. If the comparison times are large, the query efficiency is still low.

If there is a definite corresponding relation between the value of the element and the index position in the array, we call this relation hash, then the corresponding formula between the value of the element and the index is: Index = hash (value), that is, given the value of an element, the hash (value) method is invoked to find the value of the element in the array

For example, the hash algorithm in the figure is: index = value/10-1. When storing objects in the hash table, the hash algorithm is the hashCode method of the object (the real hash algorithm is not like this, just for example, we do not need to care about the real hash algorithm).

Before JDK1.8, hash table is implemented by array + linked list, that is, using array to deal with conflicts, linked lists with the same hash value are stored in an array. However, when there are many elements in a bucket, that is, there are many elements with the same hash value, searching by key value is inefficient. In JDK1.8, hash table storage is realized by array + linked list + red black tree. When the length of the linked list exceeds the threshold value (8), the linked list is converted to red black tree, which greatly reduces the search time **. In simple terms, hash tables are implemented by arrays + linked lists + red-black trees (red-black trees have been added to JDK1.8). 支那

It works like this,JDK1.8The introduction of red-black trees greatly optimizes the performance of the HashMap, so for us to ensure the uniqueness of the elements of the HashSet is actually determined by the object’s hashCode and equals methods. If we store custom objects in the collection to make them unique, we must override the hashCode and equals methods to set up comparisons that belong to the current object.

1.2.2. Trees and binary trees

1.2.2.1, trees,

A tree in a computer, abstracted from a tree in life, represents a set of N nodes that have a parent-child relationship.

  • When N is 0, the set of nodes is empty, and the tree is empty

  • In any non-empty tree, there is only one root node (root)

  • For N>1, a tree consists of roots and subtrees, each of which consists of smaller subtrees

  • Nodes in a tree are divided into two types, depending on whether they have children:

    1. Normal node: a node with child nodes.
    2. Leaf node: a node without byte points.

noun meaning
node Refers to an element in a tree
The degree of node The number of subtrees that a node has. The degree of the binary tree is not greater than 2
A leaf node Nodes with degree 0 are also called terminal nodes
highly The height of the leaf node is 1, the height of the parent node is 2, and so on, the height of the root node is the highest
layer The root node is at the first level, and so on
The parent node If a node contains children, the node is called the parent of its children
Child nodes The child node is the node at the next level from the parent node
Brother nodes Nodes that have a common parent are called siblings

1.2.2.2 Binary tree

The structure of the tree is really too complicated because of the existence of multiple seed nodes. If we add some constraints to the ordinary tree, such as making the node of each tree contain only two child nodes at most, and strictly distinguish the left child node from the right child node (the left and right positions cannot be swapped), then a binary tree will be formed.

1.2.2.3 sorting binary trees

A sorted binary tree is an ordered number that satisfies the following three conditions:

  • If the left subtree is not empty, the values of all nodes of the left subtree are less than the values of the root node.
  • If the right subtree is not empty, the value of all nodes in the right subtree is greater than the value of the root node.
  • The left and right subtrees are also sorted binary trees

Add, delete, modify, and look are very high performance so when you iterate over the elements you can iterate over them in left-middle-right order;

Note: problems existing in binary search trees: there will be “lame” phenomenon, affecting query efficiency. So this is equivalent to a linked list, so 12345678 becomes a linked list if you line it up in a tree

1.2.2.4 Balanced binary tree

In order to avoid the “lame” phenomenon, reduce the height of the tree, improve our search efficiency, there is a tree structure: “balanced binary tree”.

Rules:The absolute value of the height difference between the left and right subtrees is no more than 1, and both subtrees are a balanced binary tree

The figure on the left is a balanced binary tree with root node 10, and the height difference between the left and right subtrees is 1. On the right, although the height difference between the left and right subtrees of the root node is 0, the height difference between the left and right subtrees of the right subtree 15 is 2, which does not conform to the definition, so the figure on the right is not a balanced binary tree.

The way to become a balanced binary tree is to rotate it in the opposite direction.

1.2.2.4.1, left-handed

​ Left-rotation is to pull the right branch of the node to the left, and the right child node becomes the parent node, and transfer the excess left child node after promotion to the right child node of the degraded node;

1.2.2.4.2, right

By pulling the left branch of the node to the right, the left child node becomes the parent node, and the excess right child node after promotion is transferred to the left child node of the degraded node

For example, in the figure above, whether the binary tree is balanced or not, on the left, the tree is still balanced before the first “19” node is inserted, but after the insertion of “19”, the left and right subtrees of “15” are not “balanced”.

So we can rotate “15” to the left, so that “15” itself gives the node to “17” as the left tree of “17”, so that “17” is balanced on the left and right subtrees, and “15” has no subtrees, so it is balanced on the left and right. The diagram below:

In the construction of a balanced binary tree, when a new node is inserted, the balance after insertion will be judged, which indicates that the new node is always balanced before insertion, that is, the absolute value of the height difference will not exceed 1.

When a new node is inserted, the tree may be unbalanced, so it needs to be adjusted. There are four possible situations, which are respectively called left-left, left-right, right-left and right-right.

1.2.2.4.3, left to the left

In the original balanced binary tree, a new node is inserted under the left subtree of the left subtree of the node, resulting in a height difference of 2 between the left and right subtrees of the node. The following is the left subtree “7” of the node “10” and the left subtree “4” of the node. The node “5” or “3” is inserted, resulting in imbalance.

1.2.2.4.4 around,

Left and right means that in the original balanced binary tree, a new node is inserted under the right subtree of the left subtree of the node, resulting in a height difference of 2 between the left and right subtrees of the node. For example, the left subtree “7” of the node “11” and the right subtree “9” of the node are inserted, resulting in an imbalance.

1.2.2.4.5, right to the left

Right-left means that in the original balanced binary tree, a new node is inserted under the left subtree of the right subtree of the node, resulting in a height difference of 2 between the left and right subtrees of the node, such as the right subtree “15” of the node “11” and the left subtree “13” of the node. The node “12” or “14” is inserted to cause imbalance.

1.2.2.4.6, right, right

Right-right means that in the original balanced binary tree, a new node is inserted under the right subtree of the right subtree of the node, resulting in a height difference of 2 between the left and right subtrees of the node. The following is the right subtree “13” of the node “11”, and the left subtree “15” of the node. Node “14” or “19” is inserted, resulting in imbalance.

Right and right nodes only need to turn left once to adjust the balance, as shown in the figure below, for “11” nodes.

1.2.2.5 Red black tree

Red-black tree is a sorted binary tree with higher query efficiency in essence.

Sorting binary trees can be searched quickly, but if there are only left nodes or left and right nodes, the binary tree becomes a common linked list structure, and the query efficiency is low. For this reason, a more efficient binary tree emerged — red-black tree, which meets the following conditions:

  1. Each node is either red or black.
  2. The root node is always black.
  3. All leaf nodes are null and are black.
  4. Two children of each red node are black.
  5. The path from any node to each leaf node of its subtree contains the same number of black nodes.

There is a Collection

A collection is a container provided in Java that can be used to store multiple pieces of data

Arrays have obvious disadvantages compared to collections:

  1. The length of an array is fixed, while the length of a collection is variable
  2. Using Java classes to encapsulate container classes, developers only need to call directly, no longer manually create container classes
  3. Arrays are much harder to manipulate than collections, which are more flexible and suitable for development

2.1 Overview of collection framework

Collection is a container provided in Java, which can be used to store multiple data. The architecture formed according to different storage modes is called collection framework system.Collections are also often called containers, and the data stored in a collection is called an element, and an element can only be an object

2.2. Classification of sets

According to the different storage characteristics of containers, it can be divided into three cases:

A collection of describe
List (List) Allows recording of order of addition, allows element repetition (Ordered repeatability)
Set Does not record the order in which elements are added, and does not allow elements to be repeated (Unordered and unique)
Map (Map) Each element in the container contains a pair of keys and a value. The key cannot be repeated, but the value can be repeated

List and Set inherit from the Collection interface. Map does not inherit from the Collection interface.Container interfaces or classes are in the java.util package

interface describe
The Collection interface It refers to a Set in a broad sense, and mainly refers to the List and Set storage modes
The List interface Represents a list, ordered and repeatable
The Set interface Represents a set in narrow sense, unordered and unrepeatable
The Map interface Representation mapping

List interface

The List interface is a Collection interface subinterface. The List interface defines a specification that requires the container to record the order in which elements are added and to allow elements to be repeated. The implementation classes of the List interface follow this specification.

List collection storage features:

  1. Allow elements to repeat
  2. Allows you to record the order in which elements are added

Common implementation classes for this interface are:

  1. ArrayList: a list of arrays
  2. LinkedList class: LinkedList, representing bidirectional lists and bidirectional queue structures, implemented in linked lists
  3. Stack class: Stack, Stack structure, using an array
  4. Vector class: Vectors, which are essentially the old ArrayList, are implemented in arrays

3.1 List common API

3.1.1. Add operations

  1. Boolean add(Object e) : Adds an element to the end of the list
  2. Void add(int index, Object Element) : Inserts the specified element at the specified position in the list
  3. Boolean addAll(Collection C) : Adds all elements from c to the current list

3.1.2 Delete operations

  1. Object Remove (int index) : Removes the element at the specified index position from the list and returns the deleted element
  2. Boolean removeAll(Collection C) : Removes all elements from c list from this list

3.1.3 Modification operation

Object set(int index, Object ele) : Modifies the element in the list at the specified index position, and returns the replaced old element

3.1.4. Query operation

  1. Int size() : Returns the number of elements in the current list
  2. Boolean isEmpty() : Checks whether the number of elements in the current list is 0
  3. Object GET (int index) : Queries the element corresponding to the specified index position in the list
  4. Object[] toArray() : Converts list objects into Object arrays
  5. Boolean Contains (Object O): Determines whether the list contains the specified Object

Fourth, the ArrayList class

The ArrayList class is a list based on the array algorithm. If you look at the source code, you will find that the underlying is actually an Object array

ArrayList is an implementation class of the List interface that implements mutable arrays. When an element is added, if the capacity is sufficient, it is added directly. If the capacity is insufficient, it is expanded according to the principle newCapacity = oldCapacity + oldCapacity/2

Since the underlying data structure of ArrayList is an array, this implementation class is more suitable for query scenarios, but less efficient for add and delete scenarios

public class ArrayListDemo1 {
    /** ArrayList **/
public static void main(String[] args) {
// Create a list object with the default length
List list = new ArrayList();
// Prints the number of elements in the collection
System.out.println("Element number:"+list.size());/ / 0
// Add operation: Add 4 elements to the list
list.add("Will");
list.add(100);
list.add(true);
list.add("Lucy");
// Query operation:
System.out.println("All elements in the list:"+list);// Output :[Will, 100, true, Lucy]
System.out.println("Element number:"+list.size());/ / 4
System.out.println("First element:"+list.get(0));//Will
// Change the element with index 2 to WolfCode
list.set(2."wolfcode");
System.out.println("After modification:"+list);// Output :[Will, 100, Wolfcode, Lucy]
// Delete: delete the element whose index is 1
list.remove(1);
System.out.println("After deletion:"+list);// Output :[Will, Wolfcode, Lucy]}}Copy the code

Let’s draw the memory map of ArrayList and you can see thatAny object stored in a collection class stores a reference to the object, not the object itself

Five, the LinkedList class

LinkedList because the underlying data structure is a LinkedList, it is efficient to add and delete elements, but inefficient to query elements. LinkedList class, the underlying use of LinkedList algorithm, the realization of LinkedList, queue, stack data structure. Both lists and queues operate primarily on header and tail elements, so there are many header and tail methods in the LinkedList class in addition to the List interface methods. The common methods are as follows:

// Inserts the specified element at the beginning of the list.
void addFirst(Object e);
// Adds the specified element to the end of the list.
void addLast(Object e); 
// Returns the first element of this list.
Object getFirst(a);
// Returns the last element of this list.
Object getLast(a);
// Remove and return the first element of this list.
Object removeFirst(a); 
// Remove and return the last element of this list.
Object removeLast(a);

// Inserts the specified element at the beginning of this list.
boolean offerFirst(Object e);
Inserts the specified element at the end of this list.
boolean offerLast(Object e);
//// gets, but does not remove, the first element of this list; If this list is empty, null is returned.
Object peekFirst(a);
//// gets, but does not remove, the last element of this list; If this list is empty, null is returned.
Object peekLast(a);
//// gets and removes the first element of this list; If this list is empty, null is returned.
Object pollFirst(a);
// Get and remove the last element of this list; If this list is empty, null is returned.
Object pollLast(a);

// Push the element onto the stack represented by this list.
void push(Object e);
// Pops an element from the stack represented by this list.
Object pop(a);
// Gets, but does not remove, the first element of this list.
Object peek(a) 
Copy the code
import java.util.LinkedList;
public class LinkedListDemo {
  public static void main(String[] args) {
    LinkedList list = new LinkedList();
// Add elements
    list.addFirst("A");
    list.addFirst("B");
    System.out.println(list);
    list.addFirst("C");
    System.out.println(list);
    list.addLast("D");
    System.out.println(list);
// Get the element
    System.out.println("Get first element:" + list.getFirst());//C
    System.out.println("Get last element:" + list.getLast());//D
// Delete elements
    list.removeFirst();
    System.out.println("After deleting the first element:" + list);//[B, A, D]
    list.removeLast();
    System.out.println("After removing the last element:" + list);//[B, A]}}Copy the code

Stack and Vector classes

Vector: A list based on an array algorithm, a precursor to ArrayList. The difference with ArrayList is that methods use synchronized decorations, so they are thread-safe but less efficient than ArrayList. Stack: represents a Stack. It is a subclass of Vector, LIFO, and has push and pop methods.

7. Traversal of sets

List<String> list = new ArrayList<>();
	list.add("Beauty");
	list.add("Wang Zhaojun");
	list.add("The sable cicada");
	list.add("Yang Yuhuan");
Copy the code

7.1. For loop

for (int index = 0; index < list.size(); index++) {
	String ele = list.get(index);
	System.out.println(ele);
}
Copy the code

7.2. Use iterators

In program development, it is often necessary to iterate over all the elements in a collection. For this purpose, the JDK provides an interface called java.util.iterator.

To iterate over the Collection, we need to get the iterator to complete the iteration. Here’s how to get the iterator:

  • public Iterator iterator(): Gets the iterator corresponding to the collection, which is used to traverse the elements in the collection.

Iterator represents an Iterator object that has a pointer to the first element by default, followed by the following methods:

  1. public E next(): Checks whether the next element exists after the pointer
  2. public boolean hasNext(): Gets the next element at the pointer position, moves the pointer back one bit, and returns true if there are still elements to iterate over
Iterator iterator = list.iterator();
    while (iterator.hasNext()){
      System.out.println(iterator.next());
    }
Copy the code

Note:

  1. Will be thrown if there are no elements in the collection and the iterator’s next method continues when fetching collection elementsjava.util.NoSuchElementExceptionNo collection element exceptions.
  2. If an element is added or removed from the collection during collection element fetching, the iteration cannot continue and will be thrownConcurrentModificationExceptionConcurrent modification is abnormal.

7.3 for-each Traversal (enhanced for loop)

Grammar:

For (data type iteration variable: instance object){	//TODO
}
Copy the code
for (String ele : list) {
	System.out.println(ele);
}
Copy the code

7.4. Functional programming traversal of forEach

list.forEach(object -> System.out.println(object));
Copy the code

7.5 concurrent Modification is abnormal

Delete collection elements during iteration, such as Wang Zhaojun

List<String> list = new ArrayList<>();
    list.add("Beauty");
    list.add("Wang Zhaojun");
    list.add("The sable cicada");
    list.add("Yang Yuhuan");
    for (String ele : list){
      if ("Wang Zhaojun".equals(ele)){
        list.remove(ele);
      }
      System.out.println(ele);
    }
Copy the code

Error:

The error is caused by the fact that it is not allowed to change the length of the collection during iteration (it cannot be deleted or added).

If you want to remove elements during iteration, you cannot use the remove method of the collection. You can only use the remove method of the iterator. In this case, you can only use the iterator, not foreach.

   List<String> list = new ArrayList<>();
    list.add("Beauty");
    list.add("Wang Zhaojun");
    list.add("The sable cicada");
    list.add("Yang Yuhuan");
	Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()){
      if ("Wang Zhaojun".equals(iterator.next())){
        iterator.remove();
      }
    }
    System.out.println(list);
Copy the code

8. Set interface

Set is a subinterface of Collection. The Set interface defines a specification that the container does not record the order in which elements are added and does not allow elements to be repeated.

8.1. Characteristics of Set

  1. Element duplication is not allowed

  2. The order in which elements are added is not recorded

    The set contains only methods inherited from the Collection, but the set cannot remember the order in which the elements were added, nor can it allow elements to be repeated. When two identical elements are added to the set, the add operation fails, and the add method (add()) returns false

8.2 Common implementation classes of Set interface

  1. HashSet class: The underlying implementation is a hash table

  2. TreeSet class: The underlying red and black book implementation allows sorting of elements in a collection

8.3, HashSet

8.3.1 HashSet principle

The HashCode value of the element object determines the location in the hash table. When adding a new element to the HashSet, we will first determine whether the location has an element:

  1. If not, the new object is directly stored in the location specified by hashCode

  2. If so, compare the new object with equals of the collection object:

    • If equals is true, it is treated as the same object, not saved, and the add() method returns false
    • If equals is false, store a linked list in the same location as the previous object

Each object stored in the hash table has to override the hashCode and equals methods to determine if it is the same object. In general, hashCode should also be equal when equals is true. Idea can automatically generate these methods

8.3.2 Common methods of HashSet

package day14_ArrayList2.classing;

    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.Set;

/ * * *@author Xiao_Lin
 * @version 1.0
 * @date2020/12/17 cometh * /
public class SetApi {

  public static void main(String[] args) {
    Set<String> set = new HashSet<>();

    // Add an element to the list
    set.add("will");
    set.add("wolf");
    set.add("code");
    set.add("lucy");

    // Query operation
    System.out.println("All elements in the set are:"+set);
    System.out.println("Element number:"+set.size());
    System.out.println("Is there an element:"+set.contains("111"));
    System.out.println("Is there an element:"+set.contains("code"));

    // Delete elements
    set.remove("code");
    System.out.println("The deleted set is:"+set);

    // Enhance for loop traversal
    for (String ele : set){
      System.out.println(ele);
    }
    // iterator traversal
    Iterator<String> it = set.iterator();
    while(it.hasNext()){ System.out.println( it.next()); }}}Copy the code
package day14_ArrayList2.classing;

/** Override equals and hashCode methods *@author Xiao_Lin
 * @version 1.0
 * @date 2020/12/17 11:34
 */
public class Student {
  private String name;
  private Integer sn;
  private String classname;

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

    Student student = (Student) o;

    if(name ! =null? ! name.equals(student.name) : student.name ! =null) {
      return false;
    }
    if(sn ! =null? ! sn.equals(student.sn) : student.sn ! =null) {
      return false;
    }
    returnclassname ! =null ? classname.equals(student.classname) : student.classname == null;
  }

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

  public Student(String name, Integer sn, String classname) {
    this.name = name;
    this.sn = sn;
    this.classname = classname;
  }

  public Student(a){}public String getName(a) {
    return name;
  }

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

  public Integer getSn(a) {
    return sn;
  }

  public void setSn(Integer sn) {
    this.sn = sn;
  }

  public String getClassname(a) {
    return classname;
  }

  public void setClassname(String classname) {
    this.classname = classname;
  }

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

8.4, TreeSet

TreeSet uses the red-black tree algorithm at the bottom, and the stored element objects are naturally sorted (ascending) by default.

The data type collation
BigDecimal, BigInteger, Byte, Double, Float, Integer, Long, Short Sort by numeric size
Character Sort characters by numeric size of their Unicode value
String Sort by the Unicode value of the characters in the string

The element objects in the TreeSet collection must be of the same data type, otherwise an error is reported

import java.util.Set;
import java.util.TreeSet;

public class TreeSetDemo{
  public static void main(String[] args) {
    Set<String> set = new TreeSet<>();
    set.add("wolf");
    set.add("will");
    set.add("sfef");
    set.add("allen");
    System.out.println(set);//[allen, sfef, will, wolf]}}Copy the code

8.4.1 Detailed explanation of TreeSet’s underlying data structure

The first step

Insert the first node, without comparison, directly as the root node

The second step

Insert the second node, compared to the Wolf root, as the left subtree if it is smaller than the root, and as the right subtree if it is larger

The third step

Insert the third node, compare it with the Wolf root node, move it to the left as the left subtree, because there is already a left subtree on the left, so compare it with the Will node, keep it on the left as the left subtree

The fourth step

Since TreeSet is a balanced binary tree, if the tree is unbalanced (the difference between left and right subtrees is greater than 1), the node will be adjusted

Step 5

Insert a fourth node, first compare it with the root node will, which is small and moves to the left, then compare it with the sfef node, which is still small and moves to the left

Comparable Interface

By default, TreeSet elements are sorted from small to large. In this case, element objects must implement the java.util.Comparable interface. Most JDK classes implement this interface. For example, the eight most common wrapper classes and String TreeSet call the element’s comparaTo() method to compare the element’s size and then arrange the collection elements in ascending order

public interface Comparable<T> {
	public int compareTo(T o);
}
Copy the code

Compare the rules

  • The current element is greater than the one passed in, returns a positive integer 1, with a higher priority
  • The current element is less than the one passed in, returns a negative integer -1, lower priority
  • The current element is equal to the element passed in, returns 0, and the two objects are considered the same object

If we are customizing a class and we need to store it in TreeSet, we need to make that class implement the Comparable interface and override the compareTo() method to write comparison rules in that method

package day14_ArrayList2.classing;

/ * * *@author Xiao_Lin
 * @version 1.0
 * @date 2020/12/17 11:34
 */
public class Student implements Comparable<Student>{
  private String name;
  private Integer sn;
  private String classname;

  // Compare rules
  @Override
  public int compareTo(Student student) {
    // The current object is larger than the one passed in
    if (this.sn > student.sn){
      return 1;
    }else if (this.sn < student.sn){
      return -1;
    }
    return 0;
    
    // Can be simplified as;
    //return this.sn - student.sn;
    
  }

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

    Student student = (Student) o;

    if(name ! =null? ! name.equals(student.name) : student.name ! =null) {
      return false;
    }
    if(sn ! =null? ! sn.equals(student.sn) : student.sn ! =null) {
      return false;
    }
    returnclassname ! =null ? classname.equals(student.classname) : student.classname == null;
  }

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

  public Student(String name, Integer sn, String classname) {
    this.name = name;
    this.sn = sn;
    this.classname = classname; }}Copy the code

8.4.3. The Comparator interface

TreeSet supports custom sorting in addition to the default natural sorting. When you build TreeSet objects, pass the java.util.Comparator interface implementation object. The Comparator represents a Comparator that encapsulates the comparison rules.

If compare returns 0, the two objects are considered to be the same object, and the positive number is first and the negative number is second.

public interface Comparator<T> {
  int compare(T o1, T o2);
}
Copy the code

demonstration

class User {
	private String name;
    import java.util.TreeSet;

private int age;
public User(String name, int age) {
    this.name = name;
    this.age = age;
    }
public int getAge(a) {
    return age;
    }
public String getName(a) {
    return name;
    }
public String toString(a) {
    return "User [name=" + name + ", age=" + age + "]"; }}public class App {
  public static void main(String[] args) {
    Set<User> set = new TreeSet<>(new NameLengthComparator());
    set.add(new User("James".30));
    set.add(new User("Bryant".22));
    set.add(new User("Allen".28));
    set.add(new User("Will".17));
    System.out.println(set);//}}// Encapsulates the comparison rules
class NameLengthComparator implements java.util.Comparator<User> {
  public int compare(User o1, User o2) {
    int ret = o1.getName().length() - o2.getName().length();
    if (ret > 0) {
      return 1;
    } else if (ret < 0) {
      return -1;
    } else {
      if (o1.getAge() > o2.getAge()) {
        return 1;
      } else if (o1.getAge() < o2.getAge()) {
        return -1;
      } else {
        return 0; }}}}Copy the code

9. Map interface

Map = Map

From the structure diagram, Map is not a Collection, but a mapping relationship similar to two collections. Therefore, the Collection interface is not implemented in Map

In Map, it is required that each key of Set A can find A unique value corresponding to it in Set B, which means that elements in Set A cannot be repeated while elements in Set B can be repeated. Therefore, Set A should be A Set, while Set B is A List

In fact, a Map consists of many key-values (KV key-value pairs), and each key-value pair is represented by Entry

In fact, we can also think of a Map as a collection of multiple entries

In general, we are used to calling a Map a Set, but unlike List and Set, which are single-element sets, a Map is a two-element Set

  • Single-element collection: Only one element can be stored at a time, such as List and Set

  • Two-element collection: You need to store two elements (one key and one value) at a time, such as a Map

    Note:

    1. The Map interface does not inherit from the Collection interface or from the Iterable interface, so you cannot directly iterate over a Map with a for-each
    2. Value is the stored data, and key is the name of the value

9.1 Commonly used APIS for Map

9.1.1. Add operations

  1. Boolean PUT (Object key,Object value) : Stores a key-value pair into a Map
  2. Boolean putAll(Map M) : Add all key/value pairs in M to the current Map

9.1.2 Delete operations

Object Remove (Object Key) : Deletes the key-value pairs of the specified key from the Map and returns the value of the deleted key

9.1.3 Modification Operation

There is no special method, you can call the PUT method, store the same key, different value pair, can override the original.

9.1.4. Query Operation

  1. Int size() : Returns the number of key-value pairs in the current Map
  2. Boolean isEmpty() : Checks whether the number of key-value pairs in the current Map is 0.
  3. Object GET (Object key) : Returns the value of the specified key in the Map. If the key does not exist, null is returned
  4. Boolean containsKey(Object key): Checks whether the Map contains the specified key
  5. Boolean containsValue(Object value): Checks whether the Map contains the specified value
  6. Set keySet() : Returns the Set of all keys in the Map
  7. Collection values() : Returns a Collection of all values in the Map
  8. Set entrySet() : Returns a Set of all key-value pairs in the Map

Lambda 8 expression collection traversal

map.forEach((k,v)->{
   System.out.println(k+""+v); 
});
Copy the code

9.2, HashMap

The underlying HashMap is based on the hash table algorithm. The key object and HashCode value stored in the Map determine the location of storage in the hash table. Since the key in the Map is a Set, the sequence of addition cannot be guaranteed, and repetition is not allowed

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo1{
  public static void main(String[] args) {
    Map<String, String> map = new HashMap<>();
    map.put("girl1"."Beauty");
    map.put("girl2"."Wang Zhaojun");
    map.put("girl3"."The sable cicada");
    map.put("girl4"."Yang Yuhuan");
    System.out.println("How many key-value pairs are there in the map:"+map.size());
    System.out.println(map);
    System.out.println("Contain key girl1:"+map.containsKey("girl1"));
    System.out.println("Whether to include value as diao Chan:"+map.containsValue("The sable cicada"));
// Replace key with girl3 value
    map.put("girl3"."Joe");
    System.out.println(map);
// delete the key pair with key girl3
    map.remove("girl3"); System.out.println(map); }}Copy the code

9.2.1 Iterative traversal of Map

// Get all the keys in the Map
Set<String> keys = map.keySet();
System.out.println("All keys in Map:"+keys);
// Get all the values in the Map
Collection<String> values = map.values();
System.out.println("All values in Map:"+values);
// Get all key-values in the Map.
Set<Entry<String, String>> entrys = map.entrySet();
for (Entry<String, String> entry : entrys) {
  String key = entry.getKey();
  String value = entry.getValue();
  System.out.println(key+"- >"+value);
}
Copy the code

9.2.2, practice

Counts the number of occurrences of every other character in a string

package day14_ArrayList2.classing;

import java.util.HashMap;
import java.util.Scanner;

/ * * *@author Xiao_Lin
 * @version 1.0
 * @date2020/12/17 16:54 * /
public class Test1 {
  // Requirement: Count the number of occurrences of each character in a string
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    String str = scanner.nextLine();
    HashMap<Character, Integer> map = new HashMap();// Create a map. The key of the map stores characters and the value stores the number of occurrences
    // Map traversal
      for (int i = 0; i<str.length(); i++){char c = str.charAt(i);// The STR string is iterated and strongly converted to characters
        if (map.containsKey(c)){// Map contains traversal characters
          Integer value = map.get(c);// If it does, the value of the original character is extracted and incremented
          value+=1;// The number of times increases
          map.put(c,value);// Put the modified value into the map collection
        }else {
          map.put(c,1);// Otherwise put the character into the collection and set the degree to 1} } System.out.println(map); }}Copy the code

9.3, TreeMap

The underlying keys in TreeMap are based on a red-black tree. Since the keys in a Map are also a Set, the order in which they are added cannot be guaranteed, nor can they be repeated. By default, the keys stored in a Map are in natural order (from smallest to largest). In addition to the use of natural sorting can also be custom sorting

import java.util.Map;
import java.util.TreeMap;

public class App {
  public static void main(String[] args) {
    Map<String, String> map = new TreeMap<>();
    map.put("girl4"."Yang Yuhuan");
    map.put("girl2"."Wang Zhaojun");
    map.put("key1"."Beauty");
    map.put("key3"."The sable cicada");
    System.out.println(map);
//-------------------------------------------
    map = newTreeMap<>(map); System.out.println(map); }}Copy the code
package day14_ArrayList2.classing;

import java.util.Comparator;
import java.util.TreeSet;

/ * * *@author Xiao_Lin
 * @version 1.0
 * @date2020/12/17 15:55 * /
public class TreeSet1 {

  public static void main(String[] args) {
    // To use a custom Comparator, pass in an implementation class for the Comparator interface, using an anonymous inner class
    TreeSet<String> set = new TreeSet<String>(new Comparator<String>() {
      @Override
      public int compare(String s1, String s2) {
       if (s1.length()==s2.length()){
         return s1.compareTo(s2);
       }else {
         returns1.length()-s2.length(); }}}); set.add("s12");
    set.add("see");
    set.add("s1234"); System.out.println(set); }}Copy the code

Ten, abnormal

An exception is an abnormal phenomenon that occurs during the running of a program. It will interrupt the running program. An exception is not an error, nor a logical error

An exception causes the program to stop running

Java exception handling mechanism

The Java programming language provides programs with the ability to handle exceptions using the exception handling mechanism, which ensures that the program continues to run in the correct direction after an exception occurs.

Classification of exception handling

Exception handling consists of two types of code blocks:

  1. try… catch
  2. try… catch… finally

10.1. Exception Object

An Exception object is an object automatically generated by the statement in which an Exception occurs. It is automatically created by the JVM. An Exception is created in a Java class by Exception or any other specific subclass named: Exception type +Exception

methods role
toString() Returns the exception type and exception information
getMessage() Return exception information
printStackTrace Print stack information (red)

The stack information looks like this:

The first sentence consists of the exception type and the Message of the exception

Last sentence: The exact location of the exception

10.2, try… catch

We put code that might raise an exception in a try, and if it raises an exception, the catch catches the exception, and the code inside the catch requests processing

10.2.1 syntax format

try{
    // A block of code that may generate an exception
}catch(Exception type E){// Exceptions are caught by catch
    // Exception handling
}
Copy the code

10.2.2, try… Catch execution analysis

10.2.2.1. No exception

If no exception is found, the program runs normally

10.2.2.2 An exception is caught by a Catch

An exception occurs in the program and the exception is caught by the catch, that is, the type of the exception conforms to the type in the catch. In this case, the exception is processed and the program is normally executed after the processing is completed

package day15_exception.classing.exception;

import java.util.Scanner;

/ * * *@author Xiao_Lin
 * @version 1.0
 * @date2020/12/19 forasmuch * /
public class TestException {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    try {
      System.out.println("Please enter the dividend :");
      int num1 = scanner.nextInt();
      System.out.println("Please enter divisor :");
      int num2 = scanner.nextInt();
      System.out.println(num1/num2);
    }catch (Exception e){ 
      System.out.println("Abnormal"); System.out.println(e.getMessage()); }}}Copy the code

conclusion

After an exception occurs, the program does not continue to run from the line of code where the exception occurs, and immediately turns to exception handling

10.2.2.3 Exception Mismatch

The program breaks when an exception does not match

package day15_exception.classing.exception;

import java.util.Scanner;

/ * * *@author Xiao_Lin
 * @version 1.0
 * @date2020/12/19 forasmuch * /
public class TestException {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    try {
      System.out.println("Please enter the dividend :");
      int num1 = scanner.nextInt();
      System.out.println("Please enter divisor :");
      int num2 = scanner.nextInt();
      System.out.println(num1/num2);
    }catch (ArithmeticException e){// Here we catch a dipper exception, but we simulate an InputMismatchException (input matching exception), so program 2 does not match the appropriate exception interrupt here
      System.out.println("Abnormal"); e.printStackTrace(); }}}Copy the code

10.2.3 Multiple Catch

We can write multiple catches for our try code to catch multiple specific exceptions, but be aware that the subclass is on top and the parent class is on bottom at the time of writing, because Java code executes from top to bottom and uses the largest exception that is not available to catch.

package day15_exception.classing.exception;

import java.util.InputMismatchException;
import java.util.Scanner;

/ * * *@author Xiao_Lin
 * @version 1.0
 * @date2020/12/19 forasmuch * /
public class TestException {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    try {
      int num1 = scanner.nextInt();
      System.out.println("Please enter divisor :");
      int num2 = scanner.nextInt();
      int r = num1 / num2;
      System.out.println(r);
    }catch (InputMismatchException e) {
      System.out.println("Incorrect input data");
    }catch(ArithmeticException e) {
      System.out.println("The divisor cannot be zero.");
    }catch(Exception e) {
      System.out.println("Unknown exception");
    }
    System.out.println("Program complete!"); }}Copy the code

10.3, try… catch… finally

try… Catch, as before, is used to catch and handle exceptions, and the finally block is used to handle the end work after the exception.

Finally is always executed whether or not an exception occurs, but the job of finally is just to free up memory, close files, close network connections, close database connections, and so on.

Writing code and changing the value of variables is not recommended in finally, because finally cannot modify the value of a temporary stack

package day15_exception.classing.exception;

import java.util.InputMismatchException;
import java.util.Scanner;

/ * * *@author Xiao_Lin
 * @version 1.0
 * @date2020/12/19 forasmuch * /
public class TestException {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    try {
      System.out.println("Please enter the dividend");
      int num1 = scanner.nextInt();
      System.out.println("Please enter divisor :");
      int num2 = scanner.nextInt();
      int r = num1 / num2;
      System.out.println(r);
    }catch (InputMismatchException e) {
      System.out.println("Incorrect input data");
    }catch(ArithmeticException e) {
      System.out.println("The divisor cannot be zero.");
    }catch(Exception e) {
      System.out.println("Unknown exception");
    }finally {
      System.out.println("I am finally");
    }
    System.out.println("Program complete!"); }}Copy the code

The only case in which finally does not execute is when the JVM exits normally

package day15_exception.classing.exception;

import java.util.InputMismatchException;
import java.util.Scanner;

/ * * *@author Xiao_Lin
 * @version 1.0
 * @date2020/12/19 forasmuch * /
public class TestException {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    try {
      System.out.println("Please enter the dividend");
      int num1 = scanner.nextInt();
      System.out.println("Please enter divisor :");
      int num2 = scanner.nextInt();
      int r = num1 / num2;
      System.out.println(r);
    } catch (Exception e) {
      System.out.println(e.toString());
    // The JVM exits normally
      System.exit(0);
    } finally {
      System.out.println("I am finally");
    }
    System.out.println("Program complete!"); }}Copy the code

10.3.1 There is a return try… catch… finally

package day15_exception.classing.exception;

import java.util.InputMismatchException;
import java.util.Scanner;

/ * * *@author Xiao_Lin
 * @version 1.0
 * @date2020/12/19 forasmuch * /
public class TestException {

  public static int div(int a, int b) {
    int r = 0;
    try {
      r = a / b;
      return r;
    } catch (Exception e) {
      System.out.println(e.toString());
    } finally {
      System.out.println("I am finally");
    }
    return r;
  }

  public static void main(String[] args) {
    System.out.println(div(10.0));
    System.out.println("Program complete!"); }}Copy the code

conclusion

  1. There is a return try… catch… In finally, Funally executes first and then returns
  2. Return is always executed last

shortcuts

Quick try… The shortcut key for catch

  • Eclipse : Shift+Alt+Z
  • IDEA : Ctrl+Alt+T

10.4 Classification of exceptions

Exception inheritance. The Throwable class is the parent class of all errors or exceptions in the Java language.

10.5, the Error

Error, which represents a problem with the JVM (Java Virtual Machine) while the code is running. Such as system crash or memory overflow, there is no need to deal with Error, the only thing we can do is wait, which is rarely seen in development, common are the following

The Error type describe
StackOverflowError This error is thrown when the application recurses too deeply and a stack overflow occurs. Such as an infinite loop or recursive call with no exit
OutOfMemoryError This error is thrown when the Java virtual machine cannot allocate an object because it is out of memory or there is no memory available for the garbage collector. For example, new a very large number of objects without releasing them.

10.6, the Exception

Exception refers to a mild to moderate problem that can be predicted and recovered. For example, the divisor is 0, the array index is out of bounds, and so on. In this case, the programmer ensures the normal operation of the program until the end through reasonable exception handling.

Exception construction method

// Create a new exception with a null exception message
Exception();
// construct a new exception whose exception message is message
Exception(String message)
Copy the code

Classification of anomalies

  1. Runtime exception
  2. Abnormal during inspection

10.6.1 Runtime exceptions

RuntimeException is an exception that can be handled or not handled when an exception occurs during program execution. Its parent class is RuntimeException

Runtime exception describe
InputMismatchException Input mismatch exception
ArithmeticException Mathematical calculation exception (e.g. divisor 0)
IndexOutOfBoundsException Subscript/index out of bounds exception
ArrayIndexOutOfBoundsException Array index out of bounds exception
StringIndexOutOfBoundsException String subscript is out of bounds
NullPointerException Null pointer exception
IllegalArgumentException Method received an invalid parameter
ClassCastException The cast is abnormal
NumberFormatException Number format conversion exception, such as “ABC” to a number

10.6.2 Exceptions during the check

Checked Exception: Also called compile-time Exception, a check program may have abnormalities during compilation and must be handled during program running. Otherwise, the compilation fails. In Java, there is no specific parent class, and Exception is usually used to indicate check-time exceptions.

Abnormal during inspection describe
ParseException Format (date, time, etc.) parsing exception
ClassNotFoundException Class found no exception
FileNotFoundException No exception found in file
IOException IO exception
SQLException SQL exceptions
UnsupportedEncodingException String encoding exceptions are not supported

10.7 declare exceptions

10.7.1, throws

We declare possible exceptions for a method using throws.

If the definition of a method does not know that an exception will occur when the caller calls the method, but the definition does not know how to handle the exception, the definition can use the throws keyword to declare exceptions. Multiple exceptions can be declared, separated by commas

[Modifier] Return value Type Method name (parameter list) throws exception 1, exception 2,,, {}Copy the code

When declaring an exception, the classification of the exception determines whether the outside world (the calling place) must handle the exception generated by the method. Declare a checktime exception if it needs to be handled by the outside world; declare a run-time exception otherwise.

package day15_exception.classing.exception;

import java.util.InputMismatchException;
import java.util.Scanner;

/ * * *@author Xiao_Lin
 * @version 1.0
 * @date2020/12/19 forasmuch * /
public class TestException {

  public static int div(int a, int b) throws Exception{// A checktime exception was thrown
    int r = 0;
      r = a / b;
      return r;
  }

  public static void main(String[] args) {
    System.out.println(div(10.0));// The compiler fails because the exception is not resolved
    System.out.println("Program complete!"); }}Copy the code
public static void main(String[] args) {// This is how it works
    try {
      System.out.println(div(10.0));
    } catch (Exception e) {
      e.printStackTrace();
    }
    System.out.println("Program complete!");
  }
Copy the code

10.7.2. Declare the relationship between exceptions and overloading

There is no relationship

10.7.3. Declare the relationship between exceptions and overrides

If a parent class declares a runtime exception, a subclass can declare a runtime exception or not; If the parent class declares check-time exceptions, subclasses can declare check-time exceptions or not declare or run-time exceptions.

If the parent class does not declare any exceptions, subclasses either do not declare any exceptions, or they can declare run-time exceptions but not check-time exceptions.

Conclusion: Exceptions for subclass methods <= exceptions for superclass methods

10.7.4. Abnormal Up-throw

In the actual development process, if there is an exception when calling A class A method and the caller does not know how to handle the exception, we can continue to declare the exception up, we call this process of exception throwing.

Exceptions encountered in practice can be handled internally before being thrown up

public class Sub extends Parent{
	@Override
	public void showInfo(a) throws Exception{}}Copy the code
public class Test01 {
	public static void main(String[] args) throws Exception{
		Sub sub = new Sub();
		sub.showInfo();
		System.out.println("Program complete!"); }}Copy the code

10.7.5 Manually Throwing an exception

In the actual development process, developers can also according to the needs of the program, manually throw exceptions, through the throw keyword, programmers can actively throw certain types of exceptions.

package com.kal02.exception07;
public class Student {
	private String name;
	private String gender;
public void setGender(String gender) throws RuntimeException{
	if(gender.equals(Student.MAN)||gender.equals(Student.WOMAN)){
		this.gender = gender;
	}else {
		// Manually throw an exception
		throw new RuntimeException("Only male or female."); }}}Copy the code

10.8. Custom Exceptions

You can customize exceptions when the exception type in the JDK does not meet your program’s needs (that is, when you need to define specific business exceptions).

Steps for customizing exceptions:

  1. Determine the type of exception (check-time exception, run-time exception).
  2. Inherits an Exception’s parent (Exception at check time inherits Exception, RuntimeException at run time)
  3. Declare the constructor (define the constructor of the exception class, and pass in the exception information, the constructor subclass of the parent class cannot inherit)

Student class

package day15_exception.classing.customize;

/ * * *@author Xiao_Lin
 * @date2020/12/19 beginning * /
public class Student {
  private String name;
  private String Gender;

  public Student(String name, String gender) {
    this.name = name;
    Gender = gender;
  }

  public Student(a) {}public String getName(a) {
    return name;
  }

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

  public String getGender(a) {
    return Gender;
  }

  public void setGender(String gender) throws GenderException{
    if (gender.equals("Male") || gender.equals("Female") || gender.equals("Confidential")){
      Gender = gender;
    }else {
      throw new GenderException("Sex is illegal.");//s}}}Copy the code

Custom exception classes

package day15_exception.classing.customize;

/ * * *@author Xiao_Lin
 * @date2020/12/19 17:27 * /
public class GenderException extends Exception{

  public GenderException(a) {}public GenderException(String message) {
    super(message); }}Copy the code

The test class

package day15_exception.classing.customize;

/ * * *@author Xiao_Lin
 * @date2020/12/19 17:28 * /
public class CustomizeException {

  public static void main(String[] args) {
    Student student = new Student("Dormitory"."Nd");
    try {
      student.setGender("Dormitory");
    } catch(GenderException e) { e.printStackTrace(); }}}Copy the code

10.9. Interview questions

Throws and throws in Java exceptions

  • Throws:

    1. It is used to declare all possible exceptions to a method. It does nothing but uploads the exception to whoever calls me.

    2. The exception class name is used after the method declaration.

    3. Multiple exceptions can be declared, separated by,.

    4. Throws indicates a possibility. It only says that such exceptions may occur, but not 100%.

  • Throw:

    1. Throw is used to throw a specific exception.
    2. In the method body, it is followed by the object name of a specific exception.
    3. Only one exception object name can be thrown.
    4. Represents an exception thrown, handled by a statement in the method body.
    5. Throw indicates that an exception occurs, and throws indicates that an exception must occur.