Map集合

字数统计: 1.7k字 | 阅读时长: 6分

2019-01-05 java 阅读量8

Map

Map 是广义 Java 集合框架中的另外一部分，Hashtable、HashMap、TreeMap 都是最常见的一些 Map 实现，是以键值对的形式存储和操作数据的容器类型。

典型区别

Hashtable 是早期 Java 类库提供的一个哈希表实现，本身是同步的，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用。
HashMap 是应用更加广泛的哈希表实现，行为上大致上与 HashTable 一致，主要区别在于 HashMap 不是同步的，支持 null 键和值等。通常情况下，HashMap 进行 put 或者 get 操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选，比如，实现一个用户 ID 和用户信息对应的运行时存储结构。
TreeMap 则是基于红黑树的一种提供顺序访问的 Map，和 HashMap 不同，它的 get、put、remove 之类操作都是 O（log(n)）的时间复杂度，具体顺序可以由指定的 Comparator 来决定，或者根据键的自然顺序来判断。

HashMap 在并发环境可能出现无限循环占用 CPU 、size 不准确等诡异的问题。我认为这是一种典型的使用错误，因为 HashMap 明确声明不是线程安全的数据结构，如果忽略这一点，简单用在多线程场景里，难免会出现问题。

理解导致这种错误的原因，也是深入理解并发程序运行的好办法。对于具体发生了什么，你可以参考这篇很久以前的分析。

Map 整体结构

元素特征

在阿里巴巴手册中也有注意说明Map类集合K/V的存储情况；对于 TreeMap 中 Key 能不能为null，可以取决于Comparator接口，当实现Comparator接口时，若未对null情况进行判断，则key不可以为null，反之亦然。

顺序特性

HashTable、HashMap具有无序特性。
TreeMap是利用红黑树来实现的

红黑树特点
- 树中的每个左子树都小于等于父节点
- 树中的每个右子树都大于等于父节点
实现了 SortedMap接口 ，能够对保存的记录根据键进行排序。
- 一般需要排序的情况下是选择TreeMap进行，默认为升序排序（深度优先搜索），也可以自定义实现 Comparator接口 实现排序方式，或 Comparable接口（自然顺序）。使用场景也就是自定义排序.

LinkedHashMap 通常提供的是遍历顺序符合插入顺序，它的实现是通过为条目（键值对）维护一个双向链表。注意，通过特定构造函数，我们可以创建反映访问顺序的实例，所谓的 put、get、compute 等，都算作“访问”。

对于 LinkedHashMap 适用于一些特定应用场景，例如，我们构建一个空间占用敏感的资源池，希望可以自动将最不常被访问的对象释放掉，这就可以利用 LinkedHashMap 提供的机制来实现，参考下面的示例：

import java.util.LinkedHashMap;
import java.util.Map;  
public class LinkedHashMapSample {
    public static void main(String[] args) {
        LinkedHashMap<String, String> accessOrderedMap = new LinkedHashMap<>(16, 0.75F, true){
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) { // 实现自定义删除策略，否则行为就和普遍 Map 没有区别
                return size() > 3;
            }
        };
        accessOrderedMap.put("Project1", "Valhalla");
        accessOrderedMap.put("Project2", "Panama");
        accessOrderedMap.put("Project3", "Loom");
        accessOrderedMap.forEach( (k,v) -> {
            System.out.println(k +":" + v);
        });
        // 模拟访问
        accessOrderedMap.get("Project2");
        accessOrderedMap.get("Project2");
        accessOrderedMap.get("Project3");
        System.out.println("Iterate over should be not affected:");
        accessOrderedMap.forEach( (k,v) -> {
            System.out.println(k +":" + v);
        });
        // 触发删除
        accessOrderedMap.put("Project4", "Mission Control");
        System.out.println("Oldest entry should be removed:");
        accessOrderedMap.forEach( (k,v) -> {// 遍历顺序不变
            System.out.println(k +":" + v);
        });
    }
}

初始化和增长方式

初始化时：
- HashTable在不指定容量的情况下默认容量为11，且不要求底层数组的容量一定要为2的整数次幂；
- HashMap默认容量为 1 << 4 (为16)，且要求容量一定为2的整数次幂。
扩容时：
- HashTable 将容量扩容到原来的2倍加1
- HashMap 将容量扩容带原来的2倍

线程安全

HashTable 其方法函数都是同步的（采用synchronized修饰），不会出现两个线程同时对数据进行操作的情况，因此保证了线程安全性。
- 也正因为如此，在多线程运行环境下效率表现非常低下。因为当一个线程访问HashTable的同步方法时，其他线程也访问同步方法就会进入阻塞状态。比如当一个线程在添加数据时候，另外一个线程即使执行获取其他数据的操作也必须被阻塞，大大降低了程序的运行效率，在新版本中已被废弃，不推荐使用。
TreeMap和HashMap都是线程不安全的。如果需要同步有两种方法：
1. 可以用 Collections的synchronizedMap方法；
2. 使用 ConcurrentHashMap类，相较于HashTable锁住的是对象整体， ConcurrentHashMap基于lock实现锁分段技术。
  - 首先将Map存放的数据分成一段一段的存储方式，然后给每一段数据分配一把锁，当一个线程占用锁访问其中一个段的数据时，其他段的数据也能被其他线程访问。
  - ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性，而且性能上有长足的提升。

HashMap

HashMap 的性能表现非常依赖于哈希码的有效性，请务必掌握 hashCode 和 equals 的一些基本约定，比如

equals 相等，hashCode 一定要相等。
重写了 hashCode 也要重写 equals。
hashCode 需要保持一致性，状态改变返回的哈希值仍然要一致。
equals 的对称、反射、传递等特性。

类似 hashCode 和 equals 的约定，在TreeMap也会有模棱两可的情况出现，自然顺序同样需要符合一个约定，就是 compareTo 的返回值需要和 equals 一致，否则就会出现模棱两可情况。

我们可以分析 TreeMap 的 put 方法实现：

public V put(K key, V value) {
    Entry<K,V> t = …
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // ...
}

重点在于 cmp = cpr.compare(key, t.key); 这行代码，当我不遵守约定时，两个不符合唯一性（equals）要求的对象被当作是同一个（因为，compareTo 返回 0），这会导致歧义的行为表现。

参考

无限循环占用 CPU：https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6423457
hashMap并发安全使用问题：http://mailinator.blogspot.com/2009/06/beautiful-race-condition.html