编程知识 cdmana.com

That's great. I can understand java collection at one time. It's suggested to collect it!

One 、 Comparison of sets and arrays

Two 、 Set structure inheritance graph

Sets fall into two categories :
One is to store elements in a single way , The super parent interface is java.util.Collection;
One is to store elements as key value pairs , The super parent interface is java.util.Map.
Collection and Map, Is the root interface of the collection framework .

To master the structure of inheritance requires . Pay attention to distinguish which interfaces are , Which are implementation classes .

 Orderly : This is the order of the elements stored in it , Take it out in this order ;
 disorder : This is the order of saving , It doesn't have to be in this order . And there's no subscript .
 repeatable : Allow duplicate elements to be stored ;
 Do not repeat : Duplicate elements are not allowed to be stored . That is, put it in 1, You can't store it anymore 1.

3、 ... and 、Collection Interface

Collection Interface is List Interface and Set Interface's parent interface .Collection Interface defines the addition of a collection 、 Delete 、 Change 、 Methods of investigation ,List Interface and Set Interfaces inherit these methods .

Four 、List Interface and its implementation class

List It's orderly and repeatable Collection, With this interface, you can precisely control where each element is inserted . Users can use index ( The elements are in List Position in , Similar to array subscript ) To visit List The elements in . Realization List The common classes of interfaces are LinkedList,ArrayList,Vector.

List The unique method in :

1.ArrayList class

The bottom is Object Array , therefore ArrayList High efficiency of collection query , The efficiency of addition and deletion is low .
( ask : Why is array retrieval efficient , The efficiency of addition and deletion is low ?
answer : Retrieval efficiency is high because of the first :Java The type of each element stored in the array is the same , In other words, each element takes up the same amount of space ; second :Java The memory address of each element stored in the array is continuous ; Third : The memory address of the first element is used as the memory address of the entire array object , So we know the memory address of the first element ; Fourth : The elements in an array have subscripts , With a subscript, you can calculate the offset between the searched element and the first element .
The low efficiency of adding and deleting is because adding an element to a subscript position in an array needs to move the element after the subscript by one bit , The same goes for deleting .)
ArrayList Automatic expansion mechanism : The initial capacity is 10, After expansion, it will be the original capacity 1.5 times .

ArrayList Class has three constructors :

Arraylist Set test :

public static void main(String[] args) {
        //  establish ArrayList example 
        ArrayList<String> list = new ArrayList<>();
        //  to list Additive elements 
        for (int i=97; i<105; i++) {
            list.add(String.valueOf((char)i));
        }
        System.out.println("list The contents of the array are " + list);
        System.out.println("list The number of elements in the array is : " + list.size());
        list.set(0,"haha");
        System.out.println("list The content of the modified array is : " + list);
        System.out.println("list Whether the array contains “a”: " + list.contains("a"));
        System.out.println("list The array index is zero 2 The element is : " + list.get(2));
        list.remove("c");
        System.out.println("list Array removal “c” What follows is : " + list);

        //  Traverse list aggregate 
        for (String s : list) {
            System.out.printf("%s\t",s);
        }
 }

result :

list The contents of the array are [a, b, c, d, e, f, g, h]
list The number of elements in the array is : 8
list The content of the modified array is : [haha, b, c, d, e, f, g, h]
list Whether the array contains “a”: false
list The array index is zero 2 The element is : c
list Array removal “c” What follows is : [haha, b, d, e, f, g, h]
haha    b    d    e    f    g    h    

2、LinkedList class

The bottom layer adopts bidirectional linked list structure , The advantage is to insert and delete elements efficiently , But random access to elements is slower , Characteristics and ArrayList Just the opposite . If the program needs to insert and delete the collection repeatedly , Choose LinkedList class .

LinkedList Class has two constructors :

LinkedList Class also implements Deque and Queue Interface , The specified methods in these two interfaces are implemented , Elements used to handle the head and tail . You can use LinkedList Implementation stack (stack)、 queue (queue)、 The bidirectional queue (double-ended queue ). It has a way addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast() etc. .

LinkedList Set test :

public static void main(String[] args) {
        //  establish ArrayList example 
        ArrayList<String> list = new ArrayList<>();
        //  to list Additive elements 
        for (int i=97; i<105; i++) {
            list.add(String.valueOf((char)i));
        }
        System.out.println("list The contents of the array are " + list);

        //  establish LinkedList example 
        LinkedList<String> link = new LinkedList<>(list);

        System.out.println("link The content is " + link);
        link.addFirst("first");
        link.addLast("last");
        System.out.println("link The content is " + link);
        System.out.println("link The first element of the content is : " + link.getFirst());
}

result :

list The contents of the array are [a, b, c, d, e, f, g, h]
link The content is [a, b, c, d, e, f, g, h]
link The content is [first, a, b, c, d, e, f, g, h, last]
link The first element of the content is : first

3、Vector class

: The underlying data structure is an array , Quick query , Add or delete slowly , Thread safety , Low efficiency , Can store repeating elements , Not recommended .

5、 ... and 、Iterator Interface ( iterator )

Iterator Interface is to Collection Iterators that iterate . Use this interface , It can be done to Collection To access the elements in the , Realize the traversal of collection elements .
Iterator There are three ways to interface :

The iterator initially points to the first object , Use Next() Then point to the next object . In iterating over set elements , If used out of remove() Methods that change the set structure , The iterator must retrieve . And remove() Only when calling Next() Method can be used only after , Every time you execute Next() Call at most once after that .

Iterator test :

public static void main(String[] args) {
        //  establish ArrayList example 
        ArrayList<Integer> list = new ArrayList<>();
        //  to list Additive elements 
        for (int i=1; i<9; i++) {
            list.add(i);
        }
        //  return Iterator iterator 
        Iterator<Integer> it = list.iterator();
        // Iterators traverse the collection 
        while (it.hasNext()) {  //  Determine if there are elements 
            int x = it.next();  //  Get elements 
            System.out.println(x);
            if (x == 5)  //  Element is 5 Remove the element when 
                it.remove();
        }

        //  Convert to an array of objects 
        Object[] a = list.toArray();
        System.out.printf(" The content after deletion is : ");
        for (int i=0; i<a.length; i++) {
            System.out.printf("%s\t",a[i]);
        }
}

result :

1
2
3
4
5
6
7
8
 The content after deletion is : 1    2    3    4    6    7    8    

6、 ... and 、Set Interface and its implementation class

unordered set , Duplicate elements are not allowed to be stored ; Allow to use null Elements . Yes add()、equals() and hashCode() Methods are more restrictive .

( because HashSet and TreeSet The bottom of the set is Map,HashSet The bottom is HashMap,TreeSet The bottom is TreeMap. So the Map Learn to ,Set The assembly makes sense , So here's a brief introduction to Set Interface and its implementation class , You can go to the seventh section first Map Interface .)

1、HashSet class

HashSet The underlying data structure is implemented by hash table , Elements are disordered and unique , Thread unsafe , Efficient , Can be stored null Elements , The uniqueness of an element depends on whether the stored element type is overridden hashCode() and equals() Method to guarantee , If these two methods are not rewritten , There is no guarantee that the element is unique .

The comparison process of realizing uniqueness : Storage elements first use hash() The algorithm function generates a int type hashCode Hash value , And then the stored elements of hashCode Value comparison , If hashCode It's not equal , Then the two objects stored must not be equal , Now store the current new hashCode The element object at value ; If hashCode equal , The objects that store elements are not necessarily equal , This will call equals() Method to determine whether the contents of two objects are equal , If the content is equal , So it's the same object , No storage required ; If the contents of the comparison are not equal , So different objects , It's time to store , At this point, we need to use hash to solve the address conflict algorithm , At present hashCode Values are similar to a new linked list , In the same hashCode Store different objects after the value , This ensures the uniqueness of the element .

HashSet Class test :

public static void main(String[] args) {
        Set<String> strs = new HashSet<>();
        strs.add("aa");
        strs.add("bb");
        strs.add("cc");
        strs.add("dd");
        strs.add("aa");
        Iterator<String> it = strs.iterator();
        while (it.hasNext()) {
            String s = it.next();
            System.out.println(s);
        }
    }

result :

aa
bb
cc
dd

2、TreeSet class

The bottom of the set is TreeMAp,TreeMap The bottom layer is a binary tree structure . And HashSet Different types ,TreeSet Classes are not hashed , It's orderly .

Elements are unique and ordered ; Uniqueness also needs to be rewritten hashCode and equals() Method , Binary tree structure ensures the order of elements . According to the construction method , Divided into natural order ( No arguments structure ) Sort with comparator ( There are parametric structures ), Natural ordering requires that elements must implement Compareable Interface , And rewrite the compareTo() Method , Element returned by comparison int Value to determine the sort sequence , return 0 Explain that the two objects are the same , No storage required ; The comparator row needs to be in TreeSet Initialization is the time to pass in an implementation Comparator The comparator object of the interface , Or anonymous inner class new One Comparator object , Rewrite the compare() Method .

7、 ... and 、Map Interface

1、Map The collection and Colltection Set has no inheritance relationship .
2、Map Assemble to Key and Value Of <mark style="box-sizing: border-box; outline: 0px; background-color: rgb(248, 248, 64); color: rgb(0, 0, 0); overflow-wrap: break-word;"> Key value pair </mark> Mode store element .
3、Key and Value It's all storage java The memory address of the object .Key Play a leading role ,Value yes Key Accessories of .
4、 Disorder cannot be repeated .

Map Common methods in :

Map Common method test :

public static void main(String[] args) {
        //  establish Map A collection of objects 
        Map<Integer,String> map = new HashMap<>();
        //  Add key value pairs... To the collection 
        map.put(1," China ");
        map.put(2," The United States ");
        map.put(3," Russia ");
        map.put(4," The British ");
        //  adopt key obtain value
        System.out.println(map.get(1));
        //  To determine whether or not to include a key
        System.out.println(" Does it include key “4”: " + map.containsKey(4));
        //  To determine whether or not to include a key
        System.out.println(" Does it include value “ China ”: " + map.containsValue(" China "));
        // map Whether the set is empty 
        System.out.println(" Whether the set is empty : " + map.isEmpty());
        //  adopt key Delete key value pair 
        map.remove(2);
        //  Number of collection elements 
        System.out.println(" Number of collection elements : " + map.size());
        //  take map Set to Set aggregate 
        Set<Map.Entry<Integer,String>> set = map.entrySet();

        System.out.println("======================================================");
        //  Ergodic set 
        for (Map.Entry<Integer,String>entry : set) {
            System.out.println("key: " + entry.getKey() + "  value: " + entry.getValue());
        }
}

result :

 China 
 Does it include key “4”: true
 Does it include value “ China ”: true
 Whether the set is empty : false
 Number of collection elements : 3
======================================================
key: 1  value:  China 
key: 3  value:  Russia 
key: 4  value:  The British 

1、 Traverse Map Four methods of set

public static void main(String[] args) {
        Map<String, String> map= new HashMap<>();
        map.put(" Guan yu ", " Cloud long ");
        map.put(" Zhang Fei ", " Yide ");
        map.put(" zhaoyun ", " Zilong ");
        map.put(" d ", " Meng Qi ");
        map.put(" Huang Zhong ", " Hansheng ");

        // The first kind of traversal map Methods , By strengthening for loop map.keySet(), And then through the key key Get value value 
        for(String s:map.keySet()){
            System.out.println("key : "+s+" value : "+map.get(s));
        }
        System.out.println("====================================");

        // The second is to traverse only keys or values , By strengthening for loop 
        for(String s1:map.keySet()){// Traverse map Key 
            System.out.println(" key key :"+s1);
        }
        for(String s2:map.values()){// Traverse map Value 
            System.out.println(" value value :"+s2);
        }
        System.out.println("====================================");

        // The third way Map.Entry<String, String> The strengthening of for Loop through the output key key And the value value
        Set<Map.Entry<String,String>> set = map.entrySet();
        for(Map.Entry<String, String> entry : set){
            System.out.println(" key  key :"+entry.getKey()+"  value value :"+entry.getValue());
        }
        System.out.println("====================================");

        // A fourth Iterator Traversal access , And then get Map.Entry<String, String>, To get getKey() and getValue()
        Iterator<Map.Entry<String, String>> it=map.entrySet().iterator();
        while(it.hasNext()){
            Map.Entry<String, String> entry=it.next();
            System.out.println(" key key :"+entry.getKey()+" value :"+entry.getValue());
        }
        System.out.println("====================================");
    }

2、HashMap Hashtable ( Hash table ) data structure

To master HashMap aggregate , You should be familiar with the data structure of hash table . because HashMap At the bottom of the set is a hash table / Hash table data structure .

A hash table is a combination of an array and a one-way linked list .  So hash table is very efficient in querying and adding or deleting data .

HashMap The bottom layer is actually a one-dimensional array , The array contains a Node(HashMap.Node node , This node stores hash values , Key value pair , The memory address of the next node ). Hash value is key Of hashCode() Result of method ,hash The value is then passed through the hash function , Can be converted to <mark style="box-sizing: border-box; outline: 0px; background-color: rgb(248, 248, 64); color: rgb(0, 0, 0); overflow-wrap: break-word;"> Index of the array </mark>.

map.put(k,v) Realization principle :
① First, match the key value to k,v Package to Node In the object ;
② The underlying will call k Of hashCode() The way to get hash value ;
③ By hash function , take hash Value is converted to the subscript of the array .
④ Compare : Subscript position if there are no elements , Just put Node Add to this location ; If there is a linked list at the subscript position , At this point, I will take k And every node in the list k use equals() Methods for comparison ( because Map It can't be repeated ), If there are no duplicate new nodes will be added to the end of the list , Otherwise, it will cover the same k The value of the node .

map.get(k) Realization principle :
① call k Of hashCode() The way to get hash value ;
② Compare : Subscript position if there are no elements , return null, If there is a linked list at the subscript position , At this point, I will take k And every node in the list k use equals() Methods for comparison , If the results are all false, Then return to null; If a node uses equals The result is true, Then return the node's value value .

ask : Why is hash table added or deleted randomly 、 Query efficiency is high ?
answer : Addition and deletion are done on the linked list , You don't have to scan all the queries , Just a partial scan .

Here's the point , Called above hashCode() and equals() Method , Need to be <mark style="box-sizing: border-box; outline: 0px; background-color: rgb(248, 248, 64); color: rgb(0, 0, 0); overflow-wrap: break-word;"> rewrite </mark>!
equals() The reason for rewriting :equals By default, the memory addresses of two objects are compared , But what we need to compare is k The content in .
hashCode
Conclusion : Put it in HashMap() aggregate key Part of the elements ,, And put it in HashSet The elements in the collection , It needs to be rewritten at the same time hashCode and equals Method .

rewrite equals() and hashCode() Method test :
The results of code running before and after rewriting are different , You can use this code to test , Compare the previous with the comment section after uncommenting .

public class HashMapTest01 {
    public static void main(String[] args) {
        Student s1 = new Student("Jake");
        Student s2 = new Student("Jake");
        System.out.println(s1.equals(s2));
        System.out.println(s1.hashCode() == s2.hashCode());
        Set<Student> students = new HashSet<>();
        students.add(s1);
        students.add(s2);
        System.out.println(students.size());
    }
}

class Student {
    //@Override
    //public boolean equals(Object o) {
    //    if (this == o) return true;
    //    if (o == null || getClass() != o.getClass()) return false;
    //    Student student = (Student) o;
    //    return Objects.equals(name, student.name);
    //}
    //
    //@Override
    //public int hashCode() {
    //    return Objects.hash(name);
    //}

    private String name; 

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

    public String getName() {
        return name;
    }

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

3、TreeMap class

TreeMap Class is Map The concrete implementation of the interface , The bottom layer is a binary tree data structure , Supporting elements <mark style="box-sizing: border-box; outline: 0px; background-color: rgb(248, 248, 64); color: rgb(0, 0, 0); overflow-wrap: break-word;"> Orderly </mark> Storage , You can automatically sort by the size of the elements .TreeMap All elements in a class must implement Comparable Interface , And TreeSet Kind of similar (TreeSet The bottom of the class is TreeMap, Put it in TreeSet The elements in the collection , Equal to put in TreeMap In the collection key part ).

TreeSet Class auto sort test :

public static void main(String[] args) {
        TreeSet<String> ts = new TreeSet<>();
        ts.add("ss");
        ts.add("abf");
        ts.add("g");
        ts.add("f");
        ts.add("abcd");
        ts.add("abc");

        Iterator<String> it = ts.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }

result ( In ascending order of dictionary ):

abc
abcd
abf
f
h
ss

about Customize The type of ,TreeMap Can't sort automatically . You need to specify the comparison rules between custom objects . If not specified ( It doesn't say who is big or who is small ),TreeMap Class doesn't know how to sort elements , You're going to report a mistake , For example, the following code :

public class TreeSetTest02 {
    public static void main(String[] args) {
        Student s1 = new Student("Ana",18);
        Student s2 = new Student("Bob",25);
        Student s3 = new Student("Stark",21);
        Student s4 = new Student("Lip",18);

        TreeSet<Student> students = new TreeSet<>();
        students.add(s1);
        students.add(s2);
        students.add(s3);
        students.add(s4);

        Iterator<Student> it = students.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

class Student {
    private String name;
    private int age;

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

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

The results will report the following abnormalities :

 java.lang.ClassCastException: class test.Student cannot be cast to class java.lang.Comparable

In this case, we need to customize the type Realization Comparable Interface , And rewrite compareTo() Method , The logic of comparison needs to be written in this method ( Compare the rules ).
compareTo Method returns int value :
return 0 It means the same ,value Will be covered ;
return >0, I'll look for it in the right subtree ;
return <0, I'll look for it in the left tree .( If you don't know about binary tree, please )

The rules of comparison are self-made , First, compare the age , If you are the same age , Then compare the size of the string .

public class TreeSetTest02 {
    public static void main(String[] args) {
        Student s1 = new Student("Ana",18);
        Student s2 = new Student("Bob",25);
        Student s3 = new Student("Stark",21);
        Student s4 = new Student("Lip",18);

        TreeSet<Student> students = new TreeSet<>();
        students.add(s1);
        students.add(s2);
        students.add(s3);
        students.add(s4);

        Iterator<Student> it = students.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

class Student implements Comparable<Student>{
    private String name;
    private int age;

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

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

    @Override
    // compareTO Method returns int value ;
    //  The rules of comparison are self-made , First, compare the age , If you are the same age , Then compare the size of the string ;
    public int compareTo(Student o) {
        if (this.age != o.age)
            return this.age - o.age;
        else  // The same age 
            return this.name.compareTo(o.name);  //  What is called here is not in this class compareTo Method , It's called the string of compareTo Method 
    }
}

result :

Student{name='Ana', age=18}
Student{name='Lip', age=18}
Student{name='Stark', age=21}
Student{name='Bob', age=25}

TreeSet The second way elements in a collection can be sorted : Using a comparator .  Write a comparator alone , This comparator implements java.util.Comparator Interface . And creating TreeSet When the collection , Pass in the comparator .

public class TreeSetTest02 {
    public static void main(String[] args) {
        Student s1 = new Student("Ana",18);
        Student s2 = new Student("Bob",25);
        Student s3 = new Student("Stark",21);
        Student s4 = new Student("Lip",18);

        // establish TreeSet When the collection , You need to pass in the comparator 
        TreeSet<Student> students = new TreeSet<>(new StudentComparator());
        students.add(s1);
        students.add(s2);
        students.add(s3);
        students.add(s4);

        Iterator<Student> it = students.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

class Student {
    public String name;
    public int age;

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

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

// Write a comparator alone 
// Comparator implements java.util.Comparator Interface 
class StudentComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        if (o1.age != o2.age)
            return o1.age - o2.age;
        else
            return o1.name.compareTo(o2.name);
    }
}

You can also use it Anonymous inner class The way .

public class TreeSetTest02 {
    public static void main(String[] args) {
        Student s1 = new Student("Ana",18);
        Student s2 = new Student("Bob",25);
        Student s3 = new Student("Stark",21);
        Student s4 = new Student("Lip",18);

        // establish TreeSet When the collection , You need to pass in the comparator ( Use anonymous inner class )
        TreeSet<Student> students = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                if (o1.age != o2.age)
                    return o1.age - o2.age;
                else
                    return o1.name.compareTo(o2.name);
            }
        });
        students.add(s1);
        students.add(s2);
        students.add(s3);
        students.add(s4);

        Iterator<Student> it = students.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

class Student {
    public String name;
    public int age;

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

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

Conclusion :  Put it in TreeSet perhaps TreeMap aggregate key Part of the elements want to be sorted , There are two ways :
The first one is : Elements placed in a collection implement java. lang. Comparable Interface .( Use this when the rules are fixed )
The second kind : In the structure TreeSet perhaps TreeMap Pass it a comparator object when assembling .( Use this when the rules of comparison change frequently )

版权声明
本文为[Bright future]所创,转载请带上原文链接,感谢

Scroll to Top