Java：集合

Written by with ♥ on in Java

说说 List , Set , Map 三者的区别？

  1. List（列表）：

    • List 是一个有序集合，允许存储重复元素。
    • 可以通过索引访问列表中的元素，支持按索引位置进行添加、删除、修改等操作。
    • 常见的 List 接口实现包括 ArrayList（基于动态数组）和 LinkedList（基于双向链表）。

  2. Set（集合）：

    • Set 是一个无序集合，不允许存储重复元素。
    • 由于不允许重复元素，当尝试向 Set 中添加重复元素时，添加操作将被忽略。
    • 常见的 Set 接口实现包括 HashSet（基于哈希表）和 TreeSet（基于红黑树）。

  3. Map（映射）：

    • Map 是一个键值对的集合，每个元素包含一个键和一个值，键是唯一的。
    • 可以通过键来查找和操作与之关联的值，支持添加、删除、修改等操作。
    • 常见的 Map 接口实现包括 HashMap（基于哈希表）和 TreeMap（基于红黑树）。

总结：List 是有序、允许重复元素的集合；Set 是无序、不允许重复元素的集合；Map 是键值对的集合，键是唯一的。在选择使用哪种集合时，需要根据需求来决定，以保证数据的存储和操作效率。

List , Set , Map 在 Java 中分别由哪些对应的实现类？底层的数据结构？

  1. List（列表）

    • ArrayList：基于动态数组实现，支持快速随机访问元素，适合随机访问、增删操作较少的场景。
    • LinkedList：基于双向链表实现，支持快速的插入和删除操作，适合频繁插入、删除元素的场景。
    • CopyOnWriteArrayList：基于数组实现，采用写时复制机制，适用于读多写少的场景。

  2. Set（集合）：

    • HashSet：基于哈希表实现，元素无序、不可重复，适用于需要快速查找的场景。
    • TreeSet：基于红黑树实现，元素有序且唯一，支持有序遍历，适用于有序集合的场景。
    • LinkedHashSet：基于哈希表和链表实现，元素按插入顺序排序，适用于需要保持插入顺序的场景。

  3. Map（映射）：

    • HashMap：基于哈希表实现，键值对无序，键不可重复，适用于需要快速查找键值对的场景。
    • TreeMap：基于红黑树实现，键值对有序，键不可重复，支持按键排序的遍历，适用于需要有序映射的场景。
    • LinkedHashMap：基于哈希表和双向链表实现，键值对按插入顺序排序，适用于需要保持插入顺序的场景。

有哪些集合是线程不安全的？怎么解决呢？

一些线程不安全的集合包括：

  1. ArrayList
  2. HashSet
  3. HashMap
  4. LinkedList
  5. TreeSet
  6. TreeMap
  7. 等等
    要解决线程不安全的集合类可能导致的问题，可以采用以下方法之一：

  8. 使用线程安全的集合类：Java 提供了一些线程安全的集合类，例如 Collections.synchronizedList()、Collections.synchronizedSet()、Collections.synchronizedMap() 等方法可以将线程不安全的集合类包装成线程安全的集合类。

    List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());
Set<String> synchronizedSet = Collections.synchronizedSet(new HashSet<>());
Map<String, Integer> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

  9. 使用并发集合类：Java 并发包（java.util.concurrent）提供了一些并发集合类，这些集合类提供了更好的并发性能，例如 ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet 等。

    
ConcurrentHashMap<String, Integer> concurrentHashMap = new ConcurrentHashMap<>();
CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
  10. 使用锁：可以使用显式的锁（例如 ReentrantLock）来保护线程不安全的集合，确保在多线程环境下对集合进行安全的访问和操作。

List

ArrayList 和 Vector 的区别?

  1. 线程安全性：

    • ArrayList 不是线程安全的，即在多线程环境下并发操作 ArrayList 可能会导致不确定的结果，需要开发者自行处理线程同步问题。
    • Vector 是线程安全的，它的所有方法都是同步的，内部使用 synchronized 关键字来实现线程安全，因此可以在多线程环境下安全地使用。

  2. 性能：

    • ArrayList 在单线程环境下性能通常比 Vector 更好，因为 ArrayList 不需要进行额外的同步操作。
    • Vector 在多线程环境下由于进行了同步操作，可能会导致一定的性能损失。

  3. 增长策略：

    • ArrayList 和 Vector 在元素数量超出其初始容量时，都会自动增长容量以容纳新元素。
    • ArrayList 的增长策略是增加 50% 的当前容量，而 Vector 的增长策略是增加当前容量的一倍。

总的来说，ArrayList 适用于单线程环境下的数据存储和操作，它更轻量且性能更好；而 Vector 适用于多线程环境下的数据存储和操作，它提供了线程安全的操作，但可能会带来一定的性能损失。在大多数情况下，推荐使用 ArrayList，除非需要线程安全性，才考虑使用 Vector。

ArrayList 与 LinkedList 区别?

  1. 底层数据结构：

    • ArrayList 内部使用动态数组（array）作为底层数据结构来存储元素。这意味着 ArrayList 支持随机访问，可以通过索引快速访问列表中的任何元素。
    • LinkedList 内部使用双向链表（doubly linked list）作为底层数据结构来存储元素。每个元素都包含对其前一个元素和后一个元素的引用。这意味着 LinkedList 不支持随机访问，需要遍历链表才能访问列表中的元素。

  2. 插入和删除操作：

    • 在 ArrayList 中，插入和删除操作可能需要移动后面的元素以保持数组的连续性，因此在中间插入或删除大量元素时效率较低，时间复杂度为 O(n)。
    • 在 LinkedList 中，插入和删除操作只需要改变相邻节点的引用，因此在中间插入或删除元素时效率较高，时间复杂度为 O(1)。

  3. 随机访问和遍历性能：

    • ArrayList 支持随机访问，因此可以通过索引快速访问列表中的任何元素，但在插入和删除操作效率较低。
    • LinkedList 不支持随机访问，因此无法直接通过索引访问元素，但在插入和删除操作效率较高，尤其是在列表中间插入或删除元素时。

  4. 空间占用：

    • ArrayList 在大多数情况下比 LinkedList 占用更少的内存空间，因为它只需要存储元素值和一个连续的数组。
    • LinkedList 每个元素都需要额外的空间来存储前后节点的引用，因此在存储大量元素时可能会占用更多的内存空间。

    ArrayList 适合对列表进行频繁的随机访问操作，而 LinkedList 适合对列表进行频繁的插入和删除操作，尤其是在列表的中间部分。

    ArrayList 扩容机制

  5. 初始容量：ArrayList 在创建时可以指定初始容量，如果不指定，则默认初始容量为 10。初始容量是指 ArrayList 内部数组的大小。
  6. 增长策略：ArrayList 在需要扩容时，会根据其增长策略自动增加容量。默认情况下，ArrayList 的增长策略是增加当前容量的一半。
  7. 触发扩容：当向 ArrayList 中添加新元素时，如果当前元素数量已经达到了数组的容量（即当前元素数量等于数组长度），就会触发扩容操作。
  8. 创建新数组：当需要扩容时，ArrayList 会创建一个新的数组，并将原数组中的元素复制到新数组中。
  9. 复制元素：ArrayList 扩容时，会将原数组中的元素逐个复制到新数组中，保持元素的顺序不变。
  10. 修改引用：扩容完成后，ArrayList 会将内部的数组引用指向新数组，原数组会被丢弃，成为垃圾对象，等待垃圾回收。

扩容操作可能会导致性能损耗，因为需要进行元素的复制操作。为了减少扩容操作的频率，可以在创建 ArrayList 时指定一个较大的初始容量，以减少扩容的次数。

Queue

Queue 与 Deque 的区别

  1. Queue（队列）：

    • Queue 是一个先进先出（FIFO）的集合，即元素按照添加顺序排列，最先添加的元素最先被移除。
    • Queue 接口提供了一系列方法，如 offer()、poll()、peek() 等，用于在队列的尾部添加元素、从队列的头部移除元素以及获取队列头部的元素。
    • 典型的实现类包括 LinkedList、PriorityQueue 等。
Queue<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
String element = queue.poll(); // 移除并返回队列头部的元素

  1. Deque（双端队列）：

    • Deque 是一个双端队列，即可以从两端添加和移除元素。它既可以作为队列（FIFO）使用，也可以作为栈（LIFO）使用。
    • Deque 接口继承自 Queue 接口，提供了额外的方法，如 offerFirst()、offerLast()、pollFirst()、pollLast() 等，用于在队列的两端添加和移除元素。
    • 典型的实现类包括 ArrayDeque、LinkedList 等。
Deque<String> deque = new LinkedList<>();
deque.offerFirst("first");
deque.offerLast("second");
String firstElement = deque.pollFirst(); // 移除并返回队列头部的元素
String lastElement = deque.pollLast(); // 移除并返回队列尾部的元素

Queue 是一个只允许在一端添加和移除元素的集合（先进先出），而 Deque 则是一个允许在两端添加和移除元素的集合，既可以作为队列使用，也可以作为栈使用。Deque 接口继承自 Queue 接口，并提供了额外的双端操作方法。

ArrayDeque 与 LinkedList 的区别

  1. 内部实现：

    • ArrayDeque 内部使用循环数组（circular array）作为底层数据结构来实现双端队列。这意味着 ArrayDeque 使用数组来存储元素，并且在需要扩容时会创建一个更大的数组，并将元素从旧数组复制到新数组。
    • LinkedList 内部使用双向链表（doubly linked list）作为底层数据结构来实现双端队列。每个元素都包含对其前一个元素和后一个元素的引用。这意味着 LinkedList 不需要像 ArrayDeque 那样进行数组的扩容操作，但在添加和删除操作时需要修改节点的引用。

  2. 性能特点：

    • ArrayDeque 在随机访问元素、尾部插入和删除元素的性能上通常优于 LinkedList。由于 ArrayDeque 使用数组作为底层数据结构，它支持随机访问，因此可以在常数时间内访问和修改队列的头部和尾部元素。
    • LinkedList 在中间插入和删除元素的性能上通常优于 ArrayDeque。由于 LinkedList 使用链表作为底层数据结构，插入和删除元素的时间复杂度为常数时间。

  3. 空间占用：

    • ArrayDeque 在大多数情况下占用的内存空间比 LinkedList 少。由于 ArrayDeque 使用数组来存储元素，而 LinkedList 使用链表，链表每个节点都需要额外的指针来指向前一个和后一个节点，因此在存储大量元素时，LinkedList 可能会占用更多的内存空间。

PriorityQueue 有什么特点

  1. 优先级排序：

    • PriorityQueue 是基于优先级的队列，它可以确保队列中的元素按照优先级顺序排列。具体来说，PriorityQueue 是一个小顶堆（min-heap）数据结构，队首元素（优先级最高的元素）是堆中的最小元素。

  2. 无序性：

    • PriorityQueue 在插入元素时并不保证元素在队列中的顺序，它只保证队首元素是优先级最高的。插入元素时会根据元素的优先级自动调整队列中的元素顺序，将优先级最高的元素排在队首。

  3. 基于堆的实现：

    • PriorityQueue 内部使用堆（heap）数据结构来实现优先队列。Java 中的 PriorityQueue 实际上是一个优先级队列的堆的实现，它使用了堆的性质来保证队首元素的优先级最高，并且在插入和删除元素时保持堆的性质。

  4. 动态扩容：

    • PriorityQueue 是一个动态数组实现的堆，在需要扩容时会自动增加容量以容纳更多元素。当插入元素时，如果队列已满，则会自动扩容，以保证队列的容量足够存储新元素。

  5. 不允许 null 元素：

    • PriorityQueue 不允许插入 null 元素，因为它会使用元素的自然顺序或者通过 Comparator 比较器来确定元素的优先级，而 null 无法比较优先级。

HashMap

HashMap 查询，删除的时间复杂度

在 HashMap 中，查询和删除操作的时间复杂度取决于哈希表中的装载因子（load factor）和桶数组的长度（buckets array length）：

  1. 查询（get）操作：

    • 平均情况下，查询操作的时间复杂度为 O(1)，即常数时间。这是因为 HashMap 使用键的哈希码来确定键值对的存储位置，并将键值对存储在桶数组的某个位置上，因此只需一次哈希计算和一次桶数组访问即可完成查询。
    • 最坏情况下，查询操作的时间复杂度为 O(n)，即线性时间。这是因为哈希冲突可能会导致多个键值对存储在同一个桶位置上，这样就需要在该桶位置上进行线性搜索来找到目标键值对。

  2. 删除（remove）操作：

    • 平均情况下，删除操作的时间复杂度为 O(1)，即常数时间。与查询操作类似，删除操作也只需要一次哈希计算和一次桶数组访问即可完成删除。
    • 最坏情况下，删除操作的时间复杂度也为 O(n)，即线性时间。同样地，哈希冲突可能会导致需要线性搜索来找到要删除的键值对。

HashMap 的底层实现

Java 中的 HashMap 是基于哈希表实现的键值对映射集合。它的底层实现主要包括两个部分：数组（buckets array）和链表/红黑树（LinkedList or Red-Black Tree）。

  1. 数组：

    • HashMap 内部维护了一个数组，称为桶数组（buckets array），用于存储键值对。数组的大小是固定的，但会根据需要动态扩容。
    • 每个桶（bucket）是一个链表的头结点（Java 8 之后的版本，当链表长度超过一定阈值时，会将链表转换为红黑树，以提高查询效率）。

  2. 链表/红黑树：

    • 每个桶中存储的元素是一个链表（Java 8 之前的版本）或者红黑树（Java 8 之后的版本）。当发生哈希冲突时，即多个键映射到同一个桶时，会将这些键值对存储在同一个桶中，形成一个链表或红黑树结构。
    • 在 Java 8 之后的版本中，当链表长度超过一定阈值（默认为8），链表会被转换为红黑树，以提高查询效率。

  3. 哈希函数：

    • HashMap 使用键的哈希码来计算键值对在桶数组中的存储位置。具体地，通过对键的哈希码进行一系列的位运算和取模操作，将键值对映射到桶数组的某个位置上。
    • 为了减少哈希冲突，HashMap 通常会使用键的哈希码的高位作为桶数组的索引，从而使键值对均匀分布在桶数组中。

  4. 负载因子和扩容：

    • HashMap 会根据装载因子（load factor）来决定何时进行扩容操作。装载因子是桶数组的填充比例，超过一定阈值（默认为0.75），HashMap 就会进行扩容操作，即创建一个更大的桶数组，并将原有的键值对重新分配到新的桶数组中。
    • 扩容操作会导致重新哈希（rehash）过程，即重新计算每个键值对在新的桶数组中的存储位置。

HashMap 的长度为什么是 2 的幂次方

HashMap 的长度选择为 2 的幂次方是为了优化哈希计算和减少哈希冲突。

在 HashMap 中，通过对键的哈希码进行位运算来确定键值对在桶数组中的存储位置。具体地，对于一个长度为 n 的桶数组，HashMap 会使用键的哈希码的低 n 位进行取模运算来确定键值对在桶数组中的存储位置。因此，n 必须为 2 的幂次方，这样才能保证取模运算的结果是一个均匀分布的索引值，从而使键值对能够均匀地分布在桶数组中。

另外，当数组长度为 2 的幂次方时，取模运算（即 n - 1）可以用位运算（即 & 操作）来代替，这样可以提高运算效率。例如，对于长度为 16 的数组，取模运算 index = hash & (length - 1) 就相当于 index = hash % length，但效率更高。

比较 HashSet 、 LinkedHashSet 和 TreeSet 三者的异同

  1. HashSet：

    • HashSet基于哈希表实现，不保证元素的顺序。
    • 元素存储的顺序是根据哈希值来确定的，因此HashSet是无序的。
    • HashSet允许存储null元素，但只能存储一个null元素。
    • HashSet的插入、删除和查询操作的时间复杂度都是近似O(1)的。
    • 由于HashSet的存储顺序是根据哈希值来确定的，因此HashSet的性能比LinkedHashSet和TreeSet要好。

  2. LinkedHashSet：

    • LinkedHashSet继承自HashSet，是HashSet的子类，但是在HashSet的基础上增加了链表来维护元素的插入顺序。
    • LinkedHashSet保留了元素的插入顺序，因此它是有序的。
    • LinkedHashSet不允许存储重复元素。
    • LinkedHashSet允许存储null元素，但只能存储一个null元素。
    • LinkedHashSet的插入、删除和查询操作的时间复杂度都是近似O(1)的。

  3. TreeSet：

    • TreeSet基于红黑树（Red-Black Tree）实现，可以保证元素的有序性。
    • TreeSet会根据元素的自然顺序或者指定的比较器来进行排序。
    • TreeSet不允许存储null元素。
    • TreeSet的插入、删除和查询操作的时间复杂度都是O(log n)，因为它是基于红黑树实现的。

HashMap 和 Hashtable 的区别？ HashMap 和 HashSet 区别？ HashMap 和 TreeMap 区别？

  • HashMap 和 Hashtable 区别：

    • 线程安全性：HashMap 不是线程安全的，而 Hashtable 是线程安全的。Hashtable 的所有方法都是同步的，因此适用于多线程环境下的并发操作，但这也导致了在单线程环境下性能较差。相反，HashMap 的方法不是同步的，因此在单线程环境下性能更好。
    • null 键和值：HashMap 允许键和值都为 null，而 Hashtable 不允许键和值为 null。
    • 继承关系：HashMap 继承自 AbstractMap 类，而 Hashtable 继承自 Dictionary 类（已经被弃用）。

  • HashMap 和 HashSet 区别：

    • 数据结构：HashMap 是基于哈希表实现的键值对映射集合，而 HashSet 是基于哈希表实现的唯一性集合，其中只存储键值对的键，不存储值。
    • 用途：HashMap 适用于需要存储键值对的场景，而 HashSet 适用于需要存储唯一性元素的场景。
    • 接口：HashMap 实现了 Map 接口，而 HashSet 实现了 Set 接口。

  • HashMap 和 TreeMap 区别：

    • 内部数据结构：HashMap 是基于哈希表实现的，不保证元素的顺序，而 TreeMap 是基于红黑树实现的，可以保证元素的有序性。
    • 性能：HashMap 的插入、删除和查询操作的平均时间复杂度都是 O(1)，而 TreeMap 的插入、删除和查询操作的时间复杂度都是 O(log n)，因为它是基于红黑树实现的。
    • 接口：HashMap 实现了 Map 接口，而 TreeMap 实现了 NavigableMap 接口，是有序映射。

ConcurrentHashMap

ConcurrentHashMap 和 Hashtable 的区别？

  1. 同步策略：

    • ConcurrentHashMap 采用了锁分段（Segment Locking）的策略来实现线程安全，它将整个映射表分成多个段（Segment），每个段拥有自己的锁。这样，在多线程环境下，不同的线程可以同时访问 ConcurrentHashMap 中的不同段，从而提高并发性能。
    • Hashtable 使用了同步关键字 synchronized 来实现线程安全。Hashtable 的所有方法都是同步的，即每个方法都需要获取对象级别的锁，因此在多线程环境下，只允许一个线程访问 Hashtable，其他线程需要等待。

  2. 性能：

    • 在并发环境下，ConcurrentHashMap 的性能通常比 Hashtable 更好。由于 ConcurrentHashMap 使用了锁分段的机制，不同的线程可以同时访问不同的段，因此可以在一定程度上提高并发性能。而 Hashtable 的所有方法都是同步的，因此在多线程环境下性能较差。

  3. null 键和值：

    • ConcurrentHashMap 允许键和值为 null，而 Hashtable 不允许键和值为 null。在 ConcurrentHashMap 中，null 值被视为一个有效的值，但在 Hashtable 中，如果键或值为 null，会抛出 NullPointerException 异常。

  4. 迭代器：

    • ConcurrentHashMap 的迭代器是弱一致的（weakly consistent），而 Hashtable 的迭代器是强一致的（fail-fast）。弱一致性意味着 ConcurrentHashMap 的迭代器可以在遍历过程中反映出其他线程对映射表的修改，而强一致性意味着 Hashtable 的迭代器会在并发修改时抛出 ConcurrentModificationException 异常。

ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

ConcurrentHashMap 的线程安全性是通过锁分段（Segment Locking）的方式来实现的。它将整个映射表分成多个段（Segment），每个段拥有自己的锁。这样，在多线程环境下，不同的线程可以同时访问 ConcurrentHashMap 中的不同段，从而提高并发性能。

具体来说，ConcurrentHashMap 的底层实现可以分为以下几个关键点：

  1. Segment 分段：

    • ConcurrentHashMap 内部维护了一个由多个 Segment 组成的数组，每个 Segment 都是一个独立的哈希表，用于存储键值对。
    • 默认情况下，ConcurrentHashMap 的初始大小为 16，它会创建一个长度为 16 的 Segment 数组，每个 Segment 作为一个独立的哈希表来存储键值对。

  2. 锁机制：

    • 每个 Segment 都有一个独立的锁，用于控制对该段的访问。这意味着不同的线程可以同时访问 ConcurrentHashMap 中的不同段，从而提高并发性能。
    • 当执行插入、删除、更新等操作时，只会锁住相应的 Segment，而不是整个 ConcurrentHashMap。

  3. 并发性能：

    • 在多线程环境下，ConcurrentHashMap 可以实现较高的并发性能，因为不同线程可以同时操作不同的 Segment，减少了竞争，提高了并发性能。
    • 在读取操作上，ConcurrentHashMap 的性能通常比 Hashtable 更好，因为读取操作不需要获取锁。

  4. 内部实现：

    • 每个 Segment 本质上是一个独立的哈希表，它的结构与普通的 HashMap 类似，采用了链表和红黑树的结构来存储键值对。
    • 当执行插入、删除、更新等操作时，会根据键的哈希值来确定它应该被存储在哪个 Segment 中，并且对该 Segment 上的锁进行加锁操作，保证线程安全。
tag(s): none
show comments · back · home
Edit with Markdown