文章将在我的Git Page更新 原文链接
前言
大家开发中用得最多的工具类就是JAVA的集合框架了,今天我们来从源码的角度剖析Map集合的实现之一HashMap
。
HashMap 简介
这里我就直接翻译JDK源码注释了,其实注释讲得很详细了。
基于哈希表的Map接口的实现。 此实现提供所有可选的映射操作,并允许空值和空键。 ( HashMap类与Hashtable大致等效,不同之处在于它是不同步的,并且允许为null。)此类不保证映射的顺序。 特别是,它不能保证顺序会随着时间的推移保持恒定。
假设哈希函数将元素正确分散在存储桶中,则此实现为基本操作( get和put )提供恒定时间(这里指时间复杂度为o1)的性能。 集合视图上的迭代所需的时间与HashMap实例的“容量”(存储桶数)及其大小(键-值映射数)成正比。 因此,如果迭代性能很重要,则不要将初始容量设置得过高(或负载因数过低),这一点非常重要。
HashMap的实例具有两个影响其性能的参数:初始容量和负载因子。 容量是哈希表中存储桶的数量,初始容量只是创建哈希表时的容量。 负载因子是在自动增加其哈希表容量之前允许哈希表获得的满度的度量。 当哈希表中的条目数超过负载因子和当前容量的乘积时,哈希表将被重新哈希(即,内部数据结构将被重建),因此哈希表的存储桶数约为两倍。
通常,默认负载因子(.75)在时间和空间成本之间提供了一个很好的权衡。 较高的值会减少空间开销,但会增加查找成本(在HashMap类的大多数操作中都得到体现,包括get和put )。 设置其初始容量时,应考虑映射中的预期条目数及其负载因子,以最大程度地减少重新哈希操作的次数。 如果初始容量大于最大条目数除以负载因子,则将不会发生任何哈希操作。
如果将许多映射存储在HashMap实例中,则创建具有足够大容量的映射将比让其根据需要增长表的自动重新哈希处理更有效地存储映射。 请注意,使用具有相同hashCode()许多键是降低任何哈希表性能的肯定方法。 为了改善影响,当键为Comparable ,此类可以使用键之间的比较顺序来帮助打破平局。
请注意,此实现未同步。 如果多个线程同时访问哈希映射,并且至少有一个线程在结构上修改该映射,则必须在外部进行同步。 (结构修改是添加或删除一个或多个映射的任何操作;仅更改与实例已经包含的键相关联的值不是结构修改。)通常通过在自然封装了Map的某个对象上进行同步来实现。 。 如果不存在这样的对象,则应使用Collections.synchronizedMap方法“包装”Map。 最好在创建时完成此操作,以防止意外不同步地访问Map:
Map m = Collections.synchronizedMap(new HashMap(…));
该类的所有“集合视图方法”返回的迭代器都是快速失败的:如果在创建迭代器后的任何ff时间以任何方式对Map进行结构修改,则除了通过迭代器自己的remove方法之外,迭代器都会抛出ConcurrentModificationException 。 因此,面对并发修改,迭代器会快速干净地失败,而不会在未来的不确定时间冒着任意,不确定的行为的风险。
请注意,迭代器的快速失败行为无法得到保证,因为通常来说,在存在不同步的并发修改的情况下,不可能做出任何严格的保证。 快速失败的迭代器会尽最大努力抛出ConcurrentModificationException 。 因此,编写依赖于此异常的程序的正确性是错误的:迭代器的快速失败行为应仅用于检测错误。
此类是Java Collections Framework的成员
几个重要的成员变量
Node<K,V>[] table
核心数据结构 数组 + 链表int size
集合的大小int modCount
被修改的次数int threshold
下一个要调整大小的大小值(容量 * 负载因子)float loadFactor
负载因子Set<Map.Entry<K,V>> entrySet
KV集
方法
构造方法
HashMap
有多个重载构造方法,但最终都会去掉下面这个构造方法
1 | public HashMap(int initialCapacity, float loadFactor) { |
有两个参数
- initialCapacity 初始容量
- loadFactor 负载因子
HashMap
就是对散列表
这种数据结构的实现,所以需要这个两个参数去定义散列表
tableSizeFor
我们从上面的构造方法可以看出,HashMap
在初始化的时候,会调用这个方法去计算实际初始化的容量并暂存为threshold
。
1 | /** |
这个方法返回大于输入参数且最近的2的整数次幂的数。比如10,则返回16。
先来分析有关n位操作部分:先来假设n的二进制为01xxx…xxx。接着
对n右移1位:001xx…xxx,再位或:011xx…xxx
对n右移2为:00011…xxx,再位或:01111…xxx
此时前面已经有四个1了,再右移4位且位或可得8个1
同理,有8个1,右移8位肯定会让后八位也为1。
综上可得,该算法让最高位的1后面的位全变为1。
最后再让结果n+1,即得到了2的整数次幂的值了。
现在回来看看第一条语句:
1 | int n = cap - 1; |
让cap - 1
再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000,十进制数值为8。如果不对它减1而直接操作,将得到答案10000,即16。显然不是结果。减1后二进制为111,再进行操作则会得到原来的数值1000,即8。
这种方法的效率非常高,可见Java8对容器优化了很多
hash
1 | static final int hash(Object key) { |
这里是取hash的高16位与hash值进行异或运算,因为在进行槽位计算的时候容易丢失高位的特征,所以采取低位与高位进行运算获得一个结果,保留了高位与低位的特征。如果采用|
将会使位偏向1,如果采用&
将会偏向0,而采用^
则没有明显的偏向性。
槽位计算源码
1 | tab[i = (n - 1) & hash] |
PUT
1 | public V put(K key, V value) { |
这个方法将元素加入散列表,具体实现是下面这个putVal
方法
1 | /** |
明确几个局部变量的意义
Node<K,V>[] tab
散列表Node<K,V> p
新增的节点int n
散列表数组的长度int i
计算出的槽位
我们跟随源码的流程进行分析
首先判断散列表是否有被创建出来,如果没有创建,则进行散列表的初始化。这是一种懒加载策略。初始化的过程我们下面再分析。
然后就是计算散列位置,判断该位置上是否有元素。若没有则直接把元素放入。如果该节点上有元素了,则发生了hash碰撞,需要另外的处理。
下面分析一下槽点计算的源码
1 | i = (n - 1) & hash |
将容量-1与hash值进行与运算。由于散列表在初始化的时候,容量是2的次幂,所以在减一之后,二进制位都变为了1,再与hash值进行与运算其实就是取余数,这个就相当于hash % n
。但是效率确比取模运算高出很多。
如果发生了hash碰撞,则首先会进行key
是否一致导致的,如果key不等发生的hash碰撞,则会吧当前元素放在链表的下一个节点,如果链表长度超过8,则会树化处理,变为红黑树。