HashMap构造函数-白红宇

HashMap构造函数

阅读量：796 次

发布时间：2023-03-28

本文共 1826 字，大约阅读时间需要 6 分钟。

HashMap是Java集合框架中非常常用的数据结构，它以其高效的查询和操作性能著称。其中，HashMap的初始化和扩容机制是其高效性和稳定性的关键所在。本文将深入分析HashMap的初始化过程以及扩容机制。

HashMap的初始化主要通过三个构造函数完成：

默认构造函数：HashMap()

这个构造函数初始化一个空的HashMap，其初始容量为16，装填因子为0.75。当容量达到一定数量时，才会触发扩容操作。

指定初始容量的构造函数：HashMap(int initialCapacity)

这个构造函数初始化一个空的HashMap，其容量由参数指定，装填因子仍然是0.75。

指定初始容量和装填因子的构造函数：HashMap(int initialCapacity, float loadFactor)

这个构造函数允许开发者自定义HashMap的初始容量和装填因子。需要注意的是，初始容量不能小于0，装填因子不能小于等于0或为NaN值。

初始化过程：

默认初始化：当调用HashMap()时，loadFactor被设置为0.75，threshold（即扩容阈值）被设置为tableSizeFor(initialCapacity)。tableSizeFor方法会返回一个最接近给定容量的2的幂次方。

自定义初始化：当调用HashMap(int initialCapacity, float loadFactor)时，首先检查参数的合法性。如果初始容量超过最大允许值（MAXIMUM_CAPACITY），则将其设置为最大值。接着，将loadFactor设置为指定值，并计算初始threshold。

HashMap的扩容主要通过resize()方法实现。扩容的触发条件是当当前的键值对数量超过threshold时。

扩容逻辑：

保存当前表和容量：保存当前的table、oldCap（旧容量）和oldThr（旧阈值）。

确定新容量和新阈值：

如果旧容量大于0：
- 如果旧容量超过最大容量，设置threshold为Integer.MAX_VALUE。
- 如果旧容量小于最大容量且需要扩容，容量翻倍（左移1位）。
- 扩容后，新阈值newThr被设置为旧阈值的左移1位。

调整阈值：如果新阈值为0，根据当前容量和装填因子重新计算阈值。

初始化新表：创建一个新的table，其长度为新容量。

迁移旧数据：将旧table中的节点迁移到新table中，保持哈希值不变。

哈希函数：

HashMap的哈希函数通过对键的hashCode()进行异或操作，高位和低位信息混合，提高哈希的随机性，减少碰撞概率。具体实现如下：

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

冲突处理：

当两个键的哈希值相同，称为碰撞。此时，HashMap会将两个键插入同一个链表节点中，形成一个链表（线性探测）。如果链表长度超过树化阈值（TREEIFY_THRESHOLD），则链表会被树化，形成一个红黑树结构，进一步减少碰撞。

链表扩容：

当链表长度超过树化阈值时，treeifyBin()方法会将链表节点转换为红黑树节点，保持树的平衡。

HashMap通过动态调整容量和哈希函数，实现了高效的空间和时间复杂度。其优化点包括：

容量预留：在容量不足时，预留一定的空间以避免频繁扩容。

无符号右移：扩容时使用无符号右移操作，确保容量总是2的幂次方。

树化与链表：根据冲突情况自动选择链表或树化结构，保持哈希表的平衡性。

HashMap通过灵活的容量管理和高效的哈希算法，在保证高效查询和操作的同时，实现了较好的空间利用率。其初始化和扩容机制为后续的数据存储和操作提供了稳定且高效的支持，是Java集合框架中不可或缺的一部分。

转载地址：http://tvhfk.baihongyu.com/

你可能感兴趣的文章