Java容器学习笔记（三） Map接口及其重要实现类学习总结

在本文中如果您发现了错误，请您花费几分钟的时间给予指出，谢谢！！



本文主要总结Map接口及其重要实现类的用法。



三．Map接口

Ø  Map中的每个成员方法由一个关键字（key）和一个值（value）构成。Map接口不直接继承于Collection接口，因为它包装的是一组成对的“键-值”对象的集合，而且在Map接口的集合中也不能有重复的key出现，因为每个键只能与一个成员元素相对应。

Ø  Map接口的子接口以及主要实现类有：

子接口：Bindings、ConcurrentMap、ConcurrentNavigableMap、MessageContext、LogicMessageContext、NavigableMap、SOAPMessageMap、SortedMap

实现类：AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, EnumMap,ConcurrentSkipListMap,HashMap, Hashtable, IdentityHashMap, LinkedHashMap, PrinterStateReasons,Properties, Provider, RenderingHints, SimpleBindings, TabularDataSupport,TreeMap, UIDefaults,WeakHashMap


Map接口中定义的方法清单：

Ø  Map中定义的方法说明：

在Map接口中定义的通用方法并不是很多。

a)      添加和删除Map中的某个元素

•         put(K, V) ： 将给定的“键-值”对放入到给定的Map当中

•         putAll(Map<? extends K, ? extends V) : 将指定的Map中的“键-值”对放入到给定的Map当中

•         remove(Object key) : 从该集合中移除指定的对象，并返回对应的value

•         clear() : 清空Map中的所有对象

b)      查询与Map有关的数据

•         int size() : 返回此Map中“键-值”对的个数

•         boolean isEmpty() : 判断此Map中“键-值”对的个数是否为0

•         boolean containsKey(Object key) : 测试此Map中是否有该key

•         boolean containsValue(Object value) : 测试此Map中是否包含该value

•         V get(Object key) : 通过指定的key查询Map中对应的value

•         Collection<Object value> values() : 取得Map中所有的value

•         Set<Object key> keySet() : 取得当前Map中key的集合

•         Set<Entry<K, V>> entrySet() : 取得当前Map中entry的集合

Ø  HashMap的特点、实现机制及使用方法

a)      HashMap的特点：

HashMap实现了Map、CloneMap、Serializable三个接口，并且继承自AbstractMap类。

b)      HashMap的实现机制：
HashMap基于hash数组实现，若key的hash值相同则使用链表方式进行保存，详见HashSet中的说明。我引用网上一个名词叫“链表散列”来形容这样的数据结构。

新建一个HashMap时会初始化一个大小为16，负载因子为0.75的空的HashMap。

    /** 
      * The table, resized as necessary. Length MUST Always be a power of two. 
      */  
     transient Entry[] table;  

那么Entry到底是怎么实现的呢？

    static class Entry<K,V> implements Map.Entry<K,V> {  
          final K key;  
          V value;  
          Entry<K,V> next;  
          final int hash;  
          ......  

上面代码其实告诉我们Entry是一个结点，它持有下一个元素的引用，这样就构成了一个链表。

那么，整体上来说HashMap底层就是使用这样一个数据结构来实现的。

我们提到使用Hash，但是Hash值如何与元素的存储建立关系呢？（Hash算法）

在数据结构课中我们学习过Hash的简单算法，就是给你一个Hash因子，通过对该元素的hashCode简单的求余，来实现对其快速的定位和索引。

在HashMap中有这样的代码：

    /** 
      * Returns index for hash code h. 
      */  
    static int indexFor(int h, int length) {  
         return h & (length-1);  
    }  

这个方法在HashMap中非常重要，凡是与查询、添加、删除有关的方法中都有调用该方法，为什么这么短的一个代码使用率这么高？根据代码注释我们知道，这个方法是根据hashCode及当前table的长度（数组的长度，不是map的size）得到该元素应该存放的位置，或者在table中的索引。

现在我们需要看一下当数据量已经超过初始定义的负载因子时，HashMap如何处理？

在HashMap中当数据量很多时，并且已经达到了负载限度时，会重新做一次哈希，也就是说会再散列。调用的方法为resize()，并且java默认传入的参数为2*table.length。先看一下JDK源码：

    /** 
         * Rehashes the contents of this map into a new array with a 
         * larger capacity.  This method is called automatically when the 
         * number of keys in this map reaches its threshold. 
         * 
         * If current capacity is MAXIMUM_CAPACITY, this method does not 
         * resize the map, but sets threshold to Integer.MAX_VALUE. 
         * This has the effect of preventing future calls. 
         * 
         * @param newCapacity the new capacity, MUST be a power of two; 
         *        must be greater than current capacity unless current 
         *        capacity is MAXIMUM_CAPACITY (in which case value 
         *        is irrelevant). 
         */  
        void resize(int newCapacity) {  
            Entry[] oldTable = table;  
            int oldCapacity = oldTable.length;  
            if (oldCapacity == MAXIMUM_CAPACITY) {  
                threshold = Integer.MAX_VALUE;  
                return;  
            }  
      
            Entry[] newTable = new Entry[newCapacity];  
            transfer(newTable);  
            table = newTable;  
            threshold = (int)(newCapacity * loadFactor);  
        }  
      
        /** 
         * Transfers all entries from current table to newTable. 
         */  
        void transfer(Entry[] newTable) {  
            Entry[] src = table;  
            int newCapacity = newTable.length;  
            for (int j = 0; j < src.length; j++) {  
                Entry<K,V> e = src[j];  
                if (e != null) {  
                    src[j] = null;  
                    do {  
                        Entry<K,V> next = e.next;  
                        int i = indexFor(e.hash, newCapacity);  
                        e.next = newTable[i];  
                        newTable[i] = e;  
                        e = next;  
                    } while (e != null);  
                }  
            }  
        }  

看到这里我们会发现resize（再哈希）的工作量是不是很大啊。再哈希是重新建一个指定容量的数组，然后将每个元素重新计算它要放的位置，这个工作量确实是很大的。

这里就产生了一个很重要的问题，那就是怎么让哈希表的分布比较均匀，也就是说怎么让它即不会成为一个单链表（极限情况，每个key的hash值都集中到了一起），又不会使hash空间过大（导致内存浪费）？

上面两个问题一个是解决了怎么计算hash值快速存取，一个是怎么实现再哈希，何时需要再哈希。快速存取的前提是元素分布均匀，不至于集中到一点，再哈希是元素过于零散，导致不断的重新构建表。

那么在第一个问题中我们看到了这样一个代码return h & (length-1);在第二个问题中我们说过内部调用传入的值为2*table.length;并且默认情况下HashMap的大小为一个16的数字，除了默认构造提供大小为16的空间外，如果我们使用

public HashMap(int initialCapacity, float loadFactor)

上面的构造方法，我们会发现这样的代码：

    // Find a power of 2 >= initialCapacity  
    int capacity = 1;  
    while (capacity < initialCapacity)  
          capacity <<= 1;  
    ……  
    table = new Entry[capacity];  

也就是说当我们传入1000时，它并没有给我们构造一个容量为1000的哈希表，而是构建了一个容量为1024大小的哈希表。

从整体上我们发现一个问题，那就是无论什么情况HashMap中哈希表的容量总是2的n次方的一个数。并且有这样一个公式：

       当length=2^n时，hashcode & (length-1) == hashcode % length

也就是这一点验证了第一个问题，hash索引值的计算方法其实就是对哈希因子求余。只有大小为2的n次方时，那样的计算才成立，所以HashMap为我们维护了一个这样大小的一个哈希表。（位运算速度比取模运算快的多）

c)      HashMap的使用方法：

我在很多代码中都用到了HashMap，原因是首先它符合存储关联数据的要求，其次它的存取速度快，这是一个选择的问题。

比较重要的是HashMap的遍历方法，在我的博客中有专门写到HashMap的遍历方法：http://blog.csdn.net/tsyj810883979/article/details/6746274

Ø  LinkedHashMap的特点、实现机制及使用方法

a)      LinkedHashMap的特点：

LinkedHashMap继承自HashMap并且实现了Map接口。和HashMap一样，LinkedHashMap允许key和value均为null。

于该数据结构和HashMap一样使用到hash算法，因此它不能保证映射的顺序，尤其是不能保证顺序持久不变（再哈希）。

如果你想在多线程中使用，那么需要使用Collections.synchronizedMap方法进行外部同步。

LinkedHashMap与HashMap的不同之处在于，LinkedHashMap维护者运行于所有条目的双重链接列表，此链接列表可以是插入顺序或者访问顺序。

b)      LinkedHashMap的实现机制：

无法总结下去，在网上看到这样一篇文章：http://zhangshixi.iteye.com/blog/673789

感觉真的没办法总结下去了。

Ø  HashMap与Hashtable的区别：

Hashtable实现Map接口，继承自古老的Dictionary类，实现一个key-value的键值映射表。任何非空的（key-value）均可以放入其中。

区别主要有三点：

1.      Hashtable是基于陈旧的Dictionary实现的，而HashMap是基于Java1.2引进的Map接口实现的；

2.      Hashtable是线程安全的，而HashMap是非线程安全的，我们可以使用外部同步的方法解决这个问题。

3.      HashMap可以允许你在列表中放一个key值为null的元素，并且可以有任意多value为null，而Hashtable不允许键或者值为null。

Ø  WeakHashMap的特点：

我没有使用过这个类。网摘：WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。(后续使用后进行总结)

Ø  Properties及TreeMap在后续内容里进行总结。