🔎【Java 源码探索】深入浅出的分析 HashMap(JDK8)
【每日一句】
一个人最大的挑战,是如何去克服自己的缺点。
【基本原理】
HashMap 是一个基于 map 接口实现的散列表,存储内容是键值对 (key-value) 映射,并且键和值都可以使用 null,因为 key 不允许重复,因此只能有一个键为 null。
HashMap 使用 hash 算法进行数据的存储和查询。
HashMap 的实现用的是数组+链表+红黑树的结构,也叫哈希桶。在 jdk 1.8 之前都是数组+链表的结构,因为在链表的查询操作都是 O(N)的时间复杂度,如果当节点数量多,转换为红黑树结构,那么将会提高很大的效率,因为红黑树结构中,增删改查都是 O(log n)。
【基本特性】
HashMap 的散列表是懒加载机制,在第一次 put 的时候才会创建
它根据键的 hashCode 值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。
HashMap 最多只允许一条记录的键(Key)为 null,允许多条记录的值为 null。
HashMap 是无序不重复的,而且 HashMap 是线程不安全的。
HashMap 默认情况下使用一个 Entry 表示键值对 key-value,用 Entry 的数组保存所有键值对,Entry 通过链表的方式链接后续的节点 (1.8 后会根据链表长度决定是否转换成一棵树类似 TreeMap 来节省查询时间,Node 节点会采用 LinkedHashMapEntry 的属性),Entry 通过计算 key 的 hash 值来决定映射到具体的哪个数组(也叫 Bucket) 中。
HashMap 非线程安全,即任一时刻可以有多个线程同时写 HashMap,可能会导致数据的不一致。
如果需要满足线程安全,可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力,或者使用 ConcurrentHashMap。
【优化点】
链表改为红黑树:时间复杂度(O(N) —> O(log(N)))
【原理简述】
【put 方法】
输入参数
key 值,value 值
运作流程
首先针对于传入的对 Key 求 hash 值,然后再计算下标。
如果没有碰撞,直接放入桶中(碰撞的意思是计算得到的 hash 值相同,需要放到同一个 bucket 中,代表着属于链表)。
如果 hash 值发生碰撞后,以链表的方式链接到后面。
如果链表长度超过阀值( TREEIFY THRESHOLD==8),就把链表转成红黑树,链表长度低于 6,就把红黑树转回链表。
如果 key 的 hashcode 相同且 value 也相同的情况下,就替换旧值
如果桶到达阈值(Threshold)后(初始化容量(16)以及加载因子(0.75)),就需要 resize(扩容 2 倍后并且进行重排(重新 hash 和重新排版))
数据结构图
HashMap 属性代码
首先,需要记住的是,JCF 的一个传统模式,就是集成 AbstractXXX 抽象类和实现所有的基础接口 XXX,XXX(Map,List,Set,Collection 等),并且可以实现序列化和克隆。
属性默认值
属性参数
Node[] table:的初始化长度 length(默认值是 16),loadFactor 为负载因子 (默认值 DEFAULT_LOAD_FACTOR 是 0.75),threshold 是 HashMap 所能容纳的最大数据量的 Node(键值对) 个数。
threshold = length * loadFactor。也就是说,在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多。
**这里我们需要加载因子 (load_factor),加载因子默认为 0.75,当 HashMap 中存储的元素的数量大于 (容量 × 加载因子),也就是默认大于 16*0.75=12 时,HashMap 会进行扩容的操作 **。
size:这个字段其实很好理解,就是 HashMap 中实际存在的键值对数量。注意和 table 的长度 length、容纳最大键值对数量 threshold 的区别。
modCount:字段主要用来记录 HashMap 内部结构发生变化的次数,主要用于迭代的快速失败。强调一点,内部结构发生变化指的是结构发生变化。
put 新键值对,某个 key 对应的 value 值被覆盖不属于结构变化。
HashMap 的内部功能实现很多,本文主要从根据 key 获取哈希桶数组索引位置、put 方法的详细执行、扩容过程等具有代表性的点深入展开讲解。
构造函数
第一个默认初始化+默认加载因子,第二个设置初始容量+初始化默认加载因子,第三个设置初始容量和加载因子。
节点对象
HashMap 内部类 TreeNode,该类是一个红黑树结构。
HashMap 内部类 Node, 结构为单向链表。
哈希方法
解决 Hash 的的冲突的 hash()方法,HashMap 的 hash 计算时先计算 hashCode(), 然后进行二次 hash。
这个方法非常巧妙,它总是通过 h &(table.length -1) 来得到该对象的保存位置,而 HashMap 底层数组的长度总是 2 的 n 次方。当 length 总是 2 的倍数时,h & (length-1) 将是一个非常巧妙的设计:
假设 h=5,length=16, 那么 h & length - 1 将得到 5;
假设 h=6,length=16, 那么 h & length - 1 将得到 6
假设 h=15,length=16, 那么 h & length - 1 将得到 15;
但是当 h=16 时 , length=16 时,那么 h & length - 1 将得到 0 了;当 h=17 时 , length=16 时,那么 h & length - 1 将得到 1 了。这样保证计算得到的索引值总是位于 table 数组的索引之内。
添加元素
红黑树结构的 putVal 方法
总结 put()方法大致的思路为:
对 key 的 hashCode()做 hash,然后再计算 index;
如果没碰撞直接放到 bucket 里;
如果碰撞了,以链表的形式存在 buckets 后;
如果碰撞导致链表过长 (大于等于 TREEIFY_THRESHOLD=8),就把链表转换成红黑树;
如果节点已经存在就替换 old value(保证 key 的唯一性)
如果 bucket 满了 (超过 load factor*current capacity),就要 resize。
具体步骤为
如果 table 没有使用过的情况(tab=table)==null || (n=tab.length) == 0,则以默认大小进行一次 resize。
计算 key 的 hash 值,然后获取底层 table 数组的第 (n-1) & hash 的位置的数组索引 tab[i] 处的数据,即 hash 对 n 取模的位置,依赖的是 n 为 2 的次方这一条件
先检查该 bucket 第一个元素是否是和插入的 key 相等 (如果是同一个对象则肯定 equals)
如果不相等并且是 TreeNode 的情况,调用 TreeNode 的 put 方法否则循环遍历树节点,
如果找到相等的 key 跳出循环否则达到最后一个节点时将新的节点添加到链表最后, 当前面找到了相同的 key 的情况下替换这个节点的 value 为新的 value。
最后如果新增了 key-value 对,则增加 size 并且判断是否超过了 threshold, 如果超过则需要进行 resize 扩容
扩容尺寸
扩容 (resize) 就是重新计算容量,向 HashMap 对象里不停的添加元素,而 HashMap 对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。
当然 Java 里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。
由于需要考虑 hash 冲突解决时采用的可能是链表也可能是红黑树的方式,因此 resize 方法相比 JDK7 中复杂了一些。
rehashing 触发的条件:
超过默认容量 * 加载因子;
加载因子不靠谱,比如远大于 1。
在 HashMap 进行扩容时,会进行 2 倍扩容,而且会将哈希碰撞处的数据再次分散开来,一部分依照新的 hash 索引值呆在 “原处”,另一部分加上偏移量移动到新的地方。
具体步骤为:
首先计算 resize() 后的新的 capacity 和 threshold 值。
如果原有的 capacity 大于零则将 capacity 增加一倍,否则设置成默认的 capacity。
创建新的数组,大小是新的 capacity
将旧数组的元素放置到新数组中
获取元素
get(key) 方法时获取 key 的 hash 值,计算 hash & (n-1) 得到在链表数组中的位置 first=tab[hash&(n-1)],先判断 first 的 key 是否与参数 key 相等,不等就遍历后面的链表找到相同的 key 值返回对应的 Value 值即可。
红黑树结构
树形化操作
根据哈希表中元素个数确定是扩容还是树形化,如果是树形化遍历桶中的元素,创建相同个数的树形节点,复制内容,建立起联系,然后让桶第一个元素指向新建的树头结点,替换桶的链表内容为树形内容// MIN_TREEIFY_CAPACITY 的值为 64,若当前 table 的 length 不够,则 resize() // 将桶内所有的 链表节点 替换成 红黑树节点
删除元素
下面再来看看删除方法 remove。
删除还有 clear 方法,把所有的数组下标元素都置位 null。
size()方法
HashMap 的大小很简单,不是实时计算的,而是每次新增加 Entry 的时候,size 就递增。删除的时候就递减。空间换时间的做法。因为它不是线程安全的。完全可以这么做,效率高。
评论 (2 条评论)