容器深入研究—理解Map
前言
本篇讲述《Java编程思想》第17.8小节,理解Map
概述
映射表(也称关联数组)的基本思想是它维护的键-值(对)关联,因此你可以使用键来查找值。
标准的Java类库中包含了Map的几种实现,包括:HashMap
,TreeMap
,LinkedHashMap
,WeakHashMap
,ConcurrentHashMap
,IdentityHashMap
。
它们都有同样的基本接口Map,但是行为特性各不相同,这表现在效率、键值对的保存及呈现次序、对象的保存周期、映射表如何在多线程程序中工作的判定“键”等价的策略方面。Map接口实现的数量应该让你感觉到这种工具的重要性。
Map的简单实现
你可以获的对Map更深入的理解,这有助于观察关联数组是如何创建的。下面是一个极其简单的实现。
public class AssociativeArray<K,V> {
private Object[][] pairs;
private int index;
public AssociativeArray(int length){
pairs = new Object[length][2];
}
public void put(K key,V value){
if(index >= pairs.length){
throw new ArrayIndexOutOfBoundsException();
}
pairs[index++] = new Object[]{key,value};
}
@SuppressWarnings("unchecked")
public V get(K key){
for(int i=0;i<index;i++){
if(key.equals(pairs[i][0])){
return (V)pairs[i][1];
}
}
return null;
}
public String toString(){
StringBuilder result = new StringBuilder();
for(int i=0;i<index;i++){
result.append(pairs[i][0].toString());
result.append(" : ");
result.append(pairs[i][1].toString());
if(i < index-1){
result.append("\n");
}
}
return result.toString();
}
public static void main(String[] args) {
AssociativeArray<String,String> map = new AssociativeArray<String,String>(6);
map.put("sky","blue");
map.put("grass","green");
map.put("ocean","dancing");
map.put("tree","tall");
map.put("earth","brown");
map.put("sun","warm");
try{
map.put("extra","object");
}catch (ArrayIndexOutOfBoundsException e){
System.out.println("Too many object!");
}
System.out.println(map);
System.out.println(map.get("ocean"));
}
}
运行结果
Too many object!
sky : blue
grass : green
ocean : dancing
tree : tall
earth : brown
sun : warm
dancing
关联数组中的基本方法是put()和get(),但是为了容易显示,toString()方法被覆盖为可以打印键-值对。为了展示它可以工作,main()用字符串对加载了一个AssociativeArray
,并打印了所产生的映射表,随后是一个值的get().
为了使用get()方法,你需要传递想要查找的key,然后它会将与之相关联的值作为结果返回。或者在找不到的情况下返回null。get()方法使用的可能是能想象到的效率最差的方式来定位值的:从数组头部开始,使用equals()方法依次比较键。
性能
性能是映射表中的一个重要问题,当在get()中使用线性搜索时,执行速度会相当的慢,而这正是HashMap
提高速度的地方。
HashMap
使用了特殊的值,称作散列码,来取代对键的缓慢搜索。散列码是“相对唯一”的、用以代表对象的int值,它是通过将该对象的某些信息进行转换而生成的。
hashCode()
是根类Object中的方法,因此所有Java对象都能产生散列码,HashMap
就是使用对象的hashCode()
进行快速查询的,此方法可以显著的提高性能。
下面是基本的Map实现。在HashMap
上打星号表示如果没有其他的限制,它就应该成为你的默认选择,因为它对速度进行了优化。其他的都强调其他的特性,因此都不如HashMap
快。
Map实现 | 说明 |
---|---|
HashMap* |
Map基于散列表的实现(它取代了HashTable)。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量和负载因子,以调整容器的性能。 |
LinkedHashMap |
类似于HashMap,但是迭代遍历时,取得“键值对”的顺序是其插入次序,或者是最近最少使用(LRU)的次序。只比HashMap慢一点;而在迭代访问时反映更快,因为它使用的链表维护内部次序。 |
TreeMap |
基于红黑树的实现。查看“键”或“键值对”时,它们会被排序(次序由Comparable或者Comparator决定)。TreeMap特点在于,所得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map,它可以返回一个子树。 |
WeakHashMap |
弱键(weak key)映射,允许释放映射所指向的对象;这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个“键”,则此“键”可以被垃圾回收器回收。 |
ConcurrentHashMap |
一种线程安全的Map,它不涉及同步加锁。 |
IdentityHashMap |
使用==代替equals()对“键”进行比较的散列映射。专为解决特殊问题设计的。 |
散列是映射中存储元素的最常用的方式。
对Map中使用的键的要求与对Set中的元素的要求一样。任何键都必须有一个equals()方法;如果键被用于散列Map,那么它必须还具有恰当的hashCode()
方法;如果键被用于TreeMap它必须实现Comparable。
对Map接口的可用操作
public class Maps {
public static void printKeys(Map<Integer,String> map) {
System.out.println("Size = " + map.size() + ", ");
System.out.println("Keys: ");
System.out.print(map.keySet());
}
public static void test(Map<Integer,String> map) {
System.out.print(map.getClass().getSimpleName());
map.putAll(new CountingMapData(25));
map.putAll(new CountingMapData(25));
printKeys(map);
System.out.println("Values: ");
System.out.print(map.values());
System.out.print(map);
System.out.print("map.containsKey(11): " + map.containsKey(11));
System.out.print("map.get(11): " + map.get(11));
System.out.print("map.containsValue(\"F0\"): "
+ map.containsValue("F0"));
Integer key = map.keySet().iterator().next();
System.out.print("First key in map: " + key);
map.remove(key);
printKeys(map);
map.clear();
System.out.print("map.isEmpty(): " + map.isEmpty());
map.putAll(new CountingMapData(25));
map.keySet().removeAll(map.keySet());
System.out.print("map.isEmpty(): " + map.isEmpty());
}
public static void main(String[] args) {
test(new HashMap<Integer,String>());
test(new TreeMap<Integer,String>());
test(new LinkedHashMap<Integer,String>());
test(new IdentityHashMap<Integer,String>());
test(new ConcurrentHashMap<Integer,String>());
test(new WeakHashMap<Integer,String>());
}
}
运行结果
HashMapSize = 25,
Keys:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]Values:
[A0, B0, C0, D0, E0, F0, G0, H0, I0, J0, K0, L0, M0, N0, O0, P0, Q0, R0, S0, T0, U0, V0, W0, X0, Y0]{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0, 9=J0, 10=K0, 11=L0, 12=M0, 13=N0, 14=O0, 15=P0, 16=Q0, 17=R0, 18=S0, 19=T0, 20=U0, 21=V0, 22=W0, 23=X0, 24=Y0}map.containsKey(11): truemap.get(11): L0map.containsValue("F0"): trueFirst key in map: 0Size = 24,
Keys:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]map.isEmpty(): truemap.isEmpty(): trueTreeMapSize = 25,
Keys:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]Values:
[A0, B0, C0, D0, E0, F0, G0, H0, I0, J0, K0, L0, M0, N0, O0, P0, Q0, R0, S0, T0, U0, V0, W0, X0, Y0]{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0, 9=J0, 10=K0, 11=L0, 12=M0, 13=N0, 14=O0, 15=P0, 16=Q0, 17=R0, 18=S0, 19=T0, 20=U0, 21=V0, 22=W0, 23=X0, 24=Y0}map.containsKey(11): truemap.get(11): L0map.containsValue("F0"): trueFirst key in map: 0Size = 24,
Keys:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]map.isEmpty(): truemap.isEmpty(): trueLinkedHashMapSize = 25,
Keys:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]Values:
[A0, B0, C0, D0, E0, F0, G0, H0, I0, J0, K0, L0, M0, N0, O0, P0, Q0, R0, S0, T0, U0, V0, W0, X0, Y0]{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0, 9=J0, 10=K0, 11=L0, 12=M0, 13=N0, 14=O0, 15=P0, 16=Q0, 17=R0, 18=S0, 19=T0, 20=U0, 21=V0, 22=W0, 23=X0, 24=Y0}map.containsKey(11): truemap.get(11): L0map.containsValue("F0"): trueFirst key in map: 0Size = 24,
Keys:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]map.isEmpty(): truemap.isEmpty(): trueIdentityHashMapSize = 25,
Keys:
[14, 20, 2, 24, 15, 0, 16, 22, 12, 11, 21, 19, 17, 6, 3, 8, 5, 9, 7, 13, 10, 4, 18, 23, 1]Values:
[O0, U0, C0, Y0, P0, A0, Q0, W0, M0, L0, V0, T0, R0, G0, D0, I0, F0, J0, H0, N0, K0, E0, S0, X0, B0]{14=O0, 20=U0, 2=C0, 24=Y0, 15=P0, 0=A0, 16=Q0, 22=W0, 12=M0, 11=L0, 21=V0, 19=T0, 17=R0, 6=G0, 3=D0, 8=I0, 5=F0, 9=J0, 7=H0, 13=N0, 10=K0, 4=E0, 18=S0, 23=X0, 1=B0}map.containsKey(11): truemap.get(11): L0map.containsValue("F0"): falseFirst key in map: 14Size = 24,
Keys:
[20, 2, 24, 15, 0, 16, 22, 12, 11, 21, 19, 17, 6, 3, 8, 5, 9, 7, 13, 10, 4, 18, 23, 1]map.isEmpty(): truemap.isEmpty(): trueConcurrentHashMapSize = 25,
Keys:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]Values:
[A0, B0, C0, D0, E0, F0, G0, H0, I0, J0, K0, L0, M0, N0, O0, P0, Q0, R0, S0, T0, U0, V0, W0, X0, Y0]{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0, 9=J0, 10=K0, 11=L0, 12=M0, 13=N0, 14=O0, 15=P0, 16=Q0, 17=R0, 18=S0, 19=T0, 20=U0, 21=V0, 22=W0, 23=X0, 24=Y0}map.containsKey(11): truemap.get(11): L0map.containsValue("F0"): trueFirst key in map: 0Size = 24,
Keys:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]map.isEmpty(): truemap.isEmpty(): trueWeakHashMapSize = 25,
Keys:
[24, 22, 23, 20, 21, 18, 19, 16, 17, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]Values:
[Y0, W0, X0, U0, V0, S0, T0, Q0, R0, P0, O0, N0, M0, L0, K0, J0, I0, H0, G0, F0, E0, D0, C0, B0, A0]{24=Y0, 22=W0, 23=X0, 20=U0, 21=V0, 18=S0, 19=T0, 16=Q0, 17=R0, 15=P0, 14=O0, 13=N0, 12=M0, 11=L0, 10=K0, 9=J0, 8=I0, 7=H0, 6=G0, 5=F0, 4=E0, 3=D0, 2=C0, 1=B0, 0=A0}map.containsKey(11): truemap.get(11): L0map.containsValue("F0"): trueFirst key in map: 24Size = 24,
Keys:
[22, 23, 20, 21, 18, 19, 16, 17, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]map.isEmpty(): truemap.isEmpty(): true
总结
printKeys()展示了如何生成Map的Collection视图。KeySet()方法返回由Map的键组成的Set。
评论已关闭