Java advanced programming class set framework (collection class)

Introduction to the Class Set Framework

    In actual development, no development can leave the array, but the traditional array is very cumbersome to use, and the length is its fatal flaw. Officially, due to the length problem, it is impossible to use it on a large scale, but it is far from being used during development. Without arrays, we can only rely on some data structures to implement dynamic arrays, and the two most important structures are linked lists and trees. However, in the face of the realization of these data structures, we have to face the following problems:

  • The code implementation of the data structure is difficult and cannot be used by ordinary developers
  • It is very troublesome to maintain a linked list or binary tree when updating
  • For linked lists or binary trees, it is necessary to ensure the performance of their operations as much as possible

​     Therefore, JDK1.2 began to introduce class sets in Java, mainly to complete the implementation and packaging of common data structures and provide a series of interfaces and implementation subclasses to help users reduce the development difficulties caused by data structures, but the initial The implementation of the class set uses the Object type for data reception because the technology of Java itself is not strict with the data control. After JDK1.5, due to the promotion of generic technology, the class set itself has also been improved, and generics can be directly used to save the same type of data, and with the continuous increase of the amount of data, from JDK1.8 The implementation algorithm in the starting class set also gets a good performance boost.

Introduction to Collection interface

    java.util.Collection is the largest parent interface for single-valued collection operations. All single-valued data processing operations are defined in this interface. The following operation methods are defined in this interface:

Nomethod nametype
01public boolean add(E e)ordinarysave data to collection
02public boolean addAll(Collection<? extends E> c)ordinaryAppend a set of data
03public void clear()ordinaryClear the collection, make the root node empty, and perform GC processing at the same time
04public boolean contains(Object 0)ordinaryQuery whether the data exists, need equals method support
05pbulic boolean remove(Object 0)ordinaryData deletion requires equals method
06public int size()ordinaryget data length
07public Object[] toArray()ordinaryReturns the collection to an array of objects
08public Iterator iterator()ordinaryTurn the collection into an Iterator interface

There are two methods that are most commonly used when performing set operations: add(), iterator()

​     Before JDK1.5, Collection was just an independent interface. After JDK1.5, the Iterable parent interface was provided, and after JDK1.8, the Iterable interface was also expanded. In addition, in the era of jDK1.2~JDK1.4, if you want to use the collection, you will often directly operate the Collection. But starting from JDK1.5, there are two sub-interfaces of Collection in more cases:

  • Allow duplicate List subinterfaces
  • Duplicate Set subinterfaces are not allowed

List collection

Introduction to List Interface

​    List is a sub-interface of Collection. Its biggest feature is that it allows to store duplicate element data. The definition of this interface is as follows:

public interface List<E>
extends Collection<E>

The List interface extends the methods of the Collection interface:

NOmethod nametype
1public E set(int index, E element)ordinaryGet the data on the specified index
2public E set(int index, E element)ordinaryModify the specified index data
3public ListIterator listIterator()ordinaryReturns the ListIlterator iterator

The List interface has three commonly used subclasses:

  • ArrayList
  • Vector
  • LinkedList

​     Added static methods to the List subinterface after JDK1.9 to facilitate user processing. For example List.of(), Map.of(), Set.of() for simple immutable collections of elements.

ArrayList subclass

​    ArrayList is the most used subclass in the List subinterface. Analyze ArrayLIst related definitions and source code.

The definition of ArrayList in Java is as follows:

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

inheritance relationship

import java.util.ArrayList;
import java.util.List;
public class JavaDemo{
    public static void main(String[] args) {
        List<String> all = new ArrayList<>();
        all.add("Hello");
        all.add("Hello");
        all.add("world");
        System.out.println(all);
    }
}

Through this program, you can discover the characteristics of List storage:

  • The order in which they are saved is the order in which they are stored
  • Duplicate data is allowed in the List collection

​      Although the above program implements the output of the set, the operation of this output directly uses the toString method provided by each class. In order to facilitate the output processing, a forEach method is defined in the Iterable parent interface after JDK1.8.

default void forEach(Consumer<? super T> action)

eg: Use the forEach() method to output (not standard output)

import java.util.ArrayList;
import java.util.List;
public class JavaDemo{
    public static void main(String[] args) {
        List<String> all = new ArrayList<>();
        all.add("Hello");
        all.add("Hello");
        all.add("world");
        all.forEach((str)->{
            System.out.println(str);
        });
    }

    }

Taking the function of the method as an example, the operation support in the ArrayList is very similar to the form of the linked list written before, but it is not implemented using the linked list. ArrayList encapsulates an array.

​ ArrayList constructor:

  • No-argument constructor public ArrayList()

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
  • Construct public ArrayList(int initialCapacity) with parameters

    transient Object[] elementData  //transient cannot be serialized
    public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    

​      Through the parameterized construction method, you can find that the ArrayList actually contains an array of objects. If you find that the length of the object array stored in the ArrayList collection is not enough when adding data, a new array will be opened, and at the same time Copies the original old array contents to the new array.

//jdk1.8
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

​     When the ArrayList class object is instantiated without passing the initialized length, an empty number will be used by default, but when the data is increased and the array capacity is found to be insufficient, the current increased capacity and the default capacity will be judged Size, use a larger value for array development, and you can draw a conclusion:
When the ArrayList class object is instantiated and the initialized length is not passed, an empty number will be used by default, but when the data is increased and the array capacity is found to be insufficient, the current increased capacity and the default capacity will be judged. , using a larger value for array development, you can draw a conclusion:

  1. After JDK1.9: The default construction of ArrayList will only use the default empty array, and the array will be opened when it is used, and the default length is 10.

  2. Before JDK1.9: the default construction of ArrayList will actually open up an array of size 10 by default.

  3. When the capacity stored in the ArrayList is different, it will be doubled. The original length is 10, then the next increase is 20. Estimate the amount of data by analogy. If there are more than 10, use the parameterized construction method to create it to avoid the generation of garbage arrays.

ArrayList holds custom class objects

​​     If you want to use the contains() and remove() methods when using List to save custom objects, you must ensure that the equals() method has been overridden in the class.

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

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

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if(!(obj instanceof Person)) return false;
        Person person = (Person) obj;
        return this.name.equals(person.name) &&
               this.age==person.age;
    }

    
}

LinkedList subclass

​ LinkList is implemented based on linked lists.

​ Definition of LinkList subclass:

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

inheritance relationship

​​     If you just observe the function of the program, the use of LinkeList and ArrayList is exactly the same, but the internal implementation mechanism is completely different. The LinkedList constructor does not provide a method for initializing the size like ArrayList, but only provides parameters with or without parameters. Constructor "public LinkedList()".

Observe the specific implementation of the add method:

public boolean add(E e) {
        linkLast(e);
        return true;
    }

​​     When writing a custom linked list before, it judged whether the incoming data is empty, and if it is empty, no judgment is made. But in LinkedList, no such processing is done, but all data can be saved, and then the linkLast() method is called (append at the last node).

void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

​​     The data stored in the LinkedList class is encapsulated by the Node node. At the same time, in order to improve the execution performance of the program, the last added node (the last node) will be saved each time, so that recursive processing can be avoided when adding data. When adding data, it is necessary to add the number of data saved.

[Interview Question] What is the difference between ArrayList and LinkedList:

  • ArrayList is a collection operation implemented by an array, while LinkedList is a collection operation implemented by a linked list.
  • When using the get() method in the List collection to obtain data according to the index, the time complexity of ArrayList is O(1), while the time complexity of LinkedList is O(n).
  • When ArrayList is used, the default initialized object array length is 10

Vector subclass

​​    Vector is a primitive and ancient program class, which has been provided in JDK1.0j, and then in JDK1.2 due to many development, it has become accustomed to using Vector, and many systems are also implemented based on Vector, considering its extensive type, so the class Set the frame to save it. And let it implement one more List interface.

public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

The inheritance structure and ArrayList are the same.

  public Vector() {
        this(10);
    }


 public Vector(Collection<? extends E> c) {
        elementData = c.toArray();
        elementCount = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
    }



​​    Vector class will open an array of 10 lengths if it uses the no-parameter constructor, and the rest of the implementation operations are the same as ArrayList. Through the analysis of the source code, it can be found that the operation methods in the Vector class are all synchronized, while the ArrayList is not synchronized. So the methods in the Vector class are safe to access in multiple threads, but the performance is not as high as ArrayList.

Set collection

Introduction to the Set interface

​​    Set is also a sub-interface of Collection, its biggest feature is that it does not allow to save duplicate elements.

​ Before JDK1.9, there was no difference in the definitions of Set collection and Collection collection. The Set collection continued to use the methods of the Collection interface to operate, but after JDK1.9, the Set collection also expanded some static methods like the List collection.

Definition of Set Collection

public interface Set<E>
extends Collection<E>

It should be noted that the Set collection does not expand many new methods like the List collection, and the get method cannot be used to obtain the data of the specified index.

​​     When using the new method of, if there are duplicate elements in the operation in the collection, an exception will be thrown directly. This is consistent with the traditional Set method that does not save duplicate methods, but throws an exception by itself.

The Set interface has two commonly used interfaces:

  • HashSet
  • TreeSet

HashSet subclass

​​    HashSet is the most used subclass of the Set interface, and its biggest feature is that the stored data is disordered.

The inheritance relationship of HashSet subclasses is as follows:

ublic class HashSet<E>

extends AbstractSet<E>

implements Set<E>,Cloneable.Serializable

This form of inheritance is very similar to the previous ArrayList, so now let's observe the inheritance structure of the class:
Operational characteristics of HashSet subclasses:

  • Duplicate elements are not allowed to be saved
  • The elements stored in HashSet are unordered

TreeSet subclass

The biggest difference between ​​     and the HashSet subclass is that the data stored in the TreeSet collection is ordered.

public class TreeSet<E>
extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, Serializable

When using TreeSet to save data, all data will be automatically sorted in ascending order of the data.

TreeSet sorting instructions

​​     After analysis, the data stored in the TreeSet subclass is allowed to be sorted, but this class must implement the Comparable interface. Only by implementing this interface can the size relationship of the objects be confirmed. This is because the TreeSet subclass is the storage of collection data implemented by the TreeMap subclass, and TreeMap needs to determine the size relationship according to Comparable.

​ Use a custom class to implement sorting processing operations:

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
class Person implements Comparable<Person>{
    private String name;
    private int age;
    public Person(String name,int age){
        this.name=name;
        this.age=age;
    }

    @Override
    public String toString() {
        return "Name="+this.name+",age="+this.age;
    }
    @Override
    //If this method is not overridden, Exception in thread "main" java.lang.ClassCastException: Person cannot be cast to java.lang.Comparable will occur
    public int compareTo(Person person){
        if(this.age<person.age){
            return -1;
        }else if(this.age>person.age){
            return 1;
        }else{
            return this.name.compareTo(person.name);
        }


    }
}

public class JavaDemo{

    public static void main(String[] args) {
        TreeSet<Person> strings = new TreeSet<Person>();
        strings.add(new Person("little king",20));
        strings.add(new Person("little king",20));
        strings.add(new Person("Xiao Zhang",20));
        strings.add(new Person("Xiao Li",20));
        strings.forEach(System.out::println);
    }
}

​ When using a custom object for comparison processing, all attributes in the class must be matched in order of size relationship, otherwise, when one or several attributes are the same, it will also be considered as duplicate data, so TreeSet is The Comparable interface is used to repeatedly confirm the data.

​ Since TreeSet needs to compare all attributes in the class during the operation, it is too difficult to implement. In actual development, the HashSet subclass is preferred for storage.

A note on repeating elements

​​    TreeSet subclass uses the Comparable interface to realize the judgment of repeated elements.

​​     and the HashSet subclass is implemented using the methods provided in the Object class.

Object encoding:

public int hascode();//Methods in Object

Object comparison:

public boolean equals(Object obj)

​​     When judging repeated elements, first use hashCode() to match the code. If the code does not exist, it means that the data does not exist, which proves that there is no repetition. If the code exists, the object is further compared and processed. If a repetition is found , the data cannot be saved.

package cn.mldn.demo;

import java.util.Set;

class Person //Comparators

private String name·3

private int age;

public Person(String name,int age)f

this.name = name;

this.age = age ;

@Override

public int hashCode()

final int prime=31;

int result =1;

result=prime* result + age;

result = prime*result +((name== nul1)? e: name.hashCode()) 

return result;

@Override

public boolean equals(Object obj) [

if (this == obj)

return true;

if (obj == null)

if (getClass()!= obj.getClass())

return false;

Person other =(Person) obj;

if (age l= other.age)

return false;

if (name== null)

if (other.name!= null)

return false;

] else if(!name.equals(other.name))

return false;

return true;

public String toString()

return "Name:" + this.name +",age:"+ this.age

public class JavaAPIDemo 

public static void main(String[] args) throws Exception 

[Setall= new HashSet();//Instantiate the List parent interface

all.add(new Person("Zhang San",19));

all.add(new Person("Li Si",19)); //Same age but different name

all.add(new Person("Wang Wu", 20)) ;//data duplication

all.add(new Person("King Five", 2 e));//data duplication

all.add(new Person("cockroach",78));

all.forEach(System.out::println);

Collection output

​     Set output has provided a forEach() method in the Iterable interface since JDK1.8, but the iterative output of this method is not a set output form in the traditional sense, and it is difficult to appear in actual development. For collection classes, there are four forms of iterative output:

  • Iterator iterates output
  • ListIterator iterates output in both directions
  • Enumeration enumeration output
  • foreach output

Iterator iterates output

​​     Through the inheritance relationship of the Collection interface, it can be found that since JDK1.5, one more Iterable parent interface has been inherited, and the iterator() operation method is defined in this interface, through which the Iterator interface object (before JDK1.5) can be obtained. , the method is defined directly in the Collection).

public Iterator<T>iterator();

The following methods are defined in the Iterator interface:

Nomethod nametype
1public boolean hasNext()ordinaryDetermine if there is data
2public E next()ordinaryGet current data
3public default void remove()ordinarydelete

HashSet<String> strings = new HashSet<>();
        strings.add("hello");
        strings.add("hello1");
        strings.add("hello2");
        Iterator<String> iterator = strings.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

​ ​ ​ ​  In fact, in the interface of Collection, there is an operation method for deleting by the Secretariat, but if you use the remove() method in Collect when iterating output, it will cause the iteration to fail.

 Set<String> strings = new HashSet<>();
        strings.add("hello");
        strings.add("hello1");
        strings.add("hello2");
        System.out.println(strings);
        Iterator<String> iterator = strings.iterator();
        while(iterator.hasNext()){
            String str=iterator.next();
            if("hello".equals(str)){
                    iterator.remove();
            }else{
                System.out.println(str);
            }
        }
        System.out.println(strings);

[Interview question] Please explain the difference between Collection.remove() and Iterator.remove()?

​ ​ ​ ​  If Collection.remove() is used for iterative output, it will cause concurrent update exceptions and cause program errors. At this time, only the remove() method in the Iterator interface can be used to implement normal deletion processing.

ListIterator iterates output in both directions

​ ​ ​ ​  There is a feature when using the Iterator interface to iterate output: only output from front to back is allowed. 'If you want to achieve bidirectional iterative output, you need to implement it through the Iterator sub-interface: ListIterator interface.

 ​ ​ ​  It should be noted that there is no related processing method defined in the Collection interface to obtain the ListIterator interface object, but the List interface does, which means that this output interface is specially prepared for the List collection.

The following operation methods are defined in ListIterator:

public boolean hasPrevious();
public E previous();

 List<String> strings = new ArrayList<String>();
        strings.add("hello");
        strings.add("hello1");
        strings.add("hello2");
        System.out.println(strings);
        ListIterator<String> iterator = strings.listIterator();
        //positive
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
        //reverse
        while(iterator.hasPrevious()){
            System.out.println(iterator.previous());
        }

If you want to implement backward-forward traversal, then the first thing to achieve is to have backward-forward traversal.

Enumeration enumeration output

​ ​ ​ ​ Enumeration is the output interface used in JDK1.0. This interface mainly provides output services for the Vector class. Consistent with the subsequent development of the JDK, Enumeration still only serves the Vector class. If you want to obtain For the Enumeration interface object, you must use the methods provided by the Vector class:

public Enumeration <E> element();

There are operation methods defined in Enumeration:

public boolean hasMoreElements();
public E nextElement();

forEach output

​ ​ ​ ​  In addition to using the iterative interface to achieve output, starting from JDK1.5, enhanced for loops can also achieve set output. This output form is similar to the array operation form.

Map collection

​ ​ ​ ​ Collection interface and its corresponding sub-interfaces save data as a single object. In the data structure, in addition to single data storage, binary pair objects can also be stored (key=value). The form is saved, and the core meaning of the storage object is that the specified value needs to be obtained through the key.

​ In development, the Collection collection saves data for output, and the Map collection saves data for key search.

Introduction to the Map interface

​ ​ ​ ​ Map interface is the largest parent interface for binary object storage. The definition of this interface is as follows:

public interface Map<K,V>

The core operation methods of this interface:

Nomethod nametypedescribe
1public V put(K key,V value)ordinarysave data to collection
2public get (Object key)ordinaryQuery data by key
3public Set<Map.Entry<K,V> entrySet()ordinaryConvert Map collection to Set
4public boolean containsKey(Object key)ordinaryQuery whether the specified key exists
5public Set keySet()ordinaryConvert the key in the Map collection to the Set collection
6public V remove(Object key)ordinaryDelete the specified data according to the key

​ ​ ​ ​  The data in the Map collection is stored in the form of "key=value", and repetition is not allowed when using the of() method, otherwise an "illeaglArgumentException" exception will occur, if set If the content is empty, a NullPointerException will occur.

HashMap subclass

​ ​ ​ ​ HashMap subclass is the most common subclass in the Map interface. The main feature of this class is unordered storage.

public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

​ ​ ​ ​  The definition form of this class conforms to the previous set definition form, and it still provides an abstract class and needs to repeatedly implement the Map interface.

Observe the use of the HashMap interface

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

public class JavaDemo{
    public static void main(String[] args)  {
        Map<String, Integer> map = new HashMap<>();
        map.put("one",1);
        map.put("two",2);
        map.put("one",111);//1.key repetition
        map.put(null,1);//2.key is empty
        System.out.println(map.get("one"));//111
        System.out.println(map.get(null));//1
        System.out.println(map.get("three"));//3. The key value does not exist null
    }
}

​ ​ ​ ​  The above operation form is the most standard form used by the Map collection. From the above code, it can be found that the Map interface instantiated by HashMap can save null data for key or value. At the same time, it can also be found that the key value of the saved data is the same, and there is no error, but the content is replaced.

​ ​ ​ ​  The put method in the Map interface itself provides a return value. The return value refers to returning the old Value in the case of repeated key s.

Observe the relevant source code in HashMap:

 public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

static final float DEFAULT_LOAD_FACTOR = 0.75f;

​ ​ ​ ​  When using the constructor, it will also give the loadFactor attribute, the default value of this attribute is 0.75.

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

​ ​ ​ ​  When using the put method to save data, a putVal() method will be called, and the key will be hashed (a hash code is generated), and a Node node class will still be provided for the putVal() method. Data is saved, and a resize method is called during the operation of the putVal() method to expand the capacity.

[Interview question] How to achieve expansion when HashMap performs put operation.

static final int Default_INITIAL_CAPACITY=1<<4;//aka16

​ ​ ​ ​  provides a "Default_INITIAL_CAPACITY" constant in HashMap as the initial capacity configuration, and then the size of this element is 16 elements, that is, the maximum content that can be stored by default is 16.

​ ​ ​ ​  When the capacity of the saved content exceeds a certain threshold (DEFAULT_LOAD_FACTOR=0.75f), which is equivalent to “capacity*threshold=12”, the capacity will be expanded when 12 elements are saved. When expanding, HashMap uses the double expansion mode, that is, it expands twice the capacity each time.

[Interview questions] Explain the working principle of HashMap (started after JDK1.8)

​ ​ ​ ​  The data storage in HashMap is still done using the Node class, so in this case it proves that there are only two data structures that can be used: linked list (time complexity O(n)), binary tree (time complexity degree O(logn)).

HashMap implementation has changed since jDK1.8, because it is adapted to the massive data problems of the big data age, aligned storage has changed and provides a very important constant final TREEIFY_inside HashMap THRESHOLD=8 When using HashMap to save data, if the number of saved data does not exceed the threshold value of 8(), it will be stored in the form of a linked list, and if it exceeds, the linked list will be converted in to a red-black tree to achieve tree balance, And use left-handed and right-handed to ensure data query performance.

LinkedHashMap subclass

​ ​ ​ ​ HashMap saves all data in disorder (in fact, whether it is ordered or not has little effect on the map). If you want the data in the Map to add data to it, you can use LinkedHashMap (implemented based on linked lists).

public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>

​ ​ ​ ​  Since it is stored in a linked list, the amount of data stored in LinkedListMap cannot be too large, because it will cause the time complexity to rise.

HashTable subclass

​ ​ ​ ​ HashTable is provided from JDK1.0, and it belongs to the first batch of dynamic array implementation classes along with Vector and Enumeration. Later, in order to save it, it implements one more Map interface.

public class Hashtable<K.V> extends Dictionary <K.V>

implements Map <K.V>, Cloneable,Serializable.

​ When storing data in HashMap, the set key and value are not allowed to be empty, otherwise NullPointerException will occur.

Map.Entry internal interface

​ ​ ​ ​ Map collection is how to store data? The definition of Node type can be seen in HashMap. Through the source code definition, it can be found that the inner class of Node in HashMap implements the Map.Entry interface.

static class Node<K,V> implements Map.Entry<K,V> 

​ ​ ​ ​  So it can be concluded that all key and value data are encapsulated in the Map.Entry interface, and the definition of this interface is as follows:

public static interface Map.Entry

There are two important methods provided in this internal solution space:

  • Get key: public K getKey()
  • Get value: public V getValue()

​ ​ ​ ​  In the development version before JDK1.9, users basically do not consider creating Map.Entry objects. In fact, users do not care about Map.Entry object creation in the normal development process, but from the After JDK1.9, a new method was added to the Map interface:

//Create a Map object
public static <K,V> Map.Entry<K,V> entry(K k,V v)

​ In the entire collection of Maps, the main function of Map.Entry is to use it as a packaging type for Key and Value. In most cases, when storing data, the key and value are packaged into a Map.Entry object for use. .

Use Iterator to output Map objects

​ ​ ​ ​  For set output, the most standard way is to use the Iterator interface to complete, but there is no method in the Map set that can directly return the Iterator interface object.

​ ​ ​ ​  is actually a set of Map.Entry interface objects saved in the Map collection, so the whole Map implementation is still single-valued storage, so a method is provided in the Map collection to store all the Map collections Convert to a Set collection.

public Set Map.Entry<Keym,Value> entrySet()

​ ​ ​ ​  After analysis, we can see that if you want to realize the output of the Map collection through Iterator, you must follow the following steps:

  • Use the entrySet method provided in the Map interface to convert a Map collection to a Set collection.

  • Use the iterator method in the Set interface to convert the Set collection to an Iterator interface instance.

  • Use Iterator to iterate and output the Map.Entry object of each group, and then get the data through getKey() and getValue().

     ​ ​ ​ Although the Map collection has the support of iterative output, in terms of actual development, the main usage of the Map collection is to realize the key search of the data. In addition, it should be reminded that if you do not use Iterator and use foreach syntax output Also need to convert the Map collection to Set.

Customize the key type of Map

​ ​ ​ ​  The hashCode and equals() methods must be overridden for the class where the custom key type is located, otherwise it cannot be found.

public V put(K key,V value){
    return putVal(hash(key),key,value,false,true);
}

​ ​ ​ ​  will automatically use the incoming key data to generate a hash code when saving data.

public V get(Object key){
    Node<K,V> e;
    return (e=getNode(hash(key),key))==null?null:e.value;
}

​ ​ ​ ​  When querying data according to the key value, the incoming key value is used to obtain the corresponding hash code through the hash() method, which proves that the query process must first use hashCode() to query the data. You also need to use the equals() method.

[Interview questions] How does HashMap resolve Hash conflicts.

​ ​ ​ ​  When a hash conflict occurs, in order to ensure the normal execution of the program, all the content of the Hash conflict will be converted to a linked list at the conflicting position to save.

Collection tool class

stack

public class Stack extends Vector

​ ​ ​ ​ Stack is a subclass of Vector, but it does not use the methods provided in the Vector class, but the following two methods:

//push onto the stack
public E push(E item);
//pop
public E pop()

Queue

​ ​ ​ ​  queues can be done using a subclass of LinkedList.

Queue<String> queue=new LinkedList<String>();
//Append data to pair class
public boolean offer(E e);
//Get data from queue
public E poll()

Implementation of PriorityQueue priority queue:

​ ​ ​ ​  You can use PriorityQueue to implement a priority queue (comparison function), with sorting operations. There must be a direct correspondence with the Comparable interface.

Properties property operations

​ ​ ​ ​ java.util package provides Properties type, which is a subclass of Hashtable.

public class Properties extends Hashtable<Object,Object>

It can be found that the generic type defined in Hashtable is Object when inheriting Hashtable, and Properties do not need to operate the generic type, because the type it can implement is only the String type.

​ ​ ​ ​  If you want to implement property operations in Properties, you can use the following methods:

//1. Set properties
setProperty(String key,String value)
//2. Get the property If no value is specified, return Null
getProperty(String key)
//3. Get the attribute If the key is not specified, return the default value
getProperty(String key,String defaultValue)
//4. Get a list of properties
list(PrintStream out)

Properties are often used to read the information of configuration resources, and its biggest features are:

​ ​ ​ ​  can perform input and output processing operations of resource content, but in actual development, Properties are often used to read information about configuration resources, which is mainly used for program initialization preparation in standard design.

Collections tool class

​ ​ ​ ​ Collections is a set of collection data operation tool classes provided by java, which can be used to realize the operation of each collection. Note the difference with Collection. Collection is a collection interface that allows saving single-valued objects, while Collections is a tool class for collection operations.

//Use Collections to manipulate List collections
List<String> all=new ArrayList<String>();
Collections.addAll(all,"Hello","Byebye");
//data inversion
Collections.reverse(all)
//Use binary search
Collections.sort(all);//Sort first
System.out.println((Collections.binarySearch(all,"Hello"));

Tags: Java data structure linked list

Posted by cmgmyr on Sun, 18 Sep 2022 21:19:40 +0300