在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源码来分析的其原理和实现。
实例属性
链表节点的数据结构为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;
}
HashMap容器的创建,采用了延迟初始化,创建容器时,只是指定了负载系数(loadFactor)和扩展阈值(threshold),真正创建容器,是在put第一个元素的时候;而HashMap的容量被指定为2的整数平方倍,下面来看一下怎么保证容量始终为2的整数平方倍:
这个方法可能不会那么直观的理解他的意思,下面通过一个图来说明一下:
为什么容量始终是2的整数平方倍呢?我们先看一下Hash算法是怎么确定数组下标的:
发现用hash的值与容器容量减1做按位与运算。而容器容量为2的整数平方倍,再减一的话,转化成二进制除最高位左面的位上是0,其他所有位都是1,这样做与运算得到的结果,必然落在length内,而且效率要比取模运算快。
HashMap的put操作
HashMap的get操作
HashMap的remove操作
通过分析put、get、remove源码,发现HashMap的添加、获取、删除操作,都是基于三种结构进行的,即数组、链表、红黑树。
为什么要将链表进行树化操作呢?可以看看1.7版本之前的HashMap实现,hash碰撞之后,将无限增加链表的长度,大家都知道链表的添加、查找、删除时间复杂度是O(n),这使得HashMap在发生hash碰撞之后,效率变成了链表,而完全用散列实现,在元素比较多的时候,意味着资源的浪费,所以带有自平衡属性红黑树的引入,使得HashMap整体结构和效率更加平衡。二叉树的添加、查找、删除操作的时间复杂度是O(logn)。(对于红黑树的分析,不做展开,将有专门一篇专门的文章来分析红黑树)
其实链表的树化操作,就是将第一个节点作为红黑树的根,逐渐向红黑树中添加元素,最后将平衡后的红黑树的根,放在数组下标位置,作为第一个元素
一、删除节点后,红黑树的数量太少(黑高小于2)
二、当发生扩容时,HashMap将进行rehash操作,所有元素要重新计算一次,红黑树进行将分裂操作,这时候如果子树长度小于树退化阈值(UNTREEIFY_THRESHOLD = 6),进行退化成链表处理
红黑树是一种自平衡的二叉查找树,红黑树的查找,还是二叉树的查找,时间复制度为O(logn),而红黑树的添加和删除,因为红黑树具有平衡的性质,所以每次添加、删除操作之后,时需要进行再平衡操作,以保证继续满足红黑树的性质;
虽然红黑树添加、删除之后需要平衡操作,但平衡操作可以在几种固定情况的旋转操作,就可以重新恢复平衡,所以时间复制度还是O(logn)。
在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策略主要是在使用迭代器过程中,发现并发修改了,将会抛出ConcurrentModificationException,保证这个策略的关键变量就是modCount。