Common implementation classes under Collection and Map

Collection

Collection is inherited by the List and Set interfaces, and its main graph is:

List

The implementation classes below List are all ordered and allow elements to be repeated. There are three commonly used implementation classes: ArrayList, Vector, LinkedList. The following are introduced from the following perspectives:

• The data structure in which the underlying data is stored
• Mechanism of capacity expansion
• Common methods

ArrayList

1. The underlying data structure of ArrayList

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;  
public ArrayList(a) {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }As you can see from the constructor of ArrayList, the underlying data structure is an array that maintains an Object[]
Copy the code

2. Capacity expansion mechanism of ArrayList

1. No parameter constructor

   When the constructor is called, it only initializes an empty array of Object[], so it must be expanded when storing data in the future. What is the process of expansion? Look directly at the source code is good, here with its add method debug to explore

   public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Specify a minimum array capacity, minCapacity, to ensure that the elements can be added
       elementData[size++] = e;
       return true;
   }// We then enter the ensureCapacityInternal() function to determine the capacity
    // Enter calculateCapacity() to calculate the capacity and decide whether to expand
   private static int calculateCapacity(Object[] elementData, int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           return Math.max(DEFAULT_CAPACITY, minCapacity);// Add a default size of 10 to the array for the first time
       }
       return minCapacity;// minCapacity is returned when the number of elements added exceeds 10
   }  
    // If minCapacity is greater than elementData.length, it will be expanded
   if (minCapacity - elementData.length > 0)
       grow(minCapacity);
   }
   // Start expanding the array
   private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       // When the number of elements stored in the array is greater than 10, the first expansion is performed. Each expansion is 1.5 times the previous capacity
       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);// The copyof() function here guarantees that the original data will not be overwritten
   }
   Copy the code

   To sum up, ArrayList expands by a default size10, not by calling the constructor, but at the time of addition, and then by a factor of 1.5 if the number of stored elements is greater than 10.

2. Parameterized constructor

   // Calling the parameter constructor gives the size of the initial array
   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); }}// The line of the no-argument constructor is then continued
   public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Specify a minimum array capacity, minCapacity, to ensure that the elements can be added
       elementData[size++] = e;
       return true;
   
   Copy the code

   To summarize, the parameter constructor gives the array an initial value at the beginning, and then expands the array by 1.5 times the previous size if the number of elements exceeds the previous size

3. Common methods

package generic_exercise;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Comparator;

@SuppressWarnings({"all"})

public class ArrayListTest {
    public static void main(String[] args) {
        ArrayList list = new ArrayList<>();
        list.add(1);
        list.add("jack");
        ArrayList list1 = new ArrayList<>(10);
        list1.add(1);
        list1.add("jack");
        // Add, delete, modify and check
        / / add
        list.add(2);
        list.add(1.3);// Adding an element to the specified index does not cause a substitution
        System.out.println(list);
        list.addAll(list1);// Add a list directly after the list
        System.out.println(list);
        / / delete
       list.remove(1);// Delete by index
       list.remove("jack");// Delete by object
       list.removeAll(list1);// Delete a specified list directly
       list.clear();/ / to empty the list
        / / check
        list.contains("jack");// Check whether the object has any
        System.out.println(list.containsAll(list1));// Check the list for list1
        / / change
        System.out.println(list);
        list.set(1."tom");// Replace the element on the specified index
        System.out.println(list);
        // Other common methods
        list.size();
        list.indexOf("jack");
        list.lastIndexOf("jack");
        System.out.println(list.subList(1.3)); // Intercepts a list that is left closed and right open
        list.add(3."jacky");
        / / sorting
        list.subList(1.3).sort(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                String str1 = (String)o1;
                String str2 = (String)o2;
                returnstr2.length()-str1.length(); }});// Sort by string length
        System.out.println(list.subList(1.3));

        list.subList(1.4).sort(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                String str1 = (String)o1;
                String str2 = (String)o2;
                returnstr2.compareTo(str1); }});// The compareto method is as follows: 1. Take the smaller length of the string and compare it from the first letter.
           // Return the difference between the two letters
           // 2. If two strings start the same as (jack, Jacky), return the difference in length between the two strings
        /* public int compareTo(String anotherString) { int len1 = value.length; int len2 = anotherString.value.length; int lim = Math.min(len1, len2); char v1[] = value; char v2[] = anotherString.value; int k = 0; while (k < lim) { char c1 = v1[k]; char c2 = v2[k]; if (c1 ! = c2) { return c1 - c2; } k++; } return len1 - len2; } * /
        System.out.println(list.subList(1.4));

    }
Copy the code

Vector

Vector is similar to ArrayList except that it has the synchronized keyword modifier in its methods, which is thread-safe and preferentially used when using multiple threads.

1. The underlying data structure of the Vector

 this.elementData = new Object[initialCapacity];
Copy the code

From this we can see that the underlying Vector maintains an Object[] array.

2. Expansion mechanism of Vector

1. No parameter constructor

     public Vector(int initialCapacity, int capacityIncrement) {
           super(a);if (initialCapacity < 0)
               throw new IllegalArgumentException("Illegal Capacity: "+
                                                  initialCapacity);
           this.elementData = new Object[initialCapacity];
           this.capacityIncrement = capacityIncrement;
       }
   
   public Vector(int initialCapacity) {
           this(initialCapacity, 0);
       }
   
   public Vector(a) {
           this(10);
   }// The constructor is heavily loaded
   Copy the code

   When the constructor is called, it gives the underlying array a default size(10). When the size exceeds the default size, the array will be expanded:

   private void ensureCapacityHelper(int minCapacity) {    
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
   }
   private void grow(int minCapacity) {   
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + ((capacityIncrement > 0)? capacityIncrement : oldCapacity);// The constructor with no parameters is expanded twice each time
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       elementData = Arrays.copyOf(elementData, newCapacity);
   }
   
   Copy the code

2. Parameterized constructor

   CapacityIncrement does not specify the constructor capacityIncrement. CapacityIncrement does not specify the constructor capacityIncrement. CapacityIncrement does not specify the constructor capacityIncrement. Each time on the basis of the last capacityIncrement will be ok

To sum up, Vector calls the constructor to give the underlying array a default size, whereas ArrayList assigns a default size when adding elements. The default value for ArrayList is 10.

3. Common methods

The common methods used in Vector are similar to those used in ArrayList, but we won’t repeat them here. We haven’t touched on elements yet, but we’ll supplement them later

LinkedList

1. Underlying data structure for storing data

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev; }}Copy the code

LinkedList is a bidirectional LinkedList maintained at the bottom. The LinkedList is composed of an internal class Node in LinkedList, which is combined by Node next Node prev, Node last and Node first.

2. Capacity expansion mechanism

LinkedList from the source analysis, it does not need to be expanded, each time a new data it will be a new Node to save data, at the same time through the cursor movement to replace the head and tail of the bidirectional LinkedList, the following to add a data for example analysis:

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++;
}
Copy the code

As you can see from the source code above and cursor movement, LinkedList adds data at the end of the bidirectional list by default

3. Common methods

The common methods are not much different from the previous ArrayList, so I don’t need to explore them here.

ArrayList VS Vector VS LinkedList

• ArrayList, Vector, LinkedList all implement the List interface so that their elements are ordered and all support indexes. ArrayList and Vector maintain an object[] array at the bottom. LinkedList maintains a bidirectional LinkedList at the bottom. For array, its memory address for continuous, fixed size, which is not suitable for the dynamic storage of data, but the speed will be faster, two-way chain table variable, on a commission basis for dynamic storage data and to delete the data and to add, but queries can only be carried out in accordance with the cursor in the direction of the query, so the query will be slow
• The get() and set() methods of ArrayList and Vector perform better than LinkedList, and the remove() and add() methods of LinkedList perform better than ArrayList and Vector
• ArrayList, LinkedList without synchronized modifier, thread unsafe, Vector thread safe, but resulting in slightly less efficiency than ArrayList

Set

There are three main implementation classes under the Set interface, HashSet, LinkedHashSet, TreeSet. The elements in these three implementation classes are not allowed to repeat, because this

HashSet

1. Underlying data structure for storing data

public HashSet(a) {
    map = new HashMap<>();
}// Underneath is a hashmap
static class Node<K.V> implements Map.Entry<K.V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }//Node contains key, value, hash, Node
      
        next
      ,v>

 transient Node<K,V>[] table;// Data is stored in a table composed of nodes
Copy the code

As can be seen from the constructor of HashSet, in fact, its bottom layer is HashMap. The bottom layer of HashMap maintains a hash table, namely (array + linked list + red-black tree), so the structure of its bottom data is also hash table

2. Capacity expansion mechanism

The HashSet constructor does not allocate the size of the underlying array, so it needs to be expanded when adding elements to the array for the first time.

// First create a HashMap
public HashSet(a) {
    map = new HashMap<>();
}
PRESENT = New Object(); PRESENT = new Object()
 public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
// Calculate the hash value of the key before calling putVal to prepare the subscript for Node
      
       [] table
      ,v>
  public V put(K key, V value) {
        return putVal(hash(key), key, value, false.true);
    }
// The key is computed by calling the key.hashcode () method of the passed key, or by unsigned right-shifting it 16 to get the hash value of the key
   static final int hash(Object key) {
        int h;
        return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
    }
// Then call the putVal method
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;// The resize() method is called to expand the array the first time you add data. Set the array size to 16
     // The threshold is 0.75*16=12
        
     /* final Node
      
       [] resize() { Node
       
        [] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; else { newCap = DEFAULT_INITIAL_CAPACITY; //DEFAULT_INITIAL_CAPACITY =16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); * / / / DEFAULT_LOAD_FACTOR = 0.75}
       ,v>
      ,v>
     /* if (++size > threshold) resize(); If expansion is required next time (expansion depends on the threshold of the last expansion), then size*2, threshold *2 according to (16(12)->32(24)->..) Proceed with the following code:  else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; * /
          
        if ((p = tab[i = (n - 1) & hash]) == null)// To calculate the current data, we need to store the index in the table. If the current index bit does not store Node, we can directly create a Node and store it
            tab[i] = newNode(hash, key, value, null);
        else {/* If there is a Node (indicating that the hash value of the object currently passed in is the same as the hash value of the object stored in the Node at the index location), then a further comparison is made */                      
            Node<K,V> e; K k;
            if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
                e = p;// If the hash value is the same and the object content is the same, go e! =null, do not add
            else if (p instanceof TreeNode)/* If the contents are really different, then the rows are the same as those stored in the red-black tree under the current index
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {// If it is not a node of the red-black tree then continue to look for the bidirectional linked list below the current index
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
                            treeifyBin(tab, hash);
                        break;
                    }
                    if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                        break; p = e; }}if(e ! =null) { 
                V oldValue = e.value;
                if(! onlyIfAbsent || oldValue ==null)
                    e.value = value;
                afterNodeAccess(e);
                returnoldValue; }}// Replace Value with the Value of the current object if the data passed in is a double column
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

Copy the code

When the no-parameter constructor of a HashSet is called, a HashMap will be created, which is a Node<K,V>[] table. Table is an array of nodes to store data, and a chain or even a tree will be formed between nodes. For the first time, the table array is given a default size(16) and a threshold value of 16*0.75=12. For the second time, the hash value of the passed object key is computed to determine the index that stores the object in the table array. If the hash value is the same as the last one stored in the object, the equals() value is compared, and the store is discarded (double columns replace values). If the hash value is different, the Node under the index will be hung, and the chain will be formed. If the initial hash value is different, When the size of the table array is greater than 12, the table is doubled and the threshold is doubled. When the size of the table array is greater than 64 and the length of a chain is greater than 8, the chain is treed.

3. Common methods

Add (),remove(),size(),iterator(),contain().

LinkedHashSet

LinkedHashSet is an implementation subclass of HashSet, which differs from HashSet in that its elements are accessed in the same order

1. Underlying data structure

As can be seen from the above picture, LinkedHashSet maintains a underlying LinkedHashMap, which is different from the previous HashSet, but maintains a HashMap. The table array of HashMap stores nodes. The table array of LinkedHashSet holds an Entery, and you can see that Entery is an inner class of LinkedHashMap, The fact that entries can be stored in a Node means that entries in a LinkedHashMap inherit from nodes in a HashMap. In addition, The Entry property contains before and after, so the underlying data structure of the LinkedHashSet and LinkedHashMap should be an array plus a bidirectional list, which makes up the bidirectional list, so it looks like the data is in order. The structure is shown below:

2. Capacity expansion mechanism

// Call the no-argument constructor, table array initialization size(16), load factor 0.75
public LinkedHashSet(a) {
    super(16..75f.true);
}    
// Add data is still the same as the HashSet
 public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }


Copy the code

3. Common methods

The LinkedHashSet method is similar to the HashSet method.

TreeSet

1. Underlying data structure

It can be seen that TreeSet maintains a TreeMap at the bottom, and TreeMap maintains a red-black tree with Entry as the node. When TreeSet adds data, it can use its constructor with comparator to realize adding order. As for comparator, it has been mentioned above. Add order remove natural order, it is worth noting that when adding elements, still can not repeat, this repetition criteria specified by the comparator.

2. Capacity expansion mechanism

There’s a red-black tree at the bottom, so there’s no need to expand.

3. Common methods

The common methods are similar to the previous HashSet, except that they can be ordered, so there are more ordered methods like first(),last(),floor(),ceiling(), and so on.

Map

HashMap, HashTable, TreeMap, LinkedHashMap, properties, etc.

HashSet, LinkedHashSet, and TreeSet all analyze the underlying data structure, which will not be described here. However, the organization form of data under Map is not described in the previous section. The following diagram is used to illustrate:

The Map can be traversed through keySet, values, and entrySet, with a focus on HashTable

HashTable

A HashTable is thread-safe. Elements (keys, values) in a HashMap are not allowed to be null. A HashMap can have any number of null keys and any number of null values.

1. Underlying data structure

As you can see, its underlying data structure is similar to that of HashMap.Entry is an inner class that is equivalent to Node in HashMap, and this Entry implements the map.Entry interface.

2. Expansion mode

Here to expand the word can look at the source code:

// The array is first given a default size(11) with a load factor of 0.75
public Hashtable(a) {
    this(11.0.75 f);
}
// If the load exceeds the value, the capacity will be expanded
  protected void rehash(a) {
        intoldCapacity = table.length; Entry<? ,? >[] oldMap = table;int newCapacity = (oldCapacity << 1) + 1;// Expand by 2 times +1
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
       
Copy the code

3. Common methods

The common method is similar to HashMap, so I won’t go into details.

Properties

Properties is used to read configuration files

Selection of sets