浅谈 HashMap

---

前言

HashMap 是 Java 编程中非常常用的一种数据结构，在各种面试中也是频繁出现的问题。我是一次定位问题，发现了服务后台 CPU 和内存飙升，原因是使用 HashMap 的时候，并发插入数据在 resize() 方法中产生循环链表导致死循环（JDK8 已经解决）。看到代码中大量的 HashMap，不自然的就想先了解下 HashMap 的实现原理和其线程安全问题。此文主要是介绍 HashMap 的实现原理，关于如何定位 CPU 和内存飙升问题，可以看另外一篇博客：

Jstack 使用介绍 | 笑话人生

存储结构

HashMap 是一种存储 key -> value键值对的数据结构，每一个键值对称为 Entry，这些 Entry 存储在一个 table 数组中，每个 Entry 是一个链表结构，有一个 next 指针指向下一个元素。接下来我们看一下比较重要的代码。

/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}
/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;
/**
 * The number of key-value mappings contained in this map.
 */
transient int size;
/**
 * The number of times this HashMap has been structurally modified
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure (e.g.,
 * rehash).  This field is used to make iterators on Collection-views of
 * the HashMap fail-fast.  (See ConcurrentModificationException).
 */
transient int modCount;
/**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
/**
 * The load factor for the hash table.
 *
 * @serial
 */
final float loadFactor;

• Node 就是上面说的 Entry 的实现，用来保存键值对，实现了 Map.Entry 接口。其中 hash 的值是通过 hash() 方法计算出来，key 和 value 是存入的值，next 是出现哈希冲突的时候，会使用 next 指向链表中的下一个元素对象。
• table 存储 Entry 的数组，初始长度是 DEFAULT_INITIAL_CAPACITY = 16。
• size 是实际存储的键值对数量。
• modCount 记录内部结构发生的次数，比如 put、remove 操作等。常见的一边遍历元素一边删除元素的操作就会报 java.util.ConcurrentModificationException。
• loadFactor 负载因子，默认是 DEFAULT_LOAD_FACTOR = 0.75f。
• threshold 允许存储的最大元素数量是通过 table 数组长度 * loadFactor 负载因子得出。

put 操作

在 put 操作中，将元素 key 进行 hash 计算并找到 table 的数组下标，将 Entry 直接放入数组中，作为头元素，若通过算法得到的该数组元素已经有了元素（俗称 hash 冲突，链表结构出现的实际意义也就是为了解决 hash 冲突的问题）。当新来的 Entry 映射到冲突的数组位置时，只需要插入到对应的链表即可。接下来直接在源码上解释。

/**
 * 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;
    // 首先判断 table 数组是否为空，为空则创建 table。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果通过 (n - 1) & hash 找到的数组元素为空，则直接创建新的 node，作为头节点。
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 找到数组元素，判断是相同的 key 值。
        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 {
            // 该数组元素 hash 相等，key 不等，同时链表长度 < 8。进行遍历寻找元素，有就覆盖无则新建
            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
                        // 链表长度 >=8 结构转为红黑树
                        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;
        }
    }
    // 内部结构变化次数 +1
    ++modCount;
    // 当 map 的实际大小大于了 threshold 则进行 resize 操作，将最大存储数量变为原来的两倍。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

这里确定 table 的数组下标使用的 hash 算法是 (n - 1) & hash(key)，相对于取模运算，使用位运算效率更高。key 值的 hash 计算是高 16bit 不变，低 16bit 和高 16bit 做了一个异或。主要是为了保证 n 太小的时候，高低位均能参与下标的计算。

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

get 操作

get 方法通过 hash 寻找到 Entry 数组下标，找到头节点，然后顺着对应链表的头节点，一个一个向下来查找。由于 JDK8 引用了红黑树结构，在链表元素过多时，JDK8 的实现将比 JDK7 在 get 和 put 操作上效率高上很多。

/**
 * Implements Map.get and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
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;
}

resize 操作

当 map 的实际大小大于了 threshold 则进行 resize 操作，将最大存储数量变为原来的两倍。接下来我们看一下源码。

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    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)
            newThr = oldThr << 1; // double threshold
    }
    // 第一次初始化
    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"})
    // 新的 table 数组 
    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;
                // 直接按照原始索引放入新数组中
                if (e.next == null)
                    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;
}

线程安全

HashMap 是非线程安全的，在多线程环境下对某个 HashMap 进行并行操作，可能会产生很多不可预期的情况。

多线程 put 导致元素丢失

实验代码如下：

public static void main(String[] args) throws InterruptedException {
    HashMap<Integer, Integer> map = new HashMap<>();
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < 10000; i++) {
        list.add(i);
    }

    list.forEach(i -> map.put(i, i));
    new Thread(() -> {
        for (int i = 10000; i < 20000; i++) {
            map.put(i, i);
        }
    }).start();
    new Thread(() -> {
        for (int i = 20000; i < 30000; i++) {
            map.put(i, i);
        }
    }).start();

    Thread.sleep(3000);
    System.out.println(map.entrySet().size());
}

输出：29402，元素少了很多。

这里很好理解，我们看 put 的代码，假设我们的线程1和线程2同时在执行 put 方法。其中的的 key 值计算后落入了 table 的同一个位置。这个时候，两个线程同时执行p.next = newNode(hash, key, value, null);，此时两个线程的元素值就会互相覆盖掉。

put 的同时 get 数据，可能会导致 get 的数据为 null

put 的时候，可能会产生 resize 操作，我们发现 resize 有如下代码：

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

这段代码会让新的 table 为空，这个时候调用 get 方法会获取到 null 数据。

JDK7 中并发 put 会造成循环链表

此问题在 JDK8 中已经解决，在这里是提醒下自己 JDK7 中的 resize 操作会产生循环链表导致死循环，毕竟之前项目中确确实实遇到了死循环的问题。

Jstack 使用介绍 | 笑话人生

总结

1. 什么时候会使用 HashMap？他有什么特点？
   是基于 Map 接口的实现，存储键值对时，它可以接收 null 的键值，HashMap 存储着 Entry 对象。HashMap 是非线程安全的。如果需要线程安全，则使用 ConcurrentHashMap，否则使用 HashMap 就足够了。

2. 你知道 HashMap 的工作原理吗？equals() 和 hashCode() 的都有什么作用？
   通过对 key 的 hashCode() 计算下标 n - 1 & hash，从而获得 table 下标的位置，然后用 key.equals() 方法去链表或树中去查找对应的节点。get 和 put 方法如上介绍。

3. 你知道 hash 的实现吗？为什么要这样实现？
   在 Java 1.8 的实现中，是通过 key.hashCode() 的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在 table 的长度 n 比较小的时候，也能保证考虑到高低 bit 都参与到 hash 的计算中，同时不会有太大的开销。

4. 如果 HashMap 的大小超过了负载因子(load factor)定义的容量，怎么办？
   如果超过了负载因子(默认0.75)，则会重新 resize 一个原来长度两倍的 HashMap，并且重新调用 hash 方法。

感谢

HashMap 底层实现原理 | 忆逝
什么是HashMap | 小灰
Java HashMap工作原理及实现 | Yikun
深入解读HashMap线程安全性问题 | Mr羽墨青衫
HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你！ | crossoverJie

---

文章标题：浅谈 HashMap
文章作者：cylong
文章链接：https://0skyu.cn/posts/7744.html
有问题或者建议欢迎在下方评论。欢迎转载、引用，但希望标明出处，感激不尽(●’◡’●)