Java HashMap笔记之一:基本原理

时间:2021-08-27 04:15:28
摘要: Java中的HashMap是一种简单易用而且高效强大的数据结构,在开发过程中经常使用。这里总结下HashMap的基本原理。HashMap默认内部数组大小?HashMap内部数组为16(JDK7和JDK8都是)。HashMap Default Capacity如果初始 ...

Java中的HashMap是一种简单易用而且高效强大的数据结构,在开发过程中经常使用。这里总结下HashMap的基本原理。

Java HashMap笔记之一:基本原理

HashMap默认内部数组大小?

HashMap内部数组为16(JDK7和JDK8都是)。

Java HashMap笔记之一:基本原理

HashMap Default Capacity

如果初始化大小为33,内部数组真实大小是多少?

内部数组真实大小是64。HashMap带有initialCapacity参数的构造方法会调用tableSizeFor方法进行设置,结果为大于等于initialCapacity的最小的2的幂。以下代码都是JDK8的源码,JDK7类似。

Java HashMap笔记之一:基本原理

Java HashMap笔记之一:基本原理

JDK8生成数组大小方法

HashMap内部数组大小为什么是2的幂?

HashMap充分利用了二进制中1的信息,通过hash(key) & (capacity - 1)获取内部数组中的索引位置。当capacity为2的幂的时候,capacity - 1的二进制的1的个数是最多,可以最充分的利用数组。

比如capacity = 17的时候,capacity - 1 = 16 = 0x0001 0000,这样,hash & (capacity - 1)只能有2个值,0x0000 0000 和0x0001 0000,为了最方便和充分的使用数组索引,数组的大小最好是2的幂。

Java HashMap笔记之一:基本原理

HashMap通过Hash获取索引

HashMap什么时候开辟内部数组内存?

HashMap在new的时候只是进行内部参数的初始化,但是不会对数组进行内存申请,只有在第一次put操作的时候才会开辟内存,也就是一般说的lazy模式。

Java HashMap笔记之一:基本原理

HashMap无参构造方法

可以看到在new的时候没有进行任何的内存申请的操作,而是在put的时候判断内部数组是否为空,如果为空,先进行初始化再put元素。以下代码为JDK7的源码,相对JDK8的源码比较容易理解,JDK8中直接调用resize方法申请内存。

Java HashMap笔记之一:基本原理

Java HashMap笔记之一:基本原理

PS: inflate是打气筒,使膨胀的意思,方法名称非常形象。

HashMap为什么要扩容?

索引(index of hash(key))相同的节点会存储在内部数组相同的索引中,当数据量越来越大的时候,相同索引的节点会越来越多,导致遍历的时间会越来越久。扩容可以重新计算索引值,减少相同索引节点个数和索引时间,也就是说用空间来换取时间。

假设数组大小为16,hash值为1和17的节点都会在table[1]中,当数组大小扩容到32的时候,hash值为1的节点仍然在table[1]中,hash为17的节点会被分配到table[17]中,这样table[1]中的节点个数会变少。

HashMap何时进行扩容?

HashMap除了维护内部数组大小capacity外,还会维护loadFactor(默认为0.75),当put的时候元素数量大于等于capacity * loadFactor时会进行扩容。比如capacity=16,loadFactor=0.75,当第12(16*0.75=12)个元素put的时候,会进行扩容resize操作,扩展到原来capacity的2倍,因为之前是2的幂,所以扩容后仍然是2的幂。以下代码为JDK7的源码,在调用addEntry过程中将参数传到resize方法中,JDK8中则是在resize内部进行调整。最终效果是一致的。

Java HashMap笔记之一:基本原理

HashMap Default LoadFactor

Java HashMap笔记之一:基本原理

JDK7 put value

Java HashMap笔记之一:基本原理

JDK7 resize in addEntry

JDK7和JDK8实现HashMap的区别?

  • JDK7使用数组+链表方式实现,索引相同的key在相同的链表中,新增加的key会加到链表的最后

  • JDK8使用数组+链表/红黑树的方式实现,在红黑树中的搜索时间是O(logN),好于链表的O(N)。链表和红黑树的转换规则如下:

  • 如果链表的长度超过8个,链表会转化为红黑树

  • 如果红黑树节点的个数少于6个,红黑树会转化为链表

小结

HashMap使用虽然简单,如果理解实现可以更好的利用内部特性,并借鉴设计思路。