在本文中如果您
发现了
错误,请您花费几分钟的时间给予指出,谢谢!!
本文主要总结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, UI
Defaults,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。
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
那么Entry到底是怎么实现的呢?
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
......
上面代码其实告诉我们Entry是一个结点,它持有下一个元素的引用,这样就构成了一个链表。
那么,整体上来说HashMap底层就是使用这样一个数据结构来实现的。
我们提到使用Hash,但是Hash值如何与元素的存储建立关系呢?(Hash
算法)
在数据结构课中我们学习过Hash的简单算法,就是给你一个Hash因子,通过对该元素的hashCode简单的求余,来实现对其快速的定位和索引。
在HashMap中有这样的代码:
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
这个方法在HashMap中非常重要,凡是与查询、添加、删除有关的方法中都有调用该方法,为什么这么短的一个代码使用率这么高?根据代码
注释我们知道,这个方法是根据hashCode及当前table的长度(数组的长度,不是map的size)得到该元素应该存放的位置,或者在table中的索引。
现在我们需要看一下当数据量已经超过初始定义的负载因子时,HashMap如
何处理?
在HashMap中当数据量很多时,并且已经达到了负载限度时,会重新做一次哈希,也就是说会再散列。调用的方法为resize(),并且java默认传入的参数为2*table.length。先看一下JDK源码:
/**
* 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)
上面的构造方法,我们会发现这样的代码:
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
……
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的遍历方法,在我的博客中有专门写到HashMap的遍历方法:http://blog.csdn.net/tsyj810883979/article/details/6746274
? LinkedHashMap的特点、实现机制及使用方法
a) LinkedHashMap的特点:
LinkedHashMap继承自HashMap并且实现了Map接口。和HashMap一样,LinkedHashMap允许key和value均为null。
于该数据结构和HashMap一样使用到hash算法,因此它不能保证映射的顺序,尤其是不能保证顺序持久不变(再哈希)。
如果你想在多
线程中使用,那么需要使用Collections.synchronizedMap方法进行外部
同步。
LinkedHashMap与HashMap的不同之处在于,LinkedHashMap维护者运行于所有条目的双重链接列表,此链接列表可以是插入顺序或者访问顺序。
b) LinkedHashMap的实现机制:
无法总结下去,在网上看到这样一篇文章:http://zhangshixi.iteye.com/blog/673789
感觉真的没办法总结下去了。
? HashMap与Hashtable的区别:
Hashtable实现Map接口,继承自古老的Dictionary类,实现一个key-value的键值映射表。任何非空的(key-value)均可以放入其中。
区别主要有三点:
1. Hashtable是基于陈旧的Dictionary实现的,而HashMap是基于Java1.2引进的Map接口实现的;
2. Hashtable是
线程安全的,而HashMap是非线程安全的,我们可以使用外部同步的方法解决这个问题。
3. HashMap可以允许你在列表中放一个key值为null的元素,并且可以有任意多value为null,而Hashtable不允许键或者值为null。
? WeakHashMap的特点:
我没有使用过这个类。网摘:WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。(后续使用后进行总结)
? Properties及TreeMap在后续内容里进行总结。