HashMap 随记

HashMap 构造器

HashMap 共有四个构造器：

public HashMap(int initialCapacity, float loadFactor) {
    // 对于传入的初始容量（loadFactor） 及 负载因子（loadFactor）的一些边界判断
    if (initialCapacity < 0) 
    	throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY) 
    	initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) 
    	throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    // 设值
    this.loadFactor = loadFactor;
    // 返回给定目标容量的二次方大小
    this.threshold = tableSizeFor(initialCapacity);
}
// 调用了 HashMap(int initialCapacity, float loadFactor)，其中 loadFactor 取默认值 DEFAULT_LOAD_FACTOR
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
// 容量及负载因子皆使用默认值
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; }
// 调用 putMapEntries 将值存入当前 hashmap
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

在上面构造器中存在一个方法【tableSizeFor】，这个方法的作用是：返回给定目标容量的二次方大小。

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

换句话说，HashMap 的默认容量为16，而容量是以2的次方扩充的（即使是自定义传入，也一定会经过转换，如传入30，则返回32），一是为了提高性能使用足够大的数组，二是为了能使用位运算代替取模预算；

HashMap 的实现原理

数据存储方式示例图：

在 JDK1.8 中，HashMap采用【位桶（数组table）+链表+红黑树】实现，当链表长度超过阈值（8）时，将链表转换为红黑树（table长度大于等于64），这样大大减少了查找时间；链表长度大于8时转化为红黑树，小于6时转化为链表；

HashMap put 方法：

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with key, or
 *         null if there was no mapping for key.
 *         (A null return can also indicate that the map
 *         previously associated null with key.)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

其中 hash 方法：

// 计算 hash code
static final int hash(Object key) {
    int h;
    // key.hashCode 的调用方法：Object 中的原生方法 public native int hashCode();
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

重头戏，putVal 方法：

/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
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;
}

头大，分解来看：

总体结构：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    /**
     * tab 用于保存 table 引用
     * 1、若 tab 为 null 或者 tab 的长度为 0，则调用 resize 方法进行初始化或者扩容
     */
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
     /**
     * 2、到了这一步，tab 一定存在
     * i = (n - 1) & hash 确定元素存放在 tab 中的下标，p = tab[i] 
     */
    // 2.1、若 p 为 null，表示当前 tab 的 i 位置空，则可以直接直接构建 Node 插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else { // 2.2、若 p 不为 null，表示 tab 的 i 位置已经有值，则继续进行内部判断
        Node<K,V> e; K k;
        // ... 后续单独理解
    }
     /**
     * modCount 自增，记录操作行为次数
     * 3、++size > threshold，即判断下一次增加一个结点后size是否大于最大容量，如果是，则进行一次扩容
     */
    ++modCount;
    if (++size > threshold)
        resize();
    // 插入成功时会调用的方法（默认实现为空）
    afterNodeInsertion(evict);
    return null;
}

从 1 ~ 3 共三个步骤中，理解 putVal 方法大的执行方向。其中最复杂的是 2.2 中 else 中 的内容：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // ...
    else {
        Node<K,V> e; K k;
        // 已知：p = tab[i]，是 tab[i] 中链表或者红黑树第一个结点
        // 如果 p.hash 和 p.key 与传入参数中的 hash 和 key 相同，表示对应 key 已经存在，则直接使用原结点，只需要后面改变value即可
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果 p 是红黑树结点类型，则将其插入 tab[i] 位置中的红黑树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { // p 是链表结点类型，则将其插入 tab[i] 位置中的链表中
            // 循环，尾插法
            for (int binCount = 0; ; ++binCount) {
                // 链表尾部
                if ((e = p.next) == null) {
                    // 构建新结点，并修改 p 的 next 指向
                    p.next = newNode(hash, key, value, null);
                    /**
                     * TREEIFY_THRESHOLD：将链表转换为红黑树的阈值（默认为8），超过该阈值执行 treeifyBin 方法
                     * 注意：执行 treeifyBin 方法并不代表一定会将链表转换为红黑树，它会根据 table 的总长度来决定，即：
                     * 只有当 table 的长度大于等于 64 后，才会执行转换红黑树操作，否则只会对 table 进行扩容
                     */
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 这里会判断整条链表上的结点的key、Hash值与插入的元素的key、Hash值是否相等（前面只判断了链表中的第一个结点 p）
                // 如果相等，同前面一样，表示已经存在key值相同的结点【e = p.next，其中 e 已经赋值了】，则直接退出循环
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            /**
            * public V put(K key, V value) {
            *     return putVal(hash(key), key, value, false, true);
            * }
            * 这里 onlyIfAbsent 为 false，则 !onlyIfAbsent 为 true，进而执行 e.value = value 【新值替换旧值】
            */
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            /**
             * 在HashMap中：void afterNodeAccess(Node p) { }
             * 实际上，afterNodeAccess 是提供给LinkedHashMap类【继承HashMap】使用，LinkedHashMap 可以保证输入输出顺序的一致性
             * 类似的还有 afterNodeInsertion、afterNodeRemoval 这两个方法
             */
            afterNodeAccess(e); // 这里默认实现为空
            return oldValue;
        }
    }
    // ...
    return null;
} 

putVal 方法中还涉及一些其他方法，如：

1. resize：初始化或加倍表大小。如果 table 为空，则会根据字段阈值中保持的初始容量目标进行分配。
2. treeifyBin：判断是否需要将链表替换为红黑树
   a. replacementTreeNode：将链表结点 Node 转换为树结点 TreeNode
   b. treeify：形成从该节点链接的节点的树
3. Node：链表结点
4. TreeNode：红黑树结点，关于红黑树的实现及对应操作，后续有机会再另讲

putVal 方法流程图（仅用于辅助理解源码）：

其他

关于其他的方法，如 get、entrySet、ketSet 等，都可以在理解上述代码后再去看源码即可

关于红黑树：需要首先理解红黑树概念，再回头来看这里的源码更有效果（TODO：红黑树及HashMap红黑树源码理解）

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
    // ...省略几百行
}

补充1：HashSet

HashSet 的底层实现是 HashMap，来看 HashSet 的无参构造器：

/**
 * Constructs a new, empty set; the backing HashMap instance has
 * default initial capacity (16) and load factor (0.75).
 */
public HashSet() {
    map = new HashMap<>();
}

add 方法：

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

这里是把传入的值，作为 map 的 key 传入，而 value 统一为 PRESENT【private static final Object PRESENT = new Object();】

HashSet 之所以可以保证数据不会重复，其关键在于调用了 HashMap 的 put 方法：

// ...
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); // 通过hash计算【add】方法传入的e的下标i，若在table[i]不存在则构建结点保存
else {
    // 如果结点存在，则判断 key 与 hash 值是否都相同，具体流程此处不再赘述
    Node<K,V> e; K k;
    if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    // ...
}
 // ...

也就是说，HashSet 利用 HashMap 中 key 值不能重复的特性来保证其存入的值不会重复。

HashSet 中其他方法基本都基于 HashMap 的方法，此处不再赘述。