容器深入研究--理解Map

Leefs 2020-01-17 AM 2109℃ 0条

容器深入研究—理解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。

非特殊说明,本博所有文章均为博主原创。

评论已关闭