Java集合

随笔22小时前发布张

3 0 0

引言

在Java开发中，集合框架是一个非常重要的工具，它提供了各种数据结构和算法，可以帮助我们更高效地处理数据。在这篇博客中，我们将简要介绍Java集合框架的整体知识，并重点讲解 ArrayList、LinkedList、HashMap 和 ConcurrentHashMap 的特点及使用场景。

Java集合框架概述

Java集合框架（Java Collections Framework）是一个为处理数据而设计的标准化架构。它包括了以下几个核心部分：

接口：包括 Collection、List、Set、Map、Queue 等，用于定义集合的基本行为。
实现类：例如 ArrayList、LinkedList、HashSet、HashMap 等，是对上述接口的具体实现，提供了不同的数据结构和操作特性。
算法：通过 Collections 类提供了一些标准算法，如排序、搜索、修改等。

1、ArrayList

ArrayList 是一个动态数组的实现，属于 List 接口的一个具体类。它的特点包括：

优点：

快速随机访问：通过索引可以快速访问任何元素，时间复杂度为 O(1)。
自动扩容：当元素数量超过当前容量时，ArrayList 会自动扩容为原来的1.5倍左右。

缺点：

插入和删除效率低：由于底层是数组，插入或删除操作需要移动大量元素，时间复杂度为 O(n)。

使用场景：适用于频繁访问元素而不经常进行插入和删除操作的场景，例如读取操作较多的场景。

ArrayList 细节分析：

底层数据结构：ArrayList 底层是用动态的数组实现的。这使得它在内存中是连续存储的，支持通过索引快速访问元素。
初始容量：ArrayList 初始容量为 0，当第一次添加数据的时候才会初始化容量为 10。这种懒加载的策略有助于避免不必要的内存占用。
扩容逻辑：ArrayList 在进行扩容时，其新容量为当前容量的 1.5 倍。每次扩容都需要将原数组中的元素拷贝到一个更大的数组中。尽管扩容是自动的，但频繁的扩容操作会影响性能。
添加逻辑：

容量检查：在添加元素之前，ArrayList 确保数组已使用长度（size）加 1 之后容量足够存下新的数据。
计算和扩容：如果当前数组已使用长度加 1 后的值大于当前数组的长度，则调用 grow 方法进行扩容，扩容后的容量为原来的 1.5 倍。
添加元素：确保新增的数据有地方存储后，将新元素添加到数组的最后一个有效位置（size 位置）。
返回结果：返回添加成功的布尔值。

2、LinkedList

LinkedList 是一个双向链表实现，除了实现 List 接口外，还实现了 Deque 接口，可以作为队列使用。它的特点包括：

优点：

插入和删除效率高：由于链表结构，插入或删除元素仅需调整指针，不需要像 ArrayList 一样移动元素。

缺点：

随机访问效率低：需要从头或尾开始遍历，查找某个元素的时间复杂度为 O(n)。

使用场景：适用于需要频繁插入和删除元素的场景，例如队列、双端队列等。

CopyOnWriteArrayList 实现线程安全的原理

CopyOnWriteArrayList 是 Java 提供的线程安全的 List 实现，它的线程安全性是通过“写时复制”策略来实现的。以下是 CopyOnWriteArrayList 如何实现线程安全的详细说明：

实现原理

写时复制（Copy-on-Write）：

CopyOnWriteArrayList 的核心思想是将写操作（如 add、remove）的成本转移到写入操作时。每当进行写操作时，CopyOnWriteArrayList 会创建底层数组的一个新的副本，并在新的副本上进行修改。
读操作（如 get、iterator）总是读取当前可见的数组副本，因此读操作不需要加锁，从而避免了读操作的性能开销。

内部结构：

CopyOnWriteArrayList 使用一个 volatile 数组来存储数据。这个 volatile 数组确保了多线程环境下的数据可见性。
每当进行写操作时，它会复制当前的数组，修改副本，然后将新副本替换原来的数组。这个过程是线程安全的，因为写操作在整个过程中保持了对数组的独占访问。

具体操作

读操作：

读操作（例如 get 方法）直接访问 volatile 数组的副本，因为数组副本是线程安全的，不需要额外的锁。这使得读操作非常高效。

写操作：

写操作（例如 add、remove 方法）会涉及到以下步骤：

复制数组：在进行写操作时，首先复制当前的数组。这是通过 Arrays.copyOf 等方法实现的。
修改副本：在复制的副本上执行所需的修改操作。
替换数组：使用 volatile 关键字将新的数组副本替换掉旧的数组。这一过程是原子的，因此可以确保数组的一致性。

迭代器：

CopyOnWriteArrayList 提供的迭代器是快照的，意味着它在创建时捕获了当前数组的状态。即使在迭代过程中，底层数组发生了变化，迭代器仍然可以安全地遍历创建时的数组状态。

优缺点

优点：

高效的读操作：由于读操作不需要加锁，CopyOnWriteArrayList 在读取数据时表现非常高效，适用于读操作频繁且写操作较少的场景。
线程安全：由于写操作总是基于数组副本进行，写操作不会影响正在进行的读操作，从而保证了线程安全。

缺点：

写操作开销大：每次写操作都需要复制整个数组，这会消耗较多的内存和时间。因此，CopyOnWriteArrayList 不适用于写操作频繁的场景。
内存使用：由于每次写操作都需要复制数组，内存消耗较大，特别是在数组非常大的情况下。

3、HashMap

HashMap 是基于哈希表的数据结构，实现了 Map 接口，用于存储键值对。它的特点包括：

优点：

快速查找、插入和删除：哈希表的操作时间复杂度为 O(1)，非常高效。

缺点：

线程不安全：HashMap 在多线程环境下不安全，需要外部同步处理。

使用场景：适用于需要快速访问数据的场景，不适用于多线程环境。

HashMap 细节分析：

底层数据结构：HashMap 底层是由数组和链表（或红黑树）组成。数组用于存储键值对的节点，链表或红黑树用于解决哈希冲突。

初始容量：HashMap 的默认初始容量为 16，负载因子为 0.75。这个配置在元素数量达到容量的 75% 时会触发扩容。

哈希计算：

HashMap 使用键的 hashCode() 计算哈希值，并通过 (hash ^ (hash >>> 16)) 的方式减少冲突。哈希值用于决定元素存储的位置。

索引定位：

确定索引：通过 哈希值 % 数组长度（即 hash & (length - 1)）来计算元素在数组中的存储位置。

插入逻辑：

检查节点：检查计算出的索引位置是否为空节点。

空节点：直接将新的键值对节点放入该位置。
非空节点：如果当前位置已有节点，说明发生了哈希冲突。

冲突解决：

链表方式：如果该位置是链表结构：

遍历链表，如果找到相同键的节点，替换其值。
如果没有找到相同键的节点，将新的节点追加到链表末尾。

红黑树方式：当链表长度超过阈值（默认 8）时，链表转换为红黑树，提高操作效率。

扩容逻辑：

在插入新节点后，HashMap 会检查当前的元素数量是否超过负载因子与容量的乘积（size > threshold）。
如果超过，则会将数组容量扩展为原来的两倍，并重新散列现有的键值对到新的数组中，这个过程称为再哈希（rehash）。

4、ConcurrentHashMap

ConcurrentHashMap 是一个线程安全的哈希表实现，用于高效并发操作。它的特点包括：

优点：

线程安全：通过分段锁或CAS机制，实现高效的线程安全操作。
高性能：相比同步的 HashMap，ConcurrentHashMap 提供了更高的并发度。

缺点：

复杂性较高：内部实现更复杂，调试和维护相对较难。

使用场景：适用于需要在多线程环境下高效并发访问的场景。

ConcurrentHashMap 锁机制：

乐观锁（Optimistic Locking）：

CAS（Compare-And-Swap）：

在 ConcurrentHashMap 中，乐观锁主要通过 CAS 操作来实现。CAS 是一种无锁的原子操作，用于确保数据在并发环境下的原子性。
在添加元素时，如果容器的位置为空，ConcurrentHashMap 会使用 volatile 修饰的变量和 CAS 操作来尝试初始化该位置。这种操作是乐观的，因为它假设没有其他线程在操作相同的位置。
如果容器中的某个桶为空，CAS 操作会尝试将该位置设置为新的节点。若成功，则说明没有其他线程在同一位置插入元素。如果 CAS 失败，说明有其他线程已经插入了元素，当前线程需要重新尝试插入操作。

悲观锁（Pessimistic Locking）：

synchronized：

当使用 CAS 无法保证数据一致性时，ConcurrentHashMap 会使用 synchronized 锁来确保线程安全。
如果 CAS 操作未能成功，即桶的位置已经有元素存在，ConcurrentHashMap 会使用 synchronized 锁住该桶。锁定桶后，线程会遍历桶中的链表或树结构来查找或插入元素。
锁定后，线程可以安全地修改桶中的链表或树结构，确保没有其他线程同时修改数据，从而保证数据的一致性。

结合应用：

初始化桶：在桶为空时使用 CAS 来尝试初始化桶，这是一种乐观锁的方式。如果初始化失败，表示有其他线程已经完成初始化操作，当前线程将使用悲观锁来进行插入操作。
插入数据：

如果桶的位置已有数据，线程首先使用 CAS 操作尝试直接插入新数据。如果 CAS 操作失败，说明有其他线程正在修改该桶，当前线程会使用 synchronized 锁来确保对桶的修改是安全的。

链表到红黑树的转换：

在 Java 8 及以后版本中，如果链表长度超过阈值，会将链表转换为红黑树。在这种情况下，ConcurrentHashMap 需要使用 synchronized 锁来确保转换过程的线程安全。

通过结合使用乐观锁和悲观锁，ConcurrentHashMap 实现了高效的并发控制。在大多数情况下，乐观锁（CAS）可以有效地避免使用锁，从而提高性能。而在需要进行数据一致性保证时，悲观锁（synchronized）则确保了线程安全。