HashMap 的源码,实现原理,底层结构。

这篇文章主要是解答
java2017 面试题 里面的第二个问题,也顺便看一下源码巩固一下。

HashMap 简述

  • 一般定义这种东西都是不常用到,也比较难以记住的,所以我就摘抄百度百科的定义吧:

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键 - 值映射关系数)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。

HashMap 源码

HashMap 实现原理

HashMap 的构造方法

由于最新版 java9 的源码现在正在下载中,我就浏览了一下旧版的 jdk 文档,就先看文档来说吧,等下载到了源代码,再酌情补充。下面图中就是 HashMap 的集中构造器
670bd56a251a4cd1973eb174021bbb24_blob.png

在 java9 中,HashMap 的构造器事实上也是上图中的这几种,下面我们就具体的看一下每一种构造的代码实现

1.HashMap()

官方文档给出的描述:Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75).
翻译成中文意思就是说:构造一个空的 HashMap, 其初始容量为 16,默认的加载因子是 0.75

那么这个初始容量和默认的加载因子是做什么的呢?
首先,初始容量大家都能理解,就是为了节省资源,初始化的时候给定一个 最大容量 ;当然这个最大容量也不是固定不变的,在适当的时候 HashMap 会自动进行扩容,扩容的量为当前容量的 2 倍,而这个扩充的时间点就由 0.75 这个负载因子决定,也就是当 HashMap 的达到 当前最大容量 的 75% 的时候,就会进行扩容。 比如:初始容量为 16 的 HashMap, 当 size 到达 12 的时候,就会自动进行第一次扩容,扩容后容量变为 32

1.  // Find a power of 2 >= initialCapacity  
2.      // 这里需要注意一下  
3.      int capacity = 1;  
4.      while (capacity < initialCapacity)  
5.          capacity <<= 1;

上面的代码片段就是 HashMap()这个构造器中的部分代码,在这里是进行了一个位运算,也就决定了 HashMap 每次扩容都要是 2 的幂 ,所以每次扩容就是原来的 2 倍。

2.HashMap(int initialCapacity)

Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75).

了解了前一个构造器,对于这一个也就不难理解了, 这个就是把默认的 16 改为自己传参来作为初始容量而已,默认的负载因子依然是 0.75,但是如上文所说,这个容量必须是 2 的幂,重复一遍, 假如你 new HashMap(6) , 那么它的容量是 8

3.HashMap(int initialCapacity, float loadFactor)

Constructs an empty HashMap with the specified initial capacity and load factor.

4.HashMap(Map < extends K,? xtends V> m)

Constructs a new HashMap with the same mappings as the specified Map.

未完待续……