1. Common Java containers: List, Set, Map
List:
- The Collection interface (public interface List < E > extends Collection < E >) is inherited, orderly and allows duplicate values.
Set:
- The Collection interface (public interface Set < E > extends Collection < E >) is inherited, which is disorderly and does not allow duplicate values.
Map:
- It is a container that uses key-value pairs to store (public interface Map < K, V >).
2. Differences between Collections and Collections
Collection:
- Collection is a common interface for collection classes (source code: public interface Collection < E > extends Iterable < E >).
- Looking at the source code, we can see that all of them contain some common set operation interfaces, whose direct inheritance interfaces are List and Set.
Collections:
- Collections is a collection tool class (source code: public class Collections).
- It provides a series of static methods for collecting operations, such as sorting: sort(), collecting security: synchronized Collection (), inversion: reverse(), and so on.
3. The difference between ArrayList and LinkedList
ArrayList:
- The underlying data structure is an array with high query efficiency and slow addition and deletion (adding elements at the end by default is inefficient at the designated location because subsequent elements at the designated location need to be moved backwards).
LinkedList:
- The underlying data structure is a bi-directional linked list (prev points to the front node, next points to the back node), which is slow in query efficiency and fast in addition and deletion.
4. The difference between ArrayList and Vector
ArrayList:
- Non-thread security, high reading efficiency.
Vector:
- Thread-safe (synchronized methods are used in the source code to display this class) and low reading efficiency (CopyOnWriteArrayList is recommended, which is suitable for scenarios with more reads and fewer writes).
5. The difference between HashMap and Hashtable
HashMap:
- Non-thread-safe, allowing null key values, relatively efficient execution (the underlying data structure is array + linked list + red-black tree (jdk8) or array + linked list (jdk7).
Hashtable:
- Thread-safe, no empty key values are allowed, and execution efficiency is relatively low (Concurrent HashMap is recommended).
6. Use scenarios of HashMap and TreeMap
HashMap:
- In general, insert, delete and locate elements using HashMap (commonly used).
TreeMap:
- If ordered collections are needed, TreeMap is recommended.
7, HashMap implementation principle
Take put operation as an example:
- First, the hash value (partial source code: return (key = null)? 0: (h = key. hashCode ()^ (h > > > > 16)) is obtained from the hash value of the key, and the element is placed in the position of the array (subscript) directly if there is no element in the position. Otherwise, it is judged whether the element is equal, if it is, it is covered, otherwise, the zipper method is used to solve the impulse. Sudden (create a list, first add to the end of the chain, then add to the head of the chain, more than 8 bits, using red-black tree storage).
- The elements put in are those that contain key-value pairs, not just values.
8, HashSet implementation principle
Take the add operation as an example:
- Entering the add source code (return map. put (e, PRESENT) === null), you can see that its bottom layer is implemented by map, but the value of the input is the key of the map, while the value of the map uses a unified PRESENT.
Iterator
Iterator:
- It is a lightweight object (low cost of creation), mainly used for traversal removal of collections and other operations.
- The sample code is as follows
package com.spring.test.service.demo; import java.util.*; /** * @Author: philosopherZB * @Date: 2019/10/1 */ public class Demo { public static void main(String[] args){ List<String> list = new ArrayList<>(5); for(int i=0;i<5;i++){ list.add("Test" + i); System.out.println("Input: Test" + i); } //utilize iterator()Return to one Iterator object Iterator<String> it = list.iterator(); //Determine whether there are elements while(it.hasNext()){ //First call next()It returns the first element in the collection and then the next String s = it.next(); if("Test3".equals(s)) //Remove an element it.remove(); } list.forEach(l->{ System.out.println(l); }); } }
10. ArrayList Extended Source Code Resolution (JDK8)
Source code parsing:
- First, we create an ArrayLsit using ArrayList < String > List = new ArrayList <> (5), which indicates that the initial capacity of the created ArrayList is 5.
- The source code is as follows:
//Default initial capacity 10 private static final int DEFAULT_CAPACITY = 10; //An empty default array of objects, when ArrayList(int initialCapacity)，ArrayList(Collection<? extends E> c)When the capacity in the system is equal to 0, it will be used. private static final Object[] EMPTY_ELEMENTDATA = {}; //An empty default object array for ArrayList()constructor private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //An array of objects, transient Represents not serializable transient Object[] elementData; //Array size private int size; //Construct an empty one with incoming capacity list public ArrayList(int initialCapacity) { //If the input value is greater than 0, an array of the size of the capacity is created. if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //Otherwise, if the incoming value equals 0, a default empty array is created this.elementData = EMPTY_ELEMENTDATA; } else { //Throw an exception if it is less than 0 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
- Then we use the add method to add a string to the list, list.add("Test"). Entering the add source code reveals that the true expansion occurs before the add operation.
- The source code is as follows:
//Added by default at the end of the array public boolean add(E e) { //Confirm whether expansion is needed before adding ensureCapacityInternal(size + 1); // Increments modCount!! //The new element is added at the end of the array, followed by the array. size Self increment. elementData[size++] = e; return true; }
- Enter the ensureCapacityInternal() method to see the corresponding source code as follows:
private void ensureCapacityInternal(int minCapacity) { //First pass calculateCapacity Method Calculates the final capacity to confirm the actual capacity ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
- At this point, we need to go into the calculateCapacity() method to see how it calculates the final capacity. The source code is as follows:
private static int calculateCapacity(Object[] elementData, int minCapacity) { //If elementData For the default empty array, compare the incoming value with the default value (10), and return the larger value of the two. //elementData By default, empty arrays are passed ArrayList()Created by this constructor ArrayList object if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } //Returns the incoming value return minCapacity; }
- Now that we have confirmed the final capacity, go to ensure ExplicitCapacity and check the source code as follows:
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code //If the final confirmation capacity is greater than the array capacity, then proceed grow()Capacity expansion if (minCapacity - elementData.length > 0) grow(minCapacity); }
- As you can see, only when the final capacity is larger than the capacity of the array will the capacity be expanded. Then take our example above as an example to make a concrete analysis as follows:
- First, elementData.length = 5 because we assigned the initial capacity 5 when we created it.
- When we add the first element, minCapacity is equal to size + 1 = 1.
- At this time, the condition of minCapacity - elementData. length > 0 is not valid, so it will not enter the growth (minCapacity) method for expansion.
- In this way, only when added to fifth elements, minCapacity = 6 is greater than elementData.length = 5, then the grow(minCapacity) method will be expanded.
- The source codes for growth () and hugeCapacity() are as follows:
//Maximum allocatable array size private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //Capacity expansion private void grow(int minCapacity) { // overflow-conscious code //oldCapacity Represents old capacity int oldCapacity = elementData.length; //newCapacity Represents the new capacity and the calculation rule is the old capacity.+Old capacity 0.5，1 of the old capacity.5 Times. If exceeded int The maximum value returns a negative number. //oldCapacity >> 1 Represents moving one bit to the right, which corresponds to the first power divided by two. int newCapacity = oldCapacity + (oldCapacity >> 1); //If the new capacity is less than the minimum capacity, the minimum capacity is assigned to the new capacity.(Sometimes manual expansion may return<0，The corresponding method is ensureCapacity()) if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //If the new capacity is larger than MAX_ARRAY_SIZE，Then execute hugeCapacity(minCapacity)Returns the corresponding value if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: //Copy the old array to the new capacity array to complete the expansion operation elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { //If the minimum capacity exceeds int The maximum value, minCapacity It will be a negative number, at which point a memory overflow error will be thrown if (minCapacity < 0) // overflow throw new OutOfMemoryError(); //Compare whether the minimum capacity is greater than MAX_ARRAY_SIZE，If so, return Integer.MAX_VALUE，Otherwise return MAX_ARRAY_SIZE return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
(All of the above are personal notes. If there are any mistakes, please correct them.)