Java集合

说明

收集到一些Java集合相关的内容，包括数组、集合、CopyonWriteArraylist、HashMap、ConcurrentHashMap、HashTable的原理等。

如果你有任何建议或问题，请随时联系站长

数组和集合的区别

1. 数组（Array）

数组是固定大小的、存储相同类型元素的容器。数组一旦创建，大小不可更改。

2. 集合（Collections）

集合是Java提供的一组类和接口，用于存储多个对象。集合的元素不需要是同一类型，并且集合的大小是动态可扩展的。

特性	数组	集合
大小	固定大小	动态大小（可以扩展或缩小）
类型	所有元素类型相同	元素类型可以不同（使用泛型时相同）
访问方式	通过索引直接访问	通过方法（如 add,remove）进行操作
性能	快速，直接通过索引访问	相对较慢（例如 ArrayList需要扩展数组）
操作	不支持动态增删元素	支持动态增删元素，集合框架提供丰富的操作方法

集合可以被分为哪几类？

1. List

List 是一个有序的集合，允许重复元素。它通过索引来存取元素，并且插入顺序与元素的存储顺序一致。

主要特性：

• 元素有顺序，可以根据索引来访问。
• 允许重复元素。
• 允许 null 元素。

常见实现类：

• ArrayList：基于动态数组实现，支持快速的随机访问，但插入和删除操作的效率相对较低。
• LinkedList：基于双向链表实现，适合进行频繁的插入和删除操作，但随机访问较慢。
• Vector：早期的实现，与 ArrayList 类似，但 Vector 是线程安全的。

2. Map

Map 是一个存储键值对（key-value）的集合，它不继承自 Collection 接口。每个 Map 中的键是唯一的，值可以重复。

主要特性：

• 存储键值对，键唯一，值可以重复。
• 可以根据键来访问相应的值。

常见实现类：

• HashMap：基于哈希表实现，提供常数时间复杂度的 get 和 put 操作，元素的顺序不保证。
• LinkedHashMap：继承自 HashMap，保持插入的顺序或访问顺序（如果设置了访问顺序）。
• TreeMap：基于红黑树实现，键会按照自然顺序或构造时指定的 Comparator 顺序进行排序。
• Hashtable：早期的实现，线程安全，但相较于 HashMap 性能较差，现在一般不推荐使用。

3. Set

Set 是一个无序的集合，不允许重复元素。它的特点是元素唯一，但没有索引，因此无法像 List 那样通过索引访问。

主要特性：

• 元素无序，插入顺序不一定保持。
• 不允许重复元素。
• 不支持索引访问。

常见实现类：

• HashSet：基于哈希表实现，提供快速的查找、插入和删除操作，不保证元素的顺序。
• LinkedHashSet：继承自 HashSet，它保持元素的插入顺序。
• TreeSet：基于红黑树实现，元素会按照自然顺序或构造时指定的 Comparator 顺序进行排序。

CopyonWriteArraylist

CopyonWriteArrayList 是 Java 中的一个线程安全的 List 实现，属于java.util.concurrent包，适用于读多写少的场景，读操作不加锁，写操作加锁，并发读取性能高，不适合写操作频繁的场景，它通过在每次修改时复制底层数组来保证线程安全，因此它特别适合于并发读取，但写操作（添加、删除、修改）相对较少的场景。

HashMap 的原理

HashMap 是基于哈希表的数据结构，用于储存键值对（key-value）。在 Java8 之前是通过数组+链表来解决哈希冲突的，之后是数组+链表+红黑树。

HashMap使用键的hashCode()方法计算哈希值，并通过indexFor方法（JDK 1.7 及之后版本移除了这个方法，直接使用 (n - 1) & hash）确定元素在数组中的存储位置。哈希值是经过一定扰动处理的，防止哈希值分布不均匀，从而减少冲突。

HashMap 的默认初始容量为 16，负载因子为 0.75。也就是说，当存储的元素数量超过 16 × 0.75 = 12 个时，HashMap会触发扩容操作，容量x2并重新分配元素位置。这种扩容是比较耗时的操作，频繁扩容会影响性能。

在 JDK 1.8 版本的时候做了优化，当一个链表的长度超过8的时候就转换数据结构，不再使用链表存储，而是使用红黑树，查找时使用红黑树，时间复杂度O（log n），可以提高查询性能，但是在数量较少时，即数量小于6时，会将红黑树转换回链表。（为什么长度超过 8 变红黑树，数量小于 6 变链表？而不是小于 8 或 7 或 5 等变回链表呢？）

1. Java7 HashMap 结构（数组+链表）

2. Java8 HashMap 结构（数组+链表+红黑树）

ConcurrentHashMap 1.7 和 1.8 的区别

JDK 1.7 ConcurrentHashMap 采用的是分段锁，即每个Segment是独立的，可以并发访问不同的Segment，默认是 16 个Segment，所以最多有 16 个线程可以并发执行。

而 JDK 1.8 移除了Segment，锁的粒度变得更加细化，锁只在链表或红黑树的节点级别上进行。通过 CAS 进行插入操作，只有在更新链表或红黑树时才使用synchronized，并且只锁住链表或树的头节点，进一步减少了锁的竞争，并发度大大增加。

并且 JDK 1.7ConcurrentHashMap只使用了数组 + 链表的结构，而 JDK 1.8 和HashMap一样引入了红黑树。

除此之外，还有扩容的区别以及size方法的计算也不一样。

1. JDK 1.7（Segment 分段锁）

• 采用 Segment（分段锁）+ HashEntry + 链表 结构：
  • ConcurrentHashMap 由 多个 Segment 组成，每个 Segment 类似于一个小 HashMap，各自维护 HashEntry<K, V>[] 数组。
  • Segment 通过 ReentrantLock 加锁，实现分段锁机制，支持多个线程同时访问不同的 Segment，提高并发能力。
  • 哈希冲突解决方式：采用 链表 存储元素。

2. JDK 1.8（CAS + Synchronized + 红黑树）

• 移除了 Segment 分段锁，改用 CAS + Synchronized 控制并发。
• 底层结构：
  • Node<K, V>[] table 数组（类似 HashMap）。
  • 使用 链表 + 红黑树 解决哈希冲突：
    • 当 链表长度 ≥ 8 时，转换为红黑树，提高查询效率（O(log n)）。
    • 当 链表长度 ≤ 6 时，恢复为链表，减少空间占用。
  • 采用 volatile 变量 + CAS（Compare-And-Swap）+ synchronized，保证线程安全。

CAS（Compare-And-Swap）

CAS（Compare-And-Swap） 是一种广泛用于并发编程中的 无锁 技术，它通过原子操作来保证数据一致性。CAS 主要用于多线程环境下的 共享变量 更新操作，确保更新过程不会受到其他线程干扰，从而避免了加锁带来的性能瓶颈。

CAS 操作的核心思想是：在某个位置的内存值与预期值进行比较，如果相等，就更新为新值，否则不做任何操作。

CAS 的操作步骤：

1. 读取：读取变量当前的值（假设为 V）。
2. 比较：将当前值 V 和预期值（即线程上一次读取的值）进行比较。
3. 交换：如果当前值 V 和预期值相同，原子性地将其更新为新值 newValue。
   • 如果不相等，则什么也不做，操作失败。

CAS 的形式一般是：

boolean compareAndSwap(V expectedValue, V newValue);

CAS 与锁的对比：

特性	CAS	锁（如 synchronized）
并发性	高：无锁，线程之间不会阻塞	低：线程需要等待锁释放
性能	高：避免了线程上下文切换和锁的开销	低：加锁和解锁的成本较高
死锁风险	低：不使用锁，因此不存在死锁问题	高：可能发生死锁，尤其在多锁场景下
适用场景	适用于频繁并发且对单一变量进行更新	适用于需要对多个变量进行操作的场景
操作粒度	仅限单一变量的更新	支持多个变量或复杂操作的原子性

HashMap 和 HashTable

1. HashMap 性能更好，适用于大多数场景，特别是单线程或通过外部同步来实现线程安全时。
2. Hashtable 存在同步开销，性能较差，且不允许 null 键和值，因此现在很少使用，推荐使用 ConcurrentHashMap 替代它。

特性	HashMap	Hashtable
线程安全性	否（非线程安全）	是（线程安全，通过 synchronized实现）
Null 键和值	允许一个null键和多个null值	不允许null键和值
性能	高（无同步机制，性能较好）	较低（同步开销，性能较差）
扩容机制	默认初始容量 16，负载因子 0.75，扩容是线性增长	默认初始容量 11，负载因子 0.75，扩容是线性增长
历史地位	Java 1.2引入的类，更灵活，更常用	Java 1.0提供的类，已经过时
实现方式	基于数组和链表（或红黑树）实现的哈希表	基于数组和链表实现的哈希表，synchronized用于保证线程安全
使用场景	在单线程环境下使用，或者通过外部同步来处理多线程	不推荐使用，性能较低，且 synchronized会影响并发性能

HashMap 和 ConcurrentHashMap

1. HashMap 适用于单线程环境或者外部同步的多线程环境。
2. ConcurrentHashMap 是为高并发环境设计的，它在性能和线程安全性方面优于 HashMap 和 Hashtable，尤其适用于 频繁并发读取 的场景。

特性	HashMap	ConcurrentHashMap
线程安全性	否（非线程安全）	是（线程安全，支持高并发）
Null 键和值	允许一个 null键和多个 null值	不允许 null键和值
扩容机制	需要手动扩容，扩容过程是整体锁定的	使用分段锁等机制，支持无锁扩容，性能更好
常用方法	put()、get()、remove() 等	提供并发特性的方法：如 putIfAbsent()、replace()、remove()等
性能	在单线程环境下或外部同步下较好	在多线程高并发环境下性能更优
适用场景	适合单线程环境或通过外部同步来处理多线程环境	适合高并发的多线程环境，尤其是频繁读取和少量写入的场景

HashTable 和 ConcurrentHashMap

1. Hashtable 的线程安全性是通过同步（synchronized）机制实现的，但它的性能较差，尤其在高并发场景下。
2. ConcurrentHashMap 提供了更加高效的线程安全保障，采用了分段锁、CAS 等技术，能够在高并发环境下保持较好的性能。它的并发性能远超 Hashtable，且是现代 Java 中推荐的线程安全 Map 实现。

特性	Hashtable	ConcurrentHashMap
线程安全性	是（通过 synchronized实现线程安全）	是（高效的线程安全，通过分段锁、CAS 等优化并发性能）
Null 键和值	不允许 null键和值	不允许 null键和值
性能	较低（由于 synchronized，导致加锁开销较大）	高（高并发环境下性能更好，避免了全表加锁）
扩容机制	通过同步机制实现扩容，扩容时会加锁	通过分段锁等机制支持高效扩容，减少锁的粒度
常用方法	标准的 Map操作方法	提供了并发操作方法，如 putIfAbsent()、replace()等
适用场景	适用于线程安全要求高，但并发性要求不高的场景	适用于高并发的多线程环境，尤其是频繁读取和少量写入的场景

HashSet、LinkedHashSet 和 TreeSet

1. HashSet：适合需要高性能插入、查找和删除操作且不关心顺序的场景。
2. LinkedHashSet：适合需要按插入顺序遍历元素的场景，如缓存、日志记录等。
3. TreeSet：适合需要排序或者根据自定义规则排序元素的场景，适用于范围查询和有序数据处理。

特性	HashSet	LinkedHashSet	TreeSet
元素顺序	无序（不保证元素的顺序）	保持元素的插入顺序	按照自然顺序（或指定的比较器顺序）排序
实现方式	基于哈希表（HashMap ）实现	基于哈希表和链表实现（内部使用 HashMap 存储元素）	基于红黑树实现
是否允许重复元素	不允许重复元素	不允许重复元素	不允许重复元素
性能（查找、插入、删除）	快（O(1) 平均时间复杂度）	较慢（O(1) 查找，但插入和删除会受链表维护影响）	较慢（O(log n) 查找、插入、删除）
排序规则	无排序	保持插入顺序	排序（默认按照自然顺序，或者通过自定义的比较器）
null 元素	允许一个 null元素	允许一个 null元素	不允许 null元素
线程安全性	否	否	否
适用场景	适合需要快速查找、插入和删除的场景	适合需要保持元素插入顺序的场景	适合需要自动排序元素的场