摘要:本文主要向大家介绍了JAVA语言中的Map接口实现类TreeMap、HashMap、WeakHashMap、HashTable的实例讲解,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。
本文主要向大家介绍了JAVA语言中的Map接口实现类TreeMap、HashMap、WeakHashMap、HashTable的实例讲解,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。
第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中,则删除链表中的节点即可。
上面介绍了HashMap和Hashtable的相同点。正是由于它们都是散列表,我们关注更多的是“它们的区别,以及它们分别适合在什么情况下使用”。那接下来,我们先看看它们的区别。
第2.2部分 HashMap和Hashtable的不同点
1 继承和实现方式不同
HashMap 继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。
Hashtable 继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口。
HashMap的定义:
public class HashMap
Hashtable的定义:
public class Hashtable
从中,我们可以看出:
1.1 HashMap和Hashtable都实现了Map、Cloneable、java.io.Serializable接口。
实现了Map接口,意味着它们都支持key-value键值对操作。支持“添加key-value键值对”、“获取key”、“获取value”、“获取map大小”、“清空map”等基本的key-value键值对操作。
实现了Cloneable接口,意味着它能被克隆。
实现了java.io.Serializable接口,意味着它们支持序列化,能通过序列化去传输。
1.2 HashMap继承于AbstractMap,而Hashtable继承于Dictionary
Dictionary是一个抽象类,它直接继承于Object类,没有实现任何接口。Dictionary类是JDK 1.0的引入的。虽然Dictionary也支持“添加key-value键值对”、“获取value”、“获取大小”等基本操作,但它的API函数比Map少;而且 Dictionary一般是通过Enumeration(枚举类)去遍历,Map则是通过Iterator(迭代器)去遍历。 然而‘由于Hashtable也实现了Map接口,所以,它即支持Enumeration遍历,也支持Iterator遍历。关于这点,后面还会进一步说明。
AbstractMap是一个抽象类,它实现了Map接口的绝大部分API函数;为Map的具体实现类提供了极大的便利。它是JDK 1.2新增的类。
2 线程安全不同
Hashtable的几乎所有函数都是同步的,即它是线程安全的,支持多线程。
而HashMap的函数则是非同步的,它不是线程安全的。若要在多线程中使用HashMap,需要我们额外的进行同步处理。 对HashMap的同步处理可以使用Collections类提供的synchronizedMap静态方法,或者直接使用JDK 5.0之后提供的java.util.concurrent包里的ConcurrentHashMap类。
3 对null值的处理不同
HashMap的key、value都可以为null。
Hashtable的key、value都不可以为null。
我们先看看HashMap和Hashtable “添加key-value”的方法
HashMap的添加key-value的方法
1 // 将“key-value”添加到HashMap中 2 public V put(K key, V value) { 3 // 若“key为null”,则将该键值对添加到table[0]中。 4 if (key == null) 5 return putForNullKey(value); 6 // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。 7 int hash = hash(key.hashCode()); 8 int i = indexFor(hash, table.length); 9 for (Entry
Hashtable的添加key-value的方法
1 // 将“key-value”添加到Hashtable中 2 public synchronized V put(K key, V value) { 3 // Hashtable中不能插入value为null的元素!!! 4 if (value == null) { 5 throw new NullPointerException(); 6 } 7 8 // 若“Hashtable中已存在键为key的键值对”, 9 // 则用“新的value”替换“旧的value”10 Entry tab[] = table;11 // Hashtable中不能插入key为null的元素!!!12 // 否则,下面的语句会抛出异常!13 int hash = key.hashCode();14 int index = (hash & 0x7FFFFFFF) % tab.length;15 for (Entry
根据上面的代码,我们可以看出:
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。
4 支持的遍历种类不同
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遍历。
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集合”。 (02) 通过iterator()获取“Map.Entry集合”的迭代器,再进行遍历。
HashMap的实现方式:先“从前向后”的遍历数组;对数组具体某一项对应的链表,则从表头开始往后遍历。
1 // 返回“HashMap的Entry集合” 2 public Set<Map.Entry
Hashtable的实现方式:先从“后向往前”的遍历数组;对数组具体某一项对应的链表,则从表头开始往后遍历。
View Code
6 容量的初始值 和 增加方式都不一样
HashMap默认的容量大小是16;增加容量时,每次将容量变为“原始容量x2”。
Hashtable默认的容量大小是11;增加容量时,每次将容量变为“原始容量x2 + 1”。
HashMap默认的“加载因子”是0.75, 默认的容量大小是16。
1 // 默认的初始容量是16,必须是2的幂。 2 static final int DEFAULT_INITIAL_CAPACITY = 16; 3 4 // 默认加载因子 5 static final float DEFAULT_LOAD_FACTOR = 0.75f; 6 7 // 指定“容量大小”的构造函数 8 public HashMap(int initialCapacity) { 9 this(initialCapacity, DEFAULT_LOAD_FACTOR);10 }
当HashMap的 “实际容量” >= “阈值”时,(阈值 = 总的容量 * 加载因子),就将HashMap的容量翻倍。
View Code
Hashtable默认的“加载因子”是0.75, 默认的容量大小是11。
1 // 默认构造函数。2 public Hashtable() {3 // 默认构造函数,指定的容量大小是11;加载因子是0.754 this(11, 0.75f);5 }
当Hashtable的 “实际容量” >= “阈值”时,(阈值 = 总的容量 x 加载因子),就将变为“原始容量x2 + 1”。
View Code
7 添加key-value时的hash值算法不同
HashMap添加元素时,是使用自定义的哈希算法。
Hashtable没有自定义哈希算法,而直接采用的key的hashCode()。
HashMap添加元素时,是使用自定义的哈希算法。
1 static int hash(int h) { 2 h ^= (h >>> 20) ^ (h >>> 12); 3 return h ^ (h >>> 7) ^ (h >>> 4); 4 } 5 6 // 将“key-value”添加到HashMap中 7 public V put(K key, V value) { 8 // 若“key为null”,则将该键值对添加到table[0]中。 9 if (key == null)10 return putForNullKey(value);11 // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。12 int hash = hash(key.hashCode());13 int i = indexFor(hash, table.length);14 for (Entry
Hashtable没有自定义哈希算法,而直接采用的key的hashCode()。
1 public synchronized V put(K key, V value) { 2 // Hashtable中不能插入value为null的元素!!! 3 if (value == null) { 4 throw new NullPointerException(); 5 } 6 7 // 若“Hashtable中已存在键为key的键值对”, 8 // 则用“新的value”替换“旧的value” 9 Entry tab[] = table;10 int hash = key.hashCode();11 int index = (hash & 0x7FFFFFFF) % tab.length;12 for (Entry
8 部分API不同
Hashtable支持contains(Object value)方法,而且重写了toString()方法;
而HashMap不支持contains(Object value)方法,没有重写toString()方法。
最后,再说说“HashMap和Hashtable”使用的情景。
其实,若了解它们之间的不同之处后,可以很容易的区分根据情况进行取舍。例如:(01) 若在单线程中,我们往往会选择HashMap;而在多线程中,则会选择Hashtable。(02),若不能插入null元素,则选择Hashtable;否则,可以选择HashMap。
但这个不是绝对的标准。例如,在多线程中,我们可以自己对HashMap进行同步,也可以选择ConcurrentHashMap。当HashMap和Hashtable都不能满足自己的需求时,还可以考虑新定义一个类,继承或重新实现散列表;当然,一般情况下是不需要的了。
第3部分 HashMap和WeakHashMap异同
3.1 HashMap和WeakHashMap的相同点
1 它们都是散列表,存储的是“键值对”映射。
2 它们都继承于AbstractMap,并且实现Map基础。
3 它们的构造函数都一样。
它们都包括4个构造函数,而且函数的参数都一样。
4 默认的容量大小是16,默认的加载因子是0.75。
5 它们的“键”和“值”都允许为null。
6 它们都是“非同步的”。
3.2 HashMap和WeakHashMap的不同点
1 HashMap实现了Cloneable和Serializable接口,而WeakHashMap没有。
HashMap实现Cloneable,意味着它能通过clone()克隆自己。
HashMap实现Serializable,意味着它支持序列化,能通过序列化去传输。
2 HashMap的“键”是“强引用(StrongReference)”,而WeakHashMap的键是“弱引用(WeakReference)”。
WeakReference的“弱键”能实现WeakReference对“键值对”的动态回收。当“弱键”不再被使用到时,GC会回收它,WeakReference也会将“弱键”对应的键值对删除。
这个“弱键”实现的动态回收“键值对”的原理呢?其实,通过WeakReference(弱引用)和ReferenceQueue(引用队列)实现的。 首先,我们需要了解WeakHashMap中:
第一,“键”是WeakReference,即key是弱键。
第二,ReferenceQueue是一个引用队列,它是和WeakHashMap联合使用的。当弱引用所引用的对象被垃圾回收,Java虚拟机就会把这个弱引用加入到与之关联的引用队列中。 WeakHashMap中的ReferenceQueue是queue。
第三,WeakHashMap是通过数组实现的,我们假设这个数组是table。
接下来,说说“动态回收”的步骤。
(01) 新建WeakHashMap,将“键值对”添加到WeakHashMap中。
将“键值对”添加到WeakHashMap中时,添加的键都是弱键。
实际上,WeakHashMap是通过数组table保存Entry(键值对);每一个Entry实际上是一个单向链表,即Entry是键值对链表。
(02) 当某“弱键”不再被其它对象引用,并被GC回收时。在GC回收该“弱键”时,这个“弱键”也同时会被添加到queue队列中。
例如,当我们在将“弱键”key添加到WeakHashMap之后;后来将key设为null。这时,便没有外部外部对象再引用该了key。
接着,当Java虚拟机的GC回收内存时,会回收key的相关内存;同时,将key添加到queue队列中。
(03) 当下一次我们需要操作WeakHashMap时,会先同步table和queue。table中保存了全部的键值对,而queue中保存被GC回收的“弱键”;同步它们,就是删除table中被GC回收的“弱键”对应的键值对。
例如,当我们“读取WeakHashMap中的元素或获取WeakReference的大小时”,它会先同步table和queue,目的是“删除table中被GC回收的‘弱键’对应的键值对”。删除的方法就是逐个比较“table中元素的‘键’和queue中的‘键’”,若它们相当,则删除“table中的该键值对”。
3.3 HashMap和WeakHashMap的比较测试程序
1 import java.util.HashMap; 2 import java.util.Iterator; 3 import java.util.Map; 4 import java.util.WeakHashMap; 5 import java.util.Date; 6 import java.lang.ref.WeakReference; 7 8 /** 9 * @desc HashMap 和 WeakHashMap比较程序 10 * 11 * @author skywang 12 * @email kuiwu-wang@163.com 13 */ 14 public class CompareHashmapAndWeakhashmap { 15 16 public static void main(String[] args) throws Exception { 17 18 // 当“弱键”是String时,比较HashMap和WeakHashMap 19 compareWithString(); 20 // 当“弱键”是自定义类型时,比较HashMap和WeakHashMap 21 compareWithSelfClass(); 22 } 23 24 /** 25 * 遍历map,并打印map的大小 26 */ 27 private static void iteratorAndCountMap(Map map) { 28 // 遍历map 29 for (Iterator iter = map.entrySet().iterator(); 30 iter.hasNext(); ) { 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 }
运行结果:
-- HashMap --map entry : H2 - h2
map size:1
-- WeakHashMap --map entry : W2 - w2
map size:1
-- Self-def HashMap --map entry : CompareHashmapAndWeakhashmap$Self@1ff9dc36 - s4
map size:1
-- Self-def WeakHashMap --GC Self: id=10 addr=0xCompareHashmapAndWeakhashmap$Self@12276af2)
map entry : CompareHashmapAndWeakhashmap$Self@59de3f2d - s2
map size:1
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注编程语言JAVA频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号