Overview of JAVA collection framework
1. Overview of collection framework
A collection can be regarded as a container for storing object information. All collection classes are located in Java Util package, but the collection class supporting multithreading is located in Java util. Under concurrent package.
The differences between arrays and collections are as follows:
- The length of the array cannot be changed, and the data with mapping relationship cannot be saved; The collection class is used to save data with uncertain quantity and data with mapping relationship.
- Array elements can be either basic type values or objects; Collection can only hold objects.
2. Common interfaces and implementation classes of Java collection
1)List
The List set represents an ordered and repeatable set, and each element in the set has its corresponding sequential index. The List collection sets the index of the elements by default according to the order in which the elements are added. You can access the collection elements at the specified position through the index (similar to the subscript of the array).
The collection that implements the List interface mainly includes ArrayList, LinkedList, Vector and Stack.
(1) ArrayList
- ArrayList is a dynamic array. Its bottom layer is implemented by the array, which allows the insertion of any regular elements, including null
- The initial capacity of ArrayList is 10, and each expansion is 0.5 times (the odd number is reduced by one first)
- ArrayList is good at accessing and non thread safe
ArrayList capacity expansion test:
package com.zgjt.design.collection;
import java.lang.reflect.Field;
import java.util.ArrayList;
public class ListDemo {
public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
ArrayList<String> arrayList = new ArrayList<>();
for(int i = 0; i < 50;i++){
arrayList.add("test");
getArrayListCapacity(arrayList);
}
}
public static void getArrayListCapacity(ArrayList<?> arrayList) throws NoSuchFieldException, IllegalAccessException {
Class<ArrayList> arrayListClass = ArrayList.class;
Field field = arrayListClass.getDeclaredField("elementData");
field.setAccessible(true);
Object[] objects = (Object[])field.get(arrayList);
System.out.println( objects.length + ":" + arrayList.size());
System.out.println("--------------------------");
}
}
(2) LinkedList
- Linked is a linked list implementation, and LinkedList also implements the Deque interface, which can be used as a double ended queue
- Random access efficiency is poor, and the efficiency of adding and deleting elements is high
(3) Vector and Stack
- Vector is similar to ArrayList, but vector is synchronized. So vector is a thread safe dynamic array. Its operation is almost the same as ArrayList.
- Stack inherits from Vector and implements a last in first out stack. Stack provides five additional methods to enable Vector to be used as a stack. The basic push and pop methods, as well as the peek method, get the elements at the top of the stack. The empty method tests whether the stack is empty, and the search method detects the position of an element in the stack. Stack is empty just after it is created.
2) Set
The Set Collection has the same method as the Collection, and the Set Collection is not allowed to store the same elements
(1)HashSet
- Element access order cannot be guaranteed
- HashSet is thread unsafe
- Collection elements can be null
- HashSet implementation: it is a hashMap, and the value is stored in the key of hashMap. When an element is stored in the HashSet set, the HashSet will call the hashCode() method of the object to get its hashCode value, and then determine the storage location of the object according to the hashCode value. The criteria for judging the equality of two elements in the HashSet set are (1) two objects return true through the equals() method comparison; (2) The return value of the hashCode() method of the two objects is equal. Therefore, if one of (1) and (2) does not meet the conditions, it is considered that the two objects are not equal and can be added successfully. If the return values of the hashCode() method of two objects are equal, but the two objects return false through the equals() method comparison, the HashSet will save the two objects in the same location in a chain structure, which will lead to performance degradation. Therefore, this situation should be avoided during coding.
(2)linkedHashSet
- LinkedHashSet is a subclass of HashSet. It has the characteristics of HashSet and determines the storage location of elements according to the hashCode value of elements. However, it uses a linked list to maintain the order of elements, which is consistent with the addition order. Because LinkedHashSet needs to maintain the insertion order of elements, its performance is slightly lower than that of HashSet, but it has good performance when iteratively accessing all elements in the Set.
(3)TreeSet
- TreeSet is the implementation class of SortedSet interface. TreeSet can ensure that the elements are in the sorting state and null values are not allowed. It uses the data structure of red black tree to store the set elements. TreeSet supports two sorting methods: natural sorting and custom sorting. Natural sorting is adopted by default.
3) Map
The Map interface adopts the storage method of key value pair Map < K, V > to save data with mapping relationship. Key and value can be data of any reference type. Key value cannot be repeated and can be null
(1)HashMap
- HashMap is an asynchronous implementation of Map interface based on hash table. This implementation provides all optional mapping operations and allows the use of null values and null keys. This class does not guarantee the order of the mapping, in particular, it does not guarantee that the order is constant
- HashMap is based on the hashing principle. It calls the hashCode() method of the object to calculate the hashCode value, and then finds the bucket location to store the value object. HashMap uses the linked list to solve the collision problem. When a collision occurs, the object will be stored in the next node of the linked list. jdk1. After 8, when the length of the linked list exceeds 8, it will be automatically converted to red black tree.
- hashmap capacity expansion: the default initialization length is 16, and the length can be specified. The specified length should preferably be to the nth power of 2 (if not, it will automatically become). When the number of elements in hashmap exceeds the array size * loadFactor, the array capacity will be expanded. The default value of loadFactor is 0.75, which is twice the original capacity.
- Differences between and HashMap:
1. HashMap Is thread unsafe, HashTable Is thread safe. 1. HashMap have access to null Maximum value key or value；Hashtable Not allowed null Value as key and value，If put null Put in HashTable In, a null pointer exception will occur
(2)LinkedHashMap
- linkedhashMap ensures the insertion order, and its performance is slightly lower than that of HashMap
- linkedHashMap is a subclass of HashMap. It maintains a linked list based on HashMap and is responsible for maintaining the iteration order of the Map.
(3)Properties
- Used to read configuration files
username = Zhang San age = 28
package com.zgjt.design.collection;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Properties;
public class PropertiesDemo {
public static void main(String args[]) throws IOException {
Properties properties = new Properties();
BufferedReader bufferedReader = new BufferedReader(new FileReader("D:\\Project documents\\test.properties"));
properties.load(bufferedReader);
System.out.println( properties.getProperty("username") );
}
}
(4) TreeMap
- treeMap sorting, null values are not allowed.
- TreeMap is the implementation class of SortedMap. It is a data structure of red black tree. Each key value pair is used as a node of red black tree. When storing key value pairs in TreeMap, you need to sort the nodes according to the key.
Two sorting methods:
- Natural sorting: all keys of TreeMap must implement the Comparable interface, and all keys should be objects of the same class, otherwise ClassCastException will be thrown.
- Custom sorting: when creating a TreeMap, a Comparator object is passed in, which is responsible for sorting all key s in the TreeMap.
4) Iterator
Iterator is an interface that is an iterator of a collection. The collection can traverse the elements in the collection through the iterator.
package com.zgjt.design.collection;
import java.util.*;
public class IteratorDemo {
public static void main(String[] args){
List<String> stringList = new ArrayList<>();
stringList.add("Zhang San");
stringList.add("Li Si");
stringList.add("Wang Wu");
stringList.add("Ma Liu");
Iterator<String> iterator = stringList.iterator();
/*ergodic*/
while(iterator.hasNext()){
System.out.println(iterator.next());
}
System.out.println("------------------------");
/*delete*/
iterator = stringList.iterator();
while(iterator.hasNext()){
if(iterator.next().equals("Li Si")){
iterator.remove();
}
}
for(String str : stringList){
System.out.println(str);
}
System.out.println("---------------------");
/* ListIterator */
ListIterator<String> listIterator = stringList.listIterator();
while(listIterator.hasNext()){
System.out.println(listIterator.next());
}
System.out.println("---------------------");
while(listIterator.hasPrevious()){
System.out.println(listIterator.previous());
}
}
}
5) Other common collections
(1) ConcurrentHashMap
- 1. Compared with HashMap, ConcurrentHashMap is thread safe and located in Java util. In the concurrent package, null values are not allowed for both key and value.
- 2. ConcurrentHashMap is in jdk1 7 is to use segment lock to ensure thread safety, jdk1 8 followed by cas optimistic lock + synchronized lock
- 3. The conditions for converting the ConcurrentHashMap linked list into red black tree: one is that the length of the linked list reaches 8, and the other is that the length of the array exceeds 64