logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

Map接口及其重要实现类的用法

 Dragon_chen 2017-06-26

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。

  1. <span style="font-size:10px;">1.  /**  
  2. 2.    * The table, resized as necessary. Length MUST Always be a power of two.  
  3. 3.    */    
  4. 4.   transient Entry[] table;  </span>  

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

viewplainprint

1.  static class Entry<K,V> implements Map.Entry<K,V> {  

2.        final K key;  

3.        V value;  

4.        Entry<K,V> next;  

5.        final int hash;  

6.        ......  

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

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

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

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

在HashMap中有这样的代码：

viewplainprint

1.  /** 

2.    * Returns index for hash code h. 

3.    */  

4.  static int indexFor(int h, int length) {  

5.       return h & (length-1);  

6.  }  

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

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

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

  1. 1.  /**  
  2. 2.       * Rehashes the contents of this map into a new array with a  
  3. 3.       * larger capacity.  This method is called automatically when the  
  4. 4.       * number of keys in this map reaches its threshold.  
  5. 5.       *  
  6. 6.       * If current capacity is MAXIMUM_CAPACITY, this method does not  
  7. 7.       * resize the map, but sets threshold to Integer.MAX_VALUE.  
  8. 8.       * This has the effect of preventing future calls.  
  9. 9.       *  
  10. 10.      * @param newCapacity the new capacity, MUST be a power of two;  
  11. 11.      *        must be greater than current capacity unless current  
  12. 12.      *        capacity is MAXIMUM_CAPACITY (in which case value  
  13. 13.      *        is irrelevant).  
  14. 14.      */    
  15. 15.     void resize(int newCapacity) {    
  16. 16.         Entry[] oldTable = table;    
  17. 17.         int oldCapacity = oldTable.length;    
  18. 18.         if (oldCapacity == MAXIMUM_CAPACITY) {    
  19. 19.             threshold = Integer.MAX_VALUE;    
  20. 20.             return;    
  21. 21.         }    
  22. 22.     
  23. 23.         Entry[] newTable = new Entry[newCapacity];    
  24. 24.         transfer(newTable);    
  25. 25.         table = newTable;    
  26. 26.         threshold = (int)(newCapacity * loadFactor);    
  27. 27.     }    
  28. 28.     
  29. 29.     /**  
  30. 30.      * Transfers all entries from current table to newTable.  
  31. 31.      */    
  32. 32.     void transfer(Entry[] newTable) {    
  33. 33.         Entry[] src = table;    
  34. 34.         int newCapacity = newTable.length;    
  35. 35.         for (int j = 0; j < src.length; j++) {    
  36. 36.             Entry<K,V> e = src[j];    
  37. 37.             if (e != null) {    
  38. 38.                 src[j] = null;    
  39. 39.                 do {    
  40. 40.                     Entry<K,V> next = e.next;    
  41. 41.                     int i = indexFor(e.hash, newCapacity);    
  42. 42.                     e.next = newTable[i];    
  43. 43.                     newTable[i] = e;    
  44. 44.                     e = next;    
  45. 45.                 } while (e != null);    
  46. 46.             }    
  47. 47.         }    
  48. 48.     }    

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

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

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

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

public HashMap(int initialCapacity,float loadFactor)

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

viewplainprint

1.  // Find a power of 2 >= initialCapacity  

2.  int capacity = 1;  

3.  while (capacity < initialCapacity)  

4.        capacity <<= 1;  

5.  ……  

6.  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的遍历方法,KeySet,EntrySet。

总结：

1.    HashMap采用数组方式存储key，value构成的Entry对象，无容量限制。

2.    HashMap基于key hash寻找Entry对象存放到数组的位置，对于Hash冲突采用链表的方式来解决。

3.    HashMap在插入元素时可能要扩大数组的容量，扩大容量时对所有的数据要重新计算哈希和存放到新数组中。当元素个数size大于threshold扩容threshold = (int)(newCapacity* loadFactor);

4.    HashMap保证数组的大小为2的指数大小。

5.    HashMap非线程安全。

  HashMap与Hashtable的区别：

1.        HashMap从java1.2后开始引进。Hashtable从java1.0开始引入。Hashtable一开始基于继承陈旧的抽象类Dictionary实现,后面也实现了Map接口。HashMap基于Map接口实现。

2.        HashMap允许存放key为null，value为null。对于key为null时，HashMap首先获取Entry数组中的第一个Entry对象，并基于Entry对象的next遍历链表，当找到其中Entry对象的key属性为null时，更新其value值。如果没有key属性为null的Entry，则调用addEntry(int hash, K key, V value, int bucketIndex)，参数为0,null,value,0，增加一个Entry对象，增加时先获取当前数组的第一个Entry对象，记为e，然后创建一个key为null，value为传入值得得Entry对象，next为之前获取的e。数组的第一个Entry对象链表，赋为新创建的Entry对象。由此，addEntry链表倒序插入元素的。Hashtable不允许key为null或value为null，否则会抛出NullPointerException。这从put方法的源码中很容易看出来，置于为什么真么限制，不明白？

3.       HashMap是非线程安全；Hashtable是线程安全的，其方法包含synchronized关键字实现线程安全。

4.       HashMap的计算hash值方法如下：首先对key取其hashCode,然后通过如下计算：

h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h>>> 4);

最后取index时：return h &(length-1);

Hashtable计算hash值，直接去key的hashCode值，如下：

int hash =key.hashCode();

取index时：int index = (hash& 0x7FFFFFFF) % tab.length;

5.   HashMap和Hashtable默认构造时，默认容量值不同。

HashMap默认数组大小为16，加载因子为0.75,重新hash阈值为12.

Hashtable默认数组大小为11,加载因子为0.75，重新hash阈值为8.

6.  HashMap和Hashtable的数组扩容方式不同。

HashMap中的数组容量大小始终保证为2的指数。重新hash,扩充容量方式为，当前容量大小*2.

Hashtable扩充容量方式为：int newCapacity = oldCapacity * 2 + 1;

7.  一些成员方法不同。

Hashtable包含一些旧的方法，如contains方法。

面试中常会碰到。

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

a)LinkedHashMap的特点：

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

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

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

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

b) LinkedHashMap的实现机制：


对于LinkedHashMap而言，它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。下面我们来分析LinkedHashMap的源代码：

1)Entry元素：

   LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。看源代码：

Java代码  

1. /** 

2.  * 双向链表的表头元素。 

3.  */  

4. private transient Entry<K,V> header;  

5.   

6. /** 

7.  * LinkedHashMap的Entry元素。 

8.  * 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用。 

9.  */  

10.private static class Entry<K,V> extends HashMap.Entry<K,V> {  

11.    Entry<K,V> before, after;  

12.    ……  

13.}  

2)初始化：

   通过源代码可以看出，在LinkedHashMap的构造方法中，实际调用了父类HashMap的相关构造方法来构造一个底层存放的table数组。如：

Java代码  

1. public LinkedHashMap(int initialCapacity, float loadFactor) {  

2.     super(initialCapacity, loadFactor);  

3.     accessOrder = false;  

4. }  

    HashMap中的相关构造方法：

Java代码  

1. public HashMap(int initialCapacity, float loadFactor) {  

2.     if (initialCapacity < 0)  

3.         throw new IllegalArgumentException("Illegal initial capacity: " +  

4.                                            initialCapacity);  

5.     if (initialCapacity > MAXIMUM_CAPACITY)  

6.         initialCapacity = MAXIMUM_CAPACITY;  

7.     if (loadFactor <= 0 || Float.isNaN(loadFactor))  

8.         throw new IllegalArgumentException("Illegal load factor: " +  

9.                                            loadFactor);  

10.  

11.    // Find a power of 2 >= initialCapacity  

12.    int capacity = 1;  

13.    while (capacity < initialCapacity)  

14.        capacity <<= 1;  

15.  

16.    this.loadFactor = loadFactor;  

17.    threshold = (int)(capacity * loadFactor);  

18.    table = new Entry[capacity];  

19.    init();  

20.}  

    我们已经知道LinkedHashMap的Entry元素继承HashMap的Entry，提供了双向链表的功能。在上述HashMap的构造器
中，最后会调用init()方法，进行相关的初始化，这个方法在HashMap的实现中并无意义，只是提供给子类实现相关的初始化调用。
   LinkedHashMap重写了init()方法，在调用父类的构造方法完成构造后，进一步实现了对其元素Entry的初始化操作。

Java代码  

1. void init() {  

2.     header = new Entry<K,V>(-1, null, null, null);  

3.     header.before = header.after = header;  

4. }  

3)存储：

   LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void addEntry(int hash, Kkey, V value, int bucketIndex) 和voidcreateEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。

Java代码  

1. void addEntry(int hash, K key, V value, int bucketIndex) {  

2.     // 调用create方法，将新元素以双向链表的的形式加入到映射中。  

3.     createEntry(hash, key, value, bucketIndex);  

4.   

5.     // 删除最近最少使用元素的策略定义  

6.     Entry<K,V> eldest = header.after;  

7.     if (removeEldestEntry(eldest)) {  

8.         removeEntryForKey(eldest.key);  

9.     } else {  

10.        if (size >= threshold)  

11.            resize(2 * table.length);  

12.    }  

13.}  

Java代码  

1. void createEntry(int hash, K key, V value, int bucketIndex) {  

2.     HashMap.Entry<K,V> old = table[bucketIndex];  

3.     Entry<K,V> e = new Entry<K,V>(hash, key, value, old);  

4.     table[bucketIndex] = e;  

5.     // 调用元素的addBrefore方法，将元素加入到哈希、双向链接列表。  

6.     e.addBefore(header);  

7.     size++;  

8. }  

Java代码  

1. private void addBefore(Entry<K,V> existingEntry) {  

2.     after  = existingEntry;  

3.     before = existingEntry.before;  

4.     before.after = this;  

5.     after.before = this;  

6. }  

4)读取：

   LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。

Java代码  

1. public V get(Object key) {  

2.     // 调用父类HashMap的getEntry()方法，取得要查找的元素。  

3.     Entry<K,V> e = (Entry<K,V>)getEntry(key);  

4.     if (e == null)  

5.         return null;  

6.     // 记录访问顺序。  

7.     e.recordAccess(this);  

8.     return e.value;  

9. }  

Java代码  

1. void recordAccess(HashMap<K,V> m) {  

2.     LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  

3.     // 如果定义了LinkedHashMap的迭代顺序为访问顺序，  

4.     // 则删除以前位置上的元素，并将最新访问的元素添加到链表表头。  

5.     if (lm.accessOrder) {  

6.         lm.modCount++;  

7.         remove();  

8.         addBefore(lm.header);  

9.     }  

10.}  

5)排序模式：

   LinkedHashMap定义了排序模式accessOrder，该属性为boolean型变量，对于访问顺序，为true；对于插入顺序，则为false。

Java代码  

1. private final boolean accessOrder;  

 一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。看LinkedHashMap的构造方法，如：

Java代码  

1. public LinkedHashMap(int initialCapacity, float loadFactor) {  

2.     super(initialCapacity, loadFactor);  

3.     accessOrder = false;  

4. }  

    这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个LinkedHashMap，并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用下面的构造方法构造LinkedHashMap：

Java代码  

1. public LinkedHashMap(int initialCapacity,  

2.          float loadFactor,  

3.                      boolean accessOrder) {  

4.     super(initialCapacity, loadFactor);  

5.     this.accessOrder = accessOrder;  

6. }  

    该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建LRU缓存。LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V>eldest)方法，在将新条目插入到映射后，put和 putAll将调用此方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。

Java代码  

1. protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {  

2.     return false;  

3. }  

    此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。如果用此映射构建LRU缓存，则非常方便，它允许映射通过删除旧条目来减少内存损耗。
   例如：重写此方法，维持此映射只保存100个条目的稳定状态，在每次添加新条目时删除最旧的条目。

Java代码  

1. private static final int MAX_ENTRIES = 100;  

2. protected boolean removeEldestEntry(Map.Entry eldest) {  

3.     return size() > MAX_ENTRIES;  

4. }  

总结：

1.    LinkedHashMap继承于HashMap，此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序（按从近期访问最少到近期访问最多的顺序）。默认情况下按插入顺序访问，当accessOrder设置为true时，按最后访问顺序遍历数据。

2.    LinkedHashMap非线程安全。

3.    LinkedHashMap适合做LRU缓存。

TreeMap的特点：

  TreeMap是一个支持排序的基于红黑树（Red-Black tree）的NavigableMap实现，非线程安全。TreeMap继承AbstractMap,实现NavigableMap，NavigableMap接口继承SortedMap接口。此实现为 containsKey、get、put 和 remove 操作提供受保证的 log(n) 时间开销。

    SortedMap提供关于键的总体排序的Map。该映射是根据其键的自然顺序进行排序的，或者根据通常在创建有序映射时提供的 Comparator 进行排序。对有序映射的 collection 视图（由 entrySet、keySet 和 values 方法返回）进行迭代时，此顺序就会反映出来。

插入SortedMap的所有键都必须实现 Comparable 接口（或者被指定的比较器接受）。另外，所有这些键都必须是可互相比较的：对有序映射中的任意两个键 k1 和 k2 执行 k1.compareTo(k2)（或 comparator.compare(k1, k2)）都不得抛出 ClassCastException。试图违反此限制将导致违反规则的方法或者构造方法调用抛出 ClassCastException。

所有通用SortedMap实现类都应该提供 4 个“标准”构造方法：

1) void（无参数）构造方法，它创建一个空的有序映射，按照键的自然顺序（实现Comparable接口，方法compareTo为自然比较方法，按此方法比较大小排序）进行排序。        2) 带有一个 Comparator 类型参数的构造方法，它创建一个空的有序映射，根据指定的比较器进行排序。

3) 带有一个 Map 类型参数的构造方法，它创建一个新的有序映射，其键-值映射关系与参数相同，按照键的自然顺序进行排序。

4) 带有一个 SortedMap 类型参数的构造方法，它创建一个新的有序映射，其键-值映射关系和排序方法与输入的有序映射相同。无法保证强制实施此建议，因为接口不能包含构造方法。

SortedMap新增了一些成员方法，如下图所示：

NavigableMap<K,V>接口，扩展自 SortedMap，具有了针对给定搜索目标返回最接近匹配项的导航方法。方法 lowerEntry、floorEntry、ceilingEntry 和 higherEntry 分别返回与小于、小于等于、大于等于、大于给定键的键关联的 Map.Entry 对象，如果不存在这样的键，则返回 null。类似地，方法 lowerKey、floorKey、ceilingKey 和 higherKey 只返回关联的键。所有这些方法是为查找条目而不是遍历条目而设计的。

TreeMap实现机制：

TreeMap()

    将comparator属性赋值为null。如果要控制TreeMap中元素的存储顺序，应使用带Comparator参数的构造器。

put(K,V)

  先判断root是否为null，如果为null，则创建一个新的Entry对象，并赋值给root属性。否则，首先判断是否传入了Compatator实现，如果是，则基于红黑树的方式遍历，直到为树节点null，使用传入的comparator比较Key的大小，如果找到相等的key则更新其值，若没有找到……，如果comparator为null，则判断key是否为null，如果是null，抛出NullPointerException，对于key不是null时，取key对于的Comparator进行红黑树的遍历和比较，与上述类似。

如果没有找到相同的key，则创建一个新的Entry对象，并将其parent设置为上面所寻找到的元素，并根据和parent key比较的情况设置parent的left和right属性。最后对红黑树进行调整。

ConcurrentHashMap的特点，实现原理：

    ConcurrentHashMap是线程安全的HashMap实现。支持获取，查找时完全并发和更新时可调整并发的哈希表。获取操作（包括 get）通常不会受阻塞。并发场景中(多个线程的情况下) ConcurrentHashMap比HashMap优秀很多。

    本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。
    转藏 分享 献花（0）

    来自： Dragon_chen > 《Java》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多