Map不同具体实现类的比较和应用场景的分析-白红宇

Map不同具体实现类的比较和应用场景的分析

阅读量：5109 次

发布时间：2019-06-13

本文共 13692 字，大约阅读时间需要 45 分钟。

1、Map的概括总结

(01) Map 是“键值对”映射的抽象接口。

(02) AbstractMap 实现了Map中的绝大部分函数接口。它减少了“Map的实现类”的重复编码。

(03) SortedMap 有序的“键值对”映射接口。

(04) NavigableMap 是继承于SortedMap的，支持导航函数的接口。具有了为给定搜索目标报告最接近匹配项的导航方法。

(05) HashMap, Hashtable, TreeMap, WeakHashMap这4个类是“键值对”映射的实现类。它们各有区别！

　　HashMap 是基于“拉链法”实现的散列表。一般用于单线程程序中。

　　Hashtable 也是基于“拉链法”实现的散列表。它一般用于多线程程序中。

　　WeakHashMap 也是基于“拉链法”实现的散列表，它一般也用于单线程程序中。相比HashMap，WeakHashMap中的键是“弱键”，当“弱键”被GC回收时，它对应的键值对也会被从WeakHashMap中删除；而HashMap中的键是强键。

　　TreeMap 是有序的散列表，它是通过红黑树实现的。它一般用于单线程中存储有序的映射。

2、HashMap和Hashtable异同

2.1、HashMap和Hashtable的相同点

HashMap和Hashtable都是存储“键值对(key-value)”的散列表，而且都是采用拉链法实现的。

存储的思想都是：通过table数组存储，数组的每一个元素都是一个Entry；而一个Entry就是一个单链表，Entry链表中的每一个节点就保存了key-value键值对数据。

添加key-value键值对：首先，根据key值计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。然后，根据数组索引找到Entry(即，单链表)，再遍历单链表，将key和链表中的每一个节点的key进行对比。若key已经存在Entry链表中，则用该value值取代旧的value值；若key不存在Entry链表中，则新建一个key-value节点，并将该节点插入Entry链表的表头位置。

删除key-value键值对：删除键值对，相比于“添加键值对”来说，简单很多。首先，还是根据key计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。然后，根据索引找出Entry(即，单链表)。若节点key-value存在与链表Entry中，则删除链表中的节点即可。

2.2、HashMap和Hashtable的不同点

2.2.1、继承和实现方式不一样

　　HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口

　　Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口

　　Dictionary是一个抽象类，它直接继承于Object类，没有实现任何接口。Dictionary类是JDK 1.0的引入的。虽然Dictionary也支持“添加key-value键值对”、“获取value”、“获取大小”等基本操作，但它的API函数比Map少；而且Dictionary一般是通过Enumeration(枚举类)去遍历，Map则是通过Iterator(迭代器)去遍历。然而‘由于Hashtable也实现了Map接口，所以，它即支持Enumeration遍历，也支持Iterator遍历

2.2.2、线程安全不同

　　Hashtable的几乎所有函数都是同步的，即它是线程安全的，支持多线程。

　　HashMap的函数则是非同步的，它不是线程安全的。若要在多线程中使用HashMap，需要我们额外的进行同步处理。对HashMap的同步处理可以使用Collections类提供的synchronizedMap静态方法，或者直接使用JDK 5.0之后提供的java.util.concurrent包里的ConcurrentHashMap类。

2.2.3、支持的遍历种类不同

　　HashMap只支持Iterator(迭代器)遍历。

　　Hashtable支持Iterator(迭代器)和Enumeration(枚举器)两种方式遍历

　　Enumeration 是JDK 1.0添加的接口，只有hasMoreElements(), nextElement() 两个API接口，不能通过Enumeration()对元素进行修改 而Iterator 是JDK 1.2才添加的接口，支持hasNext(), next(), remove() 三个API接口。HashMap也是JDK 1.2版本才添加的，所以用Iterator取代Enumeration，HashMap只支持Iterator遍历。

2.2.4、对null值的支持不同

　　HashMap的key、value都可以为null

　　Hashtable的key、value都不可以为null

　　Hashtable的key或value，都不能为null！否则，会抛出异常NullPointerException

　　HashMap的key、value都可以为null。 当HashMap的key为null时，HashMap会将其固定的插入table[0]位置(即HashMap散列表的第一个位置)；而且table[0]处只会容纳一个key为null的值，当有多个key为null的值插入的时候，table[0]会保留最后插入的value

2.2.5、通过Iterator迭代器遍历时，遍历的顺序不同

　　HashMap是“从前向后”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历

　　Hashtabl是“从后往前”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历

　　HashMap和Hashtable都实现Map接口，所以支持获取它们“key的集合”、“value的集合”、“key-value的集合”，然后通过Iterator对这些集合进行遍历。由于“key的集合”、“value的集合”、“key-value的集合”的遍历原理都是一样的；下面，我以遍历“key-value的集合”来进行说明。HashMap 和Hashtable 遍历"key-value集合"的方式是：(01) 通过entrySet()获取“Map.Entry集合”。

1 // 返回“HashMap的Entry集合” 2 public Set
      
       
        > entrySet() { 3     return entrySet0(); 4 } 5 // 返回“HashMap的Entry集合”，它实际是返回一个EntrySet对象 6 private Set
        
         
          > entrySet0() { 7     Set
          
           
            > es = entrySet; 8 return es != null ? es : (entrySet = new EntrySet()); 9 }10 // EntrySet对应的集合11 // EntrySet继承于AbstractSet，说明该集合中没有重复的EntrySet。12 private final class EntrySet extends AbstractSet
            
             
              > {13 ...14 public Iterator
              
               
                > iterator() {15 return newEntryIterator();16 }17 ...18 }19 // 返回一个“entry迭代器”20 Iterator
                
                 
                  > newEntryIterator() {21 return new EntryIterator();22 }23 // Entry的迭代器24 private final class EntryIterator extends HashIterator
                  
                   
                    > {25 public Map.Entry
                    
                      next() {26 return nextEntry();27 }28 }29 private abstract class HashIterator
                     
                       implements Iterator
                      
                        {30 // 下一个元素31 Entry
                       
                         next;32 // expectedModCount用于实现fail-fast机制。33 int expectedModCount;34 // 当前索引35 int index;36 // 当前元素37 Entry
                        
                          current;38 39 HashIterator() {40 expectedModCount = modCount;41 if (size > 0) { // advance to first entry42 Entry[] t = table;43 // 将next指向table中第一个不为null的元素。44 // 这里利用了index的初始值为0，从0开始依次向后遍历，直到找到不为null的元素就退出循环。45 while (index < t.length && (next = t[index++]) == null)46 ;47 }48 }49 50 public final boolean hasNext() {51 return next != null;52 }53 54 // 获取下一个元素55 final Entry
                         
                           nextEntry() {56 if (modCount != expectedModCount)57 throw new ConcurrentModificationException();58 Entry
                          
                            e = next;59 if (e == null)60 throw new NoSuchElementException();61 62 // 注意！！！63 // 一个Entry就是一个单向链表64 // 若该Entry的下一个节点不为空，就将next指向下一个节点;65 // 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。66 if ((next = e.next) == null) {67 Entry[] t = table;68 while (index < t.length && (next = t[index++]) == null)69 ;70 }71 current = e;72 return e;73 }74 75 ...76 }

View Code

(02) 通过iterator()获取“Map.Entry集合”的迭代器，再进行遍历。

1 public Set
      
       
        > entrySet() { 2     if (entrySet==null) 3         entrySet = Collections.synchronizedSet(new EntrySet(), this); 4     return entrySet; 5 } 6  7 private class EntrySet extends AbstractSet
        
         
          > { 8     public Iterator
          
           
            > iterator() { 9 return getIterator(ENTRIES);10 }11 ...12 }13 14 private class Enumerator
            
              implements Enumeration
             
              , Iterator
              
                {15 // 指向Hashtable的table16 Entry[] table = Hashtable.this.table;17 // Hashtable的总的大小18 int index = table.length;19 Entry
               
                 entry = null;20 Entry
                
                  lastReturned = null;21 int type;22 23 // Enumerator是 “迭代器(Iterator)” 还是 “枚举类(Enumeration)”的标志24 // iterator为true，表示它是迭代器；否则，是枚举类。25 boolean iterator;26 27 // 在将Enumerator当作迭代器使用时会用到，用来实现fail-fast机制。28 protected int expectedModCount = modCount;29 30 Enumerator(int type, boolean iterator) {31 this.type = type;32 this.iterator = iterator;33 }34 35 // 从遍历table的数组的末尾向前查找，直到找到不为null的Entry。36 public boolean hasMoreElements() {37 Entry
                 
                   e = entry;38 int i = index;39 Entry[] t = table;40 /* Use locals for faster loop iteration */41 while (e == null && i > 0) {42 e = t[--i];43 }44 entry = e;45 index = i;46 return e != null;47 }48 49 // 获取下一个元素50 // 注意：从hasMoreElements() 和nextElement() 可以看出“Hashtable的elements()遍历方式”51 // 首先，从后向前的遍历table数组。table数组的每个节点都是一个单向链表(Entry)。52 // 然后，依次向后遍历单向链表Entry。53 public T nextElement() {54 Entry
                  
                    et = entry;55 int i = index;56 Entry[] t = table;57 /* Use locals for faster loop iteration */58 while (et == null && i > 0) {59 et = t[--i];60 }61 entry = et;62 index = i;63 if (et != null) {64 Entry
                   
                     e = lastReturned = entry;65 entry = e.next;66 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);67 }68 throw new NoSuchElementException("Hashtable Enumerator");69 }70 71 // 迭代器Iterator的判断是否存在下一个元素72 // 实际上，它是调用的hasMoreElements()73 public boolean hasNext() {74 return hasMoreElements();75 }76 77 // 迭代器获取下一个元素78 // 实际上，它是调用的nextElement()79 public T next() {80 if (modCount != expectedModCount)81 throw new ConcurrentModificationException();82 return nextElement();83 }84 85 ...86 87 }

View Code

2.2.6、容量的初始值和增加方式都不一样

　　HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”。

　　Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”。

2.2.7、添加key-value时的hash值算法不同

　　HashMap添加元素时，是使用自定义的hash算法。

　　Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。

2.3、HashMap和Hashtable的使用场景

其实，若我们了解了它们之间的不同之处后，可以很容易的区分不同情况下如何选择哪一种集合。

例如：

　　(01)若在单线程中，我们往往会选择HashMap，而在多线程中则会选择Hashtable。

　　(02)若不能插入null元素，则选择Hashtable；否则，可以选择HashMap。

但这个不是绝对的标准。例如，在多线程中，我们可以自己对HashMap进行同步，也可以选择ConcurrentHashMap。当HashMap和Hashtable都不能满足自己的需求时，还可以考虑新定义一个类，继承或重新实现散列表；当然，一般情况下是不需要的了。

3、HashMap和WeakHashMap异同

3.1、HashMap和WeakHashMap的相同点

它们都是散列表，存储的是“键值对”映射。

它们都继承于AbstractMap，并且实现Map基础。

它们的构造函数都一样。

它们都包括4个构造函数，而且函数的参数都一样。

默认的容量大小是16，默认的加载因子是0.75。

它们的“键”和“值”都允许为null。

它们都是“非同步的”。

3.2、HashMap和WeakHashMap的不同点

3.2.1、HashMap实现了Cloneable和Serializable接口，而WeakHashMap没有。

　　HashMap实现Cloneable，意味着它能通过clone()克隆自己。

　　HashMap实现Serializable，意味着它支持序列化，能通过序列化去传输。

3.2.2、HashMap的“键”是“强引用(StrongReference)”，而WeakHashMap的键是“弱引用(WeakReference)”

WeakReference的“弱键”能实现WeakReference对“键值对”的动态回收。当“弱键”不再被使用到时，GC会回收它，WeakReference也会将“弱键”对应的键值对删除。

这个“弱键”实现的动态回收“键值对”的原理呢？其实，通过WeakReference(弱引用)和ReferenceQueue(引用队列)实现的。首先，我们需要了解WeakHashMap中：

第一，“键”是WeakReference，即key是弱键。

第二，ReferenceQueue是一个引用队列，它是和WeakHashMap联合使用的。当弱引用所引用的对象被垃圾回收，Java虚拟机就会把这个弱引用加入到与之关联的引用队列中。 WeakHashMap中的ReferenceQueue是queue。

第三，WeakHashMap是通过数组实现的，我们假设这个数组是table。

3.3、HashMap和WeakHashMap的比较测试程序

1 package com.collection.baozi;  2 import java.util.HashMap;  3 import java.util.Iterator;  4 import java.util.Map;  5 import java.util.WeakHashMap;  6 import java.util.Date;  7 import java.lang.ref.WeakReference;  8   9 /** 10  * HashMap 和 WeakHashMap比较程序 11  *  12  */ 13 public class CompareHashmapAndWeakhashmap { 14  15     public static void main(String[] args) throws Exception { 16  17         // 当“弱键”是String时，比较HashMap和WeakHashMap 18         compareWithString(); 19         // 当“弱键”是自定义类型时，比较HashMap和WeakHashMap 20         compareWithSelfClass(); 21     } 22  23     /** 24      * 遍历map，并打印map的大小 25      */ 26     private static void iteratorAndCountMap(Map map) { 27         // 遍历map 28         for (Iterator
       iter = map.entrySet().iterator(); 29                 iter.hasNext();  ) { 30             @SuppressWarnings("rawtypes") 31             Map.Entry en = (Map.Entry)iter.next(); 32             System.out.printf("map entry : %s - %s\n ",en.getKey(), en.getValue()); 33         } 34  35         // 打印HashMap的实际大小 36         System.out.printf(" map size:%s\n\n", map.size()); 37     } 38  39     /** 40      * 通过String对象测试HashMap和WeakHashMap 41      */ 42     private static void compareWithString() { 43         // 新建4个String字符串 44         String w1 = new String("W1"); 45         String w2 = new String("W2"); 46         String h1 = new String("H1"); 47         String h2 = new String("H2"); 48  49         // 新建 WeakHashMap对象，并将w1,w2添加到 WeakHashMap中 50         Map
      
        wmap = new WeakHashMap
       
        (); 51         wmap.put(w1, "w1"); 52         wmap.put(w2, "w2"); 53  54         // 新建 HashMap对象，并将h1,h2添加到 WeakHashMap中 55         Map
        
          hmap = new HashMap
         
          (); 56         hmap.put(h1, "h1"); 57         hmap.put(h2, "h2"); 58  59         // 删除HashMap中的“h1”。 60         // 结果：删除“h1”之后，HashMap中只剩下 h2 ！ 61         hmap.remove(h1); 62  63         // 将WeakHashMap中的w1设置null，并执行gc()。系统会回收w1 64         // 结果：w1是“弱键”，被GC回收后，WeakHashMap中w1对应的键值对，也会被从WeakHashMap中删除。 65         //       w2是“弱键”，但它不是null，不会被GC回收；也就不会被从WeakHashMap中删除。 66         // 因此，WeakHashMap中只有 w2 67         // 注意：若去掉“w1=null” 或者“System.gc()”，结果都会不一样！ 68         w1 = null; 69         System.gc(); 70  71         // 遍历并打印HashMap的大小 72         System.out.printf(" -- HashMap --\n"); 73         iteratorAndCountMap(hmap); 74  75         // 遍历并打印WeakHashMap的大小 76         System.out.printf(" -- WeakHashMap --\n"); 77         iteratorAndCountMap(wmap); 78     } 79  80     /** 81      * 通过自定义类测试HashMap和WeakHashMap 82      */ 83     private static void compareWithSelfClass() { 84         // 新建4个自定义对象 85         Self s1 = new Self(10); 86         Self s2 = new Self(20); 87         Self s3 = new Self(30); 88         Self s4 = new Self(40); 89          90         // 新建 WeakHashMap对象，并将s1,s2添加到 WeakHashMap中 91         Map
          
            wmap = new WeakHashMap
           
            (); 92 wmap.put(s1, "s1"); 93 wmap.put(s2, "s2"); 94 95 // 新建 HashMap对象，并将s3,s4添加到 WeakHashMap中 96 Map
            
              hmap = new HashMap
             
              (); 97 hmap.put(s3, "s3"); 98 hmap.put(s4, "s4"); 99 100 // 删除HashMap中的s3。101 // 结果：删除s3之后，HashMap中只有 s4 ！102 hmap.remove(s3);103 104 // 将WeakHashMap中的s1设置null，并执行gc()。系统会回收w1105 // 结果：s1是“弱键”，被GC回收后，WeakHashMap中s1对应的键值对，也会被从WeakHashMap中删除。106 // w2是“弱键”，但它不是null，不会被GC回收；也就不会被从WeakHashMap中删除。107 // 因此，WeakHashMap中只有 s2108 // 注意：若去掉“s1=null” 或者“System.gc()”，结果都会不一样！109 s1 = null;110 System.gc();111 112 /*113 // 休眠500ms114 try {115 Thread.sleep(500);116 } catch (InterruptedException e) {117 e.printStackTrace();118 }119 // */120 121 // 遍历并打印HashMap的大小122 System.out.printf(" -- Self-def HashMap --\n");123 iteratorAndCountMap(hmap);124 125 // 遍历并打印WeakHashMap的大小126 System.out.printf(" -- Self-def WeakHashMap --\n");127 iteratorAndCountMap(wmap);128 }129 130 private static class Self { 131 int id;132 133 public Self(int id) {134 this.id = id;135 }136 137 // 覆盖finalize()方法138 // 在GC回收时会被执行139 protected void finalize() throws Throwable {140 super.finalize();141 System.out.printf("GC Self: id=%d addr=0x%s)\n", id, this);142 } 143 }144 }

View Code

1 -- HashMap -- 2 map entry : H2 - h2 3   map size:1 4  5  -- WeakHashMap -- 6 map entry : W2 - w2 7   map size:1 8  9  -- Self-def HashMap --10 map entry : CompareHashmapAndWeakhashmap$Self@1ff9dc36 - s411   map size:112 13  -- Self-def WeakHashMap --14 GC Self: id=10 addr=0xCompareHashmapAndWeakhashmap$Self@12276af2)15 map entry : CompareHashmapAndWeakhashmap$Self@59de3f2d - s216   map size:1

3、TreeMap的应用场景

3.1、TreeMap的简单介绍

TreeMap的实现原理：基于红黑树实现的排序Map

TreeMap的常用功能的时间复杂度：TreeMap的增删改查和统计相关的操作的时间复杂度都为 O(logn)

TreeMap对Key和Value的特殊要求：由于实现了Map接口，则key的值不允许重复（重复则覆盖），也不允许为null，按照key的自然顺序排序或者Comparator接口指定的排序方法进行排序；value允许重复，也允许为null，当key重复时，会覆盖此value值。

3.2、TreeMap、HashMap、LinkedHashMap的使用场景

需要基于排序的统计功能：由于TreeMap是基于红黑树的实现的排序Map，对于增删改查以及统计的时间复杂度都控制在O(logn)的级别上，相对于HashMap和LikedHashMap的统计操作的(最大的key，最小的key，大于某一个key的所有Entry等等)时间复杂度O(n)具有较高时间效率。

需要快速增删改查的存储功能：相对于HashMap和LikedHashMap 这些 hash表的时间复杂度O(1)（不考虑冲突情况），TreeMap的增删改查的时间复杂度为O(logn)就显得效率较低。

需要快速增删改查而且需要保证遍历和插入顺序一致的存储功能：相对于HashMap和LikedHashMap 这些 hash表的时间复杂度O(1)（不考虑冲突情况），TreeMap的增删改查的时间复杂度为O(logn)就显得效率较低。但是HashMap并不保证任何顺序性。LikedHashMap额外保证了Map的遍历顺序与put顺序一致的有序性。

注意：它们都是非线程安全的

3.3、TreeMap的特别说明