Map
在数组是通过数组下角标来对内容进行索引的，而在Map中是通过对象来对对象进行索引，用来索引的对象叫Key，对应的对象叫Value，就是平时说的键值对。
Map接口是用来取代过时的Dictionary抽象类的，这个接口提供了一种映射关系，即元素是以键值对（K-V）的形式存储的，能够实现根据key快速查找到Value，并且还定义了map的基本行为方法，包括最核心的get和put操作。
Map常用实现，AbstractMap、HashMap、LinkedHashMap、Hashtable、Properties、TreeMap，为重Hashtable是已过时了的。
其中是map的key是不重复可为null的，每个key只能映射一个value。map中的元素顺序取决于Iterator的具体实现，即迭代器的顺序，如TreeMap是有序的，HashMap是无序的。
注：当使用一个可变对象作为key时，map是根据hashCode和equals方法来决定存放的位置，但是有一个特殊的案例是不允许一个map将自己作为一个key，但允许将自己作为一个value。
Map的键值对是以Entry类型的对象实例形式存在的，这个接口是Map接口内的一个内部接口，存储Map中的数据需要实现此接口。
在JDK1.8时，新增了数个比较器的静态方法。
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
n equals(Object o);
int hashCode();
/**
* @since JDK 1.8
*/
publicstatic <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
/**
* @since JDK 1.8
*/
publicstatic <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
/**
* @since JDK 1.8
*/
publicstatic <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
/**
* @since JDK 1.8
*/
publicstatic <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}
|
AbstractMap
publicabstractclass AbstractMap<K,V> implements Map<K,V> |
AbstractMap和AbstractList抽象类是类似的，还实现了Map接口，并提供了一些基础实现，如get()、remove()、clear()、put()、putAll()、isEmpty()等，其中put()和putAll()子类必须重写，这里仅仅是抛出异常。
在使用中，是要实现不可修改的map的话，可以扩展这个类，并为entrySet方法提供一个实现，该方法返回映射的集合视图。通常，返回的集合将依次在AbstractSet之上实现，这个集合不应该支持add或remove方法，它的迭代器也不应该实现remove方法。
要实现可修改的map，必须另外重写该类的put方法，否则使用put方法会抛出UnsupportedOperationException，而由entrySet().iterator()返回的迭代器，必须另外实现其remove()方法。
在查阅源码时，可以发现这个类的方法基本都是通过Entry这个对象来完成的，而获取这个对象的方法时entrySet()。
public V get(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
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();
}
}
returnnull;
}
|
继续追踪entrySet()方法，发现这却是一个抽象方法，具体实现类需要子类来完成，这是典型的模板方法设计模式，即在一个方法中定义一个算法的骨架，而将一些步骤的实现延迟到子类中，使得子类可以在不改变算法结构的情况下，重新定义算法中某些步骤的具体实现。
publicabstract Set<Entry<K,V>> entrySet(); |
继续跟进下去，AbstractMap中定义了两个用transient修饰的成员变量。
在JDK7中keySet变量是由volatile修饰的，但在JDK8中并没有使用volatile修饰，并且从注释中可以看到是这样解释的，访问这些字段的方法本身就没有同步，加上volatile也不能保证线程安全。
/**
* Each of these fields are initialized to contain an instance of the
* appropriate view the first time this view is requested. The views are
* stateless, so there's no reason to create more than one of each.
*
* <p>Since there is no synchronization performed while accessing these fields,
* it is expected that java.util.Map view classes using these fields have
* no non-final fields (or any fields at all except for outer-this). Adhering
* to this rule would make the races on these fields benign.
*
* <p>It is also imperative that implementations read the field only once,
* as in:
*
* <pre> {@code
* public Set<K> keySet() {
* Set<K> ks = keySet; // single racy read
* if (ks == null) {
* ks = new KeySet();
* keySet = ks;
* }
* return ks;
* }
*}</pre>
*/
transient Set<K> keySet;
transient Collection<V> values;
|
上面源码，注释中还有一段代码，这段代码是描述了key值的存储容器，那么返回key值的Set集合元素的方法，最简单实现，自然是遍历Entry数组取出key值放到Set集合中。
如果真的是猜测的这样的话，就意味着每次调用keySet方法都会遍历Entry数组，数据量大时，效率会大大降低，可是如果不采取遍历的方式，如何知道Map新增了一个K-V键值对？
继续阅读源码，会发现有一个keySet方法，这个方法内部重新实现了一个新的自定义Set集合，在这个自定义Set集合中又重写了iterator方法，这里是关键，iterator方法返回Iterator接口，这里又重写实现了Iterator迭代器，通过调用entrySet方法在调用它的iterator方法。
/**
* {@inheritDoc}
*
* @implSpec
* This implementation returns a set that subclasses {@link AbstractSet}.
* The subclass's iterator method returns a "wrapper object" over this
* map's <tt>entrySet()</tt> iterator. The <tt>size</tt> method
* delegates to this map's <tt>size</tt> method and the
* <tt>contains</tt> method delegates to this map's
* <tt>containsKey</tt> method.
*
* <p>The set is created the first time this method is called,
* and returned in response to all subsequent calls. No synchronization
* is performed, so there is a slight chance that multiple calls to this
* method will not all return the same set.
*/
public Set<K> keySet() {
// 获取到的是transient Set<K> keySet
Set<K> ks = keySet;
//首次调用会为空，那么自然要创建一个Set
if (ks == null) {
//创建一个自定义Set
ks = new AbstractSet<K>() {
//重写Set集合的iterator方法
public Iterator<K> iterator() {
//重写实现Iterator接口
returnnew Iterator<K>() {
//引用Entry的Set集合Iterator迭代器
private Iterator<Entry<K,V>> i = entrySet().iterator();
//对key值判断，就是对entry判断
publicboolean hasNext() {
returni.hasNext();
}
//取下一个key值，就是取entry#getKey
publicK next() {
returni.next().getKey();
}
//删除key值，就是删除entry
publicvoid remove() {
i.remove();
}
};
}
//重写Set#size方法
publicint size() {
//key值又多少就是整个Map有多大，所以调用本类的size方法即可。
//这个是内部类直接使用this关键字代表这个类，应该指明是AbstractMap中的size方法没有this则表示static静态方法
returnAbstractMap.this.size();
}
//重写Set#isEmpty方法
publicboolean isEmpty() {
//对是否有key值，就是判断Map是否为空，所以调用本类的isEmpty方法即可
returnAbstractMap.this.isEmpty();
}
//重写Set#clear方法
publicvoid clear() {
//清空key值，就是清空Map，所以调用本类的clear方法即可
AbstractMap.this.clear();
}
//重写Set#contains方法
publicboolean contains(Object k) {
//判断Set是否包含数组K，就是判断Map中是否包含key值，所以调用本类的containsKey方法即可。
returnAbstractMap.this.containsKey(k);
}
};
//将这个自定义的Set集合赋值给变量keySet，在以后再次调用keySet方法时，keySet不为null，只需要直接返回
keySet = ks;
}
return ks;
}
|
可以看到实际上就是通过一个AbstractSet的匿名内部类，而该内部类的迭代器实际上就是该entrySet()迭代器，只不过在next()的时候调用了getKey()，而其他方法的实现都是调用了AbstractMap中的方法，而values()方法的实现也与这个差不多。
尽管这个方法是围绕着Key值，但实际上可以结合Entry来实现，而不用遍历Entry，同时提到的entrySet#iterator方法，这里就是之前说的模板方法模式的实践，因为EntrySet在AbstractMap中并未实现，而是交给子类去实现了，但是对于keySet方法却可以对它进行一个算法骨架实现。
可以看到values()方法也是类似的。
/**
* {@inheritDoc}
*
* @implSpec
* This implementation returns a collection that subclasses {@link
* AbstractCollection}. The subclass's iterator method returns a
* "wrapper object" over this map's <tt>entrySet()</tt> iterator.
* The <tt>size</tt> method delegates to this map's <tt>size</tt>
* method and the <tt>contains</tt> method delegates to this map's
* <tt>containsValue</tt> method.
*
* <p>The collection is created the first time this method is called, and
* returned in response to all subsequent calls. No synchronization is
* performed, so there is a slight chance that multiple calls to this
* method will not all return the same collection.
*/
public Collection<V> values() {
Collection<V> vals = values;
if (vals == null) {
vals = new AbstractCollection<V>() {
public Iterator<V> iterator() {
returnnew Iterator<V>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
publicboolean hasNext() {
return i.hasNext();
}
public V next() {
return i.next().getValue();
}
publicvoid remove() {
i.remove();
}
};
}
publicint size() {
return AbstractMap.this.size();
}
publicboolean isEmpty() {
return AbstractMap.this.isEmpty();
}
publicvoid clear() {
AbstractMap.this.clear();
}
publicboolean contains(Object v) {
return AbstractMap.this.containsValue(v);
}
};
values = vals;
}
return vals;
}
|
继续阅读源码，AbstractMap重写的equals方法。
publicboolean equals(Object o) {
//如果是本对象返回true
if (o == this)
returntrue;
//非Map子类的话，直接返回false
if (!(o instanceof Map))
returnfalse;
//强制将Object o转换为Map，判断是否和本对象size相等，如果不相等直接返回false
//这里的参数用的是？，而不是K-V，是因为泛型在运行时类型会被擦除，编译器不知道具体的K--V是什么类型
Map<?,?> m = (Map<?,?>) o;
if (m.size() != size())
returnfalse;
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();
//循环的与传进来的Map的元素进行对比，发现不相等的元素，直接返回false
//所有内容相等了，则跳出循环，返回true
if (value == null) {
if (!(m.get(key)==null && m.containsKey(key)))
returnfalse;
} else {
if (!value.equals(m.get(key)))
returnfalse;
}
}
} catch (ClassCastException unused) {
returnfalse;
} catch (NullPointerException unused) {
returnfalse;
}
returntrue;
}
|
继续阅读源码，AbstractMap重写的hashCode方法。
publicint hashCode() {
int h = 0;
//取出取出集合中的元素
Iterator<Entry<K,V>> i = entrySet().iterator();
//循环累加
while (i.hasNext())
h += i.next().hashCode();
//返回哈希值累加的结果
return h;
}
|
在源码中，这个方法的注释是说是给SimpleEntry和SimpleImmutableEntry使用的，测试是否相等，是否为空。
虽然这个方法中的o1、o2是Object类型，Object类型的equals方法是通过==比较的引用，这里是没有问题的，因为在实际中，o1类型有可能是String（常量池地址），尽管转为了Object，所以为此时调用equals方法时，还是调用了String#equals方法。
/**
* Utility method for SimpleEntry and SimpleImmutableEntry.
* Test for equality, checking for nulls.
*
* NB: Do not replace with Object.equals until JDK-8015417 is resolved.
*/
privatestaticboolean eq(Object o1, Object o2) {
return o1 == null ? o2 == null : o1.equals(o2);
}
|
上面eq方法说到给SimpleEntry、SimpleImmutableEntry这两个类用的，在继续阅读代码会发现，SimpleEntry、SimpleImmutableEntry是属于AbstractMap的静态内部类。
SimpleEntry定义为可变entry，实现了Serializable接口，是可以被实例化，简化了构建自定义map实现的过程，如可以非常方便的在方法Map.entrySet().toArray中返回SimpleEntry实例的数组。
其中包含了两个private修饰符的属性，可以看到key被final修饰，而value没有，意味着key只要被初始化后旧不能更改，而value可以。另外，setValue方法是比较特殊的，存入的value返回的并不是存入的值，而是返回以前的旧值。
publicstaticclass SimpleEntry<K,V>
implements Entry<K,V>, java.io.Serializable
{
privatestaticfinallongserialVersionUID = -8499721149061103585L;
privatefinal K key;
private V value;
/**
* Replaces the value corresponding to this entry with the specified
* value.
*
* @param value new value to be stored in this entry
* @return the old value corresponding to the entry
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
|
SimpleImmutableEntry定位可变的entry，也是实现了Serializable接口，不提供setValue方法，在多个线程同时访问时，自然不能进行修改了，相比SimpleEntry的K-V成员变量都被定义为final。
这个类在返回键值映射的线程安全快照方法中会很方便。
区别SimpleEntry在于setValue方法。
publicstaticclass SimpleImmutableEntry<K,V>
implements Entry<K,V>, java.io.Serializable
{
privatefinal K key;
privatefinal V value;
/**
* Replaces the value corresponding to this entry with the specified
* value (optional operation). This implementation simply throws
* <tt>UnsupportedOperationException</tt>, as this class implements
* an <i>immutable</i> map entry.
*
* @param value new value to be stored in this entry
* @return (Does not return)
* @throws UnsupportedOperationException always
*/
public V setValue(V value) {
thrownew UnsupportedOperationException();
}
|
