Analysis of List and Set set Set series

Catalog

Preface

The use of collection interface has been introduced in previous blog articles. This article will introduce the use of subclasses in collection interface. Don't ask me why you want to talk about subclasses. What? Xiaobai is reading my article... I'm sorry, forgive me for what I just said, please allow me to reorganize the language... Cough, why should I talk about the subclass of the collection interface? Little white children's shoes. Collection interface is an interface. What's the purpose of the interface? It is to define a set of specifications. Without a specific class to implement the interface, the interface is meaningless! Little white children's shoes what do you want.

Another point is that if the Collection interface is not familiar with the little white children's shoes, it is strongly recommended to understand the Collection interface first and then read this article, otherwise it will only do half the work! Well, I know it's the blogger. I strongly suggested that there must be Xiaobai children's shoes not to be found. It's OK. The blogger has no other purpose. He just wants Xiaobai children's shoes to learn java well, so I'm ready for the following article ~ Click the blue font to enter~ Collection collection and implementation principle of Iterator iterator

@

List interface

Next, let's learn about the two commonly used subclasses in Collection: java.util.List Collection and java.util.Set Collection.

1.1 List interface introduction

The java.util.List interface inherits from the Collection interface, where the elements are repeatable and ordered. All elements are stored in a linear way, and the specified elements in the Collection can be accessed through index in the program, and the storage order and extraction order of the elements are consistent.

List interface features analysis:

  1. Element access order: for example, if the order of storing elements is "I", "yes", "Pei" and "Qi", then the storage of elements in the collection is completed in the order of "I", "yes", "Pei" and "Qi".
  2. Indexed sets: the same thing as array indexes
  3. Element repetition: compare whether it is a duplicate element by its equals method.

1.2 common methods in list interface

As a sub interface of Collection collection, List not only inherits all methods in Collection interface, but also has some unique methods to operate Collection according to element index, as follows:

public void add(int index, E element): adds the specified element to the specified location in the collection. -public E get(int index): returns the element at the specified location in the collection.
public E remove(int index): remove the element at the specified location in the list, and return the removed element.
public E set(int index, E element): replace the element at the specified location in the set with the specified element, and return the element before the value is updated.

The unique methods of List set are all related to index. The code is as follows:

public class ListDemo {
    public static void main(String[] args) {
        // Create List collection object
        List<String> list = new ArrayList<String>();
        
        // Add specified element to tail
        list.add("Angel shit");
        list.add("Liu Bei Tai");
        list.add("Lian Po");
        
        System.out.println(list);
        // add(int index,String s) to the specified location
        list.add(1,"Pig's feet bright");
        
        System.out.println(list);
        // String remove(int index) delete the specified location element and return the deleted element
        // Delete element with index position 2 
        System.out.println("Delete element with index position 2");
        System.out.println(list.remove(2));
        
        System.out.println(list);
        
        // String set(int index,String s)
        // Replace the element at the specified location 
        // Modify the specified location element
        list.set(0, "East emperor is too two");
        System.out.println(list);
        
        // String get(int index) gets the specified location element
        
        // Used to traverse with the size() method 
        for(int i = 0;i<list.size();i++){
            System.out.println(list.get(i));
        }
        //You can also use the enhanced for
        for (String string : list) {
            System.out.println(string);
        }   
    }
}

Subclass of List

2.1 ArrayList set

The structure of the java.util.ArrayList collection data store is an array structure. Element addition and deletion are slow, and search is fast. Since the most commonly used functions in daily development are query data and traversal data, ArrayList is the most commonly used collection.

2.2 LinkedList set

The structure of java.util.LinkedList collection data store is linked list structure. Fast addition and deletion of elements, slow search of sets.

LinkedList is a two-way linked list. What does a two-way linked list look like?

In the actual development, adding and deleting a collection element often involves the first and last operations, while LinkedList provides a lot of methods for the first and last operations. The following methods are as follows:

  • public void addFirst(E e): inserts the specified element at the beginning of this list.
  • public void addLast(E e): adds the specified element to the end of this list.
  • public E getFirst(): returns the first element of this list.
  • public E getLast(): returns the last element of this list.
  • public E removeFirst(): removes and returns the first element of this list.
  • public E removeLast(): removes and returns the last element of this list.
  • public E pop(): pops an element from the stack represented by this list.
  • Public void push (e e e): push elements into the stack represented by this list.
  • public boolean isEmpty(): returns true if the list does not contain elements.

LinkedList is a subclass of List, and the methods in List can be used. We will not give a detailed introduction here, we just need to understand the unique methods of LinkedList. At development time, the LinkedList collection can also be used as the structure of stack and queue. (just understand)

The method code is as follows:

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> link = new LinkedList<String>();
        //Additive elements
        link.addFirst("Big Joe");
        link.addFirst("Small bridge");
        link.addFirst("Old Joe");
        System.out.println(link);
        // Get elements
        System.out.println(link.getFirst());
        System.out.println(link.getLast());
        // Delete elements
        System.out.println(link.removeFirst());
        System.out.println(link.removeLast());

        while (!link.isEmpty()) { //Judge whether the set is empty
            System.out.println(link.pop()); //Top of stack element in pop-up collection
        }

        System.out.println(link);
    }
}

Well, here we go, and the list set comes to an end.

Set interface

3.1 Set interface introduction

The java.util.Set interface, like the java.util.List interface, also inherits from the Collection interface. It is basically the same as the method in the Collection interface. It does not extend the function of the Collection interface, but is more strict than the Collection interface. Different from the list interface, the elements in the set interface are unordered and not repeated, just opposite to the list interface. The set ensures that the stored elements are not repeated by some rules.

The Set collection has several subclasses. Here we introduce the two collections: java.util.HashSet and java.util.LinkedHashSet.

Set sets can extract elements in the following ways: iterator, enhanced for.

Set interface subclass

4.1 introduction to HashSet set

java.util.HashSet is an implementation class of the Set interface. The elements it stores are non repeatable and out of order (i.e. access order is inconsistent). The underlying implementation of java.util.HashSet is actually a java.util.HashMap support.

HashSet is based on the hash value of the object to determine the storage location of the elements in the collection, so it has good access and search performance. The way to guarantee element uniqueness depends on: hashCode and equals methods.

Let's use the Set set Set storage first, look at the following phenomena, and then explain the principle:

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

        //Additive elements
        set.add(new String("Angel shit"));
        set.add("Liu Bei Tai");
        set.add("Pig eight quit smoking"); 
        set.add("Angel shit");  
        //ergodic
        for (String name : set) {
            System.out.println(name);
        }
    }
}

The output is as follows, indicating that duplicate elements cannot be stored in the collection:

Angel shit
 Liu Bei Tai
 Pig eight quit smoking

According to the results, we found that the string "angel shit" only stores one, that is to say, the repeated element set set is not stored.

4.2 structure of data stored in the HashSet set (hash table)

What is a hash table?

Before JDK 1.8, the bottom layer of hash table was implemented by array + linked list, that is, using linked list to handle conflicts, and the linked list of the same hash value was stored in a linked list. However, when there are many elements in a bucket, that is, there are many elements with equal hash value, the efficiency of searching by key value in turn is low. In JDK 1.8, hash table storage is implemented by array + linked list + red black tree. When the length of linked list exceeds the threshold (8), the linked list is converted to red black tree, which greatly reduces the search time.

In short, hash table is implemented by array + linked list + red black tree (red black tree is added in JDK 1.8), as shown in the following figure.

Seeing this picture, I have children's shoes to ask. How is this stored? Just look at the picture below


In a word, the introduction of red black tree in JDK 1.8 greatly optimizes the performance of HashMap. For us, the only way to ensure the collection elements of HashSet is actually determined by the hashCode and equals methods of the object. If we store custom objects in the collection, we must copy the hashCode and equals methods to establish a comparison method that belongs to the current object to ensure that they are unique.

As for data structure, I have written about arrays and linked lists before. For your convenience, I'll post it below

[data structure 01] array

[data structure 03] on linked list

What? And the red and black trees? Well... I haven't written yet. If I'm not in a hurry to read the blogger, I'll put it back a little bit. ~ after all, I'm busy ~ I'm really in a hurry to read the blogger and try to find time to write an article

4.3 source code analysis

QnQ

public class HashSet<E>  
    extends AbstractSet<E>  
    implements Set<E>, Cloneable, java.io.Serializable  
{  
    static final long serialVersionUID = -5024744406713321676L;  
 
    // The bottom layer uses the HashMap to save all elements in the HashSet.  
    private transient HashMap<E,Object> map;  
 
    // Define a virtual Object object as the value of the HashMap, and define this Object as static final.  
    private static final Object PRESENT = new Object();  
 
    /** 
     * The default parameterless constructor constructs an empty HashSet. 
     *  
     * The actual underlying initializes an empty HashMap with a default initial capacity of 16 and a load factor of 0.75. 
     */  
    public HashSet() {  
    map = new HashMap<E,Object>();  
    }  
 
    /** 
     * Constructs a new set containing the elements in the specified collection. 
     * 
     * The actual underlying uses the default load factor of 0.75 and enough to contain the specified 
     * collection The initial capacity of all elements in to create a HashMap. 
     * @param c The elements will be stored in the collection in this set. 
     */  
    public HashSet(Collection<? extends E> c) {  
    map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));  
    addAll(c);  
    }  
 
    /** 
     * Construct an empty HashSet with the specified initialCapacity and loadFactor. 
     * 
     * The actual bottom layer constructs an empty HashMap with corresponding parameters. 
     * @param initialCapacity Initial capacity. 
     * @param loadFactor Load factor. 
     */  
    public HashSet(int initialCapacity, float loadFactor) {  
    map = new HashMap<E,Object>(initialCapacity, loadFactor);  
    }  
 
    /** 
     * Constructs an empty HashSet with the specified initialCapacity. 
     * 
     * The actual bottom layer constructs an empty HashMap with the corresponding parameters and load factor loadFactor of 0.75. 
     * @param initialCapacity Initial capacity. 
     */  
    public HashSet(int initialCapacity) {  
    map = new HashMap<E,Object>(initialCapacity);  
    }  
 
    /** 
     * Constructs a new null link hash set with the specified initialCapacity and loadFactor. 
     * This constructor is a package access right, which is not exposed to the public. It is actually only the support for LinkedHashSet. 
     * 
     * The actual underlying layer constructs an empty LinkedHashMap instance with the specified parameters. 
     * @param initialCapacity Initial capacity. 
     * @param loadFactor Load factor. 
     * @param dummy Mark. 
     */  
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {  
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);  
    }  
 
    /** 
     * Returns the iterator that iterates over the elements in this set. The order in which elements are returned is not specific. 
     *  
     * The underlying actually calls the keySet of the underlying HashMap to return all keys. 
     * It can be seen that the elements in the HashSet are only stored on the key of the underlying HashMap, 
     * value Use an Object object Object ID of static final. 
     * @return Iterator that iterates over the elements in this set. 
     */  
    public Iterator<E> iterator() {  
    return map.keySet().iterator();  
    }  
 
    /** 
     * Returns the number of elements in this set (the capacity of the set). 
     * 
     * The bottom layer actually calls the size() method of HashMap to return the number of entries, and then gets the number of elements in the Set. 
     * @return The number of elements in this set (the capacity of the set). 
     */  
    public int size() {  
    return map.size();  
    }  
 
    /** 
     * Returns true if the set does not contain any elements. 
     * 
     * The bottom layer actually calls isEmpty() of HashMap to determine whether the HashSet is empty. 
     * @return Returns true if the set does not contain any elements. 
     */  
    public boolean isEmpty() {  
    return map.isEmpty();  
    }  
 
    /** 
     * Returns true if the set contains the specified element. 
     * More specifically, if and only if this set contains a satisfaction (o = = null? E = = null: o.equals (E)) 
     * Returns true for the e element of. 
     * 
     * The bottom layer actually calls the containsKey of the HashMap to determine whether the specified key is included. 
     * @param o There are elements in this set that have been tested. 
     * @return Returns true if the set contains the specified element. 
     */  
    public boolean contains(Object o) {  
    return map.containsKey(o);  
    }  
 
    /** 
     * If this set does not contain the specified element, add the specified element. 
     * More specifically, if this set does not contain (E = = null? E2 = = null: e.equals (E2)) 
     * Element e2, the specified element e is added to this set. 
     * If the set already contains the element, the call does not change the set and returns false. 
     * 
     * The underlying layer actually places the element as a key in the HashMap. 
     * When the key value pair is added to the put() method of HashMap, the key is added to the Entry of HashMap 
     * It is the same as the key of the original Entry in the collection (hashCode() returns the same value and returns true through equals comparison), 
     * The value of the newly added Entry will overwrite the value of the original Entry, but the key will not change, 
     * Therefore, if you add an existing element to the HashSet, the newly added collection element will not be put into the HashMap, 
     * The original elements will not be changed, which satisfies the feature that the elements in the Set are not repeated. 
     * @param e Elements to be added to this set. 
     * @return Returns true if the set does not contain the specified element. 
     */  
    public boolean add(E e) {  
    return map.put(e, PRESENT)==null;  
    }  
 
    /** 
     * If the specified element exists in this set, it is removed. 
     * More specifically, if this set contains an element e that satisfies (o = = null? e = = null: o.equals (e)), 
     * Remove it. Returns true if the set already contains the element 
     * (Or: returns true if the set changes due to a call). (once the call returns, the set no longer contains the element.). 
     * 
     * The bottom layer actually calls the remove method of HashMap to delete the specified Entry. 
     * @param o Objects that need to be removed if they exist in this set. 
     * @return Returns true if the set contains the specified element. 
     */  
    public boolean remove(Object o) {  
    return map.remove(o)==PRESENT;  
    }  
 
    /** 
     * Remove all elements from this set. When this call returns, the set will be empty. 
     * 
     * The bottom layer actually calls the clear method of HashMap to empty all elements in the Entry. 
     */  
    public void clear() {  
    map.clear();  
    }  
 
    /** 
     * Returns a shallow copy of this HashSet instance: the elements themselves are not copied. 
     * 
     * The bottom layer actually calls the clone() method of the HashMap to get the shallow copy of the HashMap and set it to the HashSet. 
     */  
    public Object clone() {  
        try {  
            HashSet<E> newSet = (HashSet<E>) super.clone();  
            newSet.map = (HashMap<E, Object>) map.clone();  
            return newSet;  
        } catch (CloneNotSupportedException e) {  
            throw new InternalError();  
        }  
    }  
}  

In a word, HashSet is a HashMap that limits functions. Therefore, understanding the implementation principle of HashMap is a natural way for this HashSet. For the objects saved in the HashSet, we need to rewrite the equals method and hashCode method correctly to ensure the uniqueness of the objects put in the Set. Although the Set does not put duplicate elements, it is better to directly replace the original value of the underlying Map( The return value of the put method of this Set is really interesting). HashSet does not provide the get() method. It is willing to be the same as HashMap. The Set is unordered and can only be obtained by iteration.

4.4 HashSet stores custom type elements

When storing custom type elements in a HashSet, you need to override the hashCode and equals methods in the object and establish your own comparison method to ensure that the objects in the HashSet set are unique

Create a custom Student class

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

    public Student() {
    }

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

    public String getName() {
        return name;
    }

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

    public int getAge() {
        return age;
    }

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

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

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}
public class HashSetDemo2 {
    public static void main(String[] args) {
        //Create a collection object the collection stores Student type objects
        HashSet<Student> stuSet = new HashSet<Student>();
        //storage 
        Student stu = new Student("Programmer Lao Wang", 43);
        stuSet.add(stu);
        stuSet.add(new Student("Wang, programmer", 44));
        stuSet.add(new Student("Programmer Lao Wang", 43));
        stuSet.add(new Student("Programmer baldhead", 23));
        stuSet.add(stu);

        for (Student stud : stuSet) {
            System.out.println(stud);
        }
    }
}
//Execution result:
Student [name=Wang, programmer, age=44]
Student [name=Programmer Lao Wang, age=43]
Student [name=Programmer baldhead, age=23]

4.5 LinkedHashSet

We know that HashSet guarantees the uniqueness of elements, but there is no order for elements to be stored in, so what should we do to ensure the order? Under the HashSet, there is a subclass java.util.LinkedHashSet, which is a data storage structure composed of linked list and hash table.

The code is as follows:

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<String>();
        set.add("Bald brother");
        set.add("Mediterranean brother");
        set.add("Flat headed brother");
        set.add("False brother");
        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}
//Result:
 //Bald brother
 //Mediterranean brother
 //Flat headed brother
 //False brother

Finally, you are welcome to pay attention to my public address, explore technology, yearn for technology and pursue technology.

Tags: Java JDK

Posted on Wed, 06 Nov 2019 17:01:02 -0800 by validkeys