跟随黑马面Java-7，Java集合篇

第七篇：Java集合篇

“求其上，得其中；求其中，得其下，求其下，必败”

新版Java面试专题视频教程，java八股文面试全套真题+深度详解（含大厂高频面试真题）_哔哩哔哩_bilibili

开篇

Java集合框架体系
image-20240518004617485
Collection Map

List

数组

数组（Array）是一种用连续的内存空间存储相同数据类型数据的线性数据结构

寻址公式：a[i] = baseAddress + i * dataTypeSize

  • baseAddress：数组的首地址

  • dataTypeSize：数组中元素类型的大小。int类型占用4字节。

ArrayList源码分析

  • 成员变量

    image-20240518005732982

    • elementData：真正存储数据的位置。

    • size：集合中元素的个数。

    • DEAFAULT_CAPACITY：默认初始化大小的容量。

  • 构造函数

    image-20240518010110458 image-20240518010222974

    ArrayList有三个构造函数，分别是：

    1. ArrayList()：创建一个空的ArrayList。

    2. ArrayList(int initialCapacity)：创建一个具有指定初始容量的ArrayList。

    3. ArrayList(Collection<? extends E> c)：创建一个包含指定集合元素的ArrayList，这些元素按照它们被迭代的顺序添加到ArrayList中。

  • 关键方法

    • 扩容

      • 第一次扩容（从空ArrayList增加一个元素）

        当ArrayList从空数组添加第一个元素时,会执行以下步骤:

        1. 检查当前elementData数组的容量是否为0。如果是空数组,则minCapacity会被初始化为DEFAULT_CAPACITY(默认为10)。

        2. 由于minCapacity(10) > elementData.length(0),因此需要进行数组扩容。

        3. 调用grow(minCapacity)方法进行扩容。在grow方法中:

          • 将新容量newCapacity设置为minCapacity,即10。
          • 使用Arrays.copyOf()方法创建一个新的数组,长度为newCapacity(10)。
          • 将原数组elementData中的所有元素复制到新数组中。
          • 让elementData引用指向新数组

        4. 现在elementData数组的容量变为10,可以添加第一个元素了。

        5. 将新元素添加到elementData位置。

        6. size加1,表示ArrayList中元素数量变为1。

        因此,当从空数组向ArrayList添加第一个元素时,会将底层数组的容量从0扩容到默认容量10,并将新元素放入数组的第一个位置。这种从0扩容到默认容量的过程,只会在添加第一个元素时发生一次。

        image-20240518011316820

      • 第二次至第十次添加数据

        数组不扩容

      • 第十一次添加数据（尝试将数组容量从10变为11）

        当第11次向ArrayList添加元素时,会发生以下步骤:

        1. 检查当前elementData数组的容量是否足够容纳新元素。由于默认容量为10,当添加第11个元素时,容量不足。

        2. 调用grow(minCapacity)方法进行数组扩容。在grow方法中:

          • 计算新容量newCapacity,通常是将当前容量乘以1.5,即newCapacity=10*1.5=15。
          • 使用Arrays.copyOf()方法创建一个新的数组,长度为newCapacity(15)。
          • 将原数组elementData中的所有元素复制到新数组中。
          • 让elementData引用指向新数组。

        3. 现在elementData数组的容量变为15,可以添加第11个元素了。

        4. 将新元素添加到elementData位置。

        5. size加1,表示ArrayList中元素数量变为11。

        因此,当向ArrayList添加第11个元素时,会将底层数组的容量从默认的10扩容到15,并将新元素放入数组的第11个位置。此后如果继续添加元素,只要容量足够就不会再扩容,直到容量再次不足时才会以1.5倍的方式继续扩容。

ArrayList的底层原理

  • ArrayList底层是用动态的数组实现的。

  • ArrayList的初始容量为0，当第一次添加数据时才会初始化容量为10。

  • ArrayList在进行扩容时，会将原来容量的1.5倍，每次扩容都需要拷贝数组。

  • 在添加数据时，ArrayList会执行以下步骤：

    1. 确保数组已使用长度（size）加1后足够存放下一个数据。
    2. 计算数组的容量，如果当前数组已使用长度加1后大于当前数组长度，则调用grow方法扩容（原来的1.5倍）。
    3. 确保新增的数据有地方存储之后，将新元素添加到位于size的位置上。
    4. 返回添加成功的布尔值。
ArrayList list=new ArrayList(10)中的list扩容几次

未扩容。该语句只是声明和实例了一个ArrayList，指定了容量为10。

如何实现数组和List之间的转换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 数组转List，使用JDK中java.util.Arrays工具类的asList方法
public static void testArray2List() {
    String[] strs = {"aaa", "bbb", "ccc"};
    List<String> list = Arrays.asList(strs);
    for (String s : list) 
        System.out.println(s);
}

// List转数组，使用List的toArray方法。无参toArray方法返回Object数组，传入初始化长度的数组对象，返回该对象数组
public static void testList2Array() {
    List<String> list = new ArrayList<String>();
    list.add("aaa");
    list.add("bbb");
    list.add("ccc");
    String[] array = list.toArray(new String[list.size()]);
    for (String s : array) 
        System.out.println(s);
}

  • 用Arrays.asList转List后，如果修改了原数组内容，list受影响吗 受影响

    当使用Arrays.asList()方法将一个数组转换为List时,返回的List实际上是一个ArrayList的内部类Arrays.ArrayList的实例。这个内部类提供了一个视图(view)来操作底层的数组。因此,如果修改了底层数组的内容,那么通过Arrays.asList()获得的List也会受到影响,因为它们共享同一个数组。

  • List用toArray转数组后，如果修改了List内容，数组受影响吗 不受影响

    当使用List的toArray()方法将List转换为数组时,实际上是创建了一个新的数组,并将List中的元素复制到新数组中。因此,如果后续修改了List的内容,原来的数组不会受到影响,因为它们已经是两个独立的对象了。

image-20240518013132892
LinkedList和ArrayList的区别

  • 底层实现

    • ArrayList底层使用Object数组(数组)实现,支持随机访问。

    • LinkedList底层使用双向链表实现,由一系列节点组成,每个节点存储数据和前后节点的引用。

    image-20240518014219014

  • 操作数据效率

    • 插入和删除性能

      • ArrayList在中间插入或删除元素时,需要移动其他元素,时间复杂度为O(n)。但在尾部插入或删除时,时间复杂度为O(1)。

      • LinkedList在任意位置插入或删除元素时,只需更改节点的引用,时间复杂度为O(1)。

    • 随机访问性能

      • ArrayList支持随机访问,根据索引直接访问元素,时间复杂度为O(1)。

      • LinkedList不支持高效的随机访问,需要从头节点开始顺序遍历,时间复杂度为O(n)。

  • 内存占用

    • ArrayList的内存占用与元素个数相关,每个元素只占用实际数据的内存空间。
    • LinkedList的内存占用不仅包括元素本身,还包括存储前后节点引用的内存空间,因此比ArrayList多占用一些内存。

  • 线程安全

    它们都不是线程安全的。如果需要保证线程安全，有两种方案

    • 在方法内使用，局部变量则是线程安全的。

    • 使用线程安全的ArrayList和LinkedList

    Snipaste_2024-05-18_01-46-11

HashMap

二叉树

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

二叉树每个节点的左子树和右子树也分别满足二叉树的定义。

image-20240518014817434
二叉搜索树

二叉搜索树(Binary Search Tree,BST)又名二叉查找树，有序二叉树或者排序二叉树，是二叉树中比较常用的一种类型。二又查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

其插入，查找，删除的时间复杂度O(logn)

image-20240518014940438 image-20240518015041984
红黑树

  • 红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树（BST），之前称为平衡二叉B树（Symmetric Binary B-Tree）。

    • 性质：

      1. 节点要么是红色，要么是黑色。
      2. 根节点是黑色。
      3. 叶子节点都是黑色的空节点。
      4. 红黑树中红色节点的子节点都是黑色。
      5. 从任一节点到叶子节点的所有路径都包含相同数量的黑色节点。

    • 时间复杂度：

      • 查找操作：需要从根节点开始沿着树的路径进行比较，直到找到目标节点或遇到空节点。由于红黑树是一种平衡二叉树，其高度约为logN，因此查找操作的时间复杂度为O(logN)。
      • 插入操作：分为查找插入位置和插入新节点并进行旋转和重新着色以维护红黑树性质两个步骤。查找插入位置的时间复杂度为O(logN)，插入新节点并进行操作的最坏情况下也需要O(logN)次操作，因此插入操作的总体时间复杂度为O(logN)。
      • 删除操作：同样分为查找要删除的节点和删除节点并进行旋转和重新着色两个步骤。时间复杂度也是O(logN)。
image-20240518015146818
散列表

在HashMap中，最重要的一个数据结构是散列表（HashTable），它是根据键（Key）直接访问在内存存储位置值（Value）的数据结构。散列表是由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性。

  • 散列函数的基本要求：

    • 散列函数计算得到的散列值必须是大于等于0的正整数，因为hashValue需要作为数组的下标。
    • 如果key1 == key2，那么经过hash后得到的哈希值也必相同，即：hash(key1) == hash(key2）。
    • 如果key1 != key2，那么经过hash后得到的哈希值也必不相同，即：hash(key1) != hash(key2）。

  • 散列冲突：实际的情况下，找到一个散列函数能够做到对于不同的key计算得到的散列值都不同几乎是不可能的。即便像著名的MD5、SHA等哈希算法也无法避免这一情况。这就是散列冲突（或者哈希冲突、哈希碰撞），指的是多个key映射到同一个数组下标位置。

    image-20240518015901037

  • 链表法（拉链法）

    在散列表中，数组的每个下标位置可以称为桶（bucket）或者槽（slot）。每个桶（槽）对应一条链表，所有散列值相同的元素都被放置到相同槽位对应的链表中。

    image-20240518020114986
说一下HashMap的实现原理

  • HashMap的数据结构：底层使用Hash表数据结构，即数组和链表或红黑树。

    • 当执行put操作时，首先通过key的hashCode()计算hash值，再通过hash值经过扰动函数处理后得到在table数组中的索引i。
    • 存储时，如果出现hash值相同的key，有两种情况：
      1. 如果key相同，则覆盖原始值；
      2. 如果key不同（出现冲突），则将当前的key-value放入链表或红黑树中。
    • 获取时，直接找到hash值对应的下标，然后进一步判断key是否相同，从而找到对应值。

  • HashMap的JDK1.7和JDK1.8区别：

    • JDK1.7采用拉链法，即将链表和数组相结合。每个数组槽位对应一个链表。
    • JDK1.8在解决哈希冲突时有了较大的变化：
      • 当链表长度超过8(TREEIFY_THRESHOLD)且数组长度大于64(MIN_TREEIFY_CAPACITY)时,链表将转换为红黑树以提高查找效率。
      • 在扩容resize()时，如果红黑树拆分成的树的节点数小于等于6个，则退化为链表。
    image-20240518102504612
image-20240518103109443
HashMap的put方法的具体流程
1
2
3
4
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始容量 即16 
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认的加载因子，扩容阈值==数组容量*加载因子
transient HashMap.Node<K,V>[] table;	// HashMap中真正存储元素的数组
transient int size;	// 集合中元素的个数
image-20240518104637607

HashMap是延迟加载的，即在创建对象时并没有初始化数组。在无参的构造函数中，默认的加载因子是0.75。

  • put()方法的执行流程如下：

    1. 计算key的哈希值hash，通过调用key的hashCode()方法并对返回值进行扰动处理，使哈希值分布更均匀。
    2. 根据计算出的哈希值hash，找到它在底层数组table中对应的索引i。
    3. 如果table[i]为null，表示该位置没有数据，直接创建一个新的Node节点，并将其插入到table[i]的位置。
    4. 如果table[i]不为null，说明已经存在一个或多个节点使用了相同的哈希值，发生了哈希冲突：
      • 如果当前位置存在一个链表，就遍历链表，如果key已经存在，就直接覆盖value值；如果key不存在，就将新的Node节点插入到链表的尾部。
      • 如果当前位置存在一个红黑树，就调用红黑树的插入逻辑插入新的Node节点。
    5. 如果插入新节点后，HashMap的实际大小size超过了阈值(threshold = loadFactor * table.length)，就需要对HashMap进行扩容resize()操作。
    6. 最后，如果key已经存在，则返回旧的value值；如果key不存在，则返回null。

  • 扩容过程如下：

    1. 创建一个新的Node数组，长度是原数组的2倍。
    2. 重新计算每个节点在新数组中的位置，并把节点移动到新的数组中。
    3. 如果节点是树节点，则调整树的结构。

  • 当链表长度超过8(TREEIFY_THRESHOLD)且数组长度大于64(MIN_TREEIFY_CAPACITY)时，链表将转换为红黑树以提高查找效率。

image-20240518105431082
HashMap的扩容机制
image-20240518105558964

  • 什么时候触发扩容

    当HashMap中的元素个数超过阈值(threshold = loadFactor * table.length)时,就会触发resize()进行扩容操作。

  • 扩容过程

    1. 创建一个新的Entry数组,长度是原数组的2倍。

    2. 重新计算每个节点在新数组中的位置,并把节点移动到新的数组中。

    3. 如果节点是树节点(红黑树),则调整树的结构。

    4. 将HashMap的table指向新创建的数组。

    5. 重新计算阈值threshold。

  • 扩容后元素位置重新计算

    1. 没有哈希冲突的节点：
      • 对于没有哈希冲突的节点，直接使用e.hash & (newCap - 1)计算其在新数组中的索引位置即可。
      • 这里e.hash是节点的哈希值，newCap是新数组的容量（通常是原数组容量的两倍）。
    2. 红黑树节点：
      • 如果节点在旧数组中已经形成了红黑树，则在新数组中依旧使用红黑树的逻辑来插入这些节点。
      • 红黑树的结构能够保证在扩容后，节点插入的操作时间复杂度仍然是O(log n)。
    3. 链表节点：
      • 对于链表节点，需要遍历整个链表进行重新计算和拆分。具体步骤如下：
        1. 遍历链表
          • 对链表中的每个节点重新计算哈希值在新数组中的位置。
        2. 拆分链表
          • 判断节点e的哈希值e.hash与旧容量oldCap进行按位与操作(e.hash & oldCap)。
          • 如果结果为0，节点将保留在原位置。
          • 如果结果不为0，节点将移动到原位置加上旧容量的位置。

    这种方式的好处是,如果新容量是旧容量的2倍,那么节点要么保持在原位置,要么被移动到原始位置+增加的数组大小这个位置上。这种移动规律可以简化重新计算的操作。

  • 链表转红黑树

    当链表长度超过8(TREEIFY_THRESHOLD)且数组长度大于64(MIN_TREEIFY_CAPACITY)时,链表将转换为红黑树以提高查找效率。在扩容时,如果节点是树节点,也需要调整树的结构。

HashMap寻址算法
image-20240518143526260
  • 扰动算法

    我们一般来说直接将key用mod取模就行，但是这里它还将mod低十六位做异或：

    1
    2
    3
    4
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    这样做的原因是:

    • 无符号右移16位,是为了将hashCode()的高16位与低16位组合起来,避免只使用了部分位。

    • 异或运算可以将高16位与低16位的特征混合起来,增加了随机性。

    通过这种位运算的扰动,可以使得不同对象的哈希值分布更加均匀,减少了哈希冲突的概率。即使存入数据时对象的hashCode()本身分布不佳,扰动算法也可以弥补这种缺陷。

  • 二次哈希
    1
    2
    3
    4
    5
    6
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        ...
        // 计算索引，并检查当前位置是否为空
        if ((p = tab[i = (n - 1) & hash]) == null)
        ...
    }

    我们可以发现，hash % mod和(mod - 1) & hash的结果是一样的。而按位与运算的速度比取模更快。不过，这对mod有要求，它必须是2的n次幂。

    HashMap在真正存储数据时，会先对key调用hashCode()方法计算一次哈希值，然后再进行一次扰动计算得到最终的哈希值。这样做的目的是为了进一步减少哈希冲突，使键值对能够均匀地分布在不同的桶中。

    • 扰动计算：通过(h = key.hashCode()) ^ (h >>> 16)对哈希码进行扰动处理，混合高位和低位信息，减少哈希冲突。

    • 按位与运算：使用(n - 1) & hash计算数组索引位置，代替hash % n。按位与运算比取模运算快，并且n必须是2的幂次方。

  • 为何HashMap的长度一定是2的n次幂
    1. 计算索引时效率更高：
      • 如果长度是2的n次幂，可以使用位与运算代替取模运算。例如，(n - 1) & hash 等同于 hash % n，但位与运算速度更快。
    2. 扩容时重新计算索引效率更高：
      • 在扩容时，新的容量是旧容量的两倍。通过 hash & oldCap 判断，如果结果为0，元素保持在原位置；否则，元素的新位置为旧位置加上旧容量（oldCap）。这种方式减少了重新计算索引的复杂度，提高了效率。
HashMap在1.7情况下的多线程死循环问题

JDK1.7的时候的数据结构是数组+链表，在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环。

image-20240518144856583

  1. HashMap在扩容时,会先将原数组的所有节点转移到一个新的更大的数组中。这个转移过程是逐个遍历原数组,并将节点重新计算哈希值放入新数组对应的位置。

  2. 在转移节点的过程中,如果有另一个线程正在对HashMap进行put操作,就可能导致环形链表(循环链表)的产生。

  3. 具体来说,假设两个线程A和B同时转移节点,线程A先获取了链表头节点head,随后线程B也获取了head。线程A将head的next节点重新哈希到新数组后,线程B由于还持有原head节点,因此也会将head节点重新哈希到新数组。这样就形成了环形链表。

  4. 当其他线程遍历这个环形链表时,就会出现死循环,无法结束遍历。

  5. 这个问题在JDK1.8中通过使用Node类代替原来的单向链表Entry,并额外增加了modCount变量来检测并发修改情况,从而避免了环形链表的产生。

  • 假设有两个线程，线程1和线程2，同时对同一个HashMap进行操作，导致以下情况：

    1. 线程2开始扩容：
      • 线程2遍历链表，重排节点顺序，例如将节点A和B从旧数组移动到新数组中，但节点顺序颠倒，变成BA。
    2. 线程1持有旧的头节点A：
      • 线程1此时拿到了旧链表的头节点A（A的next指针指向B）。
    3. 线程1进行扩容：
      • 线程1开始扩容操作，将旧节点A放入新数组中，这时A的next指针还是指向B。
      • 线程1接下来处理节点B，读取旧的next指针，B的next指针指向A（因为线程1已经将B插入到新数组中并且更新了next指针）。
    4. 形成环形链表：
      • 线程1认为链表中还有元素，于是将修改过的A再次插入新数组，此时A的next指针是B。
      • 最终，新数组中的节点顺序变为A -> B -> A，形成环形链表。
image-20240518152126591 image-20240518152255521
image-20240518152330138 image-20240518152354552
image-20240518152542427