美文网首页
大神带你了解Map源码知识

大神带你了解Map源码知识

作者: 喝口你的蛋白粉 | 来源:发表于2021-08-05 16:01 被阅读0次

数组:数组存储区间是连续的,占用内存严重,故空间复杂度很大,但数组的二分查找时间复杂度很小,为 o(1),数组的特点:查找速度快、插入和删除效率低

链表:链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,为 o(n),链表的特点:查找速度慢、插入和删除效率高

哈希表:综合了数组和链表的特性,不仅查找速度快,插入和删除的效率也很高,哈希表有多种不同的实现方式,下面我们就介绍一种最常用的方法——“拉链法”,就是我们理解的“链表的数组”,如下图所示:

从上图可以看出,哈希表就是数组和链表组成的,一个长度为 16 的数组中,每个元素存储的是一个链表的头节点,这些元素是按照什么样的规则存储到数组的呢,一般是通过 hash(key)% len (也就是元素 key 的 hash 值对数组长度取模得到的)获得的,比如:12 % 16 = 12,  28 % 16 =12,108 % 16 = 12, 140 % 16 = 12,所以 12、28、108 和 140 都存储在数组下标为 12 的链表中。

HashMap简介

    java为数据结构中的映射定义了一个接口 java.util.Map,此接口主要有四个实现类,分别是 HashMap、HashTable、LinkedHashMap 和 TreeMap,关系图如下所示:

1、下面对各自的特点做一下说明:

(1)HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。HashMap 最多允许一条记录的键为null,允许多条记录的值为null。HashMap 是非线程安全的,即任一时刻有多个线程同时写 HashMap ,可能会导致数据不一致,。如果要满足线程安全,可以使用 Collections 的 SynchronizedMap 方法 或者使用 ConcurrentHashMap。

(2)HashTable:HashTable 是遗留类,很多常用的功能与 HashMap 类似,不同的是它继承 Dictionary,并且是线程安全的,任一时刻只能有一个线程写 HashTable,并发性不如 ConcurrentHashMap,因为 ConcurrentHashMap 引入了分段锁。HashTable 不建议在新代码中使用,不需要线程安全的场合使用 HashMap,需要线程安全的场合使用 ConcurrentHashMap。

(3)LinkedHashMap:LinkedHashMap 是 HashMap 的一个子类,保存了记录的插入顺序,在用 iterator 遍历 LinkedHashMap 时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

(4)TreeMap:它实现了 SortedMap 接口,能够把保存的记录根据键(key)排序,默认是按照键值的升序排序,也可以指定排序的比较器,当用 iterator 遍历时得到的记录是排过序的。如果使用排序的映射,建议使用 TreeMap,在使用 TreeMap 时,key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator,否则会在运行时抛出 java.lang.ClassCastException 类型的异常。

通过上面的比较可以得知,HashMap 是 Map 家族中普通的一员,它可以满足大多数的使用场景,因此是使用频率最高的一个,下面我们就结合 HashMap 的源码,从存储结构、常用方法、扩容以及安全性方面深入分析 HashMap。

内部实现

    要搞清楚 HashMap ,首先要知道 HashMap 是什么,即它的存储结构-字段,其次要弄明白它能做什么,即它的功能实现-方法,下面分别展开分析。

存储结构-字段

    从结构上来讲,HashMap 是数组 + 链表 + 红黑树(JDK1.8 中新增的红黑树部分)实现的,如下图所示:

这里我们首先要弄明白两个问题:数据底层到底存储的是什么?这样的存储有什么优点?

(1)从源码中得知,HashMap 类有一个非常重要的字段,就是  Node<K,V>[] table,即哈希桶数组,我们看一下源码,即Node[JDK1.8]

Node 是 HashMap 的一个内部类,其实现了 Map.Entry 接口,本质就是一个映射(键值对),上图中的每一个黑点就是一个 Node 对象。

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

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

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

    在理解 Hash 算法和扩容之前,先了解一下 HashMap 的一些重要的属性字段:

1、HashMap 的 数组 Node[] table 初始化的长度 capacity 是16,哈希桶数组长度 length 大小必须是2的n次方,这种设计主要是为了在取模和扩容时做优化(提高计算index索引的效率),同时为了减少冲突,HashMap 定位哈希桶索引位置时,也加入了高位参与运算的过程

2、loadFactor 为负载因子,默认值是 0.75,0.75 是对时间和空间效率的一个平衡选择,建议大家不要修改,除非在时间或者空间上比较特殊的情况下。例如:如果内存空间很多而又对时间效率要求很高,可以降低负载因子 loadFactor 的值,相反,如果内存空间较少而又对时间效率要求不高,可以增加负载因子 loadFactor 的值,这个值可以大于1

3、threshold 是 HashMap 所能容纳的最大的键值对的个数,threshold  = capacity  * loadFactor,也就是说 capacity  数组一定的情况下,负载因子越大,所能容纳的键值对个数越多,超出 threshold 这个数目就重新 resize(扩容),扩容后的 HashMap 的容量是之前的2倍。

4、size 是 HashMap 中实际存在的键值对的数量,注意和 Node[] table 的长度 capacity 、容纳最大键值对数量  threshold 的区别

5、modCount 主要用来记录 HashMap 内部结构发生变化的次数,主要用于迭代的快速失败。强调一点,内部结构发生变化是指结构发生变化,例如 put 新的键值对,但是某个 key 对应的 value 值被覆盖不属于结构变化

6、TREEIFY_THRESHOLD 和 MIN_TREEIFY_THRESHOLD,即使 hash 算法 和负载因子设计的再完美,也避免不了拉链过长的情况,一旦出现拉链过长,严重影响 HashMap 的性能,于是在 JDK1.8 中对数据结构做了进一步的优化,引入了红黑树。当链表长度太长(超过 TREEIFY_THRESHOLD = 8)时,当Node[] table 数组长度超过 64(MIN_TREEIFY_THRESHOLD = 64) 时,链表就转化为了红黑树,利用红黑树快速增删改查的特点提高 HashMap 的性能。

构造方法源码:

    下面我们列出 HashMap 中的所有构造方法的源码,特别注意的是 tableSizeFor 方法,该方法将传入的 capacity 转化为 2的n次方的 threshold(容量的临界值,构造时数组长度 == 临界值):

功能实现-方法

    HashMap 内部功能实现很多,下面主要对从根据 key 获取哈希桶数组索引位置、put、get等方法、扩容过程进行深入的分析

1、确定哈希桶数组索引位置

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

Hash 算法的本质就三步:获取key的hashCode值、高位运算、取模运算

取模运算设计方法非常巧妙,取模运算本来是很耗性能的,但是 HashMap 中是通过 h & (length -1)来获得该对象的保存位,而 HashMap 底层的数组长度length 总是2的n次方,这是 HashMap 在速度上的优化,当 length 总是2的n次方时, h & (length -1)运算等价于 h % length (对length 取模),& 比 % 具有更高的效率

在JDK1.8 中优化了高位运算的算法,通过hashCode的高16位异或低16位实现的:(h = key.hashCode())^ (h >>>16),主要从速度、功效、质量来考虑的,这么做可以在数组table的length较小的时候,也能保证考虑到高低Bit都参与到 Hash 的计算中,同时不会有太大的开销,下面具体说明,n 为table的长度:

2、put 方法

    先看一下 HashMap 的 put 方法的源码:

put 方法执行逻辑的图:

3、get 方法

    我们都知道,HashMap中最常用的方法就是 put 和 get 方法,上面介绍了put方法的源码,下面分析一下 get 方法的源码:

4、扩容机制

    扩容(resize)就是重新计算容量,向 HashMap 中不断的添加数据,HashMap 内部对象的数组无法承载更多的元素时就需要对象扩大数组的长度,以便能装入更多的元素。Java的数组是无法自动扩容的,方法就是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水就需要换大桶一样。

    JDK1.7采用的是单链表的头插入方式,也就是同一位置上新元素总会被放在链表的头位置,在旧数组中同一条Node链表上的元素,通过重新计算索引位置后,有可能放到新数组的不同的位置上。 JDK1.7的源码:

    下面举个例子说明扩容的过程,假设了我们的hash算法就是简单的用key mod 一下表的大小(也就是数组的长度)。其中的哈希桶数组table的size=2, 所以key = 3、7、5,put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1,即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4,然后所有的Node重新rehash的过程。

下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现,我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

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

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

红黑树的扩容的处理与链表的处理大同小异,源码如下:

总结

(1)扩容是一个特别耗性能的操作,所以当程序员在使用 HashMap,正确估算 map 的大小,初始化的时候给一个大致的数值,避免 map 进行频繁的扩容

(2)负载因子 loadFactor 是可以修改的,也可以大于1,但是建议不要轻易修改,除非情况特殊

(3)HashMap 是非线程安全的,不要在并发的情况下使用 HashMap,建议使用 ConcurrentHashMap

(4)JDK1.8 中引入了红黑树,大大的提高了 HashMap 的性能

原文链接:https://blog.csdn.net/ywlmsm1224811/article/details/91388815

相关文章

网友评论

      本文标题:大神带你了解Map源码知识

      本文链接:https://www.haomeiwen.com/subject/emwmvltx.html