容器深入研究--理解Map

Leefs 2020-01-17 AM 2018℃ 0条

# 容器深入研究--理解Map

### 前言

本篇讲述《Java编程思想》第17.8小节，理解Map

### 概述

映射表(也称关联数组)的基本思想是它维护的键-值(对)关联，因此你可以使用键来查找值。

标准的Java类库中包含了Map的几种实现，包括：`HashMap`,`TreeMap`,`LinkedHashMap`,`WeakHashMap`,`ConcurrentHashMap`,`IdentityHashMap`。

它们都有同样的基本接口Map，但是行为特性各不相同，这表现在效率、键值对的保存及呈现次序、对象的保存周期、映射表如何在多线程程序中工作的判定“键”等价的策略方面。Map接口实现的数量应该让你感觉到这种工具的重要性。

**Map的简单实现**

你可以获的对Map更深入的理解，这有助于观察关联数组是如何创建的。下面是一个极其简单的实现。

```java
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接口的可用操作**

```java
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>());
    }
}
```

> 运行结果

```basic
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。**

标签: Java编程思想, 容器深入研究, Map

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

如若转载，请注明出处：https://lilinchao.com/archives/435.html

上一篇容器深入研究--队列

下一篇基于SpringBoot的文件上传和下载

容器深入研究--理解Map

评论已关闭

栏目分类

标签云

友情链接申请

容器深入研究--理解Map

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请