Java 集合-Map

本文将介绍 Java 集合中的 Map。

一、什么是 Map？

Map 用于存储键值对。

二、常用方法

方法 说明
put(key, value) 添加元素
remove(key) 根据 key 删除元素
get(key) 根据 key 获取元素
containsKey(key) 判断集合中是否有指定的 key
containsValue(value) 判断集合中是否有指定的 value
keySet() 返回所有 key 组成的 Set
values() 返回所有 value 组成的 Set
entrySet() 返回所有键值对组成的集合
  • entrySet()：该方法将会返回一个 Set，Set 由 Map.Entry 形式的所有对象组成

三、HashMap - Java7

1. 特点

  • 基于哈希表实现

2. initialCapacity

initialCapacity 表示哈希表的初始大小。

可以通过构造函数指定，如果没有指定，则初始大小默认为 16。

3. loadFactor

loadFactor 表示哈希表的扩容因子。

可以通过构造函数指定，如果没有指定，则扩容因子默认为 0.75。

当 键值对数量size > 扩容因子loadFactor * 哈希表大小 时，容器将自动扩容并重新哈希。

4. hashCode() 和 equals()

使用 HashMap 时，应该注意元素的 hashCode() 和 equals()。

其中，hashCode() 决定了对象会被放入哪个 bucket 中；equals() 决定了两个对象是否相同。

5. 哈希冲突

不同元素哈希计算所得到的值可能相同，因此会发生哈希冲突。

针对哈希冲突，HashMap - Java7 采取拉链法。

6. 扩容机制

HashMap 扩容分为两步：

  • 创建一个新的桶数组
  • 遍历原数组，将其中所有的 Entry 重新 Hash 到新数组

需要注意的是，HashMap1.7 中，在链表上插入新元素时使用头插法，如果多个线程同时进行扩容，可能在新的桶数组中构成环形链表，从而导致死循环。

四、HashMap - Java8

1. 特点

  • Java8 对 HashMap 进行了修改，引入了红黑树

2. 红黑树

红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。

3. 为什么引入红黑树？

在 HashMap - Java7 中，查找步骤为：

  • 根据 hash 值快速定位到某个 bucket
  • 顺着链表找到具体的元素，

查找的时间复杂度与链表的长度相关，为 O(1 + N)。

为了降低开销，在 Java8 中，当链表中的元素达到 8 个，会将链表转换为红黑树，将查找的时间复杂度将为 o(1 + logN)。

4. 扩容机制

在 HashMap1.8 中，在链表上插入新元素时使用尾插法，从而可以避免死循环问题。

五、LinkedHashMap

1. 特点

  • 与 HashMap 相比，维护了键的顺序

    顺序默认为插入顺序，另外，LinkedHashMap 提供了一个构造函数，可以将顺序改为访问顺序

  • 继承自 HashMap，在 HashMap 的基础上增加了双向链表

  • 由于有双向链表，遍历时只需要遍历链表即可

2. 顺序的维护

LinkedHashMap 在 HashMap 的基础上，采用双向链表的形式将所有的键值对连接起来，保证元素的迭代顺序和插入顺序相同。

3. 数据淘汰机制

(1) removeEldestEntry

LinkedHashMap 中有方法 removeEldestEntry，用于指示是否删除 “末尾” 键值对，如下：

1
2
3
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

每次插入键值对后，LinkedHashMap 会调用该方法，当返回 true 时，删除 “末尾” 节点。

因此，可以继承 LinkedHashMap 类并重写该方法，当键值对个数超过一定数量时，删除 “末尾” 节点。

(2) 实现 FIFO 缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class FIFOCache<K, V> extends LinkedHashMap<K, V> {
    
    private final int cacheSize;
    
    public FIFOCache(int cacheSize) {
        this.cacheSize = cacheSize;
    }

    /**
     * 当键值对个数超过一定数量时，删除"最后插入的"节点
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
       return size() > cacheSize;
    }
}

(3) 实现 LRU 缓存

使用 LinkedHashMap 的 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 构造函数，将顺序指定为访问顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int cacheSize;

    public LRUCache(int cacheSize) {
        super(16, 0.75F, true);
        this.cacheSize = cacheSize;
    }

    /**
     * 当键值对个数超过一定数量时，删除"最近最少使用的"节点
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > cacheSize;
    }
}

六、WeakHashMap

1. 特点

  • 与 HashMap 相比，WeakHashMap 并不保证键值对的存活。如果某个 key 只被 WeakHashMap 引用，则它存在被回收的可能，进而将可能导致键值对被回收

2. 自动清理机制

(1) 引用

具体请看：

JVM 引用

(2) Reference 抽象类

Reference 抽象类是对引用的抽象。

(3) WeakReference 类

WeakReference 类是 Reference 抽象类的子类，代表弱引用。

WeakReference 对象不会阻止其引用对象被回收。

(4) 基于 WeakReference 的键值对

摘抄 WeakReference 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {
    
    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {

        V value;

        /**
         * Creates new entry.
         */
        Entry(Object key, V value,
              ReferenceQueue<Object> queue,
              int hash, Entry<K,V> next) {
            super(key, queue);
            this.value = value;
            this.hash  = hash;
            this.next  = next;
        }
    }
    
}

键值对类 Entry 继承自 WeakReference，持有 key 的弱引用和 value 的强引用。

(5) ReferenceQueue

ReferenceQueue 是一个队列，通过 ReferenceQueue，可以获取到 “引用的对象已被回收” 的 Reference。

摘抄 Reference 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public abstract class Reference<T> {
    
    volatile ReferenceQueue<? super T> queue;
    
    Reference(T referent, ReferenceQueue<? super T> queue) {
        this.referent = referent;
        this.queue = (queue == null) ? ReferenceQueue.NULL : queue;
    }
    
    /**
     * Adds this reference object to the queue with which it is registered,
     * if any.
     *
     * <p> This method is invoked only by Java code; when the garbage collector
     * enqueues references it does so directly, without invoking this method.
     */
    public boolean enqueue() {
        return this.queue.enqueue(this);
    }
    
}

Reference 提供了构造方法 Reference(T referent, ReferenceQueue<? super T> queue)，允许在构造时传入 ReferenceQueue 的实例，该 queue 将会被保存为对象属性。

当 Reference 引用的对象被垃圾回收后，Java 会自动将 Reference 放入 ReferenceQueue 中。

(6) 自动清理机制

每当 key 被垃圾回收后，键值对将会被添加至 ReferenceQueue<Object> queue 中。

WeekHashMap 会在各种操作进行时调用 expungeStaleEntries() 方法，删除哈希表中所有 key 已经被垃圾回收的键值对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Expunges stale entries from the table.
 */
private void expungeStaleEntries() {
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) x;
            int i = indexFor(e.hash, table.length);

            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {
                Entry<K,V> next = p.next;
                if (p == e) {
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    // Must not null out e.next;
                    // stale entries may be in use by a HashIterator
                    e.value = null; // Help GC
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

3. 适用场景

缓存。

七、TreeMap

1. 特点

  • 底层基于红黑树实现

  • 会按照 key 的大小对键值对进行排序

    key 的大小评判标准既可以是元素的自然顺序，也可以通过构造时传入的 Comparator 评判

2. 红黑树

见上文。

八、ConcurrentHashMap

具体请看：

并发编程 ConcurrentHashMap

参考