剖析 HashMap • Sun Blog

HashMap 是一个键值对存储结构，通过一个「键」（Key）可以快速地查找到对应的「值」（Value）

Map 接口#

Map 有键和值的概念。一个键映射到一个值，Map 按照键存储和访问值，键不能重复，即一个键只会存储一份，给同一个键重复设值会覆盖原来的值，使用 Map 可以方便地处理需要根据键访问对象的场景

Map 接口的定义如下：

public interface Map<K,V> {
	int size();  // 返回 Map 中键值对的数量
	boolean isEmpty();  // 判断 map 是否为空
	boolean containsKey(Object key);  // 判断 map 是否包含指定的键
	boolean containsValue(Object value);  // 判断 map 是否包含指定的值
	V get(Object key);  // 根据键获取值，不存在键返回 null
	V put(K key, V value);  // 存入键值对，如果原来 key 存在，返回原来的值
	V remove(Object key);  // 删除键值对，返回值
	void putAll(Map<? extends K, ? extends V> m);  // 保存 m 中所有键值对到当前 map
	void clear();  // 清空 map
	Set<K> keySet(); // 返回一个 Set 包含 map 中所有的键
	Collection<V> values();  // 返回一个 Collection 包含 map 中所有的值
	Set<Map.Entry<K, V>> entrySet();  // 返回一个 Entry 集合

	interface Entry<K,V> {  // 键值对接口
		K getKey();
		V getValue();
		V setValue(V value);
		boolean equals(Object o);
		int hashCode();
		// 返回一个比较器，默认按照键的字典序排序
		public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> c1.getKey().compareTo(c2.getKey());
        }
		// 返回一个比较器，按照值的字典序排序
        public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> c1.getValue().compareTo(c2.getValue());
        }
		// 返回一个比较器，使用给定的 Comparator 按键比较
        public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
            Objects.requireNonNull(cmp);
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
        }
        public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
            Objects.requireNonNull(cmp);
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
        }
	}
	
	boolean equals(Object o);
	int hashCode();
	// 根据键返回值，如果键不存在，返回给定的默认值 defaultValue
    default V getOrDefault(Object key, V defaultValue);
	// 对 map 中的每个键值对执行给定的操作
	default void forEach(BiConsumer<? super K, ? super V> action)；
	// 将每个键值对的值替换为对该键值对调用给定函数的结果
	default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)；
}

java

HashMap#

内部组成#

在 Java8 中 HashMap 底层的数据结构是 数组 + 链表/红黑树

HashMap 内部主要有以下实例变量

transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;

// 继承自 AbstractMap<K,V>
transient Set<K> keySet;
transient Collection<V> values;

java

entrySet keySet values 分别缓存了 HashMap 的键值对、键和值，size 表示实际键值对的个数。

threshold 表示阈值，当键值对个数 size 大于等于 threshold 时考虑进行扩展，一般而言，threshold 等于 table.length 乘以 loadFactor。loadFactor 是负载因子，表示整体上 table 被占用的程度，是一个浮点数，默认为 0.75, 可以通过构造方法进行修改。

table 是一个 Node 类型的数组，每一个元素称为一个哈希桶，其中的每个元素指向一个单向链表，链表的每个节点表示一个键值对。Node 是一个静态内部类：

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

java

其中 key 和 value 分别表示键和值，next 指向下一个 Node，hash 是键的哈希值，直接存储 hash 值便于在比较的时候加快计算

构造函数#

默认的无参构造函数，构建一个空的 HashMap，使用默认初始容量（16）和默认负载因子（0.75）

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
	static final float DEFAULT_LOAD_FACTOR = 0.75f;

java

可以指定初始容量和负载因子

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initialCapacity, float 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);
	}

java

this.threshold = tableSizeFor(initialCapacity); 的目的是计算出大于或等于给定容量 <initialCapacity 的最小的 2 的幂次方数作为 table 容量暂存到 threshold 字段里

保存键值对 put#

put 方法用于将一个键值对保存到 HashMap 中，代码如下

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

java

主要是先调用 hash 方法计算 key 的 hash 值

如果 key 是 null：直接返回 0。这是 HashMap 的规定，null key 的哈希值就是 0。
如果 key 不是 null：执行 (h = key.hashCode()) ^ (h >>> 16)，调用 key 对象自身的 hashCode() 方法，然后将 h 的二进制表示向右移动 16 位，再与 h 异或，将原始哈希码的高 16 位信息与低 16 位信息混合在了一起，减少 hash 冲突

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

java

然后调用 putVal 方法：

boolean onlyIfAbsent: 一个非常重要的标志位。
- 如果为 true（对应 putIfAbsent 方法），那么只有当 key 不存在时才会插入 value。如果 key 已存在，则不做任何操作。
- 如果为 false（对应 put 方法），那么无论 key 是否存在，都会用新的 value 覆盖旧的 value。
boolean evict: 这个参数主要用于 LinkedHashMap（HashMap 的子类）。在 HashMap 本身中，这个值总是 true。在 LinkedHashMap 中，当它被用作实现 LRU 缓存时，evict 为 false 可能表示这是一个「预备」插入，暂时不触发淘汰策略。

首先判断 table 是不是空表，是的话调用 resize() 方法创建一个新表

如果 tab[i = (n - 1) & hash]) == null 表示无哈希冲突，就直接创建一个新的 Node 节点并放入这个桶中

否则表示存在哈希冲突，又分为几种情况

1）桶的第一个节点就是目标 key

(p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) 首先比较哈希值，如果哈希值不同肯定不同，即使哈希值相同了可能存在哈希冲突也不一定相同；接下来检查两个 key 的引用是否相同，如果引用不同再调用 key 的 equals() 方法进行比较

如果确认是同一个 key，就把 p 赋值给 e

2）桶内是红黑树且第一个节点不是目标 key

调用 ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 方法

3）桶内是链表且第一个节点不是目标 key

binCount 是一个无限循环，同时还记录了链表长度，通过 e=p.next p=e 遍历链表，如果 e==null 说明遍历结束了，仍然没有找到相同的 key，就将新节点插入到链表后面 p.next = newNode(hash, key, value, null)

如果插入之后 binCount >= TREEIFY_THRESHOLD-1 TREEIFY_THRESHOLD 是一个常量值为 8，也就是链表长度达到 8 时需要对链表进行树化，转换为红黑树，调用 treeifyBin(tab, hash) 方法，该方法内部还会检查当前 table 数组的长度是否小于 MIN_TREEIFY_CAPACITY（默认 64），如果小于，它会优先选择扩容 resize() 而不是树化。

如果遍历过程中找到了相同的 key，就直接退出循环

最后判断如果 e!=null 则说明存在一个相同 key 的节点，就根据 onlyIfAbsent 的值判断是否要替换节点的值

afterNodeAccess(e): 这是一个回调方法，HashMap 本身是空实现。但 LinkedHashMap 会重写它，用来将访问过的节点移动到链表末尾，以实现 LRU 顺序

如果 e 是 null，说明插入了一个全新的节点，需要修改 modCount 和 size 的值，如果 size > threshold 还需要进行扩容

afterNodeInsertion(evict): 另一个回调方法。HashMap 是空实现，LinkedHashMap 会重写它来处理新插入节点的链接关系

    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; // 创建 table
        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;
    }

java

resize() 方法负责在 HashMap 的容量不足时进行扩容和数据迁移

整个方法可以分成两个部分：计算新容量和阈值并扩容、迁移数据

先看计算新容量和阈值，分为三种情况：

1）Map 已经有数据了，需要扩容，此时 oldCap > 0 即 oldTab.length > 0

首先判断容量是否达到最大值，即 oldCap >= MAXIMUM_CAPACITY 如果是的话就将阈值设置为 Integer.MAX_VALUE 这样以后就不会触发扩容了

如果容量没有达到最大值，就将新容量设置成原来的 2 倍，newCap = oldCap << 1，并且新阈值也变为老阈值的 2 倍

2）Map 未初始化但是指定了初始容量

此时 oldThr > 0 因为在构造函数中将初始容量存在了阈值中，新容量就等于阈值 newCap = oldThr

3）Map 未初始化，且未指定初始容量，即使用无参构造函数

此时 newCap = DEFAULT_INITIAL_CAPACITY 默认初始容量为 16，newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY) 阈值 = 容量 * 负载因子

在 1) 2) 两种情况下都没有对 newThr 赋值，所以接下来判断 if (newThr == 0) 则要计算新阈值

最后使用 newCap 创建一个新数组，将 table 设置为新数组

再来看数据迁移，数据迁移时遍历旧数组 oldTab，将所有元素移动到新数组 newTab，也分为三种情况

1）如果桶中只有一个元素

直接用元素的 hash 值和新容量 newCap 计算出它在新数组中的索引，然后放进去即可

2）如果桶的数据结构是红黑树，调用 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 方法

spilt() 方法中有一句

if (lc <= UNTREEIFY_THRESHOLD)
	tab[index] = loHead.untreeify(map);

java

如果红黑树的节点数小于等于 UNTREEIFY_THRESHOLD (值为 6) 需要退化成链表

3）如果桶的数据结构是链表

这部分利用了一个非常巧妙的位运算技巧来避免重新计算每个元素的 hash 索引

扩容时，新容量 newCap 是旧容量 oldCap 的两倍，oldCap 是一个 2 的幂（例如 16，二进制为 00010000）。newCap 是 oldCap 的两倍（例如 32，二进制为 00100000），所以 newCap - 1 比 oldCap - 1 在二进制表示上多了一个高位的 1，并且这个 1 就是 oldCap 的唯一一个 1

旧索引：index = hash & (oldCap - 1)
新索引：index = hash & (newCap - 1)

这意味着，一个元素在新表中的位置，要么和它在旧表中的位置一样，要么是旧位置 + oldCap，这取决于 newCap - 1 中多的那一位 1 对应元素 hash 值的位置是 0 还是 1。这个位置恰好就是 oldCap 的二进制表示中 1 所在的那一位，所以判断 (e.hash & oldCap)：

如果结果为 0：说明 hash 值在那一位上是 0。该元素的新索引与旧索引相同。
如果结果不为 0：说明 hash 值在那一位上是 1。该元素的新索引是 旧索引 + oldCap。

代码遍历链表，根据 (e.hash & oldCap) 的结果，将节点分别串联到两个新链表上：lo 链表（低位，位置不变）和 hi 链表（高位，位置偏移）。遍历完成后，lo 链表被放到新数组的 j 位置，hi 链表被放到新数组的 j + oldCap 位置。这样就高效地完成了整个链表的数据迁移。

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
		// Map 已经有数据了，需要扩容
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
				// 容量已经达到了最大值，将阈值设为最大值，以后永远不会触发扩容
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
			// 新容量设置为原来容量的 2 倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
				// 新阈值也变为老阈值的 2 倍
                newThr = oldThr << 1; // double threshold
        }
		// Map 未初始化但是指定了初始容量，初始容量是存在阈值里面的
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
		// 使用默认的无参构造函数
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
			// 阈值 = 容量 * 负载因子
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {  // 指定了初始容量的情况
            float ft = (float)newCap * loadFactor;  // 计算阈值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
		// 数据迁移
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {  // 遍历旧数组的每个桶
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null; // 释放旧数组的引用，便于GC
                    if (e.next == null) // 桶中只有一个元素
						// 直接用元素的 hash 值和新容量 newCap 计算出它在新数组中的索引，然后放进去。
                        newTab[e.hash & (newCap - 1)] = e;
					// 桶中是红黑树
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
							// 元素的新索引与旧索引相同，链表放在数组的原始位置
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)  // 尾插法插入到链表
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
							// 否则链表放在高位
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

java

查找方法#

get() 方法通过键获取值，代码为

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

java

首先调用 hash() 方法计算 key 的 hash，然后调用 getNode() 方法获取 key 对应的节点

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

java

首先检查 HashMap 中是否有数据，没有直接返回 null。然后根据检查对应哈希桶的第一个节点是否是所需的 key，是则直接返回。

如果第一个节点不是，且有下一个节点，先判断桶内是不是红黑树，是则调用 ((TreeNode<K,V>)first).getTreeNode(hash, key); 如果桶内是链表，就遍历链表知道找到对应的 key

‍

containsKey() 方法判断是否包含某个 key，逻辑与 get() 方法相同，如果返回的节点不为 null 说明存在这个 key

    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

java

‍

containsValue() 方法判断是否包含某个 value，HashMap 可以方便高效地按照键进行操作，但如果需要根据值进行操作，则需要遍历，从 table 的第一个链表开始，从上到下，从左到右逐个节点进行访问,比较值，直到找到为止

    public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

java

根据键删除键值对 remove#

remove() 方法用于根据 key 删除键值对并返回删除的值，主要是调用了 removeNode() 方法

    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

java

matchValue 为 true 时仅当值相等时移除，movable 为 false 时移除过程中不移动其他节点

一开始是查找 key 对应的节点，逻辑和 getNode() 方法中相同，如果没找到节点就直接返回 null

找到节点之后，判断下桶内是不是红黑树，是就调用 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);

如果是链表，且是第一个节点，就 tab[index] = node.next; 不是就 p.next = node.next;

    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

java

‍