阿里P8 架构师 浅谈 HashMap 的机制与原理

前言

HashMap可以说是Java程序员必知必会的东西了，基础中的基础，必会中的必会，重点中的重点；所谓万丈高楼平地起，因此，充分的了解HashMap的运行机制是很有必要的一件事

本文主要讲解 HashMap 相关的知识点

1. HashMap简介

• HashMap 是一个散列表，存储的内存是键值对的映射
• HashMap 实现了 Map 接口，根据 Key 的 HashCode 值存储数据，具有很快的访问速度，做多允许一条值为 null
• HashMap 是无序的，线程不安全的
• HashMap 继承自 AbstractMap，实现了 Map、Cloneable、Serializable 三个接口

2. 底层数据结构

如下图，HashMap 底层采用的是数组+链表/红黑树的结构

首先，HashMap 的主体是一个数组，这个数组由一个个的链表组成，而链表由一个个 Node 组成，Node 存储的是具体的 Key，Value 值，Node 会记录着下一个Node的信息

这里有几个重要的概念

• HashMap 总使用2的幂作为数组的大小，比如默认的初始化大小2的4次方等于16，其最大允许的大小是2的30次方
• 当数组里面存放的数据大于 负载因子数组大小* ，put()的过程会进行扩容
• 当链表大小大于8，数组大小大于64，会将链表转换为红黑树结构
• JDK1.8 后，插入链表的方式从头插法改为了尾插法

这几个概念在下文详细论述

3. 为什么是数组 + 链表

数组+链表的数据结构是为了解决Hash冲突而设计的

往一个 HashMap 中进行put(key, value) 操作时，先要判断这个 key 存放在数组的那个地方

1. 首先使用方法 hash(key)，得到key的hash值
2. 然后通过 (n -1) & hash（n是数组的大小） 得出一个下标，暂且称这个下标是 index，这个键值对将被存放到这个 index中

此时会有一个情况，不同的key有可能得出相同的index，这就是Hash冲突，此时就需要数组+链表的方式来解决Hash冲突

3.1 如何解决Hash冲突

HashMap 遇到 Hash 冲突时，会判断两个Key的实际值是否相等，如果相等则覆盖，如果不相等，会将这个Node插入链表的尾部，所以说，数组+链表的数据结构是为了解决Hash冲突而设计的

内部类 Node，因为集成自Map.Entry，因此也有人称 Node 为 Entry

static class Node<K,V> implements Map.Entry<K,V>

//成员变量
final int hash;
final K key;
V value;
Node<K,V> next;

3.2 头插？尾插？

既然是插入到链表中，就有插头插尾的区别

在 JDK1.7 采用的是头插法，后面加入的元素会被放在链表的头部，因为作者认为后面插入的元素被使用的概率更高，但是这个做法带来了死链的问题

于是在 JDK1.8 中，将头插法改为了尾插法

4. 由链表到红黑树的转换

随着数据在一个下标的后面不断的插入，数量会越来越大，在链表的数量大于默认阈值8之后，会调用treeifyBin()方法检查 HashMap 是否转换为红黑树，只有当数组长度大于或等于64时，才会被转换为红黑树；小于64的化，会调用resize()方法进行扩容

HashMap 内部类 TreeNode，也就是红黑树的数据结构

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;

与链表转换成红黑树相关的几个参数

//触发判断的链表阈值大小
static final int TREEIFY_THRESHOLD = 8;

//进行红黑树转换的最小数组大小
static final int MIN_TREEIFY_CAPACITY = 64;

5. HashMap的扩容机制

扩容机制，即调用了resize() 方法进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免触发扩容机制

如果安装了阿里巴巴开发规约插件，在创建一个HashMap的时候，会有这么一个提示

其目的，就是为了让你设置合适的大小，从而避免触发扩容机制

与扩容机制相关的几个参数：

• 负载因子loadFactor，其默认值是 0.75
• 数组大小capacity，刚创建时默认值时16
• 临界值threshold，超过这个值表示数组可以进行扩容了，这个值由capacity*loadFactor 得到
• 已存储Node的数量size

扩容的时候大致做了以下几件事：

1. 判断目前的容量是多少，一开始的时候是 null，第一次put() 的时候进行容量初始化，默认值是16，也可以是我们自定义的值，需要注意的是，假设我们给定的值是3，他会找大于三的2的幂来替换，也就是4，所以指定值最好是2的幂数
2. 判断目前的容量是否大于限制的最大值，如果是的话设置threshold 为Integer.MAX_VALUE，并且不触发扩容机制，随你去吧，太大了忍不了了
3. 如果没有超过最大值，就扩充为原来的两倍，临界值threshold 也同时扩充两倍
4. 将旧的 HashMap 中的元素迁移至新创建的 HashMap 中

可以结合源码看一下扩容的流程

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倍，临界值threshold 也同时扩充两倍
        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 {
        // signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize上限
    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) {
        // 把每个Node都移动到新的数组中
        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 {
                    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;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

6. HashMap 的Put机制

HashMap 开放了 Put 方法给用户添加元素，其调用的putVal()方法并没有开放给用户使用，探究Put方法的原理其实就是探究putVal() 方法

1. 首先计算 key 的 Hash 值，通过 (n -1) & hash 得到将要插入的下标
2. 如果数组是空的，调用resize() 进行初始化
3. 如果没有 Hash 冲突，直接放进该下标
4. 如果发生了 Hash 冲突，判断 Key 值是否真的相等，相等的话覆盖 Value 的值，不相等追加到链表或红黑树中
5. 在追加到链表的过程中，若是链表的大小超过了8，会调用treeifyBin() 方法来怕判断是否要转换成红黑树

总结

HashMap的原理其实并不难，但是深入到每一个细节来说，要理解清楚还是有一定难度的，希望本文的整理对你有所帮助