简介

HashMap在1.8之后通过数组(table)属性使用单向链表 + 红黑树的结构组合提高查找效率，于是我大致的画了下图：

后来写着写着发现我还是太年轻了，有什么比亲手实践更值得让人信服呢？

类图分析(只标注主要属性方法)

• Map<K,V>:键值映射的基础接口，提供常用的键值映射操作方法的抽象
• Map.Entry<K,V>:键值对条目(单个键值)抽象接口
• AbstractMap<K,V>: 简单实现了Map接口的部分方法
• HashMap<K,V>: 基于Map接口的哈希实现
• HashMap.Node<K,V>:HashMap键值对条目链表结构的实现类
• HashMap.TreeNode<K,V>:HashMap键值对条目红黑树结构的实现类
• LinkedHashMap<K,V>:基于Map接口的哈希表和链表结构实现，与HashMap的主要区别在于键值对都是有序的
• LinkedHashMap.Entry<K,V>:LinkedHashMap键值条目链表结构的实现类

属性解析

• DEFAULT_INITIAL_CAPACITY：默认16，默认初始容量，必须为2的幂值
• MAXIMUM_CAPACITY：默认1<<30(即2^29)，最大容量值，如果有参构造函数容量值比该值高，则使用该值作为容量值
• DEFAULT_LOAD_FACTOR：默认0.75f，构造函数中未指定时使用的负载因子
• TREEIFY_THRESHOLD：默认8，容器树化阈值，达到阈值(8)后容器将使用红黑树结果存储数据
• UNTREEIFY_THRESHOLD：默认6，非树化阈值，应小于TREEIFY_THRESHOLD。
• MIN_TREEIFY_CAPACITY：默认64，表中节点链表结构被树化的最小表容量值，实际会根据容器大小判断是只进行扩容还是进行树化。
• loadFactor：哈希表的负载因子
• threshold：下一次调整大小的容量阈值(capacity * load factor)
• modCount：对该HashMap进行结构修改的次数。结构修改是指更改HashMap中的映射数目或以其他方式修改其内部结构的修改（如重新哈希）。
• size：包含的键-值映射数
• table：该表(节点Node数组)在首次使用时初始化，并根据需要调整大小，分配后的长度始终是2的幂。
• entrySet：用于获取key-value映射集合Set<Map.Entry<K,V>>，在首次调用entrySet()方法时被初始化

文章使用的术语掺杂了一些个人根据源码与文档的理解，需了解注意的如下：

• 表(table数组) = 容器
• table.length = 容量 != 映射数目
• table中的节点Node元素 = 桶bin
• table中的键值对节点Node以外的元素都以null填充

方法解析，窥遍HashMap

HashMap的三个构造函数

1、 无参构造函数

/**
 * 使用默认的初始容量（16）和默认的加载因子（0.75）构造一个空的HashMap。
 * 注：该方法没有初始化阈值threshold
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

1、 带初始容量的构造函数

public HashMap(int initialCapacity) {
    // 初始化容量initialCapacity、负载因子loadFactor=DEFAULT_LOAD_FACTOR(0.75)、阈值threshold
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

1、 带初始容量与f负载因子的构造函数

/**
 * 以特定的容量与负载系数构建一个空的HashMap
 *
 * @param  initialCapacity 初始容量
 * @param  loadFactor      负载因子
 * @throws IllegalArgumentException initialCapacity为负数、负载因子为负数或非数字时抛错
 */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;   // MAXIMUM_CAPACITY = 1 << 30
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 该方法主要用于设置阈值threshold，返回大于或等于参数容量cap的的2次幂，如cap=9、11、12、15、16时都会返回16，cap=5、6、7、8时返回8
 * @param cap 容量参数
 * @return 返回大于或等于参数容量cap的的2次幂
 */
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;
}

put(K, V)添加键值

由HashMap的三个构造函数可以看出构造HashMap时主要初始化了负载因子loadFactor、table扩容阈值threshold,若是无参构造函数则只初始化阈值，所以一般table的初始化都是在put第一个键值对时初始化的。

/**
 *  获取键的哈希值
 * 
 *  @param key
 *  @return key的哈希值
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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

/**
 *  创建链表节点并设置该节点指向的下一节点
 * 
 *  @param hash  键哈希值
 *  @param key   键
 *  @param value 值
 *  @param next  新建节点指向的下一节点
 *  @return      链表节点
 */
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

/**
 * 实现Map.put和相关的方法
 *
 * @param hash key的哈希值
 * @param key
 * @param value 
 * @param onlyIfAbsent true则不替换已存在的key值
 * @param evict 标志表是否处于创建模式
 * @return 返回key之前的值，之前值不存在则返回true
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 引用属性table的临时变量
    Node<K,V>[] tab; 
    // table上的节点引用(p = pointer = 链表指针)
    Node<K,V> p; 
    // n用于记录Node<K,V>[] table长度的临时变量，i为key哈希与table.length相与后的table索引index
    int n, i;
    // 1. 若table为空则初始化键值对数组table
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2 
    // 2.1 判断key哈希值与长度相与运算获取相应的数组索引值i，判断table数组i节点是否空，空则直接在该索引放置新节点，跳到`3`；不为空则该位置上的节点将会形成桶(链表|红黑树结构)链接多个节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 2.2 table[i]上的元素节点p不为空        
    else {
        // e可看作遍历table的结果节点(e = end)，k用于引用p节点的key值
        Node<K,V> e; K k;
        // 2.2.1 判断节点p与参数的key是否相同，相同即只需执行替换value，e不为null，跳到`2.2`
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 2.2.2 参数key与table[i]上的key不匹配，若table[i]的节点为TreeNode，则以TreeNode结构存放新节点，e为null,跳到`2`
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 2.2.3 参数key与table[i]上的key不匹配，且该节点并非TreeNode，则以链式节点存储
        else {
            // binCount：桶中的元素数目，即Node<K,V>[] table中的Node节点元素内的key-value键值对数目
            for (int binCount = 0; ; ++binCount) {
                // p下一节点e为空节点，则新建节点赋到当前节点的next
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 根据桶中节点数目与容量大小判断是进行扩容还是进行树化，若桶中已有的节点数>=8且容量>=64则进行树化；e为null,跳到`3`
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // p下一节点e不为空
                // p下一节点e的key与参数key相同,e不为null，跳到`2.2`
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // p下一节点e的hash或key属性与新增的key不同，则把下一节点赋给p继续进行链表遍历，直到遇到空的节点或hash、key相同的节点
                p = e;
            }
        }
        // 2.2.4 e不为空，即Node[] table中已含键为参数key的节点，则替换key的旧值
        if (e != null) { // existing mapping for key
           // 获取参数key对应节点的旧映射值
            V oldValue = e.value;
            // 设置key新的映射值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // HashMap中为空实现，主要应用在LinkedHashMap中
            return oldValue;
        }
    }
    // 3. 节点新增成功后的容器相关属性更改
    // e为空，则有新的键值对节点添加，结构发生改变，结构修改次数自增
    ++modCount;
    // 键值对数目自增，并判断自增后若大于扩容阈值，则调整容量大小
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); // HashMap中为空实现，主要应用在LinkedHashMap中
    // 不存在旧节点，返回空
    return null;
}

/**
 * 若表太小，则resize调整表大小；否则将替换bin(桶)中给定哈希值的索引中所有链接的节点Node为TreeNode。
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // tab为空或tab数组长度 < MIN_TREEIFY_CAPACITY(64)，即元素数量不多，只重新调整tab长度(容量)，节点维持链表结构而无需更改为红黑树结构
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 判断参数hash值在tab数组中相应位置的节点是否不为空
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        // 将e与e链表上链接的所有Node节点转换为TreeNode节点
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            // 将table转为红黑树结构
            hd.treeify(tab);
    }
}

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }

综上，HashMap添加键值对的流程如下：

1、 判断table是否为空，空则调用resize()初始化table数组，一般发生在初次添加键值对
2、 参数key哈希值hash与数组table长度相与获取到索引值i，根据table[i]节点是否为空执行不同的操作

• 2.1 table[i]节点p为空：在table[i]创建新节点，跳到步骤3
• 2.2 table[i]节点p不为空，根据以下不同的情况执行相应的操作
  • 2.2.1 节点p的key、hash与参数的key、hash匹配：即最终操作只需替换原有key的值，将最终节点e设为p，跳到2.2.4
  • 2.2.2 节点p是一个红黑树节点(TreeNode)类型：根据参数创建新的红黑树节点TreeNode，根据红黑树规则把新节点插入到p节点所在的红黑树上
  • 2.2.3 其它情况(即链表结构，头节点key与参数key不同)：创建新节点并链接到链表末尾，若链表节点数大于8个，则调用treeifyBin()根据table.length长度进行不同的操作
    • table.length >= 64，将所有的Node链表节点转为TreeNode红黑树节点
    • table.length < 64,调用resize()将table.length左移一位(原lengh乘2)，即使链表节点数>8依旧保持链表结构
  • 2.2.4 设置e节点key新值，返回key旧值

1、 节点新增成功后的HashMap相关操作属性更新

实力(例)验证

为了简单直接的显示HashMap结构，这个博主直接的把HashMap实例里的核心属性都print出来了。

1、 table容量<64时，key hashCode相同的节点数>8依旧会保持链表结构

public static void stringKey() throws NoSuchFieldException, IllegalAccessException {
    HashMap<String, Integer> map = new HashMap<>(32);
    // 9个hashKey相同的字符串集合，map容量<64时会在添加第9个"20kf"进行扩容而不会树化，即32则左移一位为64,集合删除"20kf"则不会扩容仍为32
    Set<String> sameHashKeys = Sets.newHashSet("30lG", "31MG", "31Lf", "30kf", "1nlG", "2PLf", "1oLf", "2OlG", "2Okf");
    Field thresholdField = HashMap.class.getDeclaredField("threshold");
    Field tableField = HashMap.class.getDeclaredField("table");
    thresholdField.setAccessible(true);
    tableField.setAccessible(true);
    Random random = new Random();
    IntStream.range(0, 10).forEach(i -> map.put(String.valueOf(i), i));
    sameHashKeys.forEach(key -> map.put(key, random.nextInt(25)));
    Set<Map.Entry<String, Integer>> sets = map.entrySet();
    Map.Entry<String, Integer>[] table = (Map.Entry<String, Integer>[]) tableField.get(map);
    long notNullCount = Arrays.stream(table)
            .filter(Objects::nonNull)
            .count();
    Set<Class> nodeClasses = Arrays.stream(table)
            .filter(Objects::nonNull)
            .map(Object::getClass)
            .collect(Collectors.toSet());
    // 输出格式化
    String tableString = JSONObject.toJSONString(table)
            .replaceAll(",null", "")
            .replaceAll("null,", "")
            .replaceAll("\\{|}|\"", "")
            .replaceAll(":", "=")
            .replaceAll(",", ", ");
    System.out.println("map.size():" + map.size() + ", table.length: " + table.length
            + ", table node count: " + notNullCount + ", entrySet size: " + sets.size());
    System.err.println("node classes: " + nodeClasses);
    map.remove("30lG");
    System.out.println("table:  " + JSONObject.toJSONString(table));
    System.out.println("evict null table: " + tableString);
    System.out.println("entrySet: " + sets);
}

控制台输出：

map.size():19, table.length: 64, table node count: 11, entrySet size: 19
node classes: [class java.util.HashMap$Node]
table:  [null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,{"31MG":22},{"0":0},{"1":1},{"2":2},{"3":3},{"4":4},{"5":5},{"6":6},{"7":7},{"8":8},{"9":9},null,null,null,null,null,null]
evict null table: [30lG=13, 0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9]
entrySet: [31MG=22, 31Lf=1, 30kf=14, 1nlG=7, 2PLf=13, 1oLf=13, 2OlG=21, 2Okf=16, 0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9]

1、 table容量>=64时，key hashCode相同的节点数>8后HashMap会树化

HashMap<String, Integer> map = new HashMap<>(33); // 有参容量自动调整为64

控制台输出：

map.size():19, table.length: 64, table node count: 11, entrySet size: 19
node classes: [class java.util.HashMap$TreeNode, class java.util.HashMap$Node]
table:  [null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,{"30kf":19},{"0":0},{"1":1},{"2":2},{"3":3},{"4":4},{"5":5},{"6":6},{"7":7},{"8":8},{"9":9},null,null,null,null,null,null]
evict null table: [30kf=19, 0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9]
entrySet: [30kf=19, 31MG=8, 31Lf=16, 1nlG=3, 2PLf=19, 1oLf=20, 2OlG=12, 2Okf=15, 0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9]

可以看到”30kf”是该红黑树上的root。

那么问题来了，添加映射会调整结构(即更改节点Node类型)，那么删除呢？这个博主有点懒，所以不讲源码给答案： HashMap删除节点的过程十分简单，获取节点类型->根据节点类型进行相应的删除操作，若节点是树节点结构，则判断该树的节点数是否较少(源码文档标注一般为2~6)，较少则把树节点TreeNode转换为普通节点Node，如上例中删除最后4个hashCode相同的节点后(即只剩下5个Node)再打印会发现没有TreeNode了。 调用链：hashmap.remove() -> hashmap.removeNode() -> treeNode.removeTreeNode() -> treeNode.untreeify(map)

reszie()调整table容量

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    // table未初始化则设旧容量为0，构造函数并没有初始化table,即首次put添加元素时oldCap都为0
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // oldCap > 0意味着并未首次添加元素时调用方法，而是键值对数量>阈值(即size>threshold)时需要扩容调用该方法，可能发生在上文put(K,V)步骤3
    if (oldCap > 0) {
        // 容量大于默认最大容量，一般可忽略该情况
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 将新容量设为旧容量的一倍，新阈值设为旧阈值的一倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // oldCap=0 & oldThr>0，该条件可能发生在调用了有参构造函数初始化threshold、loadFactor后通过put首次添加键值对,并把此时的threshold赋给newCap(有参构造函数处提及有参初始化后threshold是2的幂值)
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // oldCap=0 & oldThr=0,该条件发生在调用了`HashMap`的无参构造函数情况下，容量与阈值皆设为默认值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;  // default cap 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // default threshold 12
    }
    if (newThr == 0) {
        // float threshold，计算后的浮点型阈值
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 设置调整后的阈值
    threshold = newThr;
    // 创建新的数组进行键值对迁移，所以建议预估好键值对数量调用有参构造函数初始化`HashMap`
    @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;
                // Node单节点迁移到新的数组
                if (e.next == null)
                    // 重新哈希
                    newTab[e.hash & (newCap - 1)] = e;
                // TreeNode拆分为较高树与较低树，若拆分后的树桶节点数< UNTREEIFY_THRESHOLD = 6，则取消树化
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 类似树节点，链表拆分为较高链与较低链
                    // loHead = Low Head, Lo Tail = Low Tail
                    Node<K,V> loHead = null, loTail = null;
                    // hiHead = High Head, hiTail = High Tail
                    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.put(K,V)调用resize()调整大小主要分以下几种情况：

• 扩容：oldCap = table.length > 0，resize()结果：
  • table.length = oldCap * 2;
  • threshold = table.length * loadFactor
• 有参函数初始化：oldCap = table.length = 0 & oldThr = threshold > 0，resize()结果：
  • table.length = threshold;，此处threshold值为跟有参构造函数运算后的threshold值，运算后的threshold值是比构造函数参数threshold大的最小一个2的幂值
  • threshold = table.length * loadFactor
• 无参函数初始化：oldCap = table.length = 0 & oldThr = threshold = 0
  • table.length = 16;
  • threshold = 12

容量调整后会再根据table中的节点结构进行相应的操作：

• 单节点Node无链接：重新哈希
• 树节点TreeNode：将树箱中的节点拆分为较高和较低的树箱，如果拆分后的树箱容量<6，则取消树化；拆分后较低的树箱放在新table[旧table原索引]，较高的树箱迁移到新table[原索引+原table.length],详细可看TreeNode.split()源码
• 链表结构Node：拆分规则迁移与TreeNode类似，低位链表head node放在新table[原索引]，高位链表迁移到新table[原索引+原table.length]

table.length=newCap和threshold调整后会创建新的节点数组进行键值对迁移，所以一般建议初始化时配置好容量避免扩容时的迁移损失。

clear()清空映射

clear()只是简单的把table数组的所有元素置为null

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

疑问record & 总结

1、 entrySet()方法返回的明明是一个new EntrySet()，为什么却打印出了完整的HashMap映射? EntrySet继承了AbstractSet类并实现了iterator()方法，AbstractSet类toString()方法会调用iterator()方法获取迭代器，再通过Iterator.next()进行元素的字符串拼接。EntrySet。iterator()返回一个实现了Iterator接口的类EntryIterator，通过EntryIterator.next()可以遍历获取HasMap中的所有Node，所以即使HashMap的entrySet属性没有初始化但通过entrySet()方法依旧可以获取HashMap的完整映射。
2、 hashCode相同的key映射数超过8个并不一定就会转为红黑树结构 HashMap当同hashCode的节点Node超过8个且table数组容量>=64才会转为红黑树结构，否则容量<64时只会进行扩容保存链表结构，Result.png:

![101\_3.png][101_3.png]

3、 resize()进行容量调整并不一定会使每个节点进行重新哈希(rehash),重新哈希只会出现在无链接的单节点上

如有笔误，还请指出

文章永久链接：https://tech.souyunku.com/43000