Java collection source code analysis (V): map and abstractmap
summary
Map interface is one of the two collection interfaces in Java. Compared with collection, the map interface structure specifies the collection container in the form of all key value pairs. At the same time, it is closely related to the sub interface set of collection. Some implementations of map depend on set set, and some implementations of set also depend on map.
There are four main implementation classes under the map interface: treemap, HashMap, linkedmap and hashtable. Based on the above four implementation classes, this is their class diagram:
Related to it is the dictionary class, which is an outdated early key value pair collection interface. Later new collections are implemented based on the map interface, which only depends on its hashtable, and it is rarely used for performance reasons. Therefore, this class is an outdated class.
1、 Map interface
Map interface is the uppermost interface of all key value pair type collection interfaces. It specifies an abstract method that all map type collections should implement, and provides a default interface class entry for view operation.
1. Abstract method
Query operation
Change operation
View operation
Map is a very special set. It represents the mapping relationship of a series of key value pairs. Therefore, it cannot be directly regarded as a collection of elements like the collection set. To this end, map defines the implementation class, which must be able to return specific three views through the following three methods to facilitate operation:
The element returned by entryset is actually the implementation class of the internal interface entry of map. An entry object represents a pair of keys and values.
2. Default method
The default method of the interface is one of the new features of jdk8, so such methods are all new methods of jdk8.
The characteristic of this kind of method is that the parameters are mostly functional structures, and most of them will not be rewritten by the implementation class. We can call it through a lambda expression.
3. Equals and hashcode
In the map, since most comparisons are based on the equals () and hashcode () methods, the map collection requires class rewriting to implement these two methods, including:
Equals() requires M1 entrySet(). Compare the sum of two map sets in the form of equals (m2. Entryset());
The hashcode () is similar to the equals () of the collection. It requires that the hashcode of the map set should be the sum of the hashcodes of all entryset () in the set.
2、 Entry interface
Entry is an internal interface class of map. Unlike the general interface, the implementation class of entry is actually used as a key value pair object in the map, that is, a pair of key and value are used as an entry object. Entry is actually a constraint on the key value pair object used in the map implementation class. According to Javadoc:
He provides nine basic methods:
We can also regard entry as a view in the map collection, but it is only limited to a pair of key value pairs.
3、 Abstractmap abstract class
Abstractmap, like abstractlist, is an abstract class that provides basic implementation for interfaces. According to Javadoc, we can simply understand it:
1. Member variables
Abstractmap has two member variables keyset and values:
// key的集合视图
transient Set<K> keySet;
// values的集合视图
transient Collection<V> values;
It is worth mentioning that the annotation of the abstract method keyset () with the same name for obtaining keyset indicates:
It can be seen that keyset obtaining instances is a typical singleton mode.
2. Internal class
Previously, we said that the internal class interface entry provided by the map interface is to provide constraints on the object for the key value of the implementation class. In abstractmap, two internal classes simpleentry and simpleimmutableentry that implement the entry interface are provided.
SimpleEntry
Simpleentry is an implementation of the internal interface class entry based on the map interface. It can be seen as a mapping of a pair of key values to objects in a collection -- or a view.
During initialization, you need to pass in key and value to assign values to member variables with the same name, and the key will be modified by final, so the key cannot be changed, but the value can be changed.
Based on the above principles, when value is a reference type and you modify it, the modification will be truly reflected in the value corresponding to the values of the external class. However, if you want to replace it, you can only replace the value in the current simpleentry object.
public static class SimpleEntry<K,V> implements Entry<K,V>,java.io.Serializable{
private static final long serialVersionUID = -8499721149061103585L;
// key不可变
private final K key;
private V value;
public SimpleEntry(K key,V value) {
this.key = key;
this.value = value;
}
public SimpleEntry(Entry<? extends K,? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
// 更新值
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
// 重写equals方法，要求key与value都需要相等
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return eq(key,e.getKey()) && eq(value,e.getValue());
}
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
public String toString() {
return key + "=" + value;
}
}
SimpleImmutableEntry
Simpleimmutableentry is no different from simpleentry, except that it has the same feature as its name: "immutable".
Compared with simpleentry, the value of simpleimmutableentry is also modified by final, and calling its setValue () method will throw an unsupported operationexception.
public static class SimpleImmutableEntry<K,java.io.Serializable {
private final K key;
private final V value;
public V setValue(V value) {
throw new UnsupportedOperationException();
}
}
5、 View of abstractmap
1. Four views
We know that since map is a collection of key value pairs, it actually stores key and value, as well as their mapping relationship. A single operation is easy to operate. Either find value according to the key or directly find key or value. However, when iterating, we need to distinguish between iterating over all keys, iterating over all values, or iterating over all keys + values at the same time. Therefore, there are three views of map:
Entryset is hard to understand. It contains entries. An entry represents a pair of key value pairs. Therefore, entry can also be understood as a view, which is limited to a pair of key value pairs.
The entryset contains all the entry views in the set, so it can also be understood as a view representing all the key values in the whole map container. Or it can be simply understood as entryset = keyset + values.
Since entry represents the set of key value pairs, you can also represent the map set as "set set of entry objects" - that is, entryset. Therefore, in the implementation class of map, entry is a very special class, which is used as a parameter in many methods.
2. Implementation of view class
Although the view class is defined, the map interface does not provide the implementation of keyset, values, entry and entryset. However, the methods keyset (), values () and enrtyset () for obtaining the three views are defined.
On the basis of the above, abstractmap provides keyset and values as member variables, and the entryset variable needs to be provided by the implementation class itself.
Therefore, if an implementation class wants to implement the map interface, abstractmap, it theoretically needs to provide seven implementation classes about Views:
In abstractmap, the implementation of entry and entryset is not provided, and the entryset () method remains abstract.
However, the keyset and values views are implemented in the form of anonymous inner classes, and both iterators use the entryset returned by the entryset () method to implement the iterators provided by the class.
In other words, if a class wants to implement the map interface, it only needs to provide three more implementation classes by inheriting abstractmap:
3.keySet()
The keyset () method is used to obtain the keyset of the set where the key is stored inside the set. It directly returns an anonymous inner class that inherits and implements the abstractset abstract method iterator (), and directly uses the iterator of the entryset.
public Set<K> keySet() {
// 获取 keySet
Set<K> ks = keySet;
// 如果keySet为null，就创建一个自定义的 AbstractSet
if (ks == null) {
ks = new AbstractSet<K>() {
// 实现了AbstractSet中的iterator()方法
public Iterator<K> iterator() {
// 返回一个自定义的迭代器类
return new Iterator<K>() {
// 获取entrySet返回的Set集合的迭代器，以下方法全部基于改迭代器实现
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public K next() {
return i.next().getKey();
}
public void remove() {
i.remove();
}
};
}
// 以下方法全部都调用AbstractMap的实现
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
keySet = ks;
}
return ks;
}
That is, the keyset used in abstractmap is equivalent to a singleton abstractset internal implementation class, and the iterator of this class is the iterator of the set set returned by the entryset () method; Other methods directly use the external class abstractmap:
The values () method of abstractmap is similar to keyset (). It returns an anonymous inner class that inherits the abstractcollection abstract class:
public Collection<V> values() {
Collection<V> vals = values;
if (vals == null) {
vals = new AbstractCollection<V>() {
// 使用entrySet().iterator()获取的迭代器
public Iterator<V> iterator() {
return new Iterator<V>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public V next() {
return i.next().getValue();
}
public void remove() {
i.remove();
}
};
}
// 直接使用AbstractMap提供的方法
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object v) {
return AbstractMap.this.containsValue(v);
}
};
values = vals;
}
return vals;
}
5、 Abstractmap method
1. Unsupported implementation
As stated in the class comment, abstractmap does not support put()
public V put(K key,V value) {
throw new UnsupportedOperationException();
}
Therefore, some logic has been implemented, but putall() cannot be used until the put() method is implemented:
public void putAll(Map<? extends K,? extends V> m) {
for (Map.Entry<? extends K,? extends V> e : m.entrySet())
put(e.getKey(),e.getValue());
}
2. Implementation method
Query operation
public int size() {
return entrySet().size();
}
public boolean isEmpty() {
return size() == 0;
}
Change operation
// get
public V get(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
// 指定要获取的key是否为null
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
// 返回对应的value
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
return null;
}
// remove
public V remove(Object key) {
// 获取entrySet的迭代器
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
// 指定要删除的key是否为null
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
// 找出key为null的那对键值对
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
// 找出指定键值对
if (key.equals(e.getKey()))
correctEntry = e;
}
}
V oldValue = null;
if (correctEntry !=null) {
// 根据key获取value
oldValue = correctEntry.getValue();
// 删除该键值对
i.remove();
}
return oldValue;
}
// clear
public void clear() {
entrySet().clear();
}
3.equals / hashCode
Collection containers basically override the equals () and hashcode () methods, and so does abstractmap.
equals
public boolean equals(Object o) {
// 是否同一个对象
if (o == this)
return true;
// 是否实现Map接口
if (!(o instanceof Map))
return false;
Map<?,?> m = (Map<?,?>) o;
// 是否长度相同
if (m.size() != size())
return false;
try {
// 遍历自己的键值对
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext()) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
// value是否为null
if (value == null) {
// 是否在比较的集合中key存在，并且对应的value是null
if (!(m.get(key)==null && m.containsKey(key)))
return false;
} else {
// 若value不为null，比较是否value一致
if (!value.equals(m.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
return true;
}
hashCode
The hashcode of abstractmap is the sum of the hashcodes of all entryset objects in the collection.
public int hashCode() {
int h = 0;
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext())
h += i.next().hashCode();
return h;
}
4.toSring
public String toString() {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (! i.hasNext())
return "{}";
StringBuilder sb = new StringBuilder();
sb.append('{');
for (;;) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
sb.append(key == this ? "(this Map)" : key);
sb.append('=');
sb.append(value == this ? "(this Map)" : value);
if (! i.hasNext())
return sb.append('}').toString();
sb.append(',').append(' ');
}
}
5.clone
protected Object clone() throws CloneNotSupportedException {
AbstractMap<?,?> result = (AbstractMap<?,?>)super.clone();
result.keySet = null;
result.values = null;
return result;
}
6、 Summary
Map interface
The map interface specifies the collection container of all key value pair types. Under it, there are four main implementation classes: hashtable, HashMap, treemap, and linkedmap, a subclass of HashMap.
Similar to him is the dictionary interface, which is implemented by hashtable. This is an outdated key value pair container interface.
The abstractmap abstract class provides most of the implementation of the map interface. In addition to handling hashtable, the other three main implementation classes inherit it.
In the map interface, the interface entry of key value pair view is provided, and it is specified that the implementation class needs to implement three abstract methods: entryset(), keyset(), values() to return the set set view of entry, the set set view of key and the collection view of value.
AbstractMap
In abstractmap, the keyset() values() method is implemented, and the corresponding member variables keyset and values are provided. However, the implementation class of entryset is not provided, and the entryset () method is not implemented.
The keyset () method used to obtain the key will return an anonymous implementation class of abstractset. The iterator obtains the iterator of the entryset class implemented by the implementation class through entryset (), while other methods directly use the of abstractmap. The same is true for the values () method used to get value, except that it returns an anonymous implementation class of abstractcollection.
For the entry interface, abstractmap provides simpleentry and simpleimmutableentry. Compared with the former, the value of the latter is modified by final, and calling setvalue() method will throw unsupportedoperationexception exception, so it is immutable.