java集合框架之HashMap

2018年05月03日 5点热度 0人点赞 0条评论

HashMap概述

HashMap是我们使用最多的的Collection,它是基于哈希表的Map接口的实现,以key-value的形式存储,系统会根据hash算法来计算key-value的存储位置。

HashMap最多只允许一条记录的键为null,允许多条记录的值为null。

HashMap并不是一个线程安全的类,如果需要进行多线程的访问,可以考虑一下方式:
1. Map map = Collections.synchronizedMap(new HashMap(...))
2. 使用HashTable
3. 使用ConcurrentHashMap(推荐使用)

本文源码若无特殊说明,源码均为JDK1.8

HashMap源码解析

HashMap定义

HashMap实现了Map接口,继承AbstractMap,其中Map接口定义了键映射到值的规则,而AbstractMap类提供Map 接口的骨干实现,其接口实现如下:

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

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

HashMap构造函数

HashMap提供了4个构造函数:

HashMap存储机制

当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,同一各链表上的Hash值是相同的,所以说数组存放的是链表。而当链表长度太长时,链表就转换为红黑树,这样大大提高了查找的效率。

其存储结构如下图所示:

从结构实现来看,HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的

HashMap就是使用哈希表来存储的。哈希表为解决冲突,可以采用开放地址法和链地址法等来解决问题,Java中HashMap采用了链地址法。链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上,例如执行下面代码:

map.put("starlin","111")

系统将调用starlin这个key的的hashCode()方法得到其hashCode值,然后在通过Hash算法的后两部运算(高位运算和取模运算)来定位该键值对的存储位置,有时两个key会定位到相同的位置,表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀,Hash碰撞的概率就越小,map的存取效率就会越高。

如果Node<k,v>[] table(哈希桶数组)很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,其实就是在根据实际情况确定哈希桶数组的大小,并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小,哈希桶数组(Node[] table)占用空间又少呢?答案就是好的Hash算法和扩容机制。

在理解Hash和扩容流程之前,我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知,构造函数就是对下面几个字段进行初始化,源码如下:

int threshold; // 所能容纳的key-value对极限
final float loadFactor; // 负载因子
int modCount;
int size;

首先,Node[] table的初始化长度length(默认值是16),Load factor为负载因子(默认值是0.75),threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说,在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多

结合负载因子的定义公式可知,threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目,超过这个数目就重新resize(扩容),扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子Load factor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1。

size这个字段其实很好理解,就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数,主要用于迭代的快速失败。强调一点,内部结构发生变化指的是结构发生变化,例如put新键值对,但是某个key对应的value值被覆盖不属于结构变化。

在HashMap中,哈希桶数组table的长度length大小必须为2的n次方(一定是合数),这是一种非常规的设计,常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数,具体证明可以参考这里,Hashtable初始化桶大小为11,就是桶大小设计为素数的应用(Hashtable扩容后不能保证还是素数)。HashMap采用这种非常规设计,主要是为了在取模和扩容时做优化,同时为了减少冲突,HashMap定位哈希桶索引位置时,也加入了高位参与运算的过程。

这里存在一个问题,即使负载因子和Hash算法设计的再合理,也免不了会出现拉链过长的情况,一旦出现拉链过长,则会严重影响HashMap的性能。于是,在JDK1.8版本中,对数据结构做了进一步的优化,引入了红黑树。而当链表长度太长(默认超过8)时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。本文不再对红黑树展开讨论,想了解更多红黑树数据结构的工作原理可以参考这里

HashMap的数据结构

1. HashMap中的属性

2. 数组元素Node<K,V>实现了Entry接口

其中有个哈希桶数组Node<k,v>[] table
Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。

3. 红黑树

4. HashMap的存取
4.1 确定哈希桶数组索引位置JDK7/8区别

不管增加、删除、查找键值对,定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,不用遍历链表,大大优化了查询的效率。HashMap定位数组索引位置,直接决定了hash方法的离散性能。先看看源码的实现:

在jdk1.8中实现如下:

在jdk1.7中实现如下:

这里的Hash算法就是三步:取key的hashcode值,高位与运算,取模运算

在JDK1.7中hash算法非常巧妙,通过h & (length-1) 来确定对象的保存位置,当length总是2的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

在JDK1.8中,采用高位运算的算法,通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16)),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

如下图所示,n为table的长度:

4.2 put方法JDK8

HashMap的put方法执行过程可以通过下图来理解

JDK1.8HashMap的put方法源码如下:

和 Java7 稍微有点不一样的地方就是,Java7 是先扩容后插入新值的,Java8 先插值再扩容,不过不影响

根据以上源码,可以简单总结下put(key,value)的过程:
1,判断键值对数组tab[]是否为空或为null,否则以默认大小resize();
2,根据键值key计算hash值得到插入的数组索引i,如果tab[i]==null,直接新建节点添加,否则转入3
3,判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理

4.3 put方法JDK7

JDK1.7HashMap的put方法源码如下:

初始化数组方法inflateTable(),将数组大小保持为2的n次方

添加节点到链表中addEntry(),这个方法的主要逻辑就是先判断是否需要扩容,需要的话先扩容,然后再将这个新的数据插入到扩容后的数组的相应位置处的链表的表头。

4.4 扩容机制JDK8

扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组

JDK1.8中的resize源码如下:

在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示意图:

这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别,JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置

4.5 扩容机制JDK7

在插入新值的时候,如果当前的 size 已经达到了阈值,并且要插入的数组位置上已经有元素,那么就会触发扩容,扩容后,数组大小为原来的 2 倍。

JDK1.7的扩容机制源码如下:

这里就是使用一个容量更大的数组来代替已有的容量小的数组,由于是双倍扩容,迁移过程中,会将原来 table[i] 中的链表的所有节点,分拆到新的数组的 newTable[i] 和 newTable[i + oldLength] 位置上。如原来数组长度是 16,那么扩容后,原来 table[0] 处的链表中的所有元素会被分配到新数组中 newTable[0] 和 newTable[16] 这两个位置。

transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里,源码如下:

newTable[i]的引用赋给了e.next,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话)

4.6 get方法JDK8

相对于put来说,get很简单,大概下面几步
1. 计算 key 的 hash 值,根据 hash 值找到对应数组下标
2. 判断数组该位置处的元素是否刚好就是我们要找的,如果不是,走第三步
3. 判断该元素类型是否是 TreeNode,如果是,用红黑树的方法取数据,如果不是,走第四步
4. 遍历链表,直到找到相等(==或equals)的 key

对应的源码如下:

4.7 get方法JDK7

JDK7的get过程大概分为以下几步:
1. 根据 key 计算 hash 值。
2. 找到相应的数组下标,hash & (length - 1)
3. 遍历该数组位置处的链表,直到找到相等(==或equals)的 key。

源码如下:

getEntry(key)方法:

参考

  1. JDK1.7&JDK1.8 源码。
  2. Java 8系列之重新认识HashMap
  3. Java7/8 中的 HashMap全解析
  4. Java中HashMap底层实现原理(JDK1.8)源码分析

starlin

生而无畏,战至终章

文章评论