Java入门记(五):容器关系的梳理(下)——Map

  1. 云栖社区>
  2. 博客>
  3. 正文

Java入门记(五):容器关系的梳理(下)——Map

长征6号 2016-05-12 12:35:00 浏览674
展开阅读全文

注意:阅读本文及相关源码时,需要数据结构相关知识,包括:哈希表、链表、红黑树。

 

  Map是将键(key)映射到值(value)的对象。不同的映射不能包含相同的键;每个键最多只能映射到一个值。下图是常见Map的接口和实现。与Collection相比,继承关系简单不少。

一、Map接口和AbstractMap抽象类

  Map接口除了增加映射、根据key获取value、判断映射中的key或value是否存在、删除映射的基本方法外,还包含了返回包含所有key的Set、包含所有value的collection的方法。由于key不能重复,返回的Collection自然具有Set的属性,很适合用Set返回。而value则不行。

  与其他Collection接口不同,Map接口中有一个子接口:Entry。Entry代表了一个映射,包含了key和value两部分,同时,一个Enry的key没有提供修改方法,而value允许修改。需要说明的是,如果用一个可变对象作为Map的key,若变化后equals()与之前的行为不同,那么映射的行为是不确定的(JDK1.6文档)。

  对于抽象类AbstractMap,大部分实现的方法借助了将所有entry组成的set返回的抽象方法entrySet():size()、isEmpty()(使用size())、containsValue()、containsKey()、get()、clear()、keySet()、values()等。而remove()、removeAll()、retainAll()、clear()、toString()则借助了抽象方法iterator()。

  values()返回值value的是一个匿名内部类实现的AbstractCollection。value在第一次访问时创建,在后续所有访问中返回。虽然不进行元素的同步,其引用几乎总是不变的,但返回值的行为会随着Map中的元素变化:

 

复制代码
public Collection<V> values() {
    if (values == null) {
        values = 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 contains(Object v) {
              return AbstractMap.this.containsValue(v);
           }
        };
    }
    return values;
}
复制代码

 

  对于Map.Entry,AbstractMap中实现了两个键值对类型:SimpleEntry和SimpleImmutableEntry。后者与前者的区别是,不允许setValue(),调用该方法抛出UnsupportedOperationException异常。

二、HashMap/LinkedHashMap/WeakHashMap

   在Java入门记(四):容器关系的梳理(上)——Collection一文中提到,HashSet/LinkedHashSet的底层实际是HashMap/LinkedHashMap。HashMap和一般的散列表实现方式相同,用数组存放相同哈希值的元素所组成队列的首元素,队列的元素是Entry,包括了key、value、hash值、next等属性。寻找指定key时,先做哈希,根据哈希值找到数组中对应的队列头,遍历队列找出key及对应的value。

  由于HashMap允许null作为key,这个key没办法做哈希值的计算,只能遍历哈希值数组,找到首元素的key为null的队列。这个实现可以参考私有方法getForNullKey()。

  HashMap的key的哈希值数组有一个容量限制:必须为2的幂次。即使在新建HashMap时或调用resize()时指定一个非2的幂次的容量,实际调用时新的HashMap容量也会扩大到不小于这个指定容量的2的幂次的值。与之相关联地,哈希值的计算hash()和某个hash值在数组的索引的计算indexFor()方式为:

复制代码
static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
}
复制代码
static int indexFor(int h, int length) {
    return h & (length-1);
}

2的幂次可以保证计算索引时适当的截断(舍弃高位)。

   LinkedHashMap与HashMap的关系并不像LinkedList和ArrayList那样。从结构上来看,LinkedHashMap仅仅是把所有的Entry组成了一个双向链表。这样,在迭代遍历时,可以使用插入顺序或LRU顺序访问所有元素(通过设置accessOrder标记位)。

  WeakHashMap和HashMap很类似,其内部包含了一个ReferenceQueue,并且它的Entry是继承自WeakReference的。通过这种方式,在clear()、resize()、size()、getTable()时,都会调用expungeStaleEntries()方法,垃圾回收掉不再使用的映射关系。这里不介绍Reference的相关内容了。

  思考下上一篇文章所提出的问题:是不是可以先实现HashSet,再用HashSet实现HashMap?个人认为,这样实现的HashSet中的元素(对应Map的Entry),只有键没有值,是无法直接实现HashMap的。

二、Hashtable/Properties

  Hashtable虽然实现了Map接口,但没有用AbstractMap来做。它的行为与HashMap很相似,保留下来是为了兼容原来的代码,不推荐继续使用。

  继承了Hashtable<Object,Object>的Properties稍有点不同,它与流的关系密切些,可保存在流中或从流中加载。另外,它是线程安全的。

三、SortedMap和TreeMap

  SortedMap中的所有元素都是排过序的。这个“排序”不同于LinkedHashMap中将所有元素组织成一个链表,而是指任意任意两个元素都可以比较大小关系,并根据这个比较规则Comparator进行排序。更准确的说,是键的大小关系。建立在有序的基础上,SortedMap接口中包含了返回部分Map的方法subMap(K fromKey, K toKey)、headMap(K toKey)、tailMap(K fromKey)以及首尾key的方法firstKey()、lastKey()。

  TreeMap是SortedMap的一个实现,其Compartor可以为null,这种情况下比较元素大小时调用元素自身的compareTo()方法。

  TreeMap实际上使用了红黑树,保存了树的根。关于红黑树的算法,讲起来可以单独开一篇文章,这里不展开了,想了解的读者可以读下《算法导论》的相关章节。TreeMap的元素插入、删除其实是红黑树节点的插入和删除。在元素有序的前提下,找到特定的key(以及对应的value)同样是使用了红黑树的查找方法。





本文转自五岳博客园博客,原文链接:http://www.cnblogs.com/wuyuegb2312/p/4458468.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
长征6号
+ 关注