本文共 10431 字,大约阅读时间需要 34 分钟。
在数组是通过数组下角标来对内容进行索引的,而在Map中是通过对象来对对象进行索引,用来索引的对象叫Key,对应的对象叫Value,就是平时说的键值对。
public interface Map<K,V> |
Map接口是用来取代过时的Dictionary抽象类的,这个接口提供了一种映射关系,即元素是以键值对(K-V)的形式存储的,能够实现根据key快速查找到Value,并且还定义了map的基本行为方法,包括最核心的get和put操作。
Map常用实现,、、、、、,为重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 */ public static <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 */ public static <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 */ public static <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 */ public static <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()); } } |
public abstract class 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(); } } return null; } |
继续追踪entrySet()方法,发现这却是一个抽象方法,具体实现类需要子类来完成,这是典型的模板方法设计模式,即在一个方法中定义一个算法的骨架,而将一些步骤的实现延迟到子类中,使得子类可以在不改变算法结构的情况下,重新定义算法中某些步骤的具体实现。
public abstract 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接口 return new Iterator<K>() { //引用Entry的Set集合Iterator迭代器 private Iterator<Entry<K,V>> i = entrySet().iterator();
//对key值判断,就是对entry判断 public boolean hasNext() { return i.hasNext(); }
//取下一个key值,就是取entry#getKey public K next() { return i.next().getKey(); }
//删除key值,就是删除entry public void remove() { i.remove(); } }; }
//重写Set#size方法 public int size() { //key值又多少就是整个Map有多大,所以调用本类的size方法即可。 //这个是内部类直接使用this关键字代表这个类,应该指明是AbstractMap中的size方法没有this则表示static静态方法 return AbstractMap.this.size(); }
//重写Set#isEmpty方法 public boolean isEmpty() { //对是否有key值,就是判断Map是否为空,所以调用本类的isEmpty方法即可 return AbstractMap.this.isEmpty(); }
//重写Set#clear方法 public void clear() { //清空key值,就是清空Map,所以调用本类的clear方法即可 AbstractMap.this.clear(); }
//重写Set#contains方法 public boolean contains(Object k) { //判断Set是否包含数组K,就是判断Map中是否包含key值,所以调用本类的containsKey方法即可。 return AbstractMap.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() { 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(); } }; }
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; } |
继续阅读源码,AbstractMap重写的equals方法。
public boolean equals(Object o) { //如果是本对象返回true if (o == this) return true;
//非Map子类的话,直接返回false if (!(o instanceof Map)) return false;
//强制将Object o转换为Map,判断是否和本对象size相等,如果不相等直接返回false //这里的参数用的是?,而不是K-V,是因为泛型在运行时类型会被擦除,编译器不知道具体的K--V是什么类型 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();
//循环的与传进来的Map的元素进行对比,发现不相等的元素,直接返回false //所有内容相等了,则跳出循环,返回true if (value == null) { if (!(m.get(key)==null && m.containsKey(key))) return false; } else { if (!value.equals(m.get(key))) return false; } } } catch (ClassCastException unused) { return false; } catch (NullPointerException unused) { return false; }
return true; } |
继续阅读源码,AbstractMap重写的hashCode方法。
public int 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. */ private static boolean 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返回的并不是存入的值,而是返回以前的旧值。
public static class SimpleEntry<K,V> implements Entry<K,V>, java.io.Serializable { private static final long serialVersionUID = -8499721149061103585L;
private final 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方法。
public static class SimpleImmutableEntry<K,V> implements Entry<K,V>, java.io.Serializable {
private final K key; private final 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) { throw new UnsupportedOperationException(); } |
转载地址:http://flmxi.baihongyu.com/