集合

集合与数组

  • 数组是固定长度的数据结构，一旦创建长度就无法改变，而集合是动态长度的数据结构，可以根据需要动态增加或减少元素。
  • 数组可以包含基本数据类型和对象，而集合只能包含对象。
  • 数组可以直接访问元素，而集合需要通过迭代器或其他方法访问元素。

常用集合

  • ArrayList：动态数组，实现了 List 接口，支持动态增长。
  • LinkedList：双向链表，也实现了 List 接口，支持快速的插入和删除操作。
  • HashMap：基于哈希表的 Map 实现，存储键值对，通过键快速查找值。
  • HashSet：基于 HashMap 实现的 Set 集合，用于存储唯一元素。
  • TreeMap：基于红黑树实现的有序 Map 集合，可以按照键的顺序进行排序。
  • LinkedHashMap：基于哈希表和双向链表实现的 Map 集合，保持插入顺序或访问顺序。
  • PriorityQueue：优先队列，可以按照比较器或元素的自然顺序进行排序。

线程安全的集合

util 包

  • Vector：线程安全的动态数组，其内部方法基本都经过 synchronized 修饰，如果不需要线程安全，并不建议选择，存在同步的额外开销。Vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。
  • Hashtable：线程安全的哈希表，HashTable 的加锁方法是给每个方法加上 synchronized 关键字，这样锁住的是整个 Table 对象，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用，如果要保证线程安全的哈希表，可以用 ConcurrentHashMap。

concurrent 包

并发 Map：

  • ConcurrentHashMap：它与 HashTable 的主要区别是二者加锁粒度的不同
    • 在JDK1.7，ConcurrentHashMap 加的是分段锁，也就是 Segment 锁，每个 Segment 含有整个 table 的一部分，这样不同分段之间的并发操作就互不影响。
    • 在JDK 1.8，取消了 Segment 字段，直接在 table 元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率。
      • 对于 put 操作，如果 Key 对应的数组元素为 null，则通过 CAS 操作（Compare and Swap）将其设置为当前值。如果 Key 对应的数组元素（也即链表表头或者树的根元素）不为 null，则对该元素使用 synchronized 关键字申请锁，然后进行操作。如果该 put 操作使得当前链表长度超过一定阈值，则将该链表转换为红黑树，从而提高寻址效率。
  • ConcurrentSkipListMap：实现了一个基于 SkipList（跳表）算法的可排序的并发集合，SkipList 是一种可以在对数预期时间内完成搜索、插入、删除等操作的数据结构，通过维护多个指向其他元素的“跳跃”链接来实现高效查找。

并发 Set：

  • ConcurrentSkipListSet：是线程安全的有序的集合。底层是使用 ConcurrentSkipListMap 实现。
  • CopyOnWriteArraySet：是线程安全的 Set 实现，它是线程安全的无序的集合，可以将它理解成线程安全的 HashSet。
    • CopyOnWriteArraySet 和 HashSet 虽然都继承于共同的父类 AbstractSet；但是，HashSet 是通过“散列表”实现的，而 CopyOnWriteArraySet 则是通过“动态数组(CopyOnWriteArrayList)”实现的，并不是散列表。

并发 List：

  • CopyOnWriteArrayList：它是 ArrayList 的线程安全的变体，其中所有写操作（add，set 等）都通过对底层数组进行全新复制来实现，允许存储 null 元素。即当对象进行写操作时，使用了 Lock 锁做同步处理，内部拷贝了原数组，并在新数组上进行添加操作，最后将新数组替换掉旧数组；若进行的读操作，则直接返回结果，操作过程中不需要进行同步。

并发 Queue：

  • ConcurrentLinkedQueue：是一个适用于高并发场景下的队列，它通过无锁的方式(CAS)，实现了高并发状态下的高性能。通常，ConcurrentLinkedQueue 的性能要好于 BlockingQueue 。
  • BlockingQueue：与 ConcurrentLinkedQueue 的使用场景不同，BlockingQueue 的主要功能并不是在于提升高并发时的队列性能，而在于简化多线程间的数据共享
    • BlockingQueue 提供一种读写阻塞等待的机制，即如果消费者速度较快，则 BlockingQueue 则可能被清空，此时消费线程再试图从 BlockingQueue 读取数据时就会被阻塞。
    • 反之，如果生产线程较快，则 BlockingQueue 可能会被装满，此时，生产线程再试图向 BlockingQueue 队列装入数据时，便会被阻塞等待。

并发 Deque：

  • LinkedBlockingDeque：是一个线程安全的双端队列实现。它的内部使用链表结构，每一个节点都维护了一个前驱节点和一个后驱节点。LinkedBlockingDeque 没有进行读写锁的分离，因此同一时间只能有一个线程对其进行操作
  • ConcurrentLinkedDeque：ConcurrentLinkedDeque 是一种基于链接节点的无限并发链表。可以安全地并发执行插入、删除和访问操作。当许多线程同时访问一个公共集合时，ConcurrentLinkedDeque 是一个合适的选择。

遍历方式

普通 for 循环

for (int i = 0; i < list.size(); i++) {
	Object o = list.get(i);
}

增强 for 循环

for (Object o : list) {

}

Iterator 迭代器

Iterator<Object> it = list.iterator();
while (it.hasNext()) {
	Object = it.next();
}

ListIterator 列表迭代器

ListIterator 是 Iterator 的子类，可以双向访问并且在迭代过程中修改元素

ListIterator<Object> it = list.listIterator();
while (it.hasNext()) {
	Object = it.next();
}

forEach

list.forEach(each -> System.out.println(each));

Stream API

list.stream().forEach(each -> System.out.println(each));

List

常见 List 集合

非线程安全：

  • ArrayList 基于动态数组实现
    • 允许快速的随机访问，即通过索引访问元素的时间复杂度为 $O (1)$。
    • 在添加和删除元素时，如果操作位置不是列表末尾，可能需要移动大量元素，性能相对较低。
    • 适用于需要频繁随机访问元素，而对插入和删除操作性能要求不高的场景，如数据的查询和展示等。
    • 在扩容时会增加 50%
    • 可以使用 Collections 类的 synchronizedList 方法将 ArrayList 包装成线程安全的 List：List<String> synchronizedList = Collections.synchronizedList(arrayList);
  • LinkedList 基于双向链表实现
    • 插入和删除元素时，只需修改链表的指针，不需要移动大量元素，时间复杂度为 $O(1)$。
    • 随机访问元素时，需要从链表头或链表尾开始遍历，时间复杂度为 $O(n)$。
    • 适用于需要频繁进行插入和删除操作的场景，如队列、栈等数据结构的实现，以及需要在列表中间频繁插入和删除元素的情况。

线程安全：

  • Vector 基于数组实现。
    • Vector 中的方法大多是同步的，这使得它在多线程环境下可以保证数据的一致性，但在单线程环境下，由于同步带来的开销，性能会略低于 ArrayList。
    • 扩容时容量提高 1 倍。
  • CopyOnWriteArrayList 在对列表进行修改（如添加、删除元素）时，会创建一个新的底层数组，将修改操作应用到新数组上，而读操作仍然在原数组上进行，这样可以保证读操作不会被写操作阻塞，实现了读写分离，提高了并发性能。
    • 适用于读操作远远多于写操作的并发场景，如事件监听列表等，在这种场景下可以避免大量的锁竞争，提高系统的性能和响应速度。

遍历中修改元素

对于非线程安全的实现：

  • 普通 for 可以直接修改元素
  • forEach()，不建议，可能会导致异常
  • 迭代器：可以使用 remove() 删除和 set() 修改（迭代器的而不是 List 本身的）

对于线程安全的实现，可以直接修改

ArrayList 和 LinkedList

  • 底层数据结构不同：ArrayList 使用数组实现，通过索引进行快速访问元素。LinkedList 使用链表实现，通过节点之间的指针进行元素的访问和操作。
  • 插入和删除操作的效率不同：ArrayList 在尾部的插入和删除操作效率较高，但在中间或开头的插入和删除操作效率较低，需要移动元素。LinkedList 在任意位置的插入和删除操作效率都比较高，因为只需要调整节点之间的指针，但是 LinkedList 是不支持随机访问的，所以除了头结点外插入和删除的时间复杂度都是 $O(n)$，效率不高
  • 随机访问的效率不同：ArrayList 支持通过索引进行快速随机访问，时间复杂度为 $O(1)$。LinkedList 需要从头或尾开始遍历链表，时间复杂度为 $O(n)$。
  • 空间占用：ArrayList 在创建时需要分配一段连续的内存空间，因此会占用较大的空间。LinkedList 每个节点只需要存储元素和指针，因此相对较小。
  • 使用场景：ArrayList 适用于频繁随机访问和尾部的插入删除操作，而 LinkedList 适用于频繁的中间插入删除操作和不需要随机访问的场景。
  • 线程安全：这两个集合都不是线程安全的

ArrayList 扩容

  • 计算新的容量：一般情况下，新的容量会扩大为原容量的 1.5 倍，然后检查是否超过了最大容量限制。
    • 1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数。
  • 创建新数组
  • 元素复制
  • 更新引用：将 ArrayList 内部指向原数组的引用指向新数组。
  • 完成扩容

CopyOnWriteArrayList 实现线程安全

CopyOnWriteArrayList 底层也是通过一个数组保存数据，使用 volatile 关键字修饰数组，保证当前线程对数组对象重新赋值后，其他线程可以及时感知到。

private transient volatile Object[] array;

在写入操作时，加了一把互斥锁 ReentrantLock 以保证线程安全。

public boolean add(E e) {
    //获取锁
    final ReentrantLock lock = this.lock;
    //加锁
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;

        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;

        setArray(newElements);
        return true;
    } finally {
        //释放锁
        lock.unlock();
    }
}

读操作没有加锁，随时可以读取（但是如果在 add() 执行过程中读取，则有可能读取到旧的数据，但是能确保不会出现并发问题）

public E get(int index) {
	return get(getArray(), index);
}

Map

常见 Map 集合

非线程安全：

  • HashMap 是基于哈希表实现的 Map
    • 根据键的哈希值来存储和获取键值对，JDK 1.8 中是用数组+链表+红黑树来实现的。
    • HashMap 是非线程安全的，在多线程环境下，当多个线程同时对 HashMap 进行操作时，可能会导致数据不一致或出现死循环等问题。
    • 比如在扩容时，多个线程可能会同时修改哈希表的结构，从而破坏数据的完整性。
  • LinkedHashMap 继承自 HashMap
    • 在 HashMap 的基础上，使用双向链表维护了键值对的插入顺序或访问顺序，使得迭代顺序与插入顺序或访问顺序一致。
    • 由于它继承自 HashMap，在多线程并发访问时，同样会出现与 HashMap 类似的线程安全问题。
  • TreeMap 是基于红黑树实现的 Map
    • 可以对键进行排序，默认按照自然顺序排序，也可以通过指定的比较器进行排序。
    • TreeMap 是非线程安全的，在多线程环境下，如果多个线程同时对 TreeMap 进行插入、删除等操作，可能会破坏红黑树的结构，导致数据不一致或程序出现异常。

线程安全：

  • Hashtable 是早期 Java 提供的线程安全的 Map 实现，它的实现方式与 HashMap 类似，但在方法上使用了 synchronized 关键字来保证线程安全。
    • 通过在每个可能修改 Hashtable 状态的方法上加上 synchronized 关键字，使得在同一时刻，只能有一个线程能够访问 Hashtable 的这些方法，从而保证了线程安全。
  • ConcurrentHashMap
    • 在 JDK 1.8 以前采用了分段锁等技术来提高并发性能。在 ConcurrentHashMap 中，将数据分成多个段（Segment），每个段都有自己的锁。在进行插入、删除等操作时，只需要获取相应段的锁，而不是整个 Map 的锁，这样可以允许多个线程同时访问不同的段，提高了并发访问的效率。
    • 在 JDK 1.8 以后是通过 volatile + CAS 或者 synchronized 来保证线程安全的。

Map 遍历

entrySet()

 // 使用for-each循环和entrySet()遍历Map
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

keySet()

 // 使用for-each循环和keySet()遍历Map的键
for (String key : map.keySet()) {
    System.out.println("Key: " + key + ", Value: " + map.get(key));
}

迭代器

// 使用迭代器遍历Map
Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Entry<String, Integer> entry = iterator.next();
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

Lambda

// 使用Lambda表达式和forEach()方法遍历Map
map.forEach((key, value) -> System.out.println("Key: " + key + ", Value: " + value));

Stream

// 使用Stream API遍历Map
map.entrySet().stream()
  .forEach(entry -> System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue()));
// 还可以进行其他操作，如过滤、映射等
Map<String, Integer> filteredMap = map.entrySet().stream()
                                    .filter(entry -> entry.getValue() > 1)
                                    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

HashMap

原理

Java7

  • 数组和链表
  • 通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）
  • 如果多个键映射到同一个槽位，以链表的形式存储在同一个槽位上

Java8

  • 当一个链表的长度超过 8 的时候就转换为红黑树，查找时使用红黑树，时间复杂度 $O(\log n)$，可以提高查询性能
  • 在数量小于 6 时，会将红黑树转换回链表

Put 过程

  • 根据键的哈希值计算索引
  • 检查数组对应位置是否为空
    • 如果为空，则创建一个 Map.Entry 对象来存储
    • 将 HashMap 的修改次数（modCount）加 1，可以发现并发修改（乐观锁）
  • 如果不为空，比较该位置的第一个键的哈希值和插入键的哈希值
    • 如果相同，则替换值
  • 如果哈希值不同，则遍历该位置下的链表（或红黑树）
    • 找到相同键，替换值
    • 未找到相同键，插入新元素（若链表则插入头部）
  • 检查链表长度是否到达阈值（默认 8），且数组长度大于等于 64，则将链表转换为红黑树
  • 检查负载因子是否超过阈值（默认 0.75）。如果键值对数量/数组长度大于阈值，则扩容
  • 扩容
    • 创建两倍大小数组
    • 键值对重新计算哈希值并分配到新数组
    • 更新数组引用和阈值参数

扩容

如果 hashmap 中的元素个数超过了总容量 75%，则会触发扩容：

  • 对哈希表长度的扩展（2 倍）
  • 将旧哈希表中的数据放到新的哈希表中
    • 元素的位置要么是在原位置
    • 要么是在原位置再移动 2 次幂的位置

在扩充 HashMap 的时候，不需要重新计算 hash，只需要判断原来的 hash 值新增的那个 bit 是 1 还是 0，0 则索引不变，1 则索引变成“原索引+oldCap”

ConcurrentHashMap

原理

Java7

分段锁技术将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

使用数组+链表实现：

  • 数组分为：大数组 Segment 和小数组 HashEntry。
    • Segment 是一种可重入锁（ReentrantLock）
    • HashEntry 用于存储键值对数据。
  • 一个 ConcurrentHashMap 里包含一个 Segment 数组
  • 一个 Segment 里包含一个 HashEntry 数组
  • 每个 HashEntry 是一个链表结构的元素

每个 Segment 都类似于一个小的 HashMap，每个 Segment 都有自己的锁，不同 Segment 之间的操作互不影响，从而提高并发性能。

在 ConcurrentHashMap 中，对于插入、更新、删除等操作，需要先定位到具体的 Segment，然后再在该 Segment 上加锁，而不是像传统的 HashMap 一样对整个数据结构加锁。这样可以使得不同 Segment 之间的操作并行进行，提高了并发性能。

Java8

通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了

使用数组+链表/红黑树

通过 volatile + CAS 或者 synchronized 来实现的线程安全的。添加元素时首先会判断容器是否为空：

  • 如果为空则使用 volatile 加 CAS 来初始化

  • 如果容器不为空，则根据存储的元素计算该位置是否为空。

    • 如果根据存储的元素计算结果为空，则利用 CAS 设置该节点；
    • 如果根据存储的元素计算结果不为空，则使用 synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

  • 在 putVal 中，如果计算出来的哈希槽没有存放元素，可以直接使用 CAS 来进行设置值。因为在设置元素的时候，哈希值在经过了各种扰动后，造成哈希碰撞的几率较低，所以可以预测能使用较少的自旋来完成哈希落槽操作。

  • 当发生了哈希碰撞的时候说明容量不够用了或者已经有大量线程访问了，因此这时候使用 synchronized 来处理哈希碰撞比 CAS 效率要高，发生了哈希碰撞大概率是线程竞争比较强烈。

ConcurrentHashMap 悲观锁和乐观锁都有使用

  • 如果为空则使用 volatile 加  CAS （乐观锁）  来初始化。
  • 如果容器不为空，则根据存储的元素计算该位置是否为空。
  • 如果根据存储的元素计算结果为空，则利用  CAS（乐观锁）  设置该节点；
  • 如果根据存储的元素计算结果不为空，则使用  synchronized（悲观锁） ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

Hashtable

  • Hashtable 的底层数据结构主要是数组+链表，数组是主体，链表是解决哈希冲突存在的。
  • HashTable 是线程安全的，实现方式是 Hashtable 的所有公共方法均采用 synchronized，当一个线程访问同步方法，另一个线程也访问的时候，就会陷入阻塞或者轮询的状态。
    • 任何一个时刻只能有一个线程可以操纵 Hashtable，效率低

区别

  • HashMap 线程不安全，效率高
    • 可以存储 null 的 key 和 value，null 的 key 只能有一个，null 的 value 可以有多个。
    • 默认初始容量为 16，每次扩充变为原来 2 倍。
    • 创建时如果给定了初始容量，则扩充为 2 的幂次方大小。
    • 底层数据结构为数组+链表，插入元素后如果链表长度大于阈值（默认为 8），先判断数组长度是否小于 64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
  • HashTable 线程安全，效率低一点，其内部方法基本都经过 synchronized 修饰
    • 不可以有 null 的 key 和 value。
    • 默认初始容量为 11，每次扩容变为原来的 2n+1。
    • 创建时给定了初始容量，会直接用给定的大小。
    • 底层数据结构为数组+链表。
    • 基本被淘汰了，要保证线程安全可以用 ConcurrentHashMap。
  • ConcurrentHashMap 主要基于分段锁和 CAS 操作。
    • 它将整个哈希表分成了多 Segment（段），每个 Segment 都类似于一个小的 HashMap，它拥有自己的数组和一个独立的锁。
    • 在 ConcurrentHashMap 中，读操作不需要锁，可以直接对 Segment 进行读取，而写操作则只需要锁定对应的 Segment，而不是整个哈希表，这样可以大大提高并发性能。

Set

无重复

  • set 集合特点：Set 集合中的元素是唯一的，不会出现重复的元素。
  • set 实现原理：Set 集合通过内部的数据结构（如哈希表、红黑树等）来实现 key 的无重复。当向 Set 集合中插入元素时，会先根据元素的 hashCode 值来确定元素的存储位置，然后再通过 equals 方法来判断是否已经存在相同的元素，如果存在则不会再次插入，保证了元素的唯一性。

有序 Set

  • 有序的 Set 是 TreeSet 和 LinkedHashSet。
    • TreeSet 是基于红黑树实现，保证元素的自然顺序。
    • LinkedHashSet 是基于双重链表和哈希表的结合来实现元素的有序存储，保证元素添加的自然顺序
  • 记录插入顺序的集合通常指的是 LinkedHashSet，它不仅保证元素的唯一性，还可以保持元素的插入顺序。当需要在 Set 集合中记录元素的插入顺序时，可以选择使用 LinkedHashSet 来实现。