Map总结(HashMap, Hashtable, TreeMap, WeakHashMap等使用场景)
学完了Map的全部内容,我们再回头开开Map的框架图。
第1部分 Map概括
Map 是“键值对”映射的抽象接口。 AbstractMap 实现了Map中的绝大部分函数接口。它减少了“Map的实现类”的重复编码。 SortedMap 有序的“键值对”映射接口。 NavigableMap 是继承于SortedMap的,支持导航函数的接口。 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的定义:
publicclass HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { ... }
Hashtable的定义:
publicclass Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { ... }
从中,我们可以看出: 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的方法
// 将“key-value”添加到HashMap中 public V put(K key, V value) { // 若“key为null”,则将该键值对添加到table[0]中。 if (key == null) return putForNullKey(value); // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出! if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 若“该key”对应的键值对不存在,则将“key-value”添加到table中 modCount++; addEntry(hash, key, value, i); return null; } // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置 private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; // recordAccess()函数什么也没有做 e.recordAccess(this); return oldValue; } } // 添加第1个“key为null”的元素都table中的时候,会执行到这里。 // 它的作用是将“设置table[0]的key为null,值为value”。 modCount++; addEntry(0, null, value, 0); return null; }
Hashtable的添加key-value的方法
// 将“key-value”添加到Hashtable中 public synchronized V put(K key, V value) { // Hashtable中不能插入value为null的元素!!! if (value == null) { throw new NullPointerException(); } // 若“Hashtable中已存在键为key的键值对”, // 则用“新的value”替换“旧的value” Entry tab[] = table; // Hashtable中不能插入key为null的元素!!! // 否则,下面的语句会抛出异常! int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { V old = e.value; e.value = value; return old; } } // 若“Hashtable中不存在键为key的键值对”, // (01) 将“修改统计数”+1 modCount++; // (02) 若“Hashtable实际容量” > “阈值”(阈值=总的容量 * 加载因子) // 则调整Hashtable的大小 if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; index = (hash & 0x7FFFFFFF) % tab.length; } // (03) 将“Hashtable中index”位置的Entry(链表)保存到e中 Entry<K,V> e = tab[index]; // (04) 创建“新的Entry节点”,并将“新的Entry”插入“Hashtable的index位置”,并设置e为“新的Entry”的下一个元素(即“新Entry”为链表表头)。 tab[index] = new Entry<K,V>(hash, key, value, e); // (05) 将“Hashtable的实际容量”+1 count++; return null; }
根据上面的代码,我们可以看出:
以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索散列表
, hashmap
, 键值对
, key
, keys
, hashtable
, key-value
, value
, entry
, hashmap hashtable
, 遍历Hashtable
, hashmap与hashtable
, WeakHashMap
Hashtable的区别
,以便于您获取更多的相关知识。