Map

Java 中提供了多种类型的 Map，比如 HashMap TreeMap 等，但有些 Map 要求 key 不能为 null，有些 Map 要求 value 不能为 null，究其原因到底为何？本文记录自己对这些问题的一些思考和猜测，如有不对之处欢迎批评指正。

先说现状

• HashTable JDK1.0 引入，key 和 value 都不可为 null
• HashMap JDK1.2 引入，key 和 value 都可以为 null
• LinkedHashMap JDK1.4 引入，key 和 value 都可以为 null
• TreeMap JDK1.2 引入，key 不能为 null，value 可以为 null
• ConcurrentHashMap JDK1.5 引入，key 和 value 都不可为 null

再说思考

在 JDK1.0 版本就引入了 HashTable，由于 HashTable 是线程安全的，可以多线程使用，因此如果 value 允许为 null，那么当需要判断是否包含某个 key 时，必然是调用 containsKey 方法来判断，当再调用 get 方法获取对应的 value 时，因为可以多线程使用该 HashTable，那么其他线程可能在此期间修改了对应的 key，导致返回值发生变化，可能出现不存在的情况。为应对这种情况，那么势必要通过加锁保证 containsKey 和 get 用是原子的，但这样一来用户使用的成本就增加了，任何接口的设计者肯定不期望这样的事情发生，故而不允许 value 为 null，那么通过判断返回值是否为 null 就可以得知是否存在对应的 key。

至于 HashTable key 不能为 null 暂时没有想到合理的解释，不过可以从如下的官方描述文档中猜测一二，设计者要求所有 key 都实现 hashCode 和 equals 方法，Java中只有非 null 的对象才实现了这两个方法。

This class implements a hash table, which maps keys to values. Any non-null object can be used as a key or as a value.

To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method.

随后在 JDK1.2 版本中引入了 HashMap 和 TreeMap，这两个都不是线程安全的 Map，因此通常都是在单线程中操作，不用考虑线程安全问题。对于上述判断是否存在某个 key 的问题，就可以通过 containsKey 方法判断，然后通过 get 方法获取对应的 value，因此 value 可以为 null。

对于 HashMap 的 key 而言，设计者可能考虑 key 也并非不可为 null，只需对 null 的 key 特殊处理即可，代码中也确实如此（具体原因暂未想到合理解释）

对于 TreeMap 的 key 而言，无参构造的情况下 key 应实现 Comparable 接口，并通过 compareTo 方法对 key 进行排序，如果 key 为 null，则无法调用 compareTo 方法。

在 JDK1.4 版本中引入了 LinkedHashMap，这是一个维护了链表结构的 Map，可以用于构建 LRU 缓存，继承自 HashMap，因此其 key 和 value 都和 HashMap 的要求保持一致，都可以为 null。

在 JDK1.5 版本中引入了支持并发的、线程安全的 ConcurrentHashMap，从官方描述文档中可以看到是对标 HashTable 的，保持了统一的功能特性，因此 key 和 value 都不能为 null

A hash table supporting full concurrency of retrievals and high expected concurrency for updates. This class obeys the same functional specification as java.util.Hashtable, and includes versions of methods corresponding to each method of Hashtable.

最后分析源码

HashTable

JDK1.0 开始引入 HashTable，是线程安全的，可以用于多线程场景

分析 put 操作

方法入口先对 value 判空，并创建对应的 Entry 实例；调用 key 的 hashCode 方法获取 hash 值，要求 key 不能为 null

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}
复制代码

分析 get 操作

调用 key 的 hashCode 方法计算 hash 值，如果不存在 key 对应的 Entry 实例则返回 null，因此可以通过返回值是否为 null 判断是否存在对应的 key

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}
复制代码

HashMap

JDK2.0 开始引入HashMap

分析 put 操作

对于 key，先调用 hash 方法计算 key 的 hash 值，如果 key == null 则取 0，否则取对应的 hashCode 方法参与计算；对于 value，在 putVal 时将 value 存储在内部类 Node 中，并没有特别的判空操作。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
复制代码

分析 get 操作

如果 key 对应的内部类 Node 实例不存在则返回 null，这就意味着仅靠判断返回值是否为 null 无法判断 Map 中是否包含该元素

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
复制代码

LinkedHashMap

JDK1.4 开始引入 LinkedHashMap，LinkedHashMap 继承自 HashMap

分析 get 操作

重写了父类的 get 方法，主要增加了 afterNodeAccess 方法可以用于 LRU 缓存等

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
复制代码

put 操作直接继承父类，不再分析

TreeMap

JDK1.2 开始引入 TreeMap，是一个有序 Map，使用自定义 Comparator 实现排序或者基于 key 的 Comparable#compareTo 方法来排序。

A Red-Black tree based NavigableMap implementation. The map is sorted according to the Comparable natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

分析 put 操作

如果构造时没有提供 Comparator 实现，则要求 key 一定不能为 null，否则无法调用 Comparable#compareTo 方法，因此统一考虑这两种方式，要求 key 不能为 null。value 并没有判空操作，直接用于构造内部类 Entry

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    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);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}
复制代码

分析 get 操作

获取 key 对应的 Entry，如果获取不到则返回 null，因此仅通过返回值是否为 null 无法判断是否存在该 key

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}
复制代码

ConcurrentHashMap

JDK1.5 开始引入 ConcurrentHashMap 是线程安全的，可以用于多线程场景

分析 put 操作

对 key 和 value 进行空校验，不能为空

public V put(K key, V value) {
    return putVal(key, value, false);
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    
    // 省略以下内容
}

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}
复制代码

分析 get 操作

直接调用 key 的 hashCode 方法获取 hash 值，如果不存在对应的 value 则直接返回 null

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}
复制代码