Java source code analysis: source code analysis of guava’s immutable set immutable map
1、 Case scenario
I have encountered such a scenario. When defining a static modified map, a large number of put () methods are used to assign values, just like this——
public static final Map<String,String> dayMap= new HashMap<>();
static {
dayMap.put("Monday","今天上英语课");
dayMap.put("Tuesday","今天上语文课");
dayMap.put("Wednesday","今天上数学课");
dayMap.put("Thursday","今天上音乐课");
dayMap.put("Sunday","今天上编程课");
......
}
At that time, I was wondering whether I could further optimize to make the code look more elegant. Then, I found that there is a class immutable map in Google guava, which can realize chain programming similar to the builder mode. The optimized results are as follows:
public static final Map<String,String> dayMap = ImmutableMap.<String,String>builder()
.put("Monday","今天上英语课")
.put("Tuesday","今天上语文课")
.put("Wednesday","今天上数学课")
.put("Thursday","今天上音乐课")
.put("Sunday","今天上编程课")
.build();
2、 Immutable map source code analysis
In the official Google guava tutorial, immutable prefixes are defined as immutable sets, including immutable set, immutable map, etc. What is immutable set? That is, after the collection is created, all States in the collection can no longer be modified in the life cycle and can only be read.
Then, what is modifiable? For example, map and list in JDK can be added or modified repeatedly through put () or add () after creation. This is a modifiable set. Since the set cannot be modified, can it be modified? No, in fact, it can be modified through reflection, but this is not the original intention of immutable sets.
To summarize, immutable collections are thread safe and can be used as constants.
Next, go inside immutablemap. You can see that it implements the map interface, which is a little similar to HashMap in that the map interface is their base class, and can realize the parent class reference to the child class object, that is, upward transformation.
public abstract class ImmutableMap<K,V> implements Map<K,V>,Serializable {}
This is an abstract class. To implement this, call immutablemap< String, string > builder(), on the surface, you can guess that < string, string > builder() must be a static method defined by static. When you enter the source code, you find that it is indeed so——
/**
* Returns a new builder. The generated builder is equivalent to the builder
* created by the {@link Builder} constructor.
*/
public static <K,V> Builder<K,V> builder() {
return new Builder<K,V>();
}
The definition of this method may be strange to some junior programmers. In fact, the essence of this method format is like this——
public <T> T method(T t)
This is a generic convention specification. It is the first to define a generic type, indicating that the current method has a generic variable type, represented by T; The second t indicates that the return type of method is t.
Looking back at the builder () method, it is easy to understand that < K, V > defines a generic type, representing the generic variable of the current method, and builder < K, V > returns an object whose generic variable is < K, V >.
Immutablemap is defined earlier< String, string > Builder (), in this builder () method, an object of new builder < string, string > () will be returned. This object initializes an immutablecollection with the size of immutablecollection through the constructor Builder. DEFAULT_ INITIAL_ The array entries of capability, and this default_ INITIAL_ The default value of capability is 4.
public static class Builder<K,V> {
Comparator<? super V> valueComparator;
ImmutableMapEntry<K,V>[] entries;
int size;
boolean entriesUsed;
public Builder() {
this(ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY);
}
Builder(int initialCapacity) {
this.entries = new ImmutableMapEntry[initialCapacity];
this.size = 0;
this.entriesUsed = false;
}
......
}
So the question is, what type of array is this immutable mapentry < K, V > []?
This immutablemapentry < K, V > class inherits an immutableentry < K, V > class——
class ImmutableMapEntry<K,V> extends ImmutableEntry<K,V> {
static <K,V> ImmutableMapEntry<K,V>[] createEntryArray(int size) {
return new ImmutableMapEntry[size];
}
ImmutableMapEntry(K key,V value) {
super(key,value);
checkEntryNotNull(key,value);
}
}
Note that checkentrynotnull (key, value) performs a check, which means that the stored key and value values cannot be empty.
static void checkEntryNotNull(Object key,Object value) {
if (key == null) {
throw new NullPointerException("null key in entry: null=" + value);
} else if (value == null) {
throw new NullPointerException("null value in entry: " + key + "=null");
}
}
In the parent immutableentry < K, V > class, two generic variables, key and value, are defined. It can be seen that when Builder () is called externally When put (key, value) is used to store key value data, it actually stores the key value data in the key and value of immutableentry object.
class ImmutableEntry<K,V> extends AbstractMapEntry<K,V> implements Serializable {
final K key;
final V value;
......
}
When we mention immutableentry < K, V > arrays to store key value data, we have to mention HashMap.
At jdk1 Among them, HashMap is composed of array + linked list + red black tree. Its internal array is defined by node < K, V > [], and this node < K, V > implements map Entry
——
Immutablemapentry < K, V > the top also implements entry < K, V >——
It can be seen that immutablemap, like HashMap, directly or indirectly implements the entry < K, V > interface for the class to which the object storing the key value belongs.
After analysis, it is easy to understand that immutable mapentries < K, V > [] entries are similar to HashMap arrays and are used to store key value data.
Next, we will analyze the logic of put.
The builder class analyzed above actually belongs to the internal static class in the abstract class immutablemap < K, V >, which means that immutablemap is executed< String,String>builder(). The essence of put ("Monday", "English class today") is actually equivalent to executing immutable map new Builder
(). Put ("Monday", "English class today").
The source code of the put method is as follows:
public Builder<K,V> put(K key,V value) {
ensureCapacity(size + 1);
ImmutableMapEntry<K,V> entry = entryOf(key,value);
// don't inline this: we want to fail atomically if key or value is null
entries[size++] = entry;
return this;
}
1、 First look at the method called in the first line of code. Its function is to judge whether there is a possibility of overflow when adding a key value object to the array. If overflow occurs, expand the capacity of the array first.
private void ensureCapacity(int minCapacity) {
if (minCapacity > entries.length) {
entries =
Arrays.copyOf(
entries,ImmutableCollection.Builder.expandedCapacity(entries.length,minCapacity));
entriesUsed = false;
}
}
2、 The second line immutable mapentry < K, value) is to create a new immutable mapentry object and initialize the key and value assigned to the object through the constructor——
static <K,V> entryOf(K key,V value) {
return new ImmutableMapEntry<K,V>(key,value);
}
3、 The third line of code entries [size + +] = entry stores the newly added immutablemapentry object in the free position of the array. In this way, the key value cached through put (key, value) is stored in the array in the form of an object.
4、 The last line returns this, which is the reason why immutablemap can realize chain programming.
Finally, execution The build () method——
ImmutableMap.<String,"今天上英语课")
......
.build();
The build () source code is very complex. It is directly and simply optimized here. The general meaning is to wrap the entries array into a sub object implementing the map interface for return.
public ImmutableMap<K,V> build() {
switch (size) {
case 0:
return of();
case 1:
return new SingletonImmutableBiMap<K,V>(k1,v1);
default:
return new RegularImmutableMap<K,V>(entries,table,mask);
}
}
When the array length exceeds 1, it can return singletonimmutablebimap or regularimmutablemap. Both of them indirectly implement the map interface. Compare their class definitions——
final class SingletonImmutableBiMap<K,V> extends ImmutableBiMap<K,V> {
final transient K singleKey;
final transient V singleValue;
......
}
final class RegularImmutableMap<K,V> extends ImmutableMap<K,V> {
// entries in insertion order
private final transient Entry<K,V>[] entries;
// array of linked lists of entries
private final transient ImmutableMapEntry<K,V>[] table;
// 'and' with an int to get a table index
private final transient int mask;
......
}
It is found that both have a common feature. The class and the attributes in the class are defined by the final modifier, which means that once the build () method is called to create initialization, it can no longer be changed.
This is the real reason why the immutable map collection is immutable.
Finally, another question is, what happens when you try to insert data through put after creating a map object through immutable map?
At this time, when calling through the put method, for example, take the daymap defined above as an example, in a method, try to pass the daymap When put ("Monday", "English class today") is used to modify or add map data, the put called here is no longer the put method in the internal class builder < K, V > (), but the put method of immutablemap itself. The source code of this method is as follows——
/**
* Guaranteed to throw an exception and leave the map unmodified.
*
* @throws UnsupportedOperationException always
* @deprecated Unsupported operation.
*/
@CanIgnoreReturnValue
@Deprecated
@Override
public final V put(K k,V v) {
throw new UnsupportedOperationException();
}
The comment indicates that the map is unmodified, that is, it can no longer be modified. If you still call put for execution, you will only mention an exception unsupportedoperationexception.