Map实现类之一:HashMap 介绍

2020-11-19 0 By admin

HashMap是Map接口使用频率最高的实现类。允许使用null键和null值,与HashSet一样,不保证映射的顺序。

一、HashMap 实现类概述

所有的key构成的集合是Set:无序的、不可重复的。所以,key所在的类要重写:equals()和hashCode()
所有的value构成的集合是Collection:无序的、可以重复的。所以,value所在的类要重写:equals()

1.1、每个元素构成一个 entry

一个key-value构成一个entry。所有的entry构成的集合是Set:无序的、不可重复的。
HashMap判断两个key相等的标准是:两个key通过equals()方法返回true,hashCode值也相等。
HashMap判断两个value相等的标准是:两个value 通过equals()方法返回true。

1.2、HashMap源码中的重要常量

  1. DEFAULT_INITIAL_CAPACITY : HashMap的默认容量,16
  2. DEFAULT_LOAD_FACTOR:HashMap的默认加载因子:0.75
  3. threshold:扩容的临界值,=容量*填充因子:16 * 0.75 => 12
  4. TREEIFY_THRESHOLD:Bucket中链表长度大于该默认值,转化为红黑树:8
  5. MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量:64

二、HashMap的底层实现原理

  1. JDK 7及以前版本:HashMap是数组+链表结构(即为链地址法)
  2. JDK 8版本发布以后:HashMap是数组+链表+红黑树实现。

2.1、HashMap在JDK7中的底层实现原理

HashMap的内部存储结构其实是数组和链表的结合。

  1. 当实例化一个HashMap时,系统会创建一个长度为Capacity的Entry数组,这个长度在哈希表中被称为容量(Capacity)。
  2. 在这个数组中可以存放元素的位置我们称之为“桶”(bucket),每个bucket都有自己的索引,系统可以根据索引快速的查找bucket中的元素。
  3. 每个bucket中存储一个元素,即一个Entry对象。
  4. 但每一个Entry对象可以带一个引用变量,用于指向下一个元素,因此,在一个桶中,就有可能生成一个Entry链。而且新添加的元素作为链表的head。
JDK7 中HashMap 存储结构
JDK7 中HashMap 存储结构
2.1.1、添加元素的过程

向HashMap中添加entry1(key,value),需要首先计算entry1中key的哈希值(根据key所在类的hashCode()计算得到),此哈希值经过处理以后,得到在底层Entry[]在数组中要存储的位置i。

  1. –如果位置i上没有元素,则entry1直接添加成功。
  2. –如果位置i上已经存在entry2(或还有链表存在的entry3,entry4),则需要通过循环的方法,依次比较entry1中key的hash值和其他的entry的hash值。
  3. —–如果彼此hash值不同,则直接添加成功。
  4. —–如果hash值相同,继续比较二者是否equals。如果返回值为true,则使用entry1的value去替换equals为true的entry的value。
  5. ——-如果遍历一遍以后,发现所有的equals返回都为false,则entry1仍可添加成功。entry1指向原有的entry元素。
2.1.2、HashMap的底层实现原理?(以jdk7为例说明)
 HashMap map = new HashMap():
 在实例化以后,底层创建了长度是16的一维数组Entry[] table。
 ...可能已经执行过多次put...
 map.put(key1,value1):
 首先,调用key1所在类的hashCode()计算key1哈希值,此哈希值经过某种算法计算以后,得到在Entry数组中的存放位置。
 如果此位置上的数据为空,此时的key1-value1添加成功。 ----情况1
 如果此位置上的数据不为空,(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值:
        如果key1的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1添加成功。----情况2
        如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同,继续比较:调用key1所在类的equals(key2)方法,比较:
             如果equals()返回false:此时key1-value1添加成功。----情况3
             如果equals()返回true:使用value1替换value2。

补充:关于情况2和情况3:此时key1-value1和原来的数据以链表的方式存储。
在不断的添加过程中,会涉及到扩容问题,当超出临界值(且要存放的位置非空)时,扩容。默认的扩容方式:扩容为原来容量的2倍,并将原有的数据复制过来。

2.1.3、HashMap的扩容

当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,
因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容,而在HashMap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。

2.1.4、那么HashMap什么时候进行扩容呢?

当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时,就会进行数组扩容。
LoadFactor的默认值(DEFAULT_LOAD_FACTOR)为0.75,这是一个折中的取值。
也就是说,默认情况下,数组大小(DEFAULT_INITIAL_CAPACITY)为16,那么当HashMap中元素个数超过16*0.75=12(这个值就是代码中的threshold值,也叫做临界值)的时候,就把数组的大小扩展为2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作。
所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。

2.2、HashMap在JDK8中的底层实现原理

HashMap的内部存储结构其实是数组+链表+红黑树的结合。
当实例化一个HashMap时,会初始化initialCapacity和loadFactor。
在put第一对映射关系时,系统会创建一个长度为initialCapacity的Node数组,这个长度在哈希表中被称为容量(Capacity)。
在这个数组中可以存放元素的位置我们称之为“桶”(bucket),每个bucket都有自己的索引,系统可以根据索引快速的查找bucket中的元素。

 JDK8 中HashMap 存储结构
JDK8 中HashMap 存储结构
2.2.1、每个bucket中存储一个元素

新添加的元素作为链表的last,或树的叶子结点。

  1. 可以是一个Node对象,但每一个Node对象可以带一个引用变量next,用于指向下一个元素,因此,在一个桶中,就有可能生成一个Node链。
  2. 也可能是一个一个TreeNode对象,每一个TreeNode对象可以有两个叶子结点left和right,因此,在一个桶中,就有可能生成一个TreeNode树。
2.2.2、那么HashMap什么时候进行扩容和树形化呢?

扩容:JDK8 中 HashMap 扩容的过程和 JDK7的过程相同。
树形化:

  1. 当HashMap中的其中一个链的对象个数如果达到了8个,此时如果capacity没有达到64,那么HashMap会先扩容解决。
  2. 如果数组的长度(容量)已经达到了64,那么这个链会变成红黑树,结点类型由Node变成TreeNode类型。
  3. 当然,如果当映射关系(元素)被移除后,下次resize方法时判断树的结点个数低于6个,也会把红黑树再转为链表。
2.2.3、关于映射关系的key是否可以修改?【重要】

answer:不要修改。
映射关系存储到HashMap中会存储key的hash值,这样就不用在每次查找时重新计算每一个Entry或Node(TreeNode)的hash值了。
因此如果已经put到Map中的映射关系,再修改key的属性,而这个属性又参与hashcode值的计算,那么会导致匹配不上。即数据存在,但根据查找逻辑查找不到这个Node。

2.3、jdk8 相较于jdk7在底层实现方面的不同

  1. new HashMap():底层没有创建一个长度为16的数组。
  2. jdk 8底层的数组是:Node[],而非Entry[]。
  3. 首次调用put()方法时,底层创建长度为16的数组。
  4. jdk7底层结构只有:数组+链表。jdk8中底层结构:数组+链表+红黑树。
    1. 形成链表时,七上八下(jdk7:新的元素指向旧的元素。jdk8:旧的元素指向新的元素)
    2. 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时,此时此索引位置上的所数据改为使用红黑树存储。