HashMap在jdk8中的源码分析
底层存储:
存储单元:
HashMap在jdk8中是通过一个个HashMap.Node进行存储的
- HashMap.Node是HashMap中的一个内部类
- HashMap.Node实现了Map.Entry
存储结构:
HashMap在jdk8中使用数组 + 链表 + 红黑树进行存储
初始化
HashMap h = new HashMap();
这个时候我们底层没有直接创建一个长度为16的数组,而是先创建了一个长度为0的空的table数组
- 创建了一个空的HashMap.Node[ ] ,这个创建的数组名为table
- 这里我们开始时不直接创建一个长度为16的数组是为了提高效率
在第一次使用put()方法时我们才会在底层创建一个长度为16的数组(默认创建方式)
- 但是我们在实际编程中往往都是创建一个给定容量的集合(也就是使用HashMap类的有参构造方法)
- 我们创建已给给定容量的集合可以提高效率
- 当我们实际编程中如果要在这个集合中添加的元素很多时,这个时候我们就直接创建一个容量比较大的集合 ---- 就可以减少扩容的次数,提高程序的执行效率
- 当我们实际编程中如果在这个集合中添加的元素很少时,这个时候我们就直接创建一个容量比较小的结合 ---- 这样就减少了内存空间的占用率,也就提高了程序的执行效率
树化:
由于我们在jdk8中是使用数据 + 链表 + 红黑树对HashMap对象进行存储,这个时候我们比jdk7中多加了一种使用红黑树的方式
- 当我们底层的table数组中某一个索引位置处元素数目 > 8个,并且如果这个时候我们底层的table数组的容量 > 64,那么这个时候我们底层的链表就会变成红黑树
为什么我们要使用红黑树来代替链表?
使用红黑树代替链表可以提高集合中元素的查询效率
- 如果我们table数组中某一个位置处有10000个元素,这个时候如果我们要查找的元素就在这个索引处,这个时候如果我们这里是使用双向链表进行存储,那么这个时候如果我们要找到这个元素我们就要将这10000个元素遍历一遍,这个时候的效率就会比较慢
- 如果这个时候这个位置的10000个元素是通过红黑树进行存储的,这个时候如果我们想查到这个元素我们就可以使用折半查找的方式来找到这个元素,这个时候就能大大提高查找的效率
注意:在我们进行树化的时候有一个注意点,如果这个时候我们底层数组的某个索引位置的元素超过了8个,但是这个时候如果我们的底层数组的容量没有超过64个,这个时候我们就会对数组进行扩容,然后一旦扩容就会重排,然后扩容之后我们如果某个索引位置的元素个数又超过了8个,这个时候如果我们的底层数组容量超过了64个,那么这个时候底层的链表就会变成红黑树
为什么当底层数组中某一个索引位置的元素个数> 8个,并且数组容量超过了64个才进行树化?
这个时经过大量的总结和实验的出的结果,当满足这个条件之后我们进行树化才是值得的,才会对我们的程序的执行效率有比较大的提升,这个时候如果我们的数组比较短,或者是链表比较短,这个时候使用链表或者是使用红黑树其实效率相差并不是很大,这个时候我们如果进行树化,那么树化也会需要实现,这个时候就不值得
数组扩容:
HashMap在jdk8中扩容时也是扩容为原来的2倍
但是jdk8中多了一种需要扩容的情况(jdk7中只要一种,就是当我们的底层数组的容量超过了临界值的时候)
- 当底层数组的容量超过了临界值时
- 默认临界值(threshold)为12
- 临界值 = 数组容量 *(乘) 加载因子(DEFAULT_LOAD_FACTOR)
- 所以默认临界值 + 默认数组容量 * 默认加载因子(12 = 16 * 0.75)
- 当我们的数组中的某个索引处的元素个数> 8时,并且如果这个时候底层的数组容量不超过64,这个时候我们数组也要进行扩容看
关于HashMap底层源码中要记忆的常量和变量
- DEFAULT_LOAD_FACTOR ----- 默认加载因子 ---- 0.75
- DEFAULT_INITIAL_CAPACITY ----- 默认初始化容量 ---- 16
- threshold ----- 底层数组扩容的容量的临界值 ---- 12
- TREEIFY_THRESHOLD ---- 底层链表进行树化的容量的临界值 ---- 8
- MIN_TREEIFY_CAPACITY ----- 底层数组进行树化的长度的最小值 ---- 64
|