HashMap源码分析篇(JDK1.8)

  • 内容
  • 评论
  • 相关

摘要:

突然发现对源码的阅读较少,所以近段时间静下心耐心好好研究一些源码,看看大神的设计思想,多学习。

 

为何要阅读源码?阅读源码的目的是什么?如何阅读源码?

源码分析的目的并不是单纯的为了肢解代码, 这只是过程, 它的目的是为了让自己能够对代码的理解更加深刻, 培养自己的直观理解力, 增强自己的代码输出能力, 同时也增加自己对复杂代码的理解能力. 所谓的源码分析, 其实是对一个复杂的源码进行降维分析, 降到自己的能力所能理解的程度, 这样, 随着源码分析能力的增进, 个人的理解能力也会上升.

 

HashMap概述

首先,看一下HashMap的继承结构:

public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {

 

在JDK1.8之前,HashMap采用数组+链表实现,即使用链表处理冲突,同一hash值的节点都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。

而JDK1.8中,HashMap采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。

 

下图是JDK1.8之前的HashMap结构,左边部分即代表哈希表,也称为哈希数组,数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中。稍后会好好聊一下如何映射。

 

JDK1.8之前的HashMap都采用上图的结构,都是基于一个数组和多个单链表,hash值冲突的时候,就将对应节点以链表的形式存储。如果在一个链表中查找其中一个节点时,将会花费O(n)的查找时间,会有很大的性能损失。到了JDK1.8,当同一个hash值的节点数不小于8时,不再采用单链表形式存储,而是采用红黑树,如下图所示。

简而言之,JDK1.8后,HashMap是由于数组+链表+红黑树实现,当链表个数大于8,当前链表重组,由Node转换为TreeNode,由链表转换成红黑树。

 

HashMap常用操作

 

HashMap的构造方法

HashMap有4个构造方法,分别是:

 

这里面有一个方法:tableSizeFor,很重要,这是HashMap扩充的算法

 

在了解这个方法之前先来看一下HashMap的一些变量:

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 默认的初始容量是16,大小必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量,也就是说2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树,太小或太大都会转换频繁都可能从而影响性能下降
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表,该值应该比上面的8小
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组,总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数,注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
int threshold;
// 填充因子
final float loadFactor;

 

HashMap的扩容机制

然后我们继续回来说tableSizeFor方法,先看一下源码:

这个算法的含义是:求得大于或等于传入值cap的最小2的幂次方,举几个例子:

传入10,返回16;

传入20,返回32;

传入100,返回128;

传入1024,返回1024;

分析原理如下:

该算法设计之巧妙,话不多说,继续。

 

put方法

首先要说一下为什么大多数人都选择用String类型作为key,因为在HashMap中key的key是要计算hash值的,而String类覆写了Object的equals方法和hashCode方法,所以我们可以愉快的使用String类型作为我们的key。

 

先看一下put方法的源码吧:

 

keySet方法

keySet()方法可以获取包含key的集合,调用该集合的迭代器可以对key进行遍历

KeySet是HashMap的内部类,继承AbstractSet,KeySet中获取迭代器为keyIterator

而KeyIterator继承HashIterator

 

get方法

先看一下源码:

源码中的注释已经写得很明了了,就不再继续阐述了。

 

entrySet方法

entrySet跟keySet有点类似,具体先看源码:

EntrySet是HashMap的内部类,继承AbstractSet,EntrySet获取的迭代器为EntryIterator

EntryIterator是HashMap的内部类,继承HashIterator

 

forEach方法

java8的lambda表达式,其实就是调用该类的forEach方法,还是看源码:

 

remove方法

remove方法是从list或map中筛除该元素,可以是根据key,也可以是根据下标(list)。

remove方法的逻辑已经在源码里阐述了,就不在过多解释了。

 

全局逻辑视图

图片暂时无法打开,请刷新重试

 

总结

HashMap结合了数组和链表的优点,使用Hash算法加快访问速度,使用散列表解决碰撞冲突的问题,其中数组的每个元素是单链表的头结点,链表是用来解决冲突的

 

HashMap有两个重要的参数:初始容量和加载因子。这两个参数极大的影响了HashMap的性能。初始容量是hash数组的长度,当前加载因子=当前hash数组元素/hash数组长度,最大加载因子为最大能容纳的数组元素个数(默认最大加载因子为0.75),当hash数组中的元素个数超出了最大加载因子和容量的乘积时,要对hashMap进行扩容,扩容过程存在于hashmap的put方法中,扩容过程始终以2次方增长。最大为2的30次方。

 

HashMap是泛型类,key和value可以为任何类型,包括null类型。key为null的键值对永远都放在以table[0]为头结点的链表中,当然不一定是存放在头结点table[0]中。对于是否能存放key或者value能否存放null类型,可以参考《阿里巴巴开发手册》-(五)集合处理-11

 

最后:

第一次看源码,有不足之处可以在下方或留言板给博主留言,多多指教

看源码一定要有求知欲和耐心,强烈的求知欲是最核心的驱动力,因为这是一个很枯燥的过程,当了解完其中的原理,我们在日常开发过程中,可以让我们写出高质量的代码。

 

 

人生充满着期待,梦想连接着未来。

喜欢 10

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Title - Artist
0:00