沈阳开发网站,购物网站建设特色,php开发微网站开发,网站建设详细需求说明书文章目录 HashMap介绍实现说明:源码解读静态常量和内部节点类 Node静态工具方法属性字段 Fields未完待续。。。 HashMap
本文主要是用于记录我在阅读Java1.8的 HashMap 源码所做的笔记。对于源码中的注释会进行翻译下来#xff0c;并且会对其中部分源码进行注释。 这一篇文章… 文章目录 HashMap介绍实现说明:源码解读静态常量和内部节点类 Node静态工具方法属性字段 Fields未完待续。。。 HashMap
本文主要是用于记录我在阅读Java1.8的 HashMap 源码所做的笔记。对于源码中的注释会进行翻译下来并且会对其中部分源码进行注释。 这一篇文章主要是介绍 HashMap的静态常量、静态工具方法、属性字段以及比较重要的内部节点类 Node。
介绍
基于哈希 table 实现的 Map 接口。此实现提供所有可选的映射操作并允许 null 值和 null 键因为key不允许重复因此只能有一个键为null。 HashMap 类大致相当于 Hashtable但它是非同步 (unsynchronized) 的并且允许空值。此类不保证映射的顺序特别是它不保证顺序会随时间保持不变。 假设哈希函数能将元素适当地分散到各个桶中此实现为基本操作get 和 put提供常数时间性能。遍历集合视图所需的时间与 HashMap 实例的“容量”桶的数量加上其大小键值映射的数量成正比。因此如果迭代性能很重要则不要将初始容量设置得太高或负载因子设置得太低。 HashMap 的实例有两个影响其性能的参数初始容量和负载因子。容量是哈希表中的桶的数量初始容量就是哈希表创建时的容量。负载因子是在哈希表的容量自动增加之前允许其达到的填充程度的度量。当哈希表中的条目数超过负载因子与当前容量的乘积时哈希表将 重新哈希rehash即重建内部数据结构使得哈希表的桶数量大约是原来的两倍。 一般来说默认的负载因子0.75在时间和空间成本之间提供了良好的折衷。较高的值减少了空间开销但增加了查找成本反映在 HashMap 类的大多数操作中包括 get 和 put。在设置初始容量时应考虑映射中的预期条目数及其负载因子以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子则不会发生重新哈希操作。 **如果要在HashMap实例中存储许多映射以足够大的容量创建它将比让它按需执行自动扩容来存储映射更有效。**注意使用具有相同hashCode()的许多键肯定会降低任何哈希表的性能。为了缓解这一影响当键是Comparable时此类可能会使用键之间的比较顺序来帮助解决冲突。 请注意此实现不是同步 synchronized 的。**如果多个线程同时访问哈希映射并且至少有一个线程对映射进行了结构修改则必须在外部进行同步。结构性修改是添加或删除一个或多个映射的任何操作仅改变映射已包含的键关联的值不是结构性修改。**这通常通过同步某个自然封装映射的对象来完成。如果不存在这样的对象应该使用Collections.synchronizedMap方法将映射“包装”。最好在创建时这样做以防止意外的非同步访问映射 Map m Collections.synchronizedMap(new HashMap(…)); 此类的所有“集合视图方法”返回的迭代器都是 fail-fast 的如果在创建迭代器之后的任何时候以除了迭代器自己的remove方法之外的任何方式对映射进行结构修改迭代器将抛出ConcurrentModificationException。因此面对并发修改迭代器会迅速且干净地失败而不是冒着在未来不确定时间出现任意、非确定性的行为的风险。 请注意迭代器的快速失败行为不能被绝对保证因为在存在非同步并发修改的情况下一般而言无法做出任何硬性保证。快速失败迭代器会在最大努力的基础上抛出ConcurrentModificationException。因此编写依赖此异常来保证其正确性的程序是错误的迭代器的快速失败行为仅应用于检测bug。换句话说不能通过捕获异常来保证并发安全
HashMap类中实现了Serializable接口意味着你可以将一个HashMap实例序列化保存到文件或通过网络发送之后在需要的时候反序列化回来恢复成原来的数据结构和内容。这对于需要存储或传输映射数据的场景非常有用。 需要注意的是序列化和反序列化过程可能会引发安全风险如对象注入攻击因此在实现序列化时应当谨慎处理敏感信息并考虑使用 transient 关键字来排除不需要序列化的成员变量或实现writeObject和readObject方法以自定义序列化和反序列化逻辑确保安全。此外序列化ID (serialVersionUID) 的存在是为了版本控制确保在序列化类结构变更时能够兼容旧版本的序列化数据。
实现说明:
**该映射通常表现为一个分箱桶装的哈希表但是当桶变得过大时它们会被转换为由 TreeNode 构成的桶这些TreeNode的结构类似于java.util.TreeMap中的节点。**大多数方法尝试使用常规桶但在适用时会转而调用TreeNode的方法简单地通过检查是否为节点实例。树节点桶即其元素全为TreeNode的桶主要按hashCode进行排序但遇到hashCode相同时若两个元素属于同一“类C实现Comparable”则使用它们的compareTo方法进行排序。我们通过反射保守地检查泛型类型以验证这一点——参见comparableClassFor方法。尽管增加了树节点的复杂性但在键具有不同哈希值或可排序的情况下提供了最坏情况下O(log n)的操作这是值得的。因此在hashCode()方法返回分布不良的值或许多键共享hashCode但只要它们也是可比较的性能就会优雅地降级。 如果这两种情况都不适用相比于不采取预防措施我们可能在时间和空间上浪费大约两倍的资源。但已知的情况都源自用户编程实践不良这些实践已经很慢以至于这一点几乎没有什么区别。 **由于TreeNodes大约是常规节点的两倍大小我们只在桶包含足够多的节点以证明使用时见TREEIFY_THRESHOLD才使用它们。当它们因移除或调整大小变得太小后又会转换回普通桶。**在用户hashCode分布良好的用法中树形桶很少使用。理想情况下随机hashCode下桶中节点的频率遵循泊松分布http://en.wikipedia.org/wiki/Poisson_distribution对于默认的重置阈值0.75平均参数约为0.5尽管由于重置粒度的原因方差很大。忽略方差预计列表大小k的发生概率是(exp(-0.5) * pow(0.5, k) / factorial(k))。前几个值如下 0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 更多小于千万分之一 **树桶的根节点通常为它的第一个节点头结点。**然而在某些情况下当前仅在Iterator.remove期间根节点可能在别处但可以通过父链接TreeNode.root()方法找回。 所有适用的内部方法都接受一个哈希码作为参数通常从公共方法提供使它们能够在彼此调用时不重新计算用户哈希码。大多数内部方法还接受一个tab参数通常为当前表但在调整大小或转换时可能是新的或旧的。 当桶列表被树化、分割或取消树化时我们保持它们在相同的相对访问/遍历顺序即Node.next字段以更好地保持局部性并稍微简化那些在调用iterator.remove时涉及分割和遍历的处理。 在插入时使用比较器时为了在重新平衡过程中保持总排序或此处所需接近的程度我们比较类和identityHashCode 作为平局决断者。 在纯模式与树模式之间使用及转换的复杂性受到LinkedHashMap子类存在的影响。请参阅下面定义的插入、移除和访问时调用的钩子方法这些方法允许LinkedHashMap内部在不依赖于这些机制的情况下保持独立。这也要求将一个映射实例传递给某些可能创建新节点的实用方法。 并发编程风格的基于SSA静态单赋值的编码有助于在所有复杂的指针操作中避免别名错误。
源码解读
静态常量和内部节点类 Node
// 静态常量定义
// DEFAULT_INITIAL_CAPACITY: 默认初始容量设置为16即1 4要求是2的幂。
static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16
// MAXIMUM_CAPACITY: 最大容量为1 30即1073741824同样要求是2的幂且不超过这个值。
static final int MAXIMUM_CAPACITY 1 30;
// DEFAULT_LOAD_FACTOR: 默认负载因子未在构造器中指定时使用默认值为0.75。负载因子决定了哈希表何时需要进行扩容。
static final float DEFAULT_LOAD_FACTOR 0.75f;
// TREEIFY_THRESHOLD: 当桶bin中节点数量达到此阈值8时该桶会从链表转换为红黑树以提高查找效率。
static final int TREEIFY_THRESHOLD 8;
// UNTREEIFY_THRESHOLD: 在调整大小操作期间分裂的桶从树转换回链表的阈值设为6。
static final int UNTREEIFY_THRESHOLD 6;
// MIN_TREEIFY_CAPACITY: 桶可以被树化的最小表容量理论上至少为4 * TREEIFY_THRESHOLD即至少为32以避免树化和扩容阈值之间的冲突。源码设置为 64 可能是出于性能优化和避免频繁resize操作的考虑。
static final int MIN_TREEIFY_CAPACITY 64;/**
* 内部类Node
* Node类实现了Map.Entry接口表示哈希表中的一个条目包含以下部分
* 成员变量
* int hash: 节点关联的哈希值。
* K key: 键。
* V value: 值。
* NodeK,V next: 指向下一个节点的引用用于链表或树结构中的链接。
*
* 构造函数初始化节点的所有字段。
* getter方法获取键(getKey)、值(getValue)。
* toString方法返回键值对的字符串表示。
* hashCode方法基于键和值计算哈希码用于确定节点在哈希表中的位置。
* setValue方法更新节点的值并返回旧值。
* equals方法比较两个节点是否相等基于键和值的相等性判断。
*/
static class NodeK,V implements Map.EntryK,V {final int hash;final K key;V value;NodeK,V next;Node(int hash, K key, V value, NodeK,V next) {this.hash hash;this.key key;this.value value;this.next next;}public final K getKey() { return key; }public final V getValue() { return value; }public final String toString() { return key value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue value;value newValue;return oldValue;}public final boolean equals(Object o) {if (o this)return true;if (o instanceof Map.Entry) {Map.Entry?,? e (Map.Entry?,?)o;if (Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue()))return true;}return false;}
}静态工具方法
/* ---------------- Static utilities静态工具方法 -------------- *//*** 计算键的哈希码通过调用key.hashCode()并采用异或XOR操作将哈希码的高位散布到低位。* 由于哈希表采用二的幂次掩码来确定索引导致仅在当前掩码高位上变化的哈希集合总是会发生碰撞。* 已知的例子包括在小表中存储连续整数的Float键集合。* 因此我们应用了一种变换将高位的影响向下扩散以改善分布。* 这里存在速度、实用性与位扩散质量之间的权衡。* 由于许多常见的哈希集合已经具有相当合理的分布所以不需要进一步分散* 并且我们使用树结构来处理桶内大量的碰撞情况* 我们仅以最经济的方式对某些位进行移位和异或操作* 以此减少系统性的哈希损失同时确保原本因表容量限制而无法在索引计算中利用到的最高位信息也能够被融入进来。*/
// 为什么需要对原始哈希值进行额外的位操作通过简单而高效的位移和异或提高哈希值分布的均匀性从而减少哈希碰撞尤其是在处理特定类型数据或小表时能显著提升哈希表的性能。
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}/*** 根据给定的目标容量返回一个2的幂次大小。* 此方法用于计算哈希表的理想容量确保容量始终是2的幂* 这对于高效地使用位运算进行索引计算至关重要。* 取最小的大于cap的2的整数次幂输入30输出32*/
static final int tableSizeFor(int cap) {// 初始化n为cap减1这样如果cap已经是2的幂最终结果仍会是cap。int n cap - 1;// 下面的位操作序列用于将n的最低位设置为1同时将紧邻的每个低位依次置为1// 直至最高有效位。这样做是为了“向上取整”到最近的2的幂。n | n 1; // 将n的右半部分与自身进行或操作使得右半部分的最低位为1。n | n 2; // 再次右移并或操作将下一部分的最低位也置为1。n | n 4; // 继续处理更高位直至覆盖所有低位。n | n 8;n | n 16; // 处理最高有效位对于32位整数而言。// 最后检查处理后的n值。// 如果n为负数这在正常情况下不会发生除非cap非常大接近Integer.MAX_VALUE// 则直接返回最小容量1。// 如果n大于最大允许容量MAXIMUM_CAPACITY通常是2^30则返回MAXIMUM_CAPACITY。// 否则返回n1因为n此时已经是比目标容量大的最小2的幂次减1加1后即为目标容量的最小2的幂次覆盖。return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}属性字段 Fields
/* ---------------- Fields -------------- *//*** table在首次使用时初始化并根据需要调整大小。当分配时长度始终是2的幂次方。* 还容忍在某些操作中长度为零的情况以允许目前不需要的引导机制。*/
transient NodeK,V[] table; // 存储键值对的哈希表数组/*** 缓存的 entrySet()。注意 AbstractMap 中的字段用于 keySet() 和 values()。*/
transient SetMap.EntryK,V entrySet; // 缓存的 Entry 集合视图/*** 此映射中包含的键值对的数量。*/
transient int size; // map 的大小即键值对的数量/*** 此 HashMap 结构修改的次数。* 结构性修改是指改变 HashMap 中映射数量或以其他方式修改其内部结构例如重新散列的操作。* 这个字段用于使 HashMap 集合视图上的迭代器快速失败。参见 ConcurrentModificationException。*/
transient int modCount;/*** 下一次调整大小时的大小值容量 * 负载因子。** serial*/
// 序列化时的 javadoc 描述是正确的。
// 另外如果表格数组尚未分配此字段保存初始数组容量
// 或者零表示 DEFAULT_INITIAL_CAPACITY。
int threshold; // 下一个阈值达到这个值时将进行重新散列/*** 哈希表的负载因子。** serial*/
final float loadFactor; // 哈希表的负载因子决定何时进行重新散列未完待续。。。
