Java集合 | 重识HashMap

众所周知,Map是键值对<key,value>形式,Map又叫映射,可以理解为数学中的函数(key-x,value-y之间存在某种函数关系)。HashMap主要是用散列方式实现的Map容器,即散列映射,对key进行散列运算,可以直接找到value,而不需要像列表或者链表那样,线性遍历查找。HashMap不同于TreeMap,主要用于存储无序的数据。

在Java中,Map接口主要定义了映射容器的一些基本属性,包括长度(size)、是否为空(isEmpty)、获取(get)、存放(put)、移除(remove),包含(contains),迭代(forEach)等。HashMap继承自Map,在1.8版本也做了很大的调整,主要用数组 + 链表+ 红黑树的存储实现方式,代替了老版本的数组 + 链表的方式。1.8版本之前,在添加元素发生hash碰撞时(这里的hash碰撞,就是根据key值得到的hash值,在进行计算得到的下标相同,但hash可能不一样),随着发生碰撞的元素越来越多,链表会一直增长,使检索效率逐渐退化成线性。1.8版本,采用了红黑树之后,提升了发生hash碰撞的元素的检索效率,使整体结构更加平衡。

那HashMap是怎么实现散列映射的呢,一图胜千言:

将key值进行hash计算,再根据hash值得到索引值,确定value在数组中的位置,将key,value,hash构建成Node(链表节点的数据结构),即新元素。如果此位置没有元素,则放入数组,此时数组下标位置相当于只有头元素的链表;如果此位置已经存在元素,则将新元素追加到当前链表的尾部。当链表长度超过8时,将链表结构进化为红黑树。下面将对照HashMap源码来分析的其原理和实现。

  • 基本属性
    • 默认初始容量:DEFAULT_INITIAL_CAPACITY = 1 << 4
    • 最大容量:MAXIMUM_CAPACITY = 1 << 30
    • 默认负载系数:DEFAULT_LOAD_FACTOR = 0.75f
    • 树进化阈值:TREEIFY_THRESHOLD = 8
    • 树退化阈值:UNTREEIFY_THRESHOLD = 6

实例属性

  • map集合长度:size
  • 扩容阈值:threshold
  • 负载系数:loadFactor
  • 修改数量:modCount

  • 存储结构

链表节点的数据结构为Node,实现自Map.Entry

Node{
    int hash;
    K key;
    V value;
    Node<K,V> next;
}

链表数组

Node<K,V>[] table

红黑树节点的数据结构为TreeNode,是Node的子类,多了红黑树的属性(父,左右子,颜色等)。

TreeNode{
    int hash;
    K key;
    V value;
    Node<K,V> next;
    Entry<K,V> before, after;
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
}
  • Hash算法和容量

HashMap容器的创建,采用了延迟初始化,创建容器时,只是指定了负载系数(loadFactor)和扩展阈值(threshold),真正创建容器,是在put第一个元素的时候;而HashMap的容量被指定为2的整数平方倍,下面来看一下怎么保证容量始终为2的整数平方倍:

  • 不指定容量的话,初始为16;
  • 如果指定的话,会使用tableSizeFor()方法转化为一个2的整数平方倍。赋给实例变量threshold,到创建容器时候又将threshold赋给了新容量。

这个方法可能不会那么直观的理解他的意思,下面通过一个图来说明一下:

  1. 指定了一个容量 1207959552,大概2的30次方左右,转化成二进制;
  2. 然后分别右移1位、2位、4位、8位、16位,并且每次移位之后,根移位之前的数做一次按位或操作;
  3. 最后就会得到都是1的数,这个数再加1,还是2的整数平方倍,也就是比指定数大的最小2的整数平方倍
  4. 两个问题:
    1. 为什么每次1、2、4、8、16移动? 这样才能保证所有的低位都能刚好被覆盖到,因为就是想得到2的整数平方倍-1的数,这样数的特点就是所有位都是1
    2. 为什么一共移动31位? HashMap指定了最大容量为 1 << 30(2的30次方),所以能保证将 1<<31的数都能转化成所有位都为1的数。
  • 扩容,每次扩容为原容量的2位

为什么容量始终是2的整数平方倍呢?我们先看一下Hash算法是怎么确定数组下标的:

发现用hash的值与容器容量减1做按位与运算。而容器容量为2的整数平方倍,再减一的话,转化成二进制除最高位左面的位上是0,其他所有位都是1,这样做与运算得到的结果,必然落在length内,而且效率要比取模运算快。

  • put、get、remove

HashMap的put操作

HashMap的get操作

HashMap的remove操作

通过分析put、get、remove源码,发现HashMap的添加、获取、删除操作,都是基于三种结构进行的,即数组、链表、红黑树。

  • 数组:因为HashMap是对key进行,hash算法直接确定的数组位置,不进行数组元素的移动,所以数组添加、修改、删除操作时间复杂度是O(1)
  • 链表:链表的添加操作是每次需要向链表尾部添加;查找也是线性的遍历链表以找到与key值相等的元素;删除操作包含查找操作,所以链表的时间复杂度是O(n)
  • 红黑树:稍后分析

  • 红黑树

为什么要将链表进行树化操作呢?可以看看1.7版本之前的HashMap实现,hash碰撞之后,将无限增加链表的长度,大家都知道链表的添加、查找、删除时间复杂度是O(n),这使得HashMap在发生hash碰撞之后,效率变成了链表,而完全用散列实现,在元素比较多的时候,意味着资源的浪费,所以带有自平衡属性红黑树的引入,使得HashMap整体结构和效率更加平衡。二叉树的添加、查找、删除操作的时间复杂度是O(logn)。(对于红黑树的分析,不做展开,将有专门一篇专门的文章来分析红黑树)

  • 链表树化

其实链表的树化操作,就是将第一个节点作为红黑树的根,逐渐向红黑树中添加元素,最后将平衡后的红黑树的根,放在数组下标位置,作为第一个元素

  • 红黑树退化:红黑树退化存在两种场景

一、删除节点后,红黑树的数量太少(黑高小于2)

二、当发生扩容时,HashMap将进行rehash操作,所有元素要重新计算一次,红黑树进行将分裂操作,这时候如果子树长度小于树退化阈值(UNTREEIFY_THRESHOLD = 6),进行退化成链表处理

  • 红黑树的添加、查找、删除

红黑树是一种自平衡的二叉查找树,红黑树的查找,还是二叉树的查找,时间复制度为O(logn),而红黑树的添加和删除,因为红黑树具有平衡的性质,所以每次添加、删除操作之后,时需要进行再平衡操作,以保证继续满足红黑树的性质;

虽然红黑树添加、删除之后需要平衡操作,但平衡操作可以在几种固定情况的旋转操作,就可以重新恢复平衡,所以时间复制度还是O(logn)。

  • HashMap的多线程表现

在1.8之前,HashMap再多线程情况下,rehash会导致死循环,主要是由于rehash过程中,链表重新计算时,顺序会由原来的1->2->3,变成3->2->1,也就是将原链表的数据,按照依次向链表头插入元素的操作(链表添加动作,1.8向尾部添加,1.7向头部添加)。如果两个线程同时进入红色框中时,可能会导致链表的环状指向,导致死循环。

而在1.8中不存在这种情况,因为1.8不是向链表头追加元素的,而是向链表尾部添加元素,这样保证了链表的顺序操作;另外1.8版本使用高位链表和低位链表两个链表来完成rehash动作的,循环完成后,两个新链表再重新放到对应的数组下标下,所以无论多少个线程同时执行,都会是重复一样的动作,不会出现1.7那样的死循环。

但1.8仍然会出现线程安全问题,开启多个线程同时向map中进行put()、get()操作,运行几次发现报如下错误:

因为同时进行put操作,当超过树化阈值时,进行树化操作,再进行将新树的根放到对应数组索引位置时候,根节点不再是TreeNode类型的节点了,为什么出现这种情况呢?感觉像是树化操作之后,在操作树的根节点时候,刚好发生了树的分裂,退化成非树节点了导致的(猜想)。

  • fail-fast策略

fail-fast策略主要是在使用迭代器过程中,发现并发修改了,将会抛出ConcurrentModificationException,保证这个策略的关键变量就是modCount。

  • 总结
  1. Hash算法
  2. HashMap的碰撞
  3. equals()和hashCode()、Comparable接口,在HashMap中的应用
  4. 扩容和rehash
  5. 红黑树
  6. 线程安全性
  7. fail-fast策略

  • 散列表
  • https://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8
  • 红黑树
  • http://www.banzclub.com/technical/red-black-tree.html
  • 深入理解HashMap
  • http://www.iteye.com/topic/539465
  • 谈谈HashMap线程不安全的体现
  • http://www.importnew.com/22011.html

本文分享自微信公众号 - BanzClub(banz-club)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券