Ten thousand word long article in-depth understanding of collections in Java – PDF download attached
1. Preface
Collection is used to store multiple data. In addition to the basic types, collection should be the most commonly used type in Java. Collection types in Java are generally concentrated in Java Util package and Java util. In the concurrent package.
The collection class in util package is the basic collection class, while the collection class in concurrent package is a collection class specially prepared for concurrency.
There are two parent classes of collection class, one is Java util. Collection, one is Java util. Map。
Let's first look at the definition of collection:
public interface Collection<E> extends Iterable<E> {
}
Collection inherits from Iterable interface, which means that all collections are traversable. And a data type can be saved in the collection.
Let's look at the definition of map:
public interface Map<K,V> {
}
You can see that map is a top-level interface, which can maintain two data types: key and value.
Collection is the parent class of list, set and queue, which constitutes the four types of collection: list, queue, set and map. We will explain them one by one next.
2. List
Let's first look at the definition of list:
public interface List<E> extends Collection<E> {
}
List is an interface inherited from collection and represents an ordered linked list. Common lists include ArrayList, LinkedList, etc.
2.1 what do you know about fail safe and fail fast
When we use collection classes, we usually need to traverse the elements in the collection and process the elements in the traversal. At this time, we need to use the iterator. Friends who often write programs should know that the collection data cannot be modified during the traversal of the iterator, otherwise a concurrentmodificationexception will be thrown.
Because of the existence of concurrentmodificationexception, iterators are divided into two categories: fail fast and fail safe.
2.1. 1 fail-fast Iterator
Fail fast can be seen by its name. It means to fail very fast. That is, if the structure of the set is modified during traversal, an error will be reported immediately.
Fail fast usually throws a concurrentmodificationexception in the following two cases:
In a single threaded environment, if the structure of the collection is modified by calling other methods instead of the remove method of the iterator itself after the iterator is created, an error will be reported.
If an iterator is created in one thread and the structure of the collection is modified in another thread, an error will be reported.
Let's take a look at an example of fail fast:
Map<Integer,String> users = new HashMap<>();
users.put(1,"jack");
users.put(2,"alice");
users.put(3,"jone");
Iterator iterator1 = users.keySet().iterator();
//not modify key,so no exception
while (iterator1.hasNext())
{
log.info("{}",users.get(iterator1.next()));
users.put(2,"mark");
}
In the above example, we build a map, and then traverse the key of the map. In the process of traversal, we modify the value of the map.
It is found that the program executes perfectly without reporting any exceptions.
This is because we traverse the key of the map. As long as the key of the map is not manually modified, there is no problem.
Take another example:
Map<Integer,"jone");
Iterator iterator1 = users.keySet().iterator();
Iterator iterator2 = users.keySet().iterator();
//modify key,get exception
while (iterator2.hasNext())
{
log.info("{}",users.get(iterator2.next()));
users.put(4,"mark");
}
In the above example, we modified the key while traversing the key of the map. In this case, an error will be reported.
2.1. 2. Principle of fail fast
Why is an exception reported when the structure of the set is modified?
Let's take ArrayList as an example to explain the principle of fail fast.
In abstractlist, a modcount variable is defined:
protected transient int modCount = 0;
In the process of traversal, the checkforcomodification() method will be called to detect modcount:
public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (indexoutofboundsexception e) {
checkForComodification();
throw new NoSuchElementException();
}
}
If the test result is not as expected, an error will be reported:
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
When creating the iterator, the current modcount will be copied for comparison, and this modcount will change every time the collection is modified, resulting in the inconsistency between the modcount in the iterator and the existing modcount.
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.set(lastRet,e);
expectedModCount = modCount;
} catch (indexoutofboundsexception ex) {
throw new ConcurrentModificationException();
}
}
Note that fail fast does not guarantee that all modifications will report errors. We cannot rely on concurrentmodificationexception to judge whether the collection is modified during traversal.
2.1. 3 Fail-safe Iterator
Let's talk about fail safe again. Fail safe means that no error will be reported if the collection is modified during traversal.
The following types of concurrent package are fail safe. Take a concurrent HashMap example:
Map<Integer,String> users = new ConcurrentHashMap<>();
users.put(1,"mark");
}
Iterator iterator2 = users.keySet().iterator();
//modify key,"mark");
}
The above example performs perfectly and will not report an error.
2.2 three methods of iterator to list
Iterator is indispensable for the variables of a collection. It is very simple to call the iterator method directly from the collection.
So how to generate a list from the iterator in turn? Today I will teach you three methods.
2.2. 1 use while
The simplest and most basic logic is to use while to traverse the iterator, and add the elements in the iterator to the new list during the traversal.
As shown in the following code:
@Test
public void useWhile(){
List<String> stringList= new ArrayList<>();
Iterator<String> stringIterator= Arrays.asList("a","b","c").iterator();
while(stringIterator.hasNext()){
stringList.add(stringIterator.next());
}
log.info("{}",stringList);
}
2.2. 2 using foreachremaining
The iterator interface has a default method:
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
In fact, the underlying layer of this method encapsulates the while loop, so we can directly use the foreachremaining method:
@Test
public void useForEachRemaining(){
List<String> stringList= new ArrayList<>();
Iterator<String> stringIterator= Arrays.asList("a","c").iterator();
stringIterator.forEachRemaining(stringList::add);
log.info("{}",stringList);
}
2.2. 3 use stream
We know that when building a stream, we can call the stream method of streamsupport:
public static <T> Stream<T> stream(Spliterator<T> spliterator,boolean parallel)
This method passes in a splitter parameter. The Iterable interface happens to have a splitter () method:
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnkNownSize(iterator(),0);
}
Then we can convert iterator to iteratable and pass it into stream.
A careful study of the Iterable interface shows that Iterable is a functional interface. You only need to implement the following interfaces:
Iterator<T> iterator();
Using lambda expression, we can easily convert iterator to iteratable:
Iterator<String> stringIterator= Arrays.asList("a","c").iterator();
Iterable<String> stringIterable = () -> stringIterator;
Finally, wrap it into a list:
List<String> stringList= StreamSupport.stream(stringIterable.spliterator(),false).collect(Collectors.toList());
log.info("{}",stringList);
2.3 stories that aslist and ArrayList have to tell
When it comes to collection classes, ArrayList should be used a lot. The ArrayList here is Java util. ArrayList, how do we usually create ArrayList?
2.3. 1 create ArrayList
Take the following example:
List<String> names = new ArrayList<>();
The above method creates an ArrayList. If we need to add elements to it, we need to call the add method again.
We usually use a more concise method to create a list:
@Test
public void testAsList(){
List<String> names = Arrays.asList("alice","bob","jack");
names.add("mark");
}
See the definition of the aslist method:
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
Good, use arrays Aslist, we can easily create ArrayList.
Run the above example. Something strange happened. The above example threw an unsupported operation exception.
java.lang.UnsupportedOperationException
at java.util.AbstractList.add(AbstractList.java:148)
at java.util.AbstractList.add(AbstractList.java:108)
at com.flydean.AsListUsage.testAsList(AsListUsage.java:18)
2.3. 2 UnsupportedOperationException
Let's talk about this exception first. Unsupported operationexception is a runtime exception, which is usually used in some methods that do not implement interfaces in some classes.
Why does the above ArrayList throw an exception when calling the add method?
2.3. 3 asList
Let's take a closer look at arrays ArrayList returned in aslist method:
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess,java.io.Serializable
As you can see, arrays The ArrayList returned by aslist is an internal class in the arrays class, not Java util. ArrayList。
This class inherits from abstractlist. In abstractlist, the add method is defined as follows:
public void add(int index,E element) {
throw new UnsupportedOperationException();
}
Well, our problem has been solved.
2.3. 4 Conversion
We use arrays After aslist gets the ArrayList, can it be converted into Java util. What about ArrayList? The answer is yes.
Let's look at the following example:
@Test
public void testList(){
List<String> names = new ArrayList<>(Arrays.asList("alice","jack"));
names.add("mark");
}
The above example can be executed normally.
There are many classes with the same name in Java. We need to find out what they are. Don't confuse them.
2.4 four methods of copy ArrayList
ArrayList is a collection class that we often use. Sometimes we need to copy an ArrayList. Today, I'd like to introduce four common ways to copy ArrayList.
2.4. 1 use constructor
ArrayList has a constructor that can pass in a collection:
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData,size,Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
From the above code, we can see that the underlying layer actually calls arrays Copyof method to copy the array. This copy calls the system's native array copy method. Note that the copy here is a reference copy, not a value copy. This means that if the value of the object changes after copying, the source object will also change.
for instance:
@Test
public void withConstructor(){
List<String> stringList=new ArrayList<>(Arrays.asList("a","c"));
List<String> copyList = new ArrayList<>(stringList);
copyList.set(0,"e");
log.info("{}",stringList);
log.info("{}",copyList);
List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("b"),new CustBook("c")));
List<CustBook> copyobjectList = new ArrayList<>(objectList);
copyobjectList.get(0).setName("e");
log.info("{}",objectList);
log.info("{}",copyobjectList);
}
Operation results:
22:58:39.001 [main] INFO com.flydean.CopyList - [a,b,c]
22:58:39.008 [main] INFO com.flydean.CopyList - [e,c]
22:58:39.009 [main] INFO com.flydean.CopyList - [CustBook(name=e),CustBook(name=b),CustBook(name=c)]
22:58:39.009 [main] INFO com.flydean.CopyList - [CustBook(name=e),CustBook(name=c)]
We see that the change of the object actually changes the source of the copy. And copylist Set (0, "e") actually creates a new string object and assigns it to the 0 position of the copylist.
2.4. 2 use the addall method
List has an addall method, which we can use to copy:
@Test
public void withAddAll(){
List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("c")));
List<CustBook> copyobjectList = new ArrayList<>();
copyobjectList.addAll(objectList);
copyobjectList.get(0).setName("e");
log.info("{}",copyobjectList);
}
The same copy is the reference of the object.
2.4. 3. Use collections copy
Similarly, use collections Copy can also get the same effect. See the following code:
@Test
public void withcopy(){
List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("c")));
List<CustBook> copyobjectList = new ArrayList<>(Arrays.asList(new CustBook("d"),new CustBook("e"),new CustBook("f")));
Collections.copy(copyobjectList,objectList);
copyobjectList.get(0).setName("e");
log.info("{}",copyobjectList);
}
2.4. 4 use stream
We can also use stream introduced by Java 8 to implement:
@Test
public void withStream(){
List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("c")));
List<CustBook> copyobjectList=objectList.stream().collect(Collectors.toList());
copyobjectList.get(0).setName("e");
log.info("{}",copyobjectList);
}
Well, the four methods are finished. Please note that the four methods are all reference copies. Be careful when using them.
3. Map
Let's first look at the definition of map:
public interface Map<K,V> {
}
Map is a collection of key value pairs, where key cannot be repeated, but value can be repeated. Common maps include treemap and HashMap.
3.1 deeply understand the difference between HashMap and treemap
HashMap and treemap are two classes commonly used in the map family. What are the differences between the two classes in use and essence? This paper will make an in-depth discussion from these two aspects, hoping to reveal its essence.
3.1. 1. Essential difference between HashMap and treemap
Let's first look at the definition of HashMap:
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>,Cloneable,Serializable
Look at the definition of treemap:
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,java.io.Serializable
From the definition of classes, HashMap and treemap inherit from abstractmap. The difference is that HashMap implements the map interface, while treemap implements the navigablemap interface. Navigablemap is a SortedMap, which implements the sorting of keys in the map.
In this way, the first difference between the two comes out. Treemap is sorted and HashMap is not.
Let's look at the difference between the constructors of HashMap and treemap.
public HashMap(int initialCapacity,float loadFactor)
In addition to the default parameterless constructor, HashMap can also accept two parameters, initialCapacity and LoadFactor.
The underlying structure of HashMap is an array of nodes:
transient Node<K,V>[] table
InitialCapacity is the initial capacity of the table. If you do not pass initialCapacity, HashMap provides a default value:
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
When there is too much data stored in the HashMap, the table array will be full. At this time, the capacity needs to be expanded. The capacity of the HashMap is expanded in a multiple of 2. The LoadFactor specifies when capacity expansion is required. The default LoadFactor is 0.75.
static final float DEFAULT_LOAD_FACTOR = 0.75f;
Let's look at some very interesting variables:
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
What's the use of the above three variables? Before Java 8, HashMap used the form of linked list to solve hashcode conflict. In order to improve efficiency, Java 8 transformed it into treenode. When will this conversion be sent?
At this time, we need to look at the two variables treeify_ Threshold and untreeify_ THRESHOLD。
Some students may have found treeify_ Why is threshold better than untreeify_ What about threshold 2? In fact, I don't know this problem, but if you look at the source code, untreeify is used_ When threshold is used, it is < =, but treeify is used_ When threshold is used, it is > = tree_ Threshold - 1, so the two variables are essentially the same.
MIN_ TREEIFY_ Capacity means that if table converts the minimum capacity of treenode, only capacity > = min_ TREEIFY_ The conversion of treenode is allowed only when the capability is.
The difference between treemap and HashMap is that the bottom layer of treemap is an entry:
private transient Entry<K,V> root
His implementation is a red black tree, which is convenient for traversal and search.
The constructor of treemap can be passed into a comparator to implement custom comparison methods.
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
If no custom comparison method is provided, the natural order of the key is used.
3.1. 2 sorting difference
After we have finished talking about the essence of the two, let's take an example to see the difference between the two:
@Test
public void withOrder(){
Map<String,String> books = new HashMap<>();
books.put("bob","books");
books.put("c","concurrent");
books.put("a","a lock");
log.info("{}",books);
}
@Test
public void withOrder(){
Map<String,String> books = new TreeMap<>();
books.put("bob",books);
}
In the same code, one uses HashMap and the other uses treemap. We will find that the output results of treemap are in good order, while the output results of HashMap are uncertain.
3.1. 3 difference between null values
HashMap can allow one null key and multiple null values. Treemap does not allow null keys, but multiple null values can be allowed.
@Test
public void withNull() {
Map<String,String> hashmap = new HashMap<>();
hashmap.put(null,null);
log.info("{}",hashmap);
}
@Test
public void withNull() {
Map<String,String> treemap = new TreeMap<>();
treemap.put(null,treemap);
}
Treemap will report: NullPointerException.
3.1. 4 performance differences
The bottom layer of HashMap is array, so HashMap will be very fast in adding, finding, deleting and other methods. The bottom layer of treemap is a tree structure, so the speed will be relatively slow.
In addition, HashMap will cause a waste of space because it needs to save an array, while treemap only saves the nodes to be maintained, so it occupies a small space.
In case of hash conflict in HashMap, the efficiency will become worse. However, after the treenode conversion in Java 8, the efficiency has been greatly improved.
Treemap will reorder when adding and deleting nodes, which will affect the performance.
3.1. 5 common ground
Neither of them allows duplicate keys, and neither of them is thread safe.
3.2 deeply understand the difference between HashMap and LinkedHashMap
We know that the variable order of HashMap is unpredictable, which means that the convenient output order is not necessarily consistent with the insertion order of HashMap. This feature usually causes some problems in our work. To achieve this, we can use LinkedHashMap.
3.2. 1. Detailed explanation of LinkedHashMap
Let's take a look at the definition of LinkedHashMap:
public class LinkedHashMap<K,V>
extends HashMap<K,V>
LinkedHashMap inherits from HashMap, so all functions of HashMap can be used in LinkedHashMap.
The difference between LinkedHashMap and HashMap is that a new entry is created:
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before,after;
Entry(int hash,K key,V value,Node<K,V> next) {
super(hash,key,value,next);
}
}
This entry inherits from HashMap Node, an additional before and after is added to realize the connection between nodes.
Through this newly created entry, you can ensure that the traversal order is consistent with the insertion order.
3.2. 2 insert
Here is an example of LinkedHashMap insertion:
@Test
public void insertOrder(){
LinkedHashMap<String,String> map = new LinkedHashMap<>();
map.put("ddd","desk");
map.put("aaa","ask");
map.put("ccc","check");
map.keySet().forEach(System.out::println);
}
Output results:
ddd
aaa
ccc
You can see that the output result is consistent with the insertion result.
3.2. 3 Access
In addition to the traversal order, LinkedHashMap also has a very distinctive access order.
Let's take another look at the constructor of LinkedHashMap:
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity,loadFactor);
this.accessOrder = accessOrder;
}
The first two parameters, initialCapacity and LoadFactor, have been discussed before. Now let's look at the last parameter, accessorder.
When accessorder is set to true, access order is enabled.
Access order means that objects are installed in the order from the oldest access to the latest access. Let's take an example:
@Test
public void accessOrder(){
LinkedHashMap<String,String> map = new LinkedHashMap<>(16,.75f,true);
map.put("ddd","check");
map.keySet().forEach(System.out::println);
map.get("aaa");
map.keySet().forEach(System.out::println);
}
Output results:
ddd
aaa
ccc
ddd
ccc
aaa
We can see that because we visited "AAA" once, we ranked last in the traversal.
3.2. 4 removeEldestEntry
Finally, let's take a look at a special feature of LinkedHashMap, removeeldestentry. What does this method do?
By re removeeldestentry method, LinkedHashMap can save a specific number of entries, which is usually used when LinkedHashMap is used as cache.
Removeeldestentry will delete the oldest entry and keep the latest one.
ublic class CustLinkedHashMap<K,V> extends LinkedHashMap<K,V> {
private static final int MAX_ENTRIES = 10;
public CustLinkedHashMap(
int initialCapacity,loadFactor,accessOrder);
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
}
Take a look at the above customized example. In the above example, we created a LinkedHashMap with 10 entry nodes.
LinkedHashMap inherits from HashMap and provides two very useful functions.
3.3 enummap and enumset
Generally speaking, we will choose to use HashMap to store data in key value format. Considering such a special case, the keys of a HashMap come from an enum class. In this case, we can consider using enummap to be discussed in this article.
3.3. 1 EnumMap
Let's take a look at the comparison between enummap definition and HashMap definition:
public class EnumMap<K extends Enum<K>,V>
implements java.io.Serializable,Cloneable
public class HashMap<K,Serializable
We can see that enummap is almost the same as HashMap. The difference is that the key of enummap is an enum.
Here is a simple example:
Define an enum first:
public enum Types {
RED,GREEN,BLACK,YELLO
}
Let's see how to use enummap:
@Test
public void useEnumMap(){
EnumMap<Types,String> activityMap = new EnumMap<>(Types.class);
activityMap.put(Types.BLACK,"black");
activityMap.put(Types.GREEN,"green");
activityMap.put(Types.RED,"red");
}
Other operations are actually similar to HashMap. We won't talk about them here.
3.3. 2 when to use enummap
Because the possible values of all keys in enummap are known at the time of creation, using enummap can improve efficiency compared with HashMap.
At the same time, because the key is relatively simple, there is no need to consider some complex situations like HashMap in the implementation of enummap.
3.3. 3 EnumSet
Similar to enummap, enumset is a set, and the elements in the set are of an enum type.
Enumset is an abstract class. To create an enumset class, you can use two static methods provided by enumset, noneof and allof.
Let's look at a noneof:
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
Enum<?>[] universe = getUniverse(elementType);
if (universe == null)
throw new ClassCastException(elementType + " not an enum");
if (universe.length <= 64)
return new RegularEnumSet<>(elementType,universe);
else
return new JumboEnumSet<>(elementType,universe);
}
Noneof passes in an enum class and returns an empty enumset of enum type.
From the above code, we can see that enumset has two implementations. Jumboenumset is used when the length is greater than 64 and regularenumset is used when the length is less than 64.
Note that jumboenumset and regularenumset are not recommended to be used directly. They are internal classes.
Take another look at allof:
public static <E extends Enum<E>> EnumSet<E> allOf(Class<E> elementType) {
EnumSet<E> result = noneOf(elementType);
result.addAll();
return result;
}
AllOf is very simple. First call noneOf to create an empty set, then call the addAll method to add all the elements.
3.3. 4 Summary
Enummap and enumset optimize specific enum objects and can be used in appropriate cases.
3.4 implementation of skiplist and concurrentskiplistmap
At first I heard that skiplist made me look stupid. What? And skiplist? What is this.
After continuous search and learning, I finally realized that skiplist was originally a data structure, and the concurrentskiplistmap and concurrentskiplistset in Java are the implementation of this structure.
Next, let's unveil skiplist and concurrentskiplistmap step by step.
3.4. 1 SkipList
Let's take a look at the definition of skiplist in Wikipedia:
Skiplist is a hierarchical structure. At the bottom is the most primitive linked list that has been sorted.
Up is a layer by layer hierarchical structure, and each bottom node appears in the list of the upper layer according to a certain probability. This probability is called P, usually P takes 1 / 2 or 1 / 4.
First set a function f, which can randomly generate 0 and 1, and the probability of these two numbers is the same, then p is 1 / 2.
For each node, we operate as follows:
We run f once. When f = 1, we insert the node into the list of the upper layer. When f = 0, do not insert.
For example, there are 10 sorted nodes in the list in the above figure, and the first node is on each layer by default. For the second node, run f = 0 without inserting. For the third node, run f = 1, insert the third node into layer 1, and so on. Finally, the nodes in layer 1 list are: 1, 3, 4, 6 and 9.
Then we continue to build the layer up. Finally, the skiplist in the figure above is obtained.
By using skiplist, we build multiple lists containing different sorted nodes, so as to improve the search efficiency of lists.
We can have a clearer understanding through the following figure:
Each search starts from the top layer, because the number of nodes at the top layer is the least. If the node to be searched is between two nodes in the list, move down one layer to continue the search. Finally, find the position to be inserted at the bottom layer, insert the node, and then call the probability function f again to decide whether to copy the node upward.
It is essentially equivalent to binary search, and the time complexity of search is O (logn).
3.4. 2 ConcurrentSkipListMap
If concurrent skiplistmap is a concurrent skiplist, it has two characteristics, skiplist and concurrent. Let's explain it separately.
The data structure of skiplist is explained above. Next, let's see how concurrentskiplistmap implements this skiplist:
There are three structures in concurrentskiplistmap: base nodes, head nodes and index nodes.
Base nodes constitutes an ordered linked list structure and is the bottom implementation of concurrentskiplistmap.
static final class Node<K,V> {
final K key;
volatile Object value;
volatile Node<K,V> next;
/**
* Creates a new regular node.
*/
Node(K key,Object value,V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
As can be seen above, each node is a K, V entry, and it has a next pointing to the next node.
Index nodes is the basic node for building the skiplist superstructure:
static class Index<K,V> {
final Node<K,V> node;
final Index<K,V> down;
volatile Index<K,V> right;
/**
* Creates index node with given values.
*/
Index(Node<K,V> node,Index<K,V> down,V> right) {
this.node = node;
this.down = down;
this.right = right;
}
}
From the above structure, we can see that the index node contains node nodes. In addition, the index also has two pointers, one pointing to the next node of the same layer and the other pointing to the node of the next layer.
Such a structure can facilitate the implementation of traversal.
Finally, take a look at headindex, which represents the head node:
static final class HeadIndex<K,V> extends Index<K,V> {
final int level;
HeadIndex(Node<K,V> right,int level) {
super(node,down,right);
this.level = level;
}
}
Headindex is very similar to index, except that a level field is added to indicate the level.
During the initialization of concurrentskiplistmap, headindex will be initialized:
head = new HeadIndex<K,V>(new Node<K,V>(null,BASE_HEADER,null),null,1);
We can see that the node in headindex is key = null and value = base_ Virtual node of header. Initial level = 1.
Next, let's look at how concurrency is implemented:
Basically, concurrent classes are through unsafe Compareandswapobject, and concurrentskiplistmap is no exception.
Suppose we have three nodes, b-n-f. Now you need to delete node n.
The first step is to use CAS to set the value of n's valu from non null to null. At this time, any external operation will think that this node does not exist. However, those internal insert or delete operations will continue to modify n's next pointer.
The second step is to use CAS to point the next pointer of n to a new marker node. From this time on, the next pointer of n will not point to any other node.
Let's take a look at the definition of the marker node:
Node(Node<K,V> next) {
this.key = null;
this.value = this;
this.next = next;
}
We can see that the marker node is actually a node with null key and value.
Step 3: use CAS to point the next pointer of B to F. From this step, n nodes will not be accessed by other programs, which means that n can be garbage collected.
Let's think about why we want to insert a marker node. This is because when deleting, we need to tell all threads that node n is ready to be deleted, because n originally points to node F. at this time, we need an intermediate node to represent the state ready to be deleted.
4. Queue
Let's first look at the definition of queue:
public interface Queue<E> extends Collection<E> {
}
Queue represents a queue, which is characterized by first in first out. Commonly used queues include delayqueue, BlockingQueue, etc.
4.1 queue family in Java
Collection collection in Java has three families: list, set and queue. Of course, map is also a collection class, but map does not inherit the collection interface.
List and set are often used in our work and are usually used to store result data, while queue is usually used in producer consumer mode due to its particularity.
The popular message oriented middleware, such as rabbit MQ, is the expansion of the data structure queue.
Today's article will take you into the queue family.
4.1. 1 queue interface
Let's first look at the inheritance relationship of queue and the methods defined therein:
Queue inherits from collection, and collection inherits from Iterable.
Queue has three main methods. Let's use a table to see their differences:
4.1. 2. Classification of queues
Generally speaking, queues can be divided into BlockingQueue, deque and transferqueue.
BlockingQueue is an implementation of queue, which provides two additional functions:
BlockingQueue operations can be divided into the following four categories:
The first type is the operation that will throw an exception. When the insertion fails and the queue is empty, an exception is thrown.
The second type is operations that do not throw exceptions.
The third type is block operation. When the queue is empty or reaches the maximum capacity.
The fourth type is the operation of time out, which will block at a given time and return directly after timeout.
BlockingQueue is a thread safe queue that can be used in multithreading in producer consumer mode, as shown below:
class Producer implements Runnable {
private final BlockingQueue queue;
Producer(BlockingQueue q) { queue = q; }
public void run() {
try {
while (true) { queue.put(produce()); }
} catch (InterruptedException ex) { ... handle ...}
}
Object produce() { ... }
}
class Consumer implements Runnable {
private final BlockingQueue queue;
Consumer(BlockingQueue q) { queue = q; }
public void run() {
try {
while (true) { consume(queue.take()); }
} catch (InterruptedException ex) { ... handle ...}
}
void consume(Object x) { ... }
}
class Setup {
void main() {
BlockingQueue q = new SomeQueueImplementation();
Producer p = new Producer(q);
Consumer c1 = new Consumer(q);
Consumer c2 = new Consumer(q);
new Thread(p).start();
new Thread(c1).start();
new Thread(c2).start();
}
}
Finally, the operations before inserting elements into blockqueue in one thread happen before the operations deleted or obtained from blockqueue in another thread.
Deque is a subclass of queue, which represents double ended queue, that is, elements can be inserted and deleted from the head or tail of the queue.
Similarly, deque's method can also be represented in the following table. Deque's method can be divided into head operation and tail operation:
It is basically consistent with the method description of queue, so I won't talk about it here.
When deque processes elements in FIFO (first in first out), deque is equivalent to a queue.
When deque processes elements in LIFO (last in first out), deque is equivalent to a stack.
Transferqueue inherits from BlockingQueue. Why is it called transfer? Because the transferqueue provides a transfer method, the producer can call the transfer method to wait for the consumer to call the take or poll method to get data from the queue.
Non blocking and timeout versions of the trytransfer method are also provided for use.
Let's take a producer consumer problem implemented by transferqueue.
Define a producer first:
@Slf4j
@Data
@AllArgsConstructor
class Producer implements Runnable {
private TransferQueue<String> transferQueue;
private String name;
private Integer messageCount;
public static final AtomicInteger messageProduced = new AtomicInteger();
@Override
public void run() {
for (int i = 0; i < messageCount; i++) {
try {
boolean added = transferQueue.tryTransfer( "第"+i+"个",2000,TimeUnit.MILLISECONDS);
log.info("transfered {} 是否成功: {}","第"+i+"个",added);
if(added){
messageProduced.incrementAndGet();
}
} catch (InterruptedException e) {
log.error(e.getMessage(),e);
}
}
log.info("total transfered {}",messageProduced.get());
}
}
In the producer's run method, we call the trytransfer method, wait for 2 seconds, and return directly if it fails.
Define another consumer:
@Slf4j
@Data
@AllArgsConstructor
public class Consumer implements Runnable {
private TransferQueue<String> transferQueue;
private String name;
private int messageCount;
public static final AtomicInteger messageConsumed = new AtomicInteger();
@Override
public void run() {
for (int i = 0; i < messageCount; i++) {
try {
String element = transferQueue.take();
log.info("take {}",element );
messageConsumed.incrementAndGet();
Thread.sleep(500);
} catch (InterruptedException e) {
log.error(e.getMessage(),e);
}
}
log.info("total consumed {}",messageConsumed.get());
}
}
In the run method, transferQueue. is called. Take method to get the message.
Let's take a look at the situation of one producer and zero consumers:
@Test
public void testOneProduceZeroConsumer() throws InterruptedException {
TransferQueue<String> transferQueue = new LinkedTransferQueue<>();
ExecutorService exService = Executors.newFixedThreadPool(10);
Producer producer = new Producer(transferQueue,"ProducerOne",5);
exService.execute(producer);
exService.awaitTermination(50000,TimeUnit.MILLISECONDS);
exService.shutdown();
}
Output results:
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第0个 是否成功: false
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第1个 是否成功: false
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第2个 是否成功: false
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第3个 是否成功: false
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第4个 是否成功: false
[pool-1-thread-1] INFO com.flydean.Producer - total transfered 0
You can see that the message was not sent successfully because there were no consumers.
Let's look at the next situation with consumers:
@Test
public void testOneProduceOneConsumer() throws InterruptedException {
TransferQueue<String> transferQueue = new LinkedTransferQueue<>();
ExecutorService exService = Executors.newFixedThreadPool(10);
Producer producer = new Producer(transferQueue,2);
Consumer consumer = new Consumer(transferQueue,"ConsumerOne",2);
exService.execute(producer);
exService.execute(consumer);
exService.awaitTermination(50000,TimeUnit.MILLISECONDS);
exService.shutdown();
}
Output results:
[pool-1-thread-2] INFO com.flydean.Consumer - take 第0个
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第0个 是否成功: true
[pool-1-thread-2] INFO com.flydean.Consumer - take 第1个
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第1个 是否成功: true
[pool-1-thread-1] INFO com.flydean.Producer - total transfered 2
[pool-1-thread-2] INFO com.flydean.Consumer - total consumed 2
You can see that producers and consumers produce and consume one by one.
4.2 PriorityQueue and priorityblockingqueue
Generally speaking, queues are FIFO. Of course, we also introduced that deque can be used as a stack. Today, we introduce a PriorityQueue, which can sort objects in natural order or custom order in the queue.
4.2. 1 PriorityQueue
Let's first look at the PriorityQueue, which inherits from abstractqueue and is non thread safe.
The capacity of PriorityQueue is unbounded, that is, it has no capacity limit, so you can add elements indefinitely. If you add too many elements, an outofmemoryerror exception will be reported in the end.
Here we teach you a recognition skill. As long as the collection class has capability, most of its underlying implementations are arrays, because only arrays have capacity. Of course, there are exceptions, such as linkedblockingdeque.
As long as there is a comparator in the collection class, the collection must be an ordered collection.
Let's look at PriorityQueue:
private static final int DEFAULT_INITIAL_CAPACITY = 11;
private final Comparator<? super E> comparator;
If the initial capacity and comparator are defined, the underlying implementation of PriorityQueue is array, and it is an ordered collection.
By default, ordered collections are sorted according to natural ordering. If you pass in comparator, they will be sorted according to the method you specify. Let's see two examples of sorting:
@Slf4j
public class PriorityQueueUsage {
@Test
public void usePriorityQueue(){
PriorityQueue<Integer> integerQueue = new PriorityQueue<>();
integerQueue.add(1);
integerQueue.add(3);
integerQueue.add(2);
int first = integerQueue.poll();
int second = integerQueue.poll();
int third = integerQueue.poll();
log.info("{},{},{}",first,second,third);
}
@Test
public void usePriorityQueueWithComparator(){
PriorityQueue<Integer> integerQueue = new PriorityQueue<>((a,b)-> b-a);
integerQueue.add(1);
integerQueue.add(3);
integerQueue.add(2);
int first = integerQueue.poll();
int second = integerQueue.poll();
int third = integerQueue.poll();
log.info("{},third);
}
}
By default, it will be arranged in ascending order. In the second example, if we pass in a comparator in reverse order, it will be arranged in reverse order.
4.2. 2 PriorityBlockingQueue
Priorityblockingqueue is a BlockingQueue, so it is thread safe.
Let's consider the question: if the natural ordering or comparator order of two objects is the same, is the order of two objects still fixed?
In this case, the default order cannot be determined, but we can encapsulate the objects in this way, so that the objects can be sorted according to the creation order first in first out FIFO when the sorting order is the same:
public class FIFOEntry<E extends Comparable<? super E>>
implements Comparable<FIFOEntry<E>> {
static final AtomicLong seq = new AtomicLong(0);
final long seqNum;
final E entry;
public FIFOEntry(E entry) {
seqNum = seq.getAndIncrement();
this.entry = entry;
}
public E getEntry() { return entry; }
public int compareTo(FIFOEntry<E> other) {
int res = entry.compareTo(other.entry);
if (res == 0 && other.entry != this.entry)
res = (seqNum < other.seqNum ? -1 : 1);
return res;
}
}
In the above example, first compare the natural ordering of two entries. If they are consistent, then sort them according to seqnum.
4.3 synchronousqueue details
Synchronous queue is a kind of BlockingQueue, so synchronous queue is thread safe. The difference between synchronous queue and other blockingqueues is that the capacity of synchronous queue is 0. That is, the synchronousqueue does not store any elements.
That is, each insert operation of the synchronousqueue must wait for other linear remove operations. Each remove operation must also wait for the insert operation of other threads.
This feature reminds us of exchange. Unlike exchange, you can pass the same object in two threads using synchronous queue. One thread puts the object and the other thread takes the object.
4.3. 1 example
Let's take an example of passing objects in multithreading. Let's take the example of producer consumer. We create an object in the producer, and we take out the object in the consumer. Let's take a look at what to do with countdownlatch:
@Test
public void useCountdownLatch() throws InterruptedException {
ExecutorService executor = Executors.newFixedThreadPool(2);
AtomicReference<Object> atomicReference= new AtomicReference<>();
CountDownLatch countDownLatch = new CountDownLatch(1);
Runnable producer = () -> {
Object object=new Object();
atomicReference.set(object);
log.info("produced {}",object);
countDownLatch.countDown();
};
Runnable consumer = () -> {
try {
countDownLatch.await();
Object object = atomicReference.get();
log.info("consumed {}",object);
} catch (InterruptedException ex) {
log.error(ex.getMessage(),ex);
}
};
executor.submit(producer);
executor.submit(consumer);
executor.awaitTermination(50000,TimeUnit.MILLISECONDS);
executor.shutdown();
}
In the above example, we use atomicreference to store the objects to be passed, and define a countdownlatch with a model quantity of 1.
In producer, we store objects and count down.
In the consumer, we wait, and then take out the object.
Output results:
[pool-1-thread-1] INFO com.flydean.SynchronousQueueUsage - produced java.lang.Object@683d1b4b
[pool-1-thread-2] INFO com.flydean.SynchronousQueueUsage - consumed java.lang.Object@683d1b4b
You can see that the same object is passed in and output.
The above example can also be rewritten with synchronousqueue:
@Test
public void useSynchronousQueue() throws InterruptedException {
ExecutorService executor = Executors.newFixedThreadPool(2);
SynchronousQueue<Object> synchronousQueue=new SynchronousQueue<>();
Runnable producer = () -> {
Object object=new Object();
try {
synchronousQueue.put(object);
} catch (InterruptedException ex) {
log.error(ex.getMessage(),ex);
}
log.info("produced {}",object);
};
Runnable consumer = () -> {
try {
Object object = synchronousQueue.take();
log.info("consumed {}",TimeUnit.MILLISECONDS);
executor.shutdown();
}
In the above example, if we use synchronous queue, we can avoid manual synchronization and additional storage.
If we need to use this thread to pass objects in our code, use synchronous queue.
4.4 use of delayqueue
Today, I'd like to introduce delayqueue to you. Delayqueue is a kind of BlockingQueue, so it is thread safe. The characteristic of delayqueue is that the data inserted into the queue can be sorted according to the user-defined delay time. Only elements whose delay time is less than 0 can be fetched.
4.4. 1 DelayQueue
Let's take a look at the definition of delayqueue:
public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
implements BlockingQueue<E>
As can be seen from the definition, all objects stored in delayqueue must be subclasses of delayed.
Delayed inherits from comparable and needs to implement a getdelay method.
Why is it designed like this?
Because the underlying storage of delayqueue is a PriorityQueue, as we mentioned in the previous article, PriorityQueue is a sortable queue, and its elements must implement the comparable method. The getdelay method is used to determine whether the sorted elements can be taken out of the queue.
4.4. 2. Application of delayqueue
Delayqueue is generally used in producer consumer mode. Let's take a specific example below.
First, to use delayqueue, you must customize a delayed object:
@Data
public class DelayedUser implements Delayed {
private String name;
private long avaibleTime;
public DelayedUser(String name,long delayTime){
this.name=name;
//avaibleTime = 当前时间+ delayTime
this.avaibleTime=delayTime + System.currentTimeMillis();
}
@Override
public long getDelay(TimeUnit unit) {
//判断avaibleTime是否大于当前系统时间，并将结果转换成MILLISECONDS
long diffTime= avaibleTime- System.currentTimeMillis();
return unit.convert(diffTime,TimeUnit.MILLISECONDS);
}
@Override
public int compareTo(Delayed o) {
//compareTo用在DelayedUser的排序
return (int)(this.avaibleTime - ((DelayedUser) o).getAvaibleTime());
}
}
In the above object, we need to implement getdelay and CompareTo methods.
Next, we create a producer:
@Slf4j
@Data
@AllArgsConstructor
class DelayedQueueProducer implements Runnable {
private DelayQueue<DelayedUser> delayQueue;
private Integer messageCount;
private long delayedTime;
@Override
public void run() {
for (int i = 0; i < messageCount; i++) {
try {
DelayedUser delayedUser = new DelayedUser(
new Random().nextInt(1000)+"",delayedTime);
log.info("put delayedUser {}",delayedUser);
delayQueue.put(delayedUser);
Thread.sleep(500);
} catch (InterruptedException e) {
log.error(e.getMessage(),e);
}
}
}
}
In the producer, we create a new delayeduser object every 0.5 seconds and merge it into the queue.
Create another consumer:
@Slf4j
@Data
@AllArgsConstructor
public class DelayedQueueConsumer implements Runnable {
private DelayQueue<DelayedUser> delayQueue;
private int messageCount;
@Override
public void run() {
for (int i = 0; i < messageCount; i++) {
try {
DelayedUser element = delayQueue.take();
log.info("take {}",element );
} catch (InterruptedException e) {
log.error(e.getMessage(),e);
}
}
}
}
In the consumer, we loop to get objects from the queue.
Finally, let's take a call example:
@Test
public void useDelayedQueue() throws InterruptedException {
ExecutorService executor = Executors.newFixedThreadPool(2);
DelayQueue<DelayedUser> queue = new DelayQueue<>();
int messageCount = 2;
long delayTime = 500;
DelayedQueueConsumer consumer = new DelayedQueueConsumer(
queue,messageCount);
DelayedQueueProducer producer = new DelayedQueueProducer(
queue,messageCount,delayTime);
// when
executor.submit(producer);
executor.submit(consumer);
// then
executor.awaitTermination(5,TimeUnit.SECONDS);
executor.shutdown();
}
In the above test example, we defined a thread pool of two threads. The producer generates two messages. The delaytime is set to 0.5 seconds, that is, after 0.5 seconds, the inserted object can be obtained.
The thread pool will be closed after 5 seconds.
Run and see the following results:
[pool-1-thread-1] INFO com.flydean.DelayedQueueProducer - put delayedUser DelayedUser(name=917,avaibleTime=1587623188389)
[pool-1-thread-2] INFO com.flydean.DelayedQueueConsumer - take DelayedUser(name=917,avaibleTime=1587623188389)
[pool-1-thread-1] INFO com.flydean.DelayedQueueProducer - put delayedUser DelayedUser(name=487,avaibleTime=1587623188899)
[pool-1-thread-2] INFO com.flydean.DelayedQueueConsumer - take DelayedUser(name=487,avaibleTime=1587623188899)
We see that the put and take of the message are alternating, which is in line with our expectations.
If we modify the delaytime to 50000, the elements inserted before the process pool is closed will not expire, that is, the consumer cannot obtain the results.
Delayqueue is a BlockingQueue with strange features that can be used when needed.
5. Other key points
5.1 differences between comparable and comparator
java. Lang. comparable and Java util. Comparator is two easily confused interfaces. Both of them have the meaning of comparison. What are the differences between the two interfaces and under what circumstances?
5.1. 1 Comparable
Comparable is Java The interface under the Lang package can be regarded as the basic language interface of Java.
In fact, the comparable interface defines only one method:
public int compareTo(T o);
All classes implementing this interface need to implement the CompareTo method to represent the comparison between the two classes.
The order after comparison and sorting is called natural ordering according to Java. This order is used for some sortable sets, such as sortedset, SortedMap, etc.
When these sortable collections are used to add corresponding objects, the CompareTo method will be called to sort the natural ordering.
Almost all digital type objects: integer, long, double, etc. implement this comparable interface.
Comparator is a functional interface, which needs to implement the compare method:
int compare(T o1,T o2);
Comparator in Java Util package represents a tool class used to assist sorting.
When talking about comparable, we mentioned that comparable specifies the natural ordering of objects. If we want to sort according to our custom method when adding to the sortable collection class, we need to use the comparator at this time.
Collections. sort(List,Comparator),Arrays. Sort (object [], comparator) and other auxiliary method classes can define sorting rules by passing in a comparator.
In the sorting process, first check whether the comparator exists. If it does not exist, the default natural ordering will be used.
Another difference is that comparator allows the comparison of null parameters, while comparable does not, otherwise it will crawl out of NullPointerException.
5.1. 3 for example
Finally, we give an example of natural ordering and comparator:
@Test
public void useCompare(){
List<Integer> list1 = Arrays.asList(5,3,2,4,1);
Collections.sort(list1);
log.info("{}",list1);
List<Integer> list2 = Arrays.asList(5,1);
Collections.sort(list2,(a,b) -> b - a);
log.info("{}",list2);
}
Output results:
[main] INFO com.flydean.CompareUsage - [1,5]
[main] INFO com.flydean.CompareUsage - [5,1]
By default, integers are arranged in ascending order, but we can change this process by passing in a comparator.
5.2 reference and reference type
There are value types and reference types in Java. Reference types are generally for objects in Java. Today, let's introduce reference types in Java. Java specifically defines a class for reference types called reference. Reference is a class closely related to Java garbage collection mechanism. By discussing the implementation of reference, we can have a deeper understanding of how Java garbage collection works.
This article starts with the four reference types in Java and unveils reference step by step.
The four reference types in Java are: strong reference, soft reference, weak reference and virtual reference.
5.2. 1 strong reference
A reference in Java is a strong reference by default. The assignment operation of any object generates a strong reference to this object.
Let's take an example:
public class StrongReferenceUsage {
@Test
public void stringReference(){
Object obj = new Object();
}
}
Above, we create an object object and assign it to obj, which is a strong reference to new object().
The characteristic of strong reference is that as long as there is a strong reference, the referenced object will not be garbage collected.
5.2. 2 soft reference
Soft reference has a special softreference type in Java. Soft reference means that the referenced object will be recycled only when there is insufficient memory.
Let's first look at the definition of softreference:
public class SoftReference<T> extends Reference<T>
Softreference inherits from reference. It has two constructors:
public SoftReference(T referent)
And:
public SoftReference(T referent,ReferenceQueue<? super T> q)
The first parameter is a soft reference object. The second parameter is called ReferenceQueue, which is used to store encapsulated reference objects to be recycled. The objects in ReferenceQueue are processed by the referencehandler internal class in the reference class.
Let's take an example of softreference:
@Test
public void softReference(){
Object obj = new Object();
SoftReference<Object> soft = new SoftReference<>(obj);
obj = null;
log.info("{}",soft.get());
System.gc();
log.info("{}",soft.get());
}
Output results:
22:50:43.733 [main] INFO com.flydean.softReferenceUsage - java.lang.Object@71bc1ae4
22:50:43.749 [main] INFO com.flydean.softReferenceUsage - java.lang.Object@71bc1ae4
You can see that when the memory is sufficient, the objects referenced by softreference will not be recycled.
5.2. 3 weak reference
WeakReference is very similar to softreference, except that the objects referenced by weekreference will be recycled as long as garbage collection is executed, regardless of whether there is insufficient memory.
Similarly, the WeakReference has two constructors:
public WeakReference(T referent)；
public WeakReference(T referent,ReferenceQueue<? super T> q)；
The meaning is the same as that of softreference, so it will not be repeated here.
Let's look at an example of weak reference:
@Test
public void weakReference() throws InterruptedException {
Object obj = new Object();
WeakReference<Object> weak = new WeakReference<>(obj);
obj = null;
log.info("{}",weak.get());
System.gc();
log.info("{}",weak.get());
}
Output results:
22:58:02.019 [main] INFO com.flydean.WeakReferenceUsage - java.lang.Object@71bc1ae4
22:58:02.047 [main] INFO com.flydean.WeakReferenceUsage - null
We see that after GC, weakly referenced objects are recycled.
5.2. 4 phantom reference
The function of phantom reference is to track the activity of garbage collector collecting objects. During GC, if phantom reference is found, GC will put the reference into ReferenceQueue and the programmer will handle it. When the programmer calls ReferenceQueue Pull () method. After removing the referenced ReferenceQueue, the reference object will become inactive, which means that the referenced object can be recycled.
Unlike softreference and WeakReference, phantom reference has only one constructor and must be passed into ReferenceQueue:
public PhantomReference(T referent,ReferenceQueue<? super T> q)
Take an example of phantom reference:
@Slf4j
public class PhantomReferenceUsage {
@Test
public void usePhantomReference(){
ReferenceQueue<Object> rq = new ReferenceQueue<>();
Object obj = new Object();
PhantomReference<Object> phantomReference = new PhantomReference<>(obj,rq);
obj = null;
log.info("{}",phantomReference.get());
System.gc();
Reference<Object> r = (Reference<Object>)rq.poll();
log.info("{}",r);
}
}
Operation results:
07:06:46.336 [main] INFO com.flydean.PhantomReferenceUsage - null
07:06:46.353 [main] INFO com.flydean.PhantomReferenceUsage - java.lang.ref.PhantomReference@136432db
We see that the value of get is null, while after GC, poll has value.
Because phantomreference refers to objects that need to be garbage collected, in the class definition, get always returns null:
public T get() {
return null;
}
5.2. 5 reference and ReferenceQueue
After talking about the above four references, let's talk about the functions of their parent classes reference and ReferenceQueue.
Reference is an abstract class. Each reference has an object to which it points. There are five very important properties in reference: reference, next, discovered, pending and queue.
private T referent; /* Treated specially by GC */
volatile ReferenceQueue<? super T> queue;
Reference next;
transient private Reference<T> discovered; /* used by VM */
private static Reference<Object> pending = null;
Each reference can be regarded as a node, and multiple references are associated through the next, discovered and pending attributes.
First, use a diagram to have an overall concept of reference:
Referent is the object actually referenced by reference.
The ReferenceQueue can be built through the next attribute.
The discovered list can be built through the discovered attribute.
With the pending attribute, you can build a pending list.
Before talking about the three queue / lists, let's talk about the four states of reference:
From the above figure, we can see that a reference can have four states.
Because reference has two constructors, one with ReferenceQueue and the other without.
Reference(T referent) {
this(referent,null);
}
Reference(T referent,ReferenceQueue<? super T> queue) {
this.referent = referent;
this.queue = (queue == null) ? ReferenceQueue.NULL : queue;
}
For the reference with ReferenceQueue, GC will put the reference of the object to be recycled into ReferenceQueue, and the subsequent reference needs to be handled by the programmer (call the poll method).
References without ReferenceQueue are handled by GC itself, and the reference status of objects to be recycled will become inactive.
Once the reference is created, it enters the active state.
In the active state, if the reachable state of the reference object is sent, the change will change to the inactive or pending state.
The inactive state is well understood. The reference state that reaches the inactive state cannot be changed and will wait for GC recovery.
The pending status represents waiting to enter the queue. There is a referencehandler inside the reference, which will call the enqueue method to enter the pending object into the queue.
The status of the object that is queued becomes enqueued.
For objects in enqueued status, if the poll method is called to take them out of ReferenceQueue, the status of the reference will become inactive and wait for GC recycling.
This is a complete life cycle of reference.
With the concepts of the above four states, let's talk about three queues / lists: ReferenceQueue, discovered list and pending list.
ReferenceQueue has been mentioned when talking about status. It is essentially connected by next in reference. Used to store GC objects to be recycled.
The pending list is the list to be entered into the ReferenceQueue.
The discovered list is a little special. In the pending state, the discovered list is equal to the pending list.
In the active state, the discovered list actually maintains a reference chain. Through this reference chain, we can obtain the chain structure of references. When a reference state is no longer active, we need to delete the reference from the discovered list.
5.2. 6 WeakHashMap
Finally, let's talk about weakhashmap. Weakhashmap is a little similar to WeakReference. If the key is no longer used and is assigned null, the entry corresponding to the key will be automatically deleted from the weakhashmap.
Let's take an example:
@Test
public void useWeakHashMap(){
WeakHashMap<Object,Object> map = new WeakHashMap<>();
Object key1= new Object();
Object value1= new Object();
Object key2= new Object();
Object value2= new Object();
map.put(key1,value1);
map.put(key2,value2);
log.info("{}",map);
key1 = null;
System.gc();
log.info("{}",map);
}
Output results:
[main] INFO com.flydean.WeakHashMapUsage - {java.lang.Object@14899482=java.lang.Object@2437c6dc,java.lang.Object@11028347=java.lang.Object@1f89ab83}
[main] INFO com.flydean.WeakHashMapUsage - {java.lang.Object@14899482=java.lang.Object@2437c6dc}
You can see that after GC, there is only one entry in weakhashmap.
5.3 type erasure
Generics is a new feature introduced by Java from JDK 5. The introduction of generics allows us to forcibly check the incoming types during code compilation, thus improving the robustness of the program.
Generics can be used on classes and interfaces, and are very common in collection classes. This article will explain the type erasure caused by generics.
5.3. 1 for example
Let's start with the simplest example:
@Slf4j
public class TypeErase {
public static void main(String[] args) {
ArrayList<String> stringArrayList = new ArrayList<String>();
stringArrayList.add("a");
stringArrayList.add("b");
action(stringArrayList);
}
public static void action(ArrayList<Object> al){
for(Object o: al)
log.info("{}",o);
}
}
In the above example, we defined an ArrayList, where the specified type is string.
Then the action method is called, and the action method needs to import a ArrayList, but the type of this list is Object.
At first glance, there seems to be no problem, because string is a subclass of object and can be converted.
But in fact, the code compilation error:
Error:(18,16) java: 不兼容的类型: java.util.ArrayList<java.lang.String>无法转换为java.util.ArrayList<java.lang.Object>
5.3. 2 reasons
The reason for the above example is type erasure. Generics in Java are detected at compile time. The binary file generated after compilation does not save type related information.
In the above example, after compilation, either ArrayList < string > or ArrayList < Object > will become ArrayList. The type object / string is invisible to the JVM.
However, during the compilation process, the compiler finds that the two types are different, and then throws an error.
5.3. 3 solution
To solve the above problems, we can use the following methods:
public static void actionTwo(ArrayList<?> al){
for(Object o: al)
log.info("{}",o);
}
By using wildcards?, You can match any type to compile.
But note that in the actiontwo method here, because we don't know what the type passed in is, we can't add any elements to actiontwo.
5.3. 4 Summary
From the above example, we can see that ArrayList < string > is not a subclass of ArrayList < Object >. If the parent-child relationship must be found, ArrayList < string > is a subclass of collection < string >.
However, object [] objarray is the parent class of string [] strarr. Because the specific type of array is known.
5.4 deep understanding of Java generics
Generics is a concept introduced by JDK 5. Generics are mainly introduced to ensure the security of types in Java, which is a bit like templates in C + +.
However, in order to ensure downward compatibility, all Java generics are implemented during compilation. The compiler performs type checking and type inference, and then generates ordinary non generic bytecode. This type is called erasure. The compiler performs type checking during compilation to ensure type safety, but erases it before subsequent bytecode generation.
This can lead to confusing results. This article will explain the use of generics in Java in detail to avoid misunderstandings.
5.4. 1 generics and covariance
For detailed description of covariance and inversion, please refer to:
Deep understanding of covariance and inversion
Here, I'll summarize that covariance and inversion are meaningful only in the type parameters in the type declaration, and have no significance for parameterized methods, because the tag affects the subclass inheritance behavior, and the method has no subclasses.
Of course, what is not shown in Java indicates whether the parameter type is covariant or inverse.
Covariance means that if there are two classes a < T > and a < C >, where C is a subclass of T, we can replace a with a.
Inversion is the opposite relationship.
Arrays in Java are covariant. For example, if integer is a subclass of number, then integer [] is also a subclass of number []. We can pass in integer [] when we need number [].
Next, let's consider the case of generics. Is list < number > the parent of list < integer >? Unfortunately, not.
We conclude that generics are not covariant.
Why? Let's take an example:
List<Integer> integerList = new ArrayList<>();
List<Number> numberList = integerList; // compile error
numberList.add(new Float(1.111));
If integerlist can be assigned to numberlist, numberlist can add any number type, such as float, which violates the original intention of generics and adds float to integer list. Therefore, the above operation is not allowed.
We just mentioned that array is covariant. If you bring generics into array, a compilation error will occur. For example, new list < string > [10] is illegal, but new list [10] Yes. Because in generics? Represents an unknown type.
List<?>[] list1 = new List<?>[10];
List<String>[] list2 = new List<String>[10]; //compile error
5.4. 2 problems encountered in the use of generics
Because of type erasure, both list < string > and list < integer > will be treated as lists during operation. So we will encounter some problems when using generics.
If we have a generic class, there is a method in the class, and the parameters of the method are generic, we want to copy the generic parameters in this method.
public class CustUser<T> {
public void useT(T param){
T copy = new T(param); // compile error
}
}
The above operation will fail to compile because we don't know what t is or whether T has a corresponding constructor.
There is no way to directly clone T. If we want to copy a set, what should we do if the type in the set is undefined?
public void useTSet(Set<?> set){
Set<?> copy1 = new HashSet<?>(set); // compile error
Set<?> copy2 = new HashSet<>(set);
Set<?> copy3 = new HashSet<Object>(set);
}
Can you see? It cannot be directly used for instantiation. But we can replace it in the following two ways.
Let's look at the use of array:
public void useArray(){
T[] typeArray1= new T[20]; //compile error
T[] typeArray2=(T[]) new Object[20];
T[] typeArray3 = (T[]) Array.newInstance(String.class,20);
}
Similarly, t cannot be directly used for instantiation, but we can replace it in the following two ways.
5.4. 3 precautions for type erasure
Because of type erasure, it is meaningless to implement two different types of the same interface in our interface implementation:
public class someClass implements Comparable<Number>,Comparable<String> { ... } // no
Because in the compiled bytecode, the two comparable are the same.
Similarly, it is meaningless for us to use t for type casting:
public <T> T cast(T t,Object o) { return (T) o; }
Because the compiler doesn't know whether the cast is right or wrong.