The penultimate Java programming foundation, thanks for not giving up their own. Study notes refer to zhang Huansheng, chief editor of Java Programming Basics. The content of this book is more suitable for the introduction of small white without what foundation, after learning a chapter and exercises, more suitable for beginners. Self-discipline, motivation, hard work, and starting with a small goal that is impossible to achieve.

This article has been included in [Column]

🌳 Introduction to Java 🌳

Previous [section] :

🎉 Java Basics 16-30,000 word summary of input and output streams

😀Java Basics 150,000-word summary of basic knowledge of exception handling

👋Java basics 14 – Internal class details summary

🤞Java basics 13 – Interface detailed knowledge summary

😁Java Basics 12 – Abstract Classes

✨ Essential Java basics 11 – Polymorphism in detail and principles

🙌Java basics 10 – Class inheritance details

😊Java Basics 9 – Wrapper classes

😎Java Basics 8 – Math class, Random class, date and time class

👌Java Basics 7 – Basic common methods for strings

😜Java basics six – one-dimensional arrays

👏Java Basics five – Class encapsulation

🤳Java basics four – member variables and local variables

👍 Java basic three – method declaration and invocation, recursion

😘Java Basics 2 – Classes and objects

👍Java Basics – Java language basics

First, Java collection introduction

1.1 What is a set?

Java is an object-oriented language, we naturally need a container to store objects when programming, array can meet this demand, but the length of array initialization is fixed, but we often need a variable length of the container, therefore, the collection appeared.

Java collections In the java.util package, these collections can be thought of as containers for storing, retrieving, manipulating, and transferring multiple elements of the same nature.

In reality, containers mainly add objects, delete objects, empty objects and so on. The clothes in the closet can be put in and taken out, as well as arranged for quick search. The same goes for Java collections, some of which are easy to insert and delete, and some of which are easy to find data.

1.2 Inheritance relationship of collection classes

The Collection interface is the root interface of the Collection class. There is no direct implementation class for this interface in Java. Map is another interface in the java.util package. It is separate from the Collection interface, but both are part of the Collection class. ==Map contains key-value pairs. A Map cannot contain duplicate keys, but can contain the same value==.

Common collection classes in Java are List collection, Set collection, and Map collection. List and Set inherit Collection interface (Queue is added after Java5). The implementation class of List interface is ArrayList and LinkedList.

MapInterfaces have two implementation classes,HashMap.HashTable, as shown below:

1.3 The difference between collections and arrays

• Length difference: Arrays are static. The length of an array instance is immutable. Once created, the capacity cannot be changed. The collection can dynamically expand the capacity, the length of the collection is variable, and the size can be dynamically changed according to needs. The collection provides more member methods, which can meet more needs. When writing the program do not know the number of objects, in the case of insufficient space to achieve automatic expansion capacity, priority to use the set to achieve, array is not applicable at this time

• Content differences: Collections do not declare the types of elements that can be stored. Collections can store elements of different types. An array declares the type of the element it contains and can hold only elements of a single type

• Element distinction: Collections can only store elements of reference type. Arrays can store reference types as well as primitive types

• Arrays are built-in data types in the Java language. They are arranged in a linear fashion and are the fastest to execute or type check.

Each collection class is described in detail below.

Collection interface and Iterator interface

2.1 the Collection interface

As mentioned above, the Collection interface is the parent of the List, Set, and List interfaces, and the methods defined in this interface can be used for Set and List collections. The Collection interface defines methods for a Collection of operations.

2.1.1 Common methods of Collection interface

methods	instructions
boolean add(Object o)	Adds the specified object o to the collection, returning true on success, false on failure
boolean addAll(Collection c)	Adds all elements from the specified collection c to the collection, returning true on success, false otherwise
void clear()	Deletes all elements in the collection
boolean contains(Object o)	Returns true if the collection contains the specified element
boolean containsAll(Collection c)	Checks whether the set contains all elements of c, and returns true
boolean isEmpty()	Returns true if the set is empty
Iterator iterator()	Returns an Iterator object that can be used to iterate over elements in a collection
boolean remove(Object o)	Removes the specified element O from the collection, returning true on success
boolean removeAll(Collection c)	Removes all elements in the collection containing collection C, returning true if 1 or more elements are deleted
boolean retainAll(Collection c)	Removes elements in the collection other than those in collection C, returning true if the collection element on which the method was called has changed
int size()	Returns the number of elements in the collection
Object[] toArray()	Returns an array containing all the elements in the collection

2.1.2 Collection Examples of common Operation methods

public class Example8_1 {
    public static void main(String[] args) {
        Collection collection = new ArrayList();// Assign a subclass object to a reference variable of the parent class
        collection.add("1");
        collection.add("2");// Add elements to the collection
        System.out.println(The number of elements in the collection is:+collection.size());
        collection.clear();// Delete all elements
        System.out.println("Collection does not have any elements:"+collection.isEmpty());
        collection.add("3");
        collection.add("4");
        System.out.println("Does the collection contain \"4\" string:"+collection.contains("4"));

        Collection collection1 =new ArrayList();
        collection1.add("3");
        collection1.add("4");
        collection1.add("c");
        collection1.retainAll(collection);// Remove elements not included in the collection from collection1
        System.out.println("Collection1 collection elements:+collection1);
        System.out.println(Does the collection completely contain collection1?+collection.containsAll(collection1));
        System.out.println("Collection elements of a collection:"+collection); }}Copy the code

The result after compiling and running is:

The number of elements in the collection is:2Collection Does not have any elements:trueCollection Indicates whether the collection contains"4"String:trueCollection1 collection elements: [3.4Collection1 = collection1;trueCollection elements of a collection: [3.4]

Copy the code

2.2 the Iterator interface

2.2.1 What does the Iterator Interface Do?

Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator

Iterator obtains or deletes an element by iterating through (iteratively accessing) the elements of a Set. Iterator is used only to traverse the Set. It applies to sets, lists, maps, and subclasses of the Set. Iterator objects are also called iterators.

ListIterator extends the Iterator base quotient to allow two-way traversal of lists, while Iterator can only iterate backwards, but ListIterator can only be used with lists and their subclasses.

2.2.2 Common methods of Iterator interfaces

methods	The interface type	instructions
boolean hasNext()	Iterator	There are also elements that can iterate to return true
Object next()	Iterator	Returns the next element
void remove()	Iterator	Delete the current element
void add(Object o)	ListIterator	Inserts the specified element O into the collection, which is returned when the next() method is called
boolean hasNext()	ListIterator	Returns true if the next element exists
boolean hasPrevious()	ListIterator	Returns true if the previous element exists
Object next()	ListIterator	Returns the next element in the list
Object previous()	ListIterator	Returns the previous element in the list
int nextIndex()	ListIterator	Returns the index of the next element in the list, or the size of the list if none exists
int previousIndex()	ListIterator	Returns the index of the previous element in the list, or -1 if none exists
void remove()	ListIterator	Delete the current element
void set(Object o)	ListIterator	Assign o to the current element, the one returned after the last call to the next or previous method

2.2.3 Examples of common Iterator methods

1. Use Iterator to output collection elements

class Example8_2 {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        arrayList.add("a");
        arrayList.add("b");
        arrayList.add("c");
        System.out.println("The contents of the set are:");
        Iterator iterator = arrayList.iterator();The iterator() method returns an iterator object
        while (iterator.hasNext()){
            Object o = iterator.next();// Loop output
            System.out.println(o);
            if(o.equals("b")){
                iterator.remove();// Delete the current element
            }
        }
        System.out.println("After deleting element B, the contents of the collection will be:"+arrayList); }}Copy the code

The result after compiling and running is:

[a, c] [a, c] [b, c]Copy the code

2. Reverse output using Iterator

class Example8_3 {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        arrayList.add("a");
        arrayList.add("b");
        arrayList.add("c");
        ListIterator listIterator = arrayList.listIterator();// Return the ListIterator object
        while (listIterator.hasNext()){
            System.out.println(listIterator.next());
        }

// Print the list in reverse
        while(listIterator.hasPrevious()){ Object o= listIterator.previous(); System.out.println(o); }}}Copy the code

The result after compiling and running is:

a
b
c
c
b
a
Copy the code

Alternatively, using the foreach loop to iteratively access elements in a collection can achieve the same effect:

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

The result after compiling and running is:

a
b
c
Copy the code

A List of

The elements of a List collection are ordered and allowed to be repeated. List collections have two main implementation classes: the ArrayList class and the LinkedList class.

3.1 the List interface

The List interface implements the Collection interface, so the List interface has all the methods provided by the Collection interface, and the List interface provides some other methods as well.

3.1.1 Common methods of the List interface

methods	instructions
boolean add(int index, Object element)	Index indicates the position to which element is added. The index position of other objects is moved one bit later, starting from 0
E remove(int index)	Removes the specified location element from the list
E set(int index, E element)	Replaces the element in the list at the specified position with the specified element
E get(int index)	Returns the element in the list at the specified location
int indexOf(Object o)	Returns the index of the specified element position in the list. If more than one index exists, return the index position of the first index. If not, return -1
int lastIndexOf(Object o)	Returns the index of the specified element position in the list. If more than one index exists, return the index position of the last one. If not, return -1
ListIterator<> listIterator()	Returns list iterators for the elements of this list (in the appropriate order)
ListIterator<> listIterator(int index)	Returns list iterators for the elements of this list, in the appropriate order, starting at the specified position in the list
List <> subList(int fromIndex, int toIndex)	Returns a List collection object from fromIndex (included) to toIndex (not included) for the specified range.

As you can see from the table, the common methods provided by the List interface are all related to indexes. This is because the ==List collection is a List type and stores objects in a linear fashion. Objects can be manipulated by their indexes. = =

The common implementation classes of List interface are ArrayList and LinkedList. When using List set, it is usually declared as List type and instantiated as ArrayList or LinkedList according to actual needs. For example:

List<String> l = new ArrayList<String>();// Use the ArrayList class to instantiate the List collection
List<String> l2 = new LinkedList<String>();// Instantiate the List collection using the LinkedList class
Copy the code

3.1.2 Examples of common functions of the List interface

1. List common method examples

class Example8_4{
    public static void main(String[] args) {
        String a = "A", b = "B", c = "C", d = "D", e = "E";
        List<String> list = new LinkedList<String>();
        list.add(a);
        list.add(e);
        list.add(d);
        list.set(1, b);// Change object e at 1 to object B
        list.add(2, c);// add object C to index position 2
        Iterator<String> it = list.iterator();
        while(it.hasNext()) { System.out.println(it.next()); }}}Copy the code

The following information is printed on the console:

A
B
C
D
Copy the code

3.2 ArrayList class

3.2.1 Constructor of the ArrayList class

methods	instructions
ArrayList()	Construct an empty array of initial capacity 10
ArrayList(Collection<? extends E> c)	Construct an array containing the elements of a Collection in the order returned by the Collection iterator
ArrayList(int initialCapacity)	Constructs an empty array with the specified initial capacity
ArrayListThe default constructor creates an empty array with an initial capacity of 10. Then the expansion algorithm is: the size of the original array + half of the original array. Recommend creatingArrayListIs given an initial capacity.

3.2.2 Common method examples of the ArrayList class

1. ArrayList is used to implement the List interface, and ArrayList can use the common methods of List interface.

class Example8_5{
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        arrayList.add("a");
        arrayList.add("b");
        arrayList.add("c");
        System.out.println(The elements of an arrayList are:+arrayList);
        arrayList.set(0."c");// Change position object A with index 0 to object C
        System.out.println("The elements of an arrayList are+arrayList);
        arrayList.add(1."e");// Add object e to index 1
        System.out.print(The elements of an arrayList are:);
        for (int i=0; i<arrayList.size(); i++){ System.out.print(arrayList.get(i));// The for loop iterates through the arrayList collection elements
        }
        System.out.println("");
        System.out.println("ArrayList specifies the index of element C."+arrayList.indexOf("c"));// Returns the index of the specified element c position in the list
        System.out.println("ArrayList specifies that the index of the last position of element C is+arrayList.lastIndexOf("c"));Returns the index of the last position of the specified element c in the list
        System.out.println("The specified region of arrayList is"+arrayList.subList(1.2));// return a List of objects that return a specified range [1,2]}}Copy the code

The result after compiling and running is:

The elements of arrayList are: [A, B, C] The elements of arrayList are [C, b, c] the elements of arrayList are :cebc arrayList Specifies the index of element C0ArrayList specifies that the index of the last position of element C is3ArrayList specifies field [e]Copy the code

2. ArrayList is used to implement the List interface, and ArrayList can use the common methods of List interface.

class Person{
    private String name;
    private long id;

    public String getName(a) {
        return name;
    }

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

    public long getId(a) {
        return id;
    }

    public void setId(long id) {
        this.id = id; }}class Example8_6 {
    public static void main(String[] args) {
        List<Person> list = new ArrayList<Person>();
        String[] names = {"Li bai"."Du fu"};
        long[] id ={20222.22222};
        for (int i=0; i<names.length; i++){ Person person =new Person();
            person.setName(names[i]);
            person.setId(id[i]);
            list.add(person);
        }

        for (int i=0;i<list.size();i++){
            Person person = list.get(i);
            System.out.println(person.getName()+person.getId());
        }
    }
}
Copy the code

The result after compiling and running is:

Li bai20222Du fu22222
Copy the code

3.3 LinkedList class

3.3.1 Common methods of the LinkedList class

methods	instructions
void addFirst(E e)	Inserts the specified element at the beginning of this list
void addLast(E e)	Inserts the specified element at the end of this list
E getFirst()	Returns the element at the beginning of the list
E getLast()	Returns the element at the end of the list
E removeFirst()	Removes the element at the beginning of the list
E removeLast()	Removes the element at the end of the list

3.3.2 Examples of common methods of the LinkedList class

1. Write the program using the methods in the table above

public class Example8_7 {
    public static void main(String[] args) {

        LinkedList linkedList = new LinkedList();
        linkedList.add("a");
        linkedList.add("b");
        linkedList.add("c");
        linkedList.add("d");
        // Get and enter the object at the beginning of the list
        System.out.println("The list begins with:"+linkedList.getFirst()+"The end element of the list is:"+linkedList.getLast());

        linkedList.addFirst("rr");// Add an object to the beginning of the list
        System.out.println("All elements in the list:"+linkedList);
        linkedList.removeLast();// Remove the end of the list element
        System.out.println("The end element of the list is:"+linkedList.getLast());// Get and print the object at the end of the list}}Copy the code

The result after compiling and running is:

The table starts with: A The table ends with: D All the table elements are [rr, a, b, c, d] the table ends with: CCopy the code

3.4 Comparison of List with ArrayList and LinkedList

First, List is an interface, and ArrayList and LinkedList are the classes that implement that interface.

When I was studying, I compared several examples and saw a few lines of code, which led to some problems:

List list; / / the correct list = null;
List list=new List(); // Is the wrong way to use it
ArrayList arrayList = new ArrayList(); 
List list = new ArrayList(); 
List<String> list = new ArrayList<String>();
Copy the code

List() =new List(); List() =new List(); List () {List ();

ArrayList = new ArrayList(); ArrayList = new ArrayList(); This object retains all properties of the ArrayList;

List List = new ArrayList() creates an ArrayList object and goes up to List. Now it’s a List object, and some ArrayList has properties and methods that List doesn’t, so it can’t be used anymore. (Think of some explanations for polymorphism: == Neither interfaces nor abstract classes can be instantiated, but they can create a reference to their own object, and their implementation class or subclass acts as such. This is the advantage of polymorphism in object-oriented programming ==)

You learned the principle of polymorphism earlier: A List owns all the attributes and methods of a List, and does not own the attributes and methods unique to its implementation class ArrayList. If the List and ArrayList have the same attributes (such as int I) and the same methods (such as void f()), then list. I calls I in the List and list.f() calls f() in the ArrayList.

List List = new ArrayList(); List List = new ArrayList() The problem is that the List interface has multiple implementation classes. Now you’re using ArrayList, and you might someday need to switch to another implementation class, such as LinkedList or Vector, etc. You just need to change this line: List = new LinkedList(); This allows the list object to exist in multiple forms. Other code that uses the list doesn’t need to be changed at all. If you start with ArrayList alist = new ArrayList(), then all of the methods and properties specific to the ArrayList implementation class will be modified.

List

List = new ArrayList

() uses generics and polymorphism: polymorphism is explained above, and generics is covered in the next section.

3.5 Comparison of ArrayList and LinkedList

An ArrayList, like an array, is arranged in a linear order and can be thought of as an array of variable size. If you need to access the elements in the collection according to the index position, so the high efficiency of the linear sequential storage method, but if the ArrayList insert and delete elements, has several times slower, as specified in the insert (delete) the index position of the element, the current element and the element after the corresponding move back one element (or after moving forward a), Thus affecting the efficiency of operation on the set.

LinkedList uses a LinkedList data structure in its implementation. Compared with ArrayList, LinkedList has a slower access speed, but it inserts and deletes familiar blocks. The main reason is that when inserting and deleting elements, it only needs to modify the corresponding link position and does not need to move a large number of elements.

Vector is an implementation of collections from older versions of Java. It operates almost the same as ArrayList, but Vector is a thread-safe dynamic array.

A Set of

4.1 the Set interface

List stores objects in the order in which they were inserted. Set stores objects out of order, so to speak, in an incomplete disorder state.

The objects in a Set are not sorted in any particular way, they are simply added to it, but the Set cannot hold duplicate objects. Because the Set interface implements the Collection interface, the Set interface has all the common methods provided by the Collection interface.

4.2 HashSet class

HashSet is the most commonly used implementation class of Set. It stores the elements in the Set according to the Hash algorithm and determines the storage location of the object according to the Hash code of the object. It has good access and search performance. The main methods of the HashSet class are:

4.2.1 Common methods of the HashSet class

methods	instructions
boolean add(E e)	Adds elements to the collection that are not in the collection
void clear()	Removes all elements from the collection
boolean contains(Object o )	Returns true if the collection contains the specified element
boolean isEmpty()	Returns true if it is an empty collection
Iterator iterator()	Returns an iterator that iterates over elements in this collection
boolean remove(Object o)	Delete the specified element
int size()	Returns the number of elements in the collection

4.2.2 Examples of common methods of HashSet class

Implementation of HashSet class:

public class Example8_8 {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("a");
        hashSet.add("null");
        hashSet.add("b");
        hashSet.add("c");
        hashSet.add("d");
        System.out.println("The elements of the set are :"+hashSet);
        hashSet.remove("b");
        System.out.println("Does the set contain b elements?"+hashSet.contains("b"));
        Object[] objects = hashSet.toArray();
        System.out.print("The elements in the array are :");
        for (Object o:objects){
            System.out.print(o);
        }
        hashSet.clear();
        System.out.println("\n"+"Does the set contain no elements :"+hashSet.isEmpty()); }}Copy the code

The result after compiling and running is:

The elements of the set are :[a, b, c,nullD] whether the set contains b elements:falseWhether the acNULLD collection does not contain any elements:true
Copy the code

You can see that the elements in the HashSet are not stored in order and can be null. There is only one null. Repeatedly add elements to the HashSet whose values are displayed only once.

Duplicate elements are not allowed in a Set. When inserting an object into a Set, how do I determine if the object already exists in the Set?

When adding a new object to a HashSet object, the Java system first calls the object’s hashCode() method to obtain the hashCode of the object. How to find the corresponding storage area according to the hashCode? If the storage area already has objects, the equals() method is called to compare them to the new elements. If they are the same, they are not saved; if they are different, they are placed at another address.

For user-defined objects, you need to override the hashCode() and equals() methods to avoid adding objects repeatedly and keep the program running properly.

4.3 the TreeSet interface

4.3.1 Common methods of TreeSet class

The elements in the TreeSet collection are sorted, and the objects are stored according to the data structure of the red-black tree. TreeSet provides some additional methods.

methods	type	instructions
TreeSet()	structure	Construct an empty Set that sorts the elements according to their natural order
TreeSet(Collectio c)	structure	Initialize Set with and of class c
TreeSet(Comparator comparator)	structure	Sort according to the comparison method specified by the Comparator
TreeSet(SortedSet s)	structure	Constructs a set containing an s element
Object first()	ordinary	Returns the first sorted element of the Set
Object last()	ordinary	Returns the last sorted element in the Set
E lower(E e)	ordinary	Returns the largest element in this Set that is strictly less than the given element, or null if none exists
E higher(E e)	ordinary	Returns the largest element in this Set that is strictly greater than the given element, or nuL if none exists
SortedSet subSet(E fromElement, E toElement)	ordinary	Returns an ordered collection of elements whose scope is fromElement,toElement
SortedSet headSet(E toElement)	ordinary	Returns a partial collection of this Set whose elements range [,toElement) is less than toElement
SortedSet tailSet(E fromElement)	ordinary	Returns a partial collection of this Set with elements in the range [fromElement,] greater than or equal to toElement

4.3.2 Examples of common methods of TreeSet class

The TreeSet method is used to operate on the elements in the collection.

class Example8_9 {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet();
        TreeSet treeSet1 = new TreeSet();
        treeSet.add(10);
        treeSet.add(3);
        treeSet.add(8);
        treeSet.add(0);
        treeSet1.add("b");
        treeSet1.add("k");
        treeSet1.add("z");
        treeSet1.add("a");
        // Prints the collection element, seeing that the collection is already in sorted state
        System.out.println("Elements in the treeSet set"+treeSet);
        System.out.println("Elements in treeSet1 collection"+treeSet1);
        System.out.println("First element in treeSet set:"+treeSet.first()+", the last element in the treeSet set:"+treeSet.last());
        System.out.println("First element in treeSet1 collection:"+treeSet1.first()+", the last element in the treeSet1 collection:"+treeSet1.last());
        // Return the set less than 5, excluding 5;
        System.out.println(treeSet.headSet(5));
        // Return the set less than c in the set
        System.out.println(treeSet1.headSet("c"));
        // Returns a set greater than or equal to 8
        System.out.println(treeSet.tailSet(8));
        // Returns a set greater than or equal to 9 and less than 11
        System.out.println(treeSet.subSet(9.11)); }}Copy the code

The result after compiling and running is:

Elements in the treeSet set [0.3.8.10[a, B, K, z] First element in treeSet set:0, the last element in the treeSet set:10First element in treeSet1: a, last element in treeSet1: z [0.3]
[a, b]
[8.10]
[10]
Copy the code

From the above results, TreeSet sorts elements by their actual size, unlike List, which sorts elements by insertion order.

TreeSet general sorting rules: If it is a value, it is based on the size; If it is a character, sort the character according to its Unicode value. If the value is date and time, sort it in chronological order. If Boolean, true is greater than false

4.4 Set implements class performance analysis

The elements in the TreeSet set are unique and have been sorted, so the additional red-black tree algorithm is used for sorting. If a set that maintains the order is needed, TreeSet should be selected.

The elements in a HashSet are unique and sorted according to the Hash algorithm. If you often add or query elements, select HashSet.

LinkedHashSet is a subclass of HashSet. It also determines the storage location of elements according to the hashCode value of elements. It uses a linked list to maintain the order of elements, so the insert and delete performance is lower than that of HashSet, and the performance is higher when iteratively accessing all elements in the collection.

A Queue

5.1 the Queue interface

The Queue interface is a first-in, first-out (FIFO) data structure that inherits the Collection interface, while the LinkedList implements the List and Deque interfaces.

5.2 Deque Interface and ArrayDeque class

The Deque interface is a subinterface of the Queue interface, and the main implementation classes of the Deque interface are the LinkedList class (previously learned) and the ArrayDeque class.

The ArrayDeque class implements a double-ended queue using a mutable loop array that does not allow null elements.

5.2.1 Deque interface and Common methods of ArrayDeque class

methods	instructions
boolean add(E e)	Insert element E at the end of this double-ended queue
void addFirst(E e)	Insert element E at the beginning of this double-ended queue
void addLast(E e)	Insert element E at the end of this double-ended queue
void clear()	Deletes all elements in the queue
boolean contains(Object o)	Checks whether the specified element is included
element()	Gets the header in the queue
getFirst()	Gets the first element in the queue
getLast()	Gets the last element in the queue
boolean offer(E e)	Insert element E at the end of this double-ended queue
boolean offerFirst(E e)	Insert element E at the beginning of this double-ended queue
boolean offerLast(E e)	Insert element E at the end of this double-ended queue
removeFirst()	Gets and deletes the first element in the queue
removeLast()	Gets and deletes the last element in the queue
int size()	Returns the number of all elements in the queue

5.2.2 Examples of common methods of Deque interface and ArrayDeque Class

class Example8_10 {
    public static void main(String[] args) {
        ArrayDeque arrayDeque = new ArrayDeque();
        arrayDeque.addFirst("b");
        arrayDeque.offerFirst("k");
        arrayDeque.addLast("z");
        arrayDeque.add("a");
        // Prints the collection element, seeing that the collection is already in sorted state
        System.out.println("Elements in an arrayDeque queue"+arrayDeque);
        System.out.println("Does the arrayDeque queue contain c:"+arrayDeque.contains("c"));
        System.out.println(arrayDeque.removeFirst());// Delete the first element
        System.out.println("First element of an arrayDeque queue:"+arrayDeque.element());
        System.out.println("First element of an arrayDeque queue:"+arrayDeque.getFirst());
        System.out.println("Number of elements in an arrayDeque queue:"+arrayDeque.size()); }}Copy the code

The result after compiling and running is:

[k, b, z, a] Whether an arrayDeque queue contains c:falseNumber of elements in a queue:3
Copy the code

5.3 PriorityQueue class

PriorityQueue is the implementation class of the Queue interface, whose bottom layer is implemented by the heap. The queue is adjusted each time an element is inserted or deleted, and the queue always forms a minimum heap or maximum heap.

5.3.1 Common methods of PriorityQueue

methods	instructions
boolean add(E e)	Inserts the specified element into the priority queue
boolean offer(E e)	Inserts the specified element into the priority queue
void clear()	Delete all elements
boolean contains(Object o)	Whether to contain the specified element
peek()	Gets the head of this priority queue, null if the queue is empty
poll()	Gets and deletes the header of this priority queue, returning NULL if the queue is empty
boolean remove(Object o)	Delete the specified element
int size()	Returns the number of priority queue elements

5.3.2 Examples of common methods of PriorityQueue

class Example8_11 {
    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.add(3);
        priorityQueue.offer(7);
        priorityQueue.add(1);
        priorityQueue.add(4);

        System.out.println("PriorityQueue Elements in the queue" + priorityQueue);
        System.out.println("PriorityQueue contains 2:" +  priorityQueue.contains(2));
        System.out.println("PriorityQueue first element of the queue:" +   priorityQueue.peek());
        System.out.println("PriorityQueue first element of the queue:" +   priorityQueue.poll());
        System.out.println("ArrayDeque queue of elements after deleting elements :"+priorityQueue);
        priorityQueue.remove(7);
        System.out.println("ArrayDeque queue of elements after deleting elements :"+priorityQueue);
        System.out.println("Number of elements in an arrayDeque queue:"+ priorityQueue.size()); }}Copy the code

The result after compiling and running is:

PriorityQueue Elements in the queue [1.4.3.7] priorityQueue Specifies whether it is contained in the queue2:falsePriorityQueue The first element of the queue:1PriorityQueue The first element of the queue:1After deleting elements,arrayDeque queue elements :[3.4.7] After the element is deleted,arrayDeque queue elements :[3.4ArrayDeque Specifies the number of elements in a queue:2

Copy the code

6. Map set

6.1 the Map interface

A Map set is used to store mapped data. A Map set stores two groups of values. One group of values is the key key and the other is the value value. There is a one-to-one relationship between key and value. You can find a unique value by using the specified key. Key keys in a Map cannot be duplicated (key keys are unique), and value values can be duplicated.

6.1.1 Common Methods of Map Interfaces

methods	instructions
put(K key, V value)	Adds the specified key-value mapping to the collection
void putAll(Map<? extends K, ? extends V> m)	Adds all key-value mappings for the specified collection to the collection
boolean containsKey(Object key)	Determines whether this collection contains the specified key mapping
boolean containsValue(Object value)	Determines whether this collection contains the specified value mapping
V get(Object key)	Returns the value mapped to the specified key, or NULL otherwise
Set keySet()	Returns all key objects in a Set collection
Collection values()	Returns all value objects in the Collection as a Collection
V remove(Object key)	Deletes and returns the value object corresponding to the key
void clear()	Clears all mappings in the collection
boolean isEmpty()	Determines whether the set is empty
int size()	Returns the number of key-value mappings in the collection
boolean equals(Object o)	Compares whether the specified key-value mapping is equal

6.1.2 Examples of common Map Interface methods

class Example8_12 {
    public static void main(String[] args) {
        Map map1 = new HashMap<>();
        Map map2 = new HashMap<>();
        Map map3 = new HashMap<>();
        map1.put(1001."Bill");
        map1.put(1002."a");
        map1.put(null.null);
        map2.put(1003."B");
        map2.put(100."C");
        map3.put(100."C");
        map3.put(1003."B");

        System.out.println("The object of map1 is:" + map1);
        System.out.println("The object of map2 is:" + map2);
        map1.putAll(map2);
        System.out.println("The object of map1 is:" + map1);
        System.out.println("Map1 contains key object null:" + map1.containsKey(null));
        System.out.println("Map1 contains \"a\" values:" + map1.containsValue("a"));
        System.out.println("Map1 key 1001 object is:" + map1.get(1001));
        System.out.println("The key object of map1 is:" + map1.keySet());
        System.out.println("The value object of map1 is:" + map1.values());
        System.out.println("After the 1003 key object is deleted, the value object of map1 is:" + map1.remove(1003) + "," + map1);
        map1.clear();
        System.out.println("The value object of map1 is:" + map1);
        System.out.println("Map1 is null:" + map1.isEmpty());
        System.out.println("Map2 size:" + map2.size());
        System.out.println("Map2 and map3 are the same object:"+ map2.equals(map3)); }}Copy the code

The result after compiling and running is:

The objects of map1 are: {null=null.1001=Bill, 1002=a} map2 = {100=C, 1003=B} map1: {null=null.100=C, 1001=Bill, 1002=a, 1003=B} map1 contains key objectsnull:trueMap1 specifies whether map1 contains"a"Value:trueMap1 keys1001The key object of Bill map1 is [null.100.1001.1002.1003] map1 value object: [null, C, Bill, A, B]1003After the key object, the value object of map1 is: B,{null=null.100=C, 1001=Bill, 1002=a} map1 is the value of {} whether map1 isnull:trueMap2 size:2Map2 and map3 are the same object:true
Copy the code

As you can see, in a Map collection, a value object can be null, and there is no limit to the number of values, so if the get() method returns a null value, the key object may not be in the collection, or the key object may not have a mapping value. To determine whether a key exists, use the containsKey() method.

6.2 a HashMap class

6.2.1 HashMap is introduced

HashMap implements the Map interface, so HashMap has all the common methods that the Map interface provides. Like a HashSet, a HashMap does not guarantee the order of elements.

HashMapThe underlying implementation of JDK1.8 uses hash tables. Before JDK1.8, hash tables were essentially” “, as shown below:

The Hash algorithm is used to store and query key-value pairs. When a strict key-value is added, the Hash value of the key element is calculated first to determine the insertion position in the array. It is possible that elements with the same Hash value have been placed in the same position in the array, and then they are added to the same Hash value. They are in the same position in the array, but form a linked list. The Hah value on the same linked list is the same, so the array stores a linked list. In JDK8, when the length of the list is greater than 8, the list is converted to a red-black tree, which improves the efficiency of finding elements.

6.2.2 Examples of common HashMap methods

public class Example8_13 {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put(109."PS");
        map.put(107."C");
        map.put(108."Js");
        map.put(99."Data structure");
        map.put(99."Java Programming");// If the same key exists, the inserted key will be overwritten
        System.out.println(map);

        Map map1 = new HashMap<>();
        map1.put(1001."Bill");
        map1.put(1001."Bi");// If the same key exists, the inserted key will be overwritten
        System.out.println(map1);

        System.out.println(map.containsKey(99));
        for(Object o:map.keySet()){
            System.out.println(o+"-- >"+map.get(o)); }}}Copy the code

The result after compiling and running is:

{99=Java programming,107= c,108=Js, 109=PS}
{1001=Bi}
true
99-->Java programming107-- -- > c108-->Js
109-->PS
                             
Copy the code

6.3 TreeMap class

6.3.1 Common TreeMap methods

TreeMap is the main implementation class of Map interface. TreeMap stores ordered data, sorted by key. The underlying TreeMap uses a red-black tree (each node of a red-black tree is a key-value pair) to sort key-values.

The main methods of the TreeMap class are as follows:

methods	type	instructions
TreeMap()	A constructor	Construct a new, empty tree map using the natural order of the keys
TreeMap(Map<? extends K, ? extends V> m)	structure	Construct a new tree map that has the same mapping relationship as the given map, sorted according to the natural order of its keys
TreeMap(Comparator<? super K> comparator)	structure	Construct a new, empty tree map that sorts according to the given comparator
TreeMap(SortedMap<K, ? extends V> m)	structure	Construct a new tree map that has the same mapping relationship and the same sort order as the given ordered map
Comparator<? super K> comparator()	ordinary	Returns a comparator that sorts the keys in this map; If this mapping uses the natural order of keys, null is returned
K firstKey()	ordinary	Returns the current first key in this mapping
K lastKey()	ordinary	Returns the current last key in this map
SortedMap<K,V> headMap(K toKey)	ordinary	Returns a partial view in this map with a key value less than toKey
SortedMap<K,V> subMap(K fromKey, K toKey)	ordinary	Returns the partial view in this map whose key value is less than toKey and greater than or equal to fromKey
SortedMap<K,V> tailMap(K fromKey)	ordinary	Returns a partial view in this map with a key value greater than or equal to fromKey

6.3.2 Examples of Common TreeMap methods

public class Example8_14{
    public static void main(String[] args) {
        TreeMap treeMap = new TreeMap();
        treeMap.put(10."a");
        treeMap.put(1."a");
        treeMap.put(9.null);
        treeMap.put(5."c");
        treeMap.put(3.null);
        System.out.println(treeMap);
        System.out.println(treeMap.lastKey());
        System.out.println(treeMap.headMap(2));
        System.out.println(treeMap.tailMap(2));
        TreeMap treeMap1 = newTreeMap(treeMap); System.out.println(treeMap1); }}Copy the code

The output is:

{1=a, 3=null.5=c, 9=null.10=a}
10
{1=a}
{3=null.5=c, 9=null.10=a}
{1=a, 3=null.5=c, 9=null.10=a}
Copy the code

6.4 Comparison of TreeMap and HashMap Performance

The HashMap is not output according to the size of the key value. If you need to insert or delete a key-value, use HashMap preferentially.

TreeMap is output by key value. For maps that need to be sorted, TreeMap is preferred.

Vii. Summarize the comparison between each set class

Arraylist	LinkedList	HashSet	TreeSet	ArrayDeque	PriorityQueue	HashMap	TreeMap
Whether to order	The orderly	The orderly	A disorderly	The orderly	The orderly	The orderly	A disorderly
Storage structure	A collection of	A collection of	A collection of	A collection of	A collection of	A collection of	Key/value pair
Thread safety	no	no	no	no	no	no	no
Whether there is duplication of elements	is	is	no	no	is	is	Unique key value, same override
Whether the element can be null	is	is	is	is	no	no	is
Underlying data structure	An array of	The list	Hash table	Binary tree	Circular array	The heap	Hash table
The characteristics of	Query fast, add and delete slow	Query slowly, add and delete quickly	Quickly find	Quick sort	Query fast, add and delete slow	/	Insert, delete, and locate elements quickly