更多详情内容请访问:JavaSE 系列文章导读

先对 Java 集合框架有一个整体的认识:

image-20220223032222505

1、ArrayList

ArrayList 是一个动态数组,实现了 List 接口以及相关的所有方法,它允许所有元素的插入,包括 null。另外,ArrayList 和 Vector 除了线程不同步之外,大致相等

1.1 基本属性

对于 ArrayList 而言,它实现 List 接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。

image-20220222115414518

ArrayList 的属性非常少,就只有这些。其中最重要的是 elementData,ArrayList 所有的方法都建立在 elementData 之上

1.2 构造方法

ArrayList 提供了三种方式的构造器:

image-20220222120733713

注意:默认情况下,elementData 是一个大小为 0 的空数组,但是当指定了初始大小的时候,new ArrayList(int initialCapacity)  指定的是缓冲区的长度而非是数组长度,因为它并没有修改其 size 属性

1.3 常用方法

image-20220222121450946

因为 ArrayList 是采用数组结构来存储的,所以它的 get 方法非常简单,先是判断一下有没有越界,之后就可以直接通过数组下标来获取元素了,所以 get 的时间复杂度是 O(1)

image-20220222123208000

ArrayList 的 add 方法,在插入元素之前,它会先检查是否需要扩容,然后再把元素添加到数组中最后一个元素的后面

ensureCapacityInternal 方法中,我们可以看见,如果当 elementData 为空数组时,它会使用默认的大小去扩容。所以说,通过无参构造方法来创建 ArrayList 时,它的大小其实是为 0 的,只有在使用到的时候,才会通过 grow 方法去创建一个大小为 10 的数组

第一个 add 方法的复杂度为 O(1),虽然有时候会涉及到扩容的操作,但是扩容的次数是非常少的,所以这一部分的时间可以忽略不计。如果使用的是带指定下标的 add方法,则复杂度为 O(n),因为涉及到对数组中元素的移动,这一操作是非常耗时的

image-20220222123407075

跟 get 非常类似,时间复杂度度为 O(1)

image-20220222124314589

remove 方法与 add 带指定下标的方法非常类似,也是调用系统的 arraycopy 方法来移动元素,从数组中移除元素的操作,也会导致被移除的元素以后的所有元素的向左移动一个位置,时间复杂度为 O(n)

image-20220222125921136

ArrayList 每次扩容都是扩 1.5 倍,然后调用 Arrays 类的 copyOf 方法,把元素重新拷贝到一个新的数组中去

这种操作的代价是很高的,因此在实际使用时,我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时,要在构造 ArrayList 实例时,就指定其容量,以避免数组扩容的发生。或者根据实际需求,通过调用 ensureCapacity 方法来手动增加 ArrayList 实例的容量

1.4 JDK 7 与 JDK 8 区别

初始化区别:

  • JDK 7:相当于饿汉式,初始化时就直接创建一个容量为 10 的数组
  • JDK 8:相当于懒汉式,初始化创建一个空数组,第一次调用 add 方法时才扩容为 10

2、HashMap

JDK 8 源码中上来对 HashMap 的概述:

image-20220222151153403

2.1 基本属性

JDK 7 中没有关于红黑树的三个关键参数:TREEIFY_THRESHOLDUNTREEIFY_THRESHOLDMIN_TREEIFY_CAPACITY

image-20220222201549147

2.2 构造器

image-20220222171657001

2.3 常用方法

image-20220222164136032

HashMap 的 put 方法执行过程可以通过下图来理解:

  1. 判断键值对数组 table[i] 是否为空或为 null,若为空或 null 执行 resize() 进行扩容;
  2. 根据键值 key 计算 hash 值得到插入的数组索引 i,如果 table[i]==null,直接新建节点添加,转向⑥,如果 table[i] 不为空,转向③
  3. 判断 table[i] 的首个元素是否和 key 一样,如果相同直接覆盖 value,若不同则转向④,这里的相同指的是 hashCode 以及 equals
  4. 判断 table[i] 是否为 treeNode,即 table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤
  5. 遍历 table[i],判断链表长度是否大于 8,大于 8 的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现 key 已经存在直接覆盖 value 即可
  6. 插入成功后,判断实际存在的键值对数量 size 是否超多了最大容量 threshold,如果超过,进行扩容

image-20220222205547566

image-20220222154655262

实现步骤大致如下:

  1. 通过 hash 值获取该 key 映射到的桶
  2. 桶上的 key 就是要查找的 key,则直接命中
  3. 桶上的 key 不是要查找的 key,则查看后续节点
    • 如果后续节点是树节点,通过调用树的方法查找该 key
    • 如果后续节点是链式节点,则通过循环遍历链查找该 key

2.4 扩容机制

2.4.1 HashMap 的 resize

当 HashMap 中的元素越来越多的时候,hash 冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对 HashMap 的数组进行扩容,数组扩容这个操作也会出现在 ArrayList 中,这是一个常用的操作,而在 HashMap 数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是 resize

2.4.2 扩容条件

  1. 一个链的对象个数 ≥ 8 且 数组长度 ≥ 64,那么这个链变成树,结点类型由 Node 变成 TreeNode 类型
  2. 一个链的对象个数 ≥ 8 且 数组长度<64,先扩容解决
  3. 映射关系被移出后,下次 resize 方法时判断树的结点个数低于6个,也会把树再转为链表

当 HashMap 中的元素个数超过数组大小 threshold(capacity * loadFactor) 时,就会进行数组扩容。

也就是说,默认情况下,当 HashMap 中元素个数超过 16 0.75 = 12 的时候,就把数组的大小扩展为 2  16 = 32,即扩大一倍

然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知 HashMap 中元素的个数,那么预设元素的个数能够有效的提高 HashMap 的性能。

2.4.3 加载因子

加载因子是表示 Hsah 表中元素的填满的程度。

若加载因子越大,则填满的元素越多,好处是空间利用率高了,但冲突的机会加大了。由于 HashMap 遇到冲突会进行链表存储或红黑树存储,当冲突多的时候,会导致链表或红黑树的数据变多,当查询数据恰好查到这个桶的时候,就会增加查询次数,从而增加了查询成本

反之,加载因子越小,填满的元素越少,好处是冲突的机会减小了,提升了查询的性能, 但空间浪费多了

因此必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡, 当负载因子为 0.75 时代入到泊松分布公式,计算出一种最佳的大小

2.5 哈希冲突

哈希值是通过哈希函数计算出来的,那么哈希冲突就是两个不同值的东西,通过哈希函数计算出来的哈希值相同,这样他们存在数组中的时候就会发生冲突,这就是哈希冲突

  1. 开放寻址法

    一旦发生了冲突,就去寻找下一个空的哈希地址,只要哈希表足够大,空的哈希地址总能找到,然后将数据存入该位置

  2. 拉链法

    HashMap 的处理方式

  3. 再哈希法

    在发生冲突的时候再用另外一个哈希函数算出哈希值,直到算出的哈希值不同为止

  4. 建立公共溢出区

    在创建哈希表的同时,再额外创建一个公共溢出区,专门用来存放发生哈希冲突的元素。查找时,先从哈希表查,查不到再去公共溢出区查

2.6 JDK 7 与 JDK 8 区别

  1. 底层数据结构不一样,1.7 是数组+链表,1.8 则是数组+链表+红黑树结构(当链表长度大于 8 且数组长度大于64,转为红黑树)
  2. JDK 1.8 中 resize() 方法在表为空时,创建表;在表不为空时,扩容;而 JDK 1.7 中 resize() 方法负责扩容,inflateTable() 负责创建表
  3. 1.8 中没有区分键为 null 的情况,而 1.7 版本中对于键为 null 的情况调用 putForNullKey() 方法。但是两个版本中如果键为 null,那么调用 hash() 方法得到的都将是 0,所以键为null的元素都始终位于哈希表table[0]中
  4. 1.7 中新增节点采用头插法,1.8 中新增节点采用尾插法。这也是为什么 1.8 不容易出现环型链表的原因
  5. 1.7 中是通过更改 hashSeed 值修改节点的 hash 值从而达到 rehash 时的链表分散,而1.8中键的 hash 值不会改变,rehash 扩容时根据(hash&oldCap)==0 将链表分散
  6. 1.8 rehash 扩容时保证原链表的顺序,而 1.7 中 rehash 时有可能改变链表的顺序(头插法导致)
  7. 在扩容的时候:1.7在插入数据之前扩容,而1.8插入数据成功之后扩容

END

本文作者:
文章标题:常用集合底层原理概述
本文地址:https://www.pendulumye.com/java-foundation/183.html
版权说明:若无注明,本文皆个人学习记录原创,转载请保留文章出处。
最后修改:2022 年 09 月 22 日
千山万水总是情,给个一毛行不行💋