HashMap集合(入门)

学习地址：https://www.bilibili.com/video/BV1nJ411J7AA
个人博客地址：https://itkxz.cn

1.什么是HashMap

HashMap 与 HashSet 一样，不保证存储的顺序，因为底层是以 hash 表的方式存储的；
HashMap 底层存储结构为数组 + 链表+红黑树（Java 8）；
HashMap 存储的 key-value 数据类型为 HashMap

N

o

d

e

类

型

，

该

类

型

实

现

了

M

a

p

Node 类型，该类型实现了 Map

$N o d e 类型，该类型实现了 M a p$ Entry 接口；
HashMap 没有实现同步，因此是线程不安全的；

2. HashMap中常用的变量/常量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的 table 数组容量 aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;  // 默认加载因子为 0.75
static final int MAXIMUM_CAPACITY = 1 << 30; // 集合最大容量的上限是：2的30次幂
static final int TREEIFY_THRESHOLD = 8; // 链表树化临界值
static final int UNTREEIFY_THRESHOLD = 6; // 树转成链表的临界值
static final int MIN_TREEIFY_CAPACITY = 64; // 树化时数组的最小长度

transient Node<K,V>[] table;  // 存放元素的数组
transient Set<Map.Entry<K,V>> entrySet;  // 存放元素的缓存
transient int size;  // HashMap 中实际元素个数
transient int modCount;  // HashMap 修改次数，每个扩容和更改map结构的计数器
int threshold;  // table 扩容临界值 数组长度 * 加载因子
final float loadFactor;  // table 加载因子

3.初始化及扩容机制

HashMap 是用一个 Node 类型的数组 table 来存储元素的，每一个元素的类型为 Node；

transient Node<K,V>[] table;

创建 HashMap 对象时，数组 table 默认为 null，加载因子 loadfactor 默认为 0.75；

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

第一次添加元素时，判断 table 为空数组，默认将 table 扩容到 16，阈值 threshold 为数组长度与加载因子的积 12（resize() 方法）；
当添加元素 key-value 时，通过 key 的 hash 值计算该元素在 table 中的索引位置，判断该索引位置是否存在 Node 结点，没有则直接添加；
如果索引位置有结点，则判断要添加的元素的 key 与该节点的 key 是否相同，如果相同，则将 value 替换到当前结点，如果不相同，则判断当前结点是否是树结构，是树结构则执行添加树结点操作；
如果不是，判断为链表结构，且要添加的元素和链表第一个结点不同，遍历链表判断 key 是否存在，不存在则向链表插入元素，并判断当前链表是否满足树化条件（链表长度大于等于8），如果存在执行替换操作；
当 table 长度达到阈值 threshold 时，则执行 resize() 方法给 table 进行扩容，扩容大小为原来的 2 倍，同时阈值更新为当前数组长度乘以加载因子；

// putVal() 添加元素成功,table长度加1, 判断是否扩容
if (++size > threshold)
    resize();

当 table 某个节点的链表长度超过 TREEIFY_THRESHOLD（默认 8）后，判断 table 的容量是否达到 MIN_TREEIFY_CAPACITY（默认 64），达到则对当前结点的链表进行树化；否则对 table 扩容；
当树的元素减少到 UNTREEIFY_THRESHOLD = 6 时，会进行剪枝操作（转回链表）

3. 阿里巴巴编码规约-初始化指定容量

【推荐】集合初始化时，指定集合初始值大小。

说明：HashMap 使用 HashMap(int initialCapacity) 初始化。

正例：initialCapacity = (需要存储的元素个数 / 负载因子) + 1。

注意负载因子（即 loader factor）默认为 0.75，如果暂时无法确定初始值大小，请设置为 16（即默认值）。

反例：HashMap 需要放置 1024 个元素，由于没有设置容量初始大小，随着元素不断增加，容量 7 次被迫扩大，resize 需要重建 hash 表，严重影响性能

4. 主要源码及常用方法分析

4.1 HashMap构造器

1.无参构造

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

指定初始容量的构造器

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

指定初始容量和加载因子的构造器

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0) // 异常:初始容量小于0 
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    // 指定容量大于数组最大容量,初始化为最大容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 异常:加载因子小于0 or NaN Not a Number
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;  // 指定加载因子大小
    // 计算 table 的大小,确保为2的n次幂,
    // 这里赋值给临界值,在第一次添加元素的时候会初始化为table大小
    this.threshold = tableSizeFor(initialCapacity);    
}

4.2 putVal()-添加元素的方法

/**
 * Implements Map.put and related methods.
 *
 * @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;  // 定义辅助变量
    
    // 0. 这里是判断table是否初始化，table = null or table.length = 0 初始化table
    if ((tab = table) == null || (n = tab.length) == 0) // table:存放元素的Node[]数组
        n = (tab = resize()).length;  // resize():扩容-数组为空给table初始化16个空间
    
    // 根据key的hash值计算索引值,将table中该索引位置的结点赋值给p,并判断p是否为空
    if ((p = tab[i = (n - 1) & hash]) == null)
        //若p为null(当前位置没有元素)则创建新的结点Node保存当前要添加的数据,存储到当前索引位置
        tab[i] = newNode(hash, key, value, null);
    else {
        // 这里说明table当前索引位置的结点已经存在数据，下面分情况判断添加元素
        Node<K,V> e; K k;
        // 1. 判断要添加的元素(key)与table中当前索引位置的Node结点是否相同
		// condition: ① hash 值相等 && (② 引用相同 || ③ equals判断相等)
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 元素重复
        // 2. 判断当前索引位置元素结点是否是红黑树类型
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 3. 说明当前索引位置结点为链表,且第一个结点与要添加的元素key不同,就遍历链表判断key是否存在
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 如果key和链表中所有节点元素都不相同，则添加到链表最后
                    p.next = newNode(hash, key, value, null);
                    // 添加元素后判断当前链表是否已经有了8个节点，够8个则将当前链表转成红黑树
                    // 这里调用treeifyBin()方法会判断table大小是否足够64个，到达64个才会树化
                    // 不满 64 个空间，会先给 table 扩容
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break; // 退出 for 循环
                }
                // 如果要添加的元素key在链表中已经存在，则直接退出循环
				// condition: ① hash 值相等 && (② 引用相同 || ③ equals判断相等)
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e; // 当前节点后移
            }
        }
        // 要添加的元素 key 已存在，则将重复的元素返回
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 将要添加的 value 替换掉旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount; // 修改次数
    // 添加元素成功,table长度加1, 判断是否扩容 数组长度是否大于阈值
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); // HashMap 没有实现该方法, 供子类实现扩充功能
    // return null 表示要添加的元素在table中不存在, 添加成功
    return null;
}

4.3 resize()-集合扩容

给 table 初始化或者将数组大小翻倍，如果 table 为null，则根据默认值指定初始容量和边界值；否则，因为我们的 table 数组容量是 2 的 n 次幂，所以每个 bin 中的元素一定保持相同的索引，或者在新 table 中移动 2 的 n 次幂的偏移量（元素在新数组中的索引位置为原来的索引或者是原来的索引 + 原容量大小

/**
 * 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) { // 将新容量和新边界值扩大为原来2倍(<<1 == *2)
        // 旧容量已经到达最大容量就扩大临界值
        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
    }
    // 将旧临界值赋值给新容量，这里的场景为初始化时使用了带参数的构造器-tableSizeFor()
    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;  // table 边界值更新为新的边界值
    @SuppressWarnings({"rawtypes","unchecked"})
    // 创建新 table 容量为默认初始容量或之前容量的2倍
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 原数组不为null，说明是扩容-遍历之前的table 赋值给新数组
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) { // 当前索引存在元素 e
                oldTab[j] = null; // 方便回收空间
                // 1. 当前索引位置只有一个元素，没有下一个结点
                if (e.next == null) 
                    // 重新计算当前元素在新table中的索引，将当前索引结点放到新table
                    newTab[e.hash & (newCap - 1)] = e; 
                // 2. 当前索引位置有下一个结点，且是红黑树,指定树的操作
                else if (e instanceof TreeNode) 
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 3. 当前索引位置有下一个结点，这里是链表类型
                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;
}

4.4 treeifyBin() – 树化

树化-将数组中的链表转成红黑树

/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 树化判断，table 数组的长度是否大于等于 64，未达到则进行数组扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 判断当前索引位置结点不为null
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null; // 头尾节点
        do {
             // 将链表结点转换为树结点类型 TreeNode
            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)
            hd.treeify(tab);
    }
}

// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

4.5 remove()-删除集合中的元素

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

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; // 辅助变量
    // table 不为空，且指定key的hash计算的索引位置有元素
    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; // 辅助变量
        // 1 判断要删除的元素是否是指定索引链表的第一个元素
        if (p.hash == hash && 
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 2 不是第一个元素，判断链表是否还有其他元素
        else if ((e = p.next) != null) {
            // 2.1 有其他元素且为树结点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else { // 2.2 有其他元素，为链表结构
                do { // 遍历链表，依次判断要删除的元素的位置
                    // 根据hash、key的值找到要删除的元素
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break; // 找到，退出
                    }
                    p = e; // p 是要删除节点的上一个节点
                } 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; // 计数器+1
            --size;   // 长度 -1
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

4.6 get()-根据key获取

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

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 数组不为空，且根据hash计算的索引位置有结点
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 查询的key与该索引位置的元素相同
        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 { // 遍历链表 找到对应的key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}