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。

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

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

viewplain print ?

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中有这样的代码：

viewplain print ?

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源码：

[java] view plaincopy 
   
  /**   
       * 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)

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

viewplain print ?

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;

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);

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优秀很多。

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

Map接口

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

a)HashMap的特点：

b)HashMap的实现机制：

总结：

Ø HashMap与Hashtable的区别：

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

a)LinkedHashMap的特点：

b) LinkedHashMap的实现机制：

1)Entry元素：

2)初始化：

3)存储：

4)读取：

5)排序模式：

总结：

ØTreeMap的特点：

TreeMap实现机制：

TreeMap()

put(K,V)

ØConcurrentHashMap的特点，实现原理：

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

Map接口

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

a)HashMap的特点：

b)HashMap的实现机制：

总结：

Ø HashMap与Hashtable的区别：

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

a)LinkedHashMap的特点：

b) LinkedHashMap的实现机制：

1)Entry元素：

2)初始化：

3)存储：

4)读取：

5)排序模式：

总结：

ØTreeMap的特点：

TreeMap实现机制：

TreeMap()

put(K,V)

ØConcurrentHashMap的特点，实现原理：

热门文章

最新文章

相关课程

相关电子书

相关实验场景