Java集合框架---Map

Map

 

Map接口不是Collection接口的继承。Map接口用于维护键/值对(key/value pairs)。该接口描述了从不重复的键到值的映射。Map 接口提供三种collection 视图，允许以键集、值集合或键-值映射关系集的形式查看某个映射的内容：

 

Set keySet(): 返回映像中所有关键字的视图集

Collection values():返回映像中所有值的视图集

Set entrySet(): 返回Map.Entry对象的视图集，即映像中的关键字/值对

 

获得的对应集合可以删除，但是不可以添加。

 

Map.Entry接口

Map的entrySet()方法返回一个实现Map.Entry接口的对象集合。集合中每个对象都是底层Map中一个特定的键/值对。

通过这个集合的迭代器，您可以获得每一个条目(唯一获取方式)的键或值并对值进行更改。当条目通过迭代器返回后，除非是迭代器自身的remove()方法或者迭代器返回的条目的setValue()方法，其余对源Map外部的修改都会导致此条目集变得无效，同时产生条目行为未定义。

 

SortedMap接口

SortedMap接口为映像的视图(子集)，包括两个端点提供了访问方法。除了排序是作用于映射的键以外，处理SortedMap和处理SortedSet一样。　　

 

添加到SortedMap实现类的元素必须实现Comparable接口，否则您必须给它的构造函数提供一个Comparator接口的实现。TreeMap类是它的唯一一份实现。

 

AbstractMap

和其它抽象集合实现相似，AbstractMap 类覆盖了equals()和hashCode()方法以确保两个相等映射返回相同的哈希码。

 

HashMap类和TreeMap类

在Map 中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和equals()的实现。

 

由于TreeMap它底层采用一棵“红黑树”来保存集合中的 Entry，这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低O（lgN）：当 TreeMap 添加元素时，需要通过循环找到新增 Entry 的插入位置，因此比较耗性能；当从 TreeMap 中取出元素时，需要通过循环才能找到合适的 Entry，也比较耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于：TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态，TreeSet 中所有元素总是根据指定排序规则保持有序状态，对排序二叉树，若按中序遍历就可以得到由小到大的有序序列。

《树和二叉树》

《各种其他树》

通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

 

TreeMap对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等。TreeMap采用红-黑树的二叉搜索树来保存Map中每一个Entry，每个Entery都被当成“红黑树”的一个节点。

 

public static void main(String[] args)

 {    TreeMap<String,Object> treeMap = new TreeMap<String,Object>();      

                treeMap.put("004", new Integer(40));      

                treeMap.put("003", new Integer(30));      

                treeMap.put("001", new Integer(10));      

                treeMap.put("002", new Integer(20));  

    }

{001=10, 002=20, 003=30, 004=40}

 

getEntry()源码：

final Entry<K,V> getEntry(Object key) 

 { 

    // 如果 comparator 不为 null，表明程序采用定制排序

    if (comparator != null) 

        // 调用 getEntryUsingComparator 方法来取出对应的 key 

        return getEntryUsingComparator(key); 

    // 如果 key 形参的值为 null，抛出 NullPointerException 异常

    if (key == null) 

        throw new NullPointerException(); 

    // 将 key 强制类型转换为 Comparable 实例

    Comparable<? super K> k = (Comparable<? super K>) key; 

    // 从树的根节点开始

    Entry<K,V> p = root; 

    while (p != null) 

    { 

        // 拿 key 与当前节点的 key 进行比较

        int cmp = k.compareTo(p.key); 

        // 如果 key 小于当前节点的 key，向“左子树”搜索

        if (cmp < 0) 

            p = p.left; 

        // 如果 key 大于当前节点的 key，向“右子树”搜索

        else if (cmp > 0) 

            p = p.right; 

        // 不大于、不小于，就是找到了目标 Entry 

        else 

            return p; 

    } 

    return null; 

 }
 
HashMap和HashTable

Hashtable和HashMap类有三个重要的不同之处。第一个不同主要是历史原因。Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现。
  
  也许最重要的不同是Hashtable的方法是同步的，而HashMap的方法不是。这就意味着，虽然你可以不用采取任何特殊的行为就可以在一个多线程的应用程序中用一个Hashtable，但你必须同样地为一个HashMap提供外同步。一个方便的方法就是利用Collections类的静态的synchronizedMap()方法，它创建一个线程安全的Map对象，并把它作为一个封装的对象来返回。这个对象的方法可以让你同步访问潜在的HashMap。这么做的结果就是当你不需要同步时，你不能切断Hashtable中的同步（比如在一个单线程的应用程序中），而且同步增加了很多处理费用。
  
  第三点不同是，只有HashMap可以让你将空值作为一个表的条目的key或value。HashMap中只有一条记录可以是一个空的key，但任意数量的条目可以是空的value。这就是说，如果在表中没有发现搜索键，或者如果发现了搜索键，但它是一个空的值，那么get()将返回null。如果有必要，用containKey()方法来区别这两种情况。 

 

LinkedHashMap

扩展HashMap，以插入顺序将关键字/值对添加进链接哈希映像中。象LinkedHashSet一样，LinkedHashMap内部也采用双重链接式列表。所以迭代顺序也就是插入顺序。

 

 

WeakHashMap

它使用WeakReference(弱引用)来存放哈希表关键字。使用这种方式时，当映射的键在 WeakHashMap 的外部不再被引用时，垃圾收集器会将它回收，但它将把到达该对象的弱引用纳入一个队列。WeakHashMap的运行将定期检查该队列，以便找出新到达的弱应用。当一个弱引用到达该队列时，就表示关键字不再被任何人使用，并且它已经被收集起来。然后WeakHashMap便删除相关的映射。

 

IdentityHashMap

这个类中，关键字的哈希码不应该由hashCode()方法来计算，而应该由System.identityHashCode方法进行计算(即使已经重新定义了hashCode方法)。这是Object.hashCode根据对象的内存地址来计算哈希码时使用的方法。另外，为了对各个对象进行比较，IdentityHashMap将使用==，而不使用equals方法。

 

换句话说，不同的关键字对象，即使它们的内容相同，也被视为不同的对象。IdentityHashMap类可以用于实现对象拓扑结构转换(topology-preserving object graph transformations)(比如实现对象的串行化或深度拷贝)，在进行转换时，需要一个“节点表”跟踪那些已经处理过的对象的引用。即使碰巧有对象相等，“节点表”也不应视其相等。另一个应用是维护代理对象。比如，调试工具希望在程序调试期间维护每个对象的一个代理对象。

 

　　“IdentityHashMap类不是一般意义的Map实现！它的实现有意的违背了Map接口要求通过equals方法比较对象的约定。这个类仅使用在很少发生的需要强调等同性语义的情况。”

 

 

 

http://a123159521.javaeye.com/blog/693225       HashMap源码解析

http://www.javaeye.com/topic/340756 HashSet与HashMap关系之源码分析