Java - Map 集合简单介绍

本文简单介绍一下 Java 中 Map 集合，包括 HashMap，HashTable，LinkedHashMap。

HashMap

HashMap 内部用于存放键值对<key,value>，其中 key 可以为null。

HashMap 内部使用数组加链表(1.8+红黑树)的结构实现。数组元素的类型为 Entry，Entry 是链表的节点，也代表了一个键值对。

HashMap 初始化时可以指定两个参数：initialCapacity(默认为16) 与 loadFactor(默认为0.75)。

• initialCapacity 对应初始化数组的长度。capacity 最总会为 比 initialCapacity 刚好大的 2 的 n 方的一个数。
• loadFactor 扩容因子，用来衡量何时对 Map 进行扩容。

当 Entry > (int)(capacity * loadFactor) 时，则会进行扩容，每次扩容到 capacity * 2 。

put 数据时，会计算 key 的 hash 并求模，得到放入 Entry[] 的下标，其中 null key 坐标为 0。写入对应链表(1.8超过8就转为红黑树)。其中计算hash使用如下公式：

index = hash(key) & (capacity - 1)

使用 & 具有较好的性能，限制 capacity 为 2的n方, 就保证了取模结果的离散型。

在迭代map时，另外的线程修改Map，会抛出 ConcurrentModificationException, 在迭代开始时，Map 迭代器会得到当前 Map 的修改次数，若在迭代过程中修改次数发生了变化，则会抛出该异常。

另外 HashSet 内部是使用 HashMap 的 key 的特性实现的。

HashTable

算是已经被弃用。

与 HashMap 的区别：

• 继承结构不同，HashTable 继承自 Dictionary, HashMap 继承自 AbstractMap。
• HashMap 允许 key 为 null，而 HashTable 不允许。
• HashMap 不是线程安全的，而 HashTable 是。

LinkedHashMap

LinkedHashMap 是 HashMap 的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用 LinkedHashMap。

LinkedHashMap 实现与 HashMap 的不同之处在于，LinkedHashMap 维护着一个运行于所有元素的双重链接列表。此链接列表标定了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

插入顺序： 保留元素插入的顺序。
访问顺序： get() 方法访问元素的顺序，当元素访问后，元素放入链表的末尾，以此来达成访问顺序的维护，使用构造函数的 accessOrder=true 开启。

LinkedHashMap 允许插入 key 为 null，且不是线程安全的。

LinkedHashMap 的 Entry 关键代码如下， before, after 即为双向链表的前置与后置引用：

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    Entry<K,V> before, after;
    ……
}

当添加了新的元素并且 Map 已满时，可以选择删除掉末尾的元素，如果方法 removeEldestEntry(Entry<K,V> eldest) 返回 false，则不会进行删除(默认)，反之则会进行删除。使用该特性，可以使用 LinkedHashMap 构建 LRU 缓存。

---

参考：
Java集合学习指南_Java开发中文手册[PDF]下载-极客学院Wiki