HashMap底层实现原理解析

  |   0 评论   |   0 浏览

hashMap数据结构什么样的,数据和链表分别有什么优势

数组加链表结构 hash表

数组特点

存储区间是连续,且占用内存严重,空间复杂也很大,时间复杂为O(1)。优点:是随机读取效率很高,原因数组是连续(随机访问性强,查找速度快)。缺点:插入和删除数据效率低,因插入数据,这个位置后面的数据在内存中要往后移的,且大小固定不易动态扩展。

链表特点

区间离散,占用内存宽松,空间复杂度小,时间复杂度O(N)。优点:插入删除速度快,内存利用率高,没有大小固定,扩展灵活。缺点:不能随机查找,每次都是从第一个开始遍历(查询效率低)。

hashMap查询效率是多少

受到bucket的数据结构影响如果未树化,为链表结构,则查询的时间复杂度为O(N)如果已经树化,为红黑树结构,则查询的时间复杂度为O(logN)

以上数组和链表,大家都知道各自优缺点。那么我们能不能把以上两种结合一起使用,从而实现查询效率高和插入删除效率也高的数据结构呢?答案是可以滴,那就是哈希表可以满足,接下来我们一起复习HashMap中的put()和get()方法实现原理。

第一步时间复杂度是O(1),第二步却是O(n)(n指链表长度)。所以key.hashCode()导致产生冲突的数量决定了这张HashMap的查询性能。

hashMap初始大小是多少

构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。

hashMap负载因子的作用是什么

在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多

比如说当前的容器容量是16,负载因子是0.75,16*0.75=12,也就是说,当容量达到了12的时候就会进行扩容操作。

他的作用很简单,相当于是一个扩容机制的阈值。当超过了这个阈值,就会触发扩容机制。HashMap源码已经为我们默认指定了负载因子是0.75。

负载因子的作用肯定也是节省时间和空间

当负载因子是1.0的时候,也就意味着,只有当数组的8个值(这个图表示了8个)全部填充了,才会发生扩容。这就带来了很大的问题,因为Hash冲突时避免不了的。当负载因子是1.0的时候,意味着会出现大量的Hash的冲突,底层的红黑树变得异常复杂。对于查询效率极其不利。这种情况就是牺牲了时间来保证空间的利用率。

负载因子是0.5的时候,这也就意味着,当数组中的元素达到了一半就开始扩容,既然填充的元素少了,Hash冲突也会减少,那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。

但是,兄弟们,这时候空间利用率就会大大的降低,原本存储1M的数据,现在就意味着需要2M的空间。

一句话总结就是负载因子太小,虽然时间效率提升了,但是空间利用率降低了。

hashMap如何计算key是放在哪个位置的

JDK7中,根据Object类型的key计算出其在数组中的下标位置,HashMap的数据结构是数组+链表。由2个方法hash(Object key)和indexFor(int h,int length)来实现。

hash :该方法主要是将Object转换成一个整型。indexFor :该方法主要是将hash生成的整型转换成链表数组中的下标。

为什么扩容是2的次幂?

①简化运算,方便利用位运算来代替取余运算、简化resize()时对旧节点的移动计算

②搭配“扰动函数“使得节点分布均匀

HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在把数据存到哪个链表中的算法;这个算法实际就是取模,hash%length。

但是,大家都知道这种运算不如位移运算快。

因此,源码中做了优化hash&(length-1)。

也就是说hash%length==hash&(length-1)

那为什么是2的n次方呢?

因为2的n次方实际就是1后面n个0,2的n次方-1,实际就是n个1。

例如长度为8时候,3&(8-1)=3 2&(8-1)=2 ,不同位置上,不碰撞。

而长度为5的时候,3&(5-1)=0 2&(5-1)=0,都在0上,出现碰撞了。

所以,保证容积是2的n次方,是为了保证在做(length-1)的时候,每一位都能&1 ,也就是和1111……1111111进行与运算。

new HashMap(10) 构造出来的map大小有多大

默认情况下HashMap的容量是16,但是,如果用户通过构造函数指定了一个数字作为容量,那么Hash会选择大于该数字的第一个2的幂作为容量。(3->4、7->8、9->16)

如果我们没有设置初始容量大小,随着元素的不断增加,HashMap会发生多次扩容,而HashMap中的扩容机制决定了每次扩容都需要重建hash表,是非常影响性能的。

hashMap扩容过程(什么时候扩容)

HashMap使用的是懒加载,构造完HashMap对象后,只要不进行put 方法插入元素之前,HashMap并不会去初始化或者扩容table。

当首次调用put方法时,HashMap会发现table为空然后调用resize方法进行初始化
,当添加完元素后,如果HashMap发现size(元素总数)大于threshold(阈值),则会调用resize方法进行扩容

  • 若threshold(阈值)不为空,table的首次初始化大小为阈值,否则初始化为缺省值大小16
  • 默认的负载因子大小为0.75,当一个map填满了75%的bucket时候,就会扩容,扩容后的table大小变为原来的两倍
  • 假设扩容前的table大小为2的N次方,有上述put方法解析可知,元素的table索引为其hash值的后N位确定
  • 扩容后的table大小即为2的N+1次方,则其中元素的table索引为其hash值的后N+1位确定,比原来多了一位
  • 重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing

因此,table中的元素只有两种情况:
元素hash值第N+1位为0:不需要进行位置调整
元素hash值第N+1位为1:调整至原索引的两倍位置
扩容或初始化完成后,resize方法返回新的table

hashMap多线程下会出现的情况

HashMap在多线程put后可能导致get无限循环

多线程put的时候可能导致元素丢失

1.7与1.8的异同,1.7扩容的问题,1.8如何解决

JDK1.7用的是头插法,而JDK1.8及之后使用的都是尾插法,那么他们为什么要这样做呢?因为JDK1.7是用单链表进行的纵向延伸,当采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法,能够避免出现逆序且链表死循环的问题。

扩容后数据存储位置的计算方式也不一样:1. 在JDK1.7的时候是直接用hash值和需要扩容的二进制数进行&(这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在,因为如果只有2的n次幂的情况时最后一位二进制数才一定是1,这样能最大程度减少hash碰撞)(hash值 & length-1)

2、而在JDK1.8的时候直接用了JDK1.7的时候计算的规律,也就是扩容前的原始位置+扩容的大小值=JDK1.8的计算方式,而不再是JDK1.7的那种异或的方法。但是这种方式就相当于只需要判断Hash值的新增参与运算的位是0还是1就直接迅速计算出了扩容后的储存方式。

JDK1.7的时候使用的是数组+ 单链表的数据结构。但是在JDK1.8及之后时,使用的是数组+链表+红黑树的数据结构(当链表的深度达到8的时候,也就是默认阈值,就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O(n)变成O(logN)提高了效率)

  1. 总结网上说的
  2. jdk7 数组+单链表 jdk8 数组+(单链表+红黑树)
  3. jdk7 链表头插 jdk8 链表尾插
  4. 头插: resize后transfer数据时不需要遍历链表到尾部再插入
    1. 头插: 最近put的可能等下就被get,头插遍历到链表头就匹配到了

      1. 头插: resize后链表可能倒序; 并发resize可能产生循环链

        1. jdk7 先扩容再put jdk8 先put再扩容 (why?有什么区别吗?)
        2. jdk7 计算hash运算多 jdk8 计算hash运算少(http://www.jasongj.com/java/concurrenthashmap/#寻址方式-1)
        3. jdk7 受rehash影响 jdk8 调整后是(原位置)or(原位置+旧容量)
          HashMap链表长度多少变成红黑树 9

      当链表长度大于或等于阈值(默认为 8)的时候,如果同时还满足容量大于或等于 MIN_TREEIFY_CAPACITY(默认为 64)的要求,就会把链表转换为红黑树。

      同样,后续如果由于删除或者其他原因调整了大小,当红黑树的节点小于或等于 6 个以后,又会恢复为链表形态。

      为什么在链表为8时出现红黑树,什么时候变回来

      链表的时间复杂度是O(n),红黑树的时间复杂度O(logn),

      因为树节点所占空间是普通节点的两倍,所以只有当节点足够多的时候,才会使用树节点。也就是说,节点少的时候,尽管时间复杂度上,红黑树比链表好一点,但是红黑树所占空间比较大,综合考虑,认为只能在节点太多的时候,红黑树占空间大这一劣势不太明显的时候,才会舍弃链表,使用红黑树。

      为了配合使用分布良好的hashCode,树节点很少使用。并且在理想状态下,受随机分布的hashCode影响,链表中的节点遵循泊松分布,而且根据统计,链表中节点数是8的概率已经接近千万分之一,而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下,才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的,特殊情况特殊处理,为了挽回性能,权衡之下,才使用红黑树,提高性能。也就是大部分情况下,hashmap还是使用的链表,如果是理想的均匀分布,节点数不到8,hashmap就自动扩容了。

      如果hash算法平均,出现红黑树的概率是多少

      如果 hashCode 分布良好,也就是 hash 计算的结果离散好的话,那么红黑树这种形式是很少会被用到的,因为各个值都均匀分布,很少出现链表很长的情况。在理想情况下,链表长度符合泊松分布,各个长度的命中概率依次递减,当长度为 8 的时候,概率仅为 0.00000006。这是一个小于千万分之一的概率,通常我们的 Map 里面是不会存储这么多的数据的,所以通常情况下,并不会发生从链表向红黑树的转换。

      哈希表特点

      HashMap的put()和get()的实现

      map.put(k,v)实现原理

      第一步首先将k,v封装到Node对象当中(节点)。

      第二步它的底层会调用K的hashCode()方法得出hash值。

      第三步通过哈希表函数/哈希算法,将hash值转换成数组的下标,下标位置上如果没有任何元素,就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时,就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false,那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true,那么这个节点的value将会被覆盖。

      map.get(k)实现原理

      第一步:先调用k的hashCode()方法得出哈希值,并通过哈希算法转换成数组的下标。

      第二步:通过上一步哈希算法转换成数组的下标之后,在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有,则返回null。如果这个位置上有单向链表,那么它就会拿着参数K和单向链表上的每一个节点的K进行equals,如果所有equals方法都返回false,则get方法返回null。如果其中一个节点的K和参数K进行equals返回true,那么此时该节点的value就是我们要找的value了,get方法最终返回这个要找的value。

      为何随机增删、查询效率都很高的原因是?

      原因:增删是在链表上完成的,而查询只需扫描部分,则效率高。

      HashMap集合的key,会先后调用两个方法,hashCode and equals方法,这这两个方法都需要重写。

      HashMap():构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。

      HashMap(int initialCapacity):构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。

      HashMap(int initialCapacity, float loadFactor):构造一个带指定初始容量和加载因子的空 HashMap。

      新建一个HashMap时,都会初始化一个table数组

      我们知道hashmap是个hash桶加上链表。

      hashmap最关键的操作就是hash的逻辑,即根据把各种给了键值对的节点node,对应到数组中的逻辑,也就是确定哈希桶数组索引位置,然后才能谈冲突后的存储和处理方式。

      引入红黑树的数据结构和扩容的优化

      HashMap是数组+链表+红黑树

      就是Node[] table,即哈希桶数组,明显它是一个Node的数组

      Node是HashMap的一个内部类,实现了Map.Entry接口,本质就是一个映射(键值对)

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

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

      int threshold; // 扩容阈值

      final float loadFactor; // 负载因子

      transient int modCount; // 出现线程问题时,负责及时抛异常

      transient int size; // HashMap中实际存在的Node数量

      首先,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值被覆盖不属于结构变化。

      我们知道java.util.HashMap不是线程安全的,因此在使用迭代器Iterator的过程中,如果有其他线程修改了map,将抛出ConcurrentModificationException,这就是所谓fail-fast策略。这一策略在源码中的实现就是通过modCount,它记录修改次数,在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount,在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了Map。所以遍历那些非线程安全的数据结构时,尽量使用迭代器Iterator。

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

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

      扩容机制

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

      线程安全性

      在多线程使用场景中,应该尽量避免使用线程不安全的HashMap,而使用线程安全的ConcurrentHashMap。主要是多线程同时put时,如果同时触发了rehash操作,会导致HashMap中的链表中出现循环节点,进而使得后面get的时候,会死循环。


标题:HashMap底层实现原理解析
作者:不断努力的青春
地址:http://songaw.com/articles/2022/01/24/1643024011965.html