HashMap源码实现分析一、前言HashMap 顾名思义,就是用hash表的原理实现的Map接口容器对象,那什么又是hash表呢。 我们对数组都很熟悉,数组是一个占用连续内存的数据结构,学过C的朋友对这一点影响肯定更为深刻。既然是一段连续的内存,数组的特点就显而易见了,一旦你知道要查第几个数据,时间复杂度就是O(1),但是对于插入操作就很困难;还有一种数据结构你也一定很熟悉,那就是链表,链表由一组指向(单向或者双向)的节点连接的数据结构,它的特点是内存不连续,查找困难,但是插入删除都很容易。 那有没有一种查找容易,插入删除查找都容易的数据结构呢, 没错,它就是hash表。 本篇,我们就来讨论:
要了解HashMap 最好的方式就是看源码,本篇内容基于Jdk1.8HashMap源码。 二、HashMap的基本要素磨刀不误砍柴功,想了解HashMap的原理,必然绕不过HashMap源码中的以下几个变量:
以上内容,有个印象就好,不必每个都记得。但这些概念对理解HashMap至关重要。 三、正文3.1 HashMap 数据结构HashMap的数据结构很简单,它是一个Node类型的数组,每个元素可以为单节点、多节点链表、多节点红黑树。关键的问题是,这么简单的结构怎么实现的put、get都很快? 什么时候从单节点转成链表又是什么时候从链表转成红黑树? 3.1.1 HashMap如何实现put、get操作时间复杂度为O(1)~O(n)?我们知道,查找一个数组的元素,当我们不知道index的时候,复杂度是很高的,但是当我们知道index的时候,这个复杂度就是O(1)级别的。HashMap使用的就是这个原理。 对于put操作,我们知道,数组插入元素的成本是高昂的,HashMap巧妙的使用链表和红黑树代替了数组插入元素需要移动后续元素的消耗。这样在最好的情况下,插入一个元素,该index位置恰好没有元素的话,时间复杂度就是O(1),当该位置有元素且为链表或者红黑树的情况下,时间复杂度会上升,但是最坏的情况下也就是O(n)。 3.1.2 HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树?单节点转链表很简单,当根据新加入的值计算出来的index处有元素时,若元素为单节点,则从节点转为链表。
当同时满足这两个条件,那么就会触发链表转红黑树的操作。 3.2 HashMap初始化时为什么要给自定义的初始容量?为啥前辈们都要求定义一个HashMap的时候一定要使用构造函数HashMap(int initialCapacity)指定初始容量呢? 在阿里的《Java开发手册》中是这样说明的:
这个问题在HashMap源码中是显而易见的,每次put函数中都会检查当前size是否大于threshold,如果大于就会进行扩容,新容量是原来容量的二倍。那么问题就来了,当你要存大量数据到HashMap中而又不指定初始容量的话,扩容会被一次接一次的触发,非常消耗性能。 而初始容量和负载因子给多少好呢,日常开发中如无必要不建议动负载因子,而是根据要使用的HashMap大小确定初始容量,这也不是说为了避免扩容初始容量给的越大越好, 越大申请的内存就越大,如果你没有这么多数据去存,又会造成hash值过于离散。 3.3 HashMap如何保证容量始终是2的幂HashMap使用方法tableSizeFor()来保证无论你给值是什么,返回的一定是2的幂:
首先我们来看操作:
假设 n=01000000, n |= n >>> 1后 n=01100000,n |= n >>> 2后n=01111000,n |= n >>> 4;后n=01111111,我们可以发现,上述5步操作可以将一个32位数第一位为1的后面所有位全变为1。这样再执行n + 1操作后,该数就必为2的幂次方了。如01111111+1 = 10000000。 3.3.1 HashMap为何要保证容量始终是2的幂说到这个问题不得不说执行put()方法时,是如何根据hash值在table中定位。
可以看到,它使用了一个 (n - 1) & hash的操作,n为当前hashmap的容量,而容量一定为2的幂次方,n-1的二进制低位都为1,举例:16=0000000000010000,15=0000000000001111,这样的处理好处在于,当执行(n - 1) & hash的操作时,元素的位置仅取决于低位而与高位无关(这种无关性随着HashMap容量的增大而减小),这个逻辑优点是,无论你的hash值有多大,我都锁定了你的取值范围小于当前容量,这样做避免了hash值过于离散的情况,而当HashMap扩容时又可以同时增大hash值的取值范围,缺点是增加了hash碰撞的可能性,为了解决这个问题HashMap修改了hash值的计算方法来增加低位的hash复杂度。 3.3.2 HashMap计算hash值不废话,直接上源码:
hash方法用 key的hash值异或上key的hash值的高16位,为什么要这样做呢? 3.4 HashMap为什么是线程不安全的在Jdk1.7中,造成HashMap线程不安全的原因之一是transfer函数,该函数使用头查法在多线程的情况下很容易出现闭环链表从而导致死循环,同时还有数据丢失的问题,Jdk1.8中没有transfer函数而是在resize函数中完成了HashMap扩容或者初始化操作,resize采用尾插法很好的解决了闭环链表的问题,但是依旧避免不了数据覆盖的问题。
在执行完 if ((tab = table) == null || (n = tab.length) == 0)判断且为true的情况下,会直接进行赋值,但是在多线程的环境下,当两个线程同时完成判断,线程1刚赋值完,线程2再进行赋值,就造成了数据覆盖的问题。 HashMap基本的原理和对应实现就说到这里了,更深入的话题如:红黑树插入节点、平衡红黑树、遍历红黑树,可以直接看红黑树对应的原理和实现。 需要源码注释的请戳这里源码解析 |
|