Java 常用的一些Collection的实现类

Java 常用的一些Collection的实现类

Collection

1.集合基础

Java 集合框架是一个强大的工具，它提供了一套标准化的接口和类，用于存储和操作集合数据。Collection 接口是这个框架的核心，它定义了一系列通用的集合操作。

2.Collection接口方法

• List list = new ArrayList();

  • 创建一个新的空列表，ArrayList 是实现 List 接口的一个常用类，它允许快速随机访问。

• list.add(Object o)：

  • 向列表中添加一个元素。如果元素已存在，则不添加。

• list.addAll(Collection c)：

  • 将指定集合中的所有元素添加到列表中。

• list.remove(Object o)：

  • 删除列表中首次出现的指定元素。如果没有这样的元素，则不执行任何操作。

• list.removeAll(Collection c)：

  • 删除列表中与指定集合共有的所有元素。

• list.contains(Object o)：

  • 判断列表中是否包含指定元素。

• list.containsAll(Collection c)：

  • 判断列表中是否包含指定集合中的所有元素。

• list.size()：

  • 返回列表中的元素数量。

• list.isEmpty()：

  • 判断列表是否为空。

• list.clear()：

  • 清空列表中的所有元素。

3.Iterator

Iterator 接口用于遍历集合中的元素。

• Iterator iterator = list.iterator();

  • 创建一个迭代器实例，用于遍历指定的集合。

• while(iterator.hasNext()) { ... }

  • 检查迭代器是否有下一个元素。

• Object o = iterator.next();

  • 返回迭代器的下一个元素。

Collection的实现类

1.List

List 接口继承自 Collection，它不仅保证了元素的唯一性，还保证了元素的顺序。

1.1 list接口方法

• list.get(int index)：

  • 返回列表中指定索引处的元素。

• list.add(int index, Object o)：

  • 在列表的指定位置插入元素。

• list.addAll(int index, Collection c)：

  • 从指定位置开始，将指定集合中的所有元素添加到列表中。

• list.indexOf(Object o)：

  • 返回指定元素第一次出现的索引，如果不存在，返回 -1。

• list.lastIndexOf(Object o)：

  • 返回指定元素最后一次出现的索引，如果不存在，返回 -1。

• list.remove(int index)：

  • 删除列表中指定索引处的元素。

• list.set(int index, Object o)：

  • 用指定元素替换列表中指定索引处的元素。

• list.subList(int fromIndex, int toIndex)：

  • 返回列表中从 fromIndex（包含）到 toIndex（不包含）的子列表。

1.2 ArrayList

ArrayList 是一个动态数组实现，它允许在数组中进行快速随机访问。

扩容

当 ArrayList 需要更多空间时，它会进行扩容。如果不指定初始容量，默认初始容量为 10，每次扩容时大小会增加大约 50%。

1.3 LinkedList

LinkedList 是 Java 集合框架中 List 接口的一个实现类，它是一个双向链表。与基于数组的集合（如 ArrayList）相比，LinkedList 提供了在列表中的任意位置高效插入和删除元素的能力。

特性

• 双向链表：每个元素（称为节点）都包含指向其前一个元素和后一个元素的引用。
• 动态大小：LinkedList 可以动态地添加和删除元素，不需要预先定义大小。
• 非同步：LinkedList 不是线程安全的，如果你在多线程环境中使用，可能需要外部的同步机制。
• 内存使用：由于每个节点包含额外的指针，LinkedList 相对于 ArrayList 可能会使用更多的内存。

方法

• LinkedList()

  • 创建一个空的 LinkedList。

• LinkedList(Collection<? extends E> c)

  • 创建一个新的 LinkedList，包含指定集合中的所有元素。

• add(E e)

  • 在列表的末尾添加一个元素。

• add(int index, E element)

  • 在列表的指定位置插入元素。

• addFirst(E e)

  • 在列表的开头添加一个元素。

• addLast(E e)

  • 在列表的末尾添加一个元素，这是 add 方法的别名。

• get(int index)

  • 返回列表中指定位置的元素。

• set(int index, E element)

  • 用指定元素替换列表中指定位置的元素。

• remove(Object o)

  • 移除列表中首次出现的指定元素。

• remove(int index)

  • 移除列表中指定位置的元素。

• removeFirst()

  • 移除并返回列表中的第一个元素。

• removeLast()

  • 移除并返回列表中的最后一个元素。

• poll()

  • 移除并返回列表中的第一个元素，如果没有元素，则返回 null。

• pollFirst()

  • 移除并返回列表中的第一个元素，如果没有元素，则返回 null，这是 poll 方法的别名。

• pollLast()

  • 移除并返回列表中的最后一个元素，如果没有元素，则返回 null。

• peek()

  • 返回列表中的第一个元素，如果没有元素，则返回 null。

• peekFirst()

  • 返回列表中的第一个元素，如果没有元素，则返回 null，这是 peek 方法的别名。

• peekLast()

  • 返回列表中的最后一个元素，如果没有元素，则返回 null。

• size()

  • 返回列表中的元素数量。

• isEmpty()

  • 判断列表是否为空。

• clear()

  • 清空列表中的所有元素。

• indexOf(Object o)

  • 返回列表中首次出现的指定元素的索引，如果不存在，返回 -1。

• lastIndexOf(Object o)

  • 返回列表中最后出现的指定元素的索引，如果不存在，返回 -1。

• subList(int fromIndex, int toIndex)

  • 返回列表中从 fromIndex（包含）到 toIndex（不包含）的子列表。

2. Map

Map 接口表示键值对的集合，它不保证元素的顺序。

2.1TreeMap

TreeMap 是一个基于红黑树实现的 NavigableMap，它按照键的自然顺序或者提供的比较器进行排序。

TreeMap 特性

• 自动排序
• 提供了访问最大键、最小键以及获取键值对的方法。
• floorEntry(int key)

// 返回一个 `Map.Entry` 对象，它映射到小于或等于指定键的最大键值对。
Map.Entry<Integer, Integer> integerEntry = treeMap.floorEntry(key);

3.Queue

Queue 接口表示一个先进先出（FIFO）的集合。

3.1PriorityQueue

PriorityQueue 是一个基于优先级堆的无界队列，元素根据自然顺序或提供的比较器排序。- - -

• PriorityQueue 使用

#创建一个优先队列，其中元素按照降序排序。
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a); 

4.Deque的实现类ArrayDeque

ArrayDeque 是 Java 集合框架中 Deque（双端队列）接口的一个实现类。它是一个可调整大小的数组实现的队列，提供了在两端快速插入和删除元素的能力。

特性

• 双端队列：支持在队列的两端进行插入（offer、add）和删除（poll、remove）操作。
• 可调整大小：内部数组大小会根据需要动态调整，以容纳更多的元素。
• 非同步：ArrayDeque 不是线程安全的，如果你在多线程环境中使用，可能需要外部的同步机制。
• 迭代器：提供迭代器支持，允许遍历双端队列中的元素。

方法

• ArrayDeque()

  • 创建一个空的双端队列。

• ArrayDeque(int initialCapacity)

  • 创建一个具有指定初始容量的空双端队列。

• offerFirst(E e)

  • 在队列的开头插入元素。

• offerLast(E e)

  • 在队列的末尾插入元素。

• addFirst(E e)

  • 在队列的开头插入元素，如果队列已满，则抛出 IllegalStateException。

• addLast(E e)

  • 在队列的末尾插入元素，如果队列已满，则抛出 IllegalStateException。

• removeFirst()

  • 移除并返回队列开头的元素。

• removeLast()

  • 移除并返回队列末尾的元素。

• pollFirst()

  • 移除并返回队列开头的元素，如果没有元素，则返回 null。

• pollLast()

  • 移除并返回队列末尾的元素，如果没有元素，则返回 null。

• getFirst()

  • 返回队列开头的元素，如果没有元素，则抛出 NoSuchElementException。

• getLast()

  • 返回队列末尾的元素，如果没有元素，则抛出 NoSuchElementException。

• peekFirst()

  • 返回队列开头的元素，如果没有元素，则返回 null。

• peekLast()

  • 返回队列末尾的元素，如果没有元素，则返回 null。

• size()

  • 返回队列中的元素数量。

• isEmpty()

  • 判断队列是否为空。

• clear()

  • 清空队列中的所有元素。

对比使用

1. ArrayDeque 与 LinkedList 的优劣？

ArrayDeque 和 LinkedList 都实现了 Queue 和 Deque 接口

1.1 ArrayDeque（数组双端队列）：

1.内部使用数组来存储元素，因此支持随机访问和快速索引。
2.在队尾进行插入和删除操作的性能很好，时间复杂度为 O(1)。
3.在队头进行插入和删除操作需要移动元素，因此时间复杂度O(n).
4.不支持 null 元素。

1.2 LinkedList（链表）：

1.内部使用双向链表来存储元素，因此插入和删除操作的性能比ArrayDeque 更好。
2.在队头和队尾进行插入和删除操作的时间复杂度都是 O(1)。
3.支持 null 元素。
4.不支持随机访问，访问元素需要按照链表顺序遍历，因此时间复杂度为 O(n)。

优劣势比较：

如果需要频繁在队头和队尾进行插入和删除操作，并且不需要随机访问元素，选择 LinkedList 更合适，因为它的插入和删除性能更好。

如果需要频繁进行随机访问或者在队尾进行插入和删除操作，并且不会频繁在队头进行插入和删除操作，选择 ArrayDeque 更合适，因为它在这些方面的性能更好。

2. 那Stack呢?

优势：
1.简单易用：Stack 提供了 push、pop、peek 等方法，使得在栈的操作上非常直观和简单。
2.符合栈的特性：栈的特性是后进先出（LIFO），Stack 类的操作方法符合这一特性，可以方便地实现栈的 功能。

限制和注意事项：

继承自 Vector： Stack 是 Vector 的子类，因此它基于数组实现，会受到数组扩容和拷贝的性能影响。
线程安全性： Stack 是线程安全的，但由于继承自 Vector，其性能相对较低。在多线程环境下，推荐使 用并发包中的类，如 ConcurrentLinkedDeque。

使用技巧

如果需要使用栈这种数据结构，并且操作相对简单，不需要高性能和大规模并发，Stack 是一个合适的选择。但是在需要高性能或者多线程环境下，可以考虑使用其他更适合的数据结构，比如 ArrayDeque 或 ConcurrentLinkedDeque。

3. ConcurrentLinkedDeque

ConcurrentLinkedDeque 是 Java 中的一个并发安全的双端队列实现，它提供了高效的并发操作支持，并且不需要使用显式的同步措施（如锁），因此适合在多线程环境下使用。

特点和优势：

1.并发安全性： ConcurrentLinkedDeque 是线程安全的数据结构，可以在多线程环境下安全地进行操作，无 需额外的同步措施。
2.非阻塞操作： 内部实现采用了无锁算法（lock-free），因此不会发生线程阻塞，提高了并发性能。
3.双端队列： 支持在队头和队尾进行插入、删除等操作，具有良好的灵活性。
4.高效性能： 在多线程环境下，ConcurrentLinkedDeque 提供了较高的性能，适用于高并发的场景。
5.无边界： ConcurrentLinkedDeque 没有固定的容量限制，可以根据需要动态调整大小。

如果需要在多线程环境下使用双端队列，并且对性能有较高要求，那么 ConcurrentLinkedDeque 是一个很好的选择。它避免了传统同步机制（如锁）带来的性能开销和线程阻塞问题，提供了高效的并发操作支持。

4. 示例

import java.util.concurrent.ConcurrentLinkedDeque;

//创建 ConcurrentLinkedDeque 实例：
ConcurrentLinkedDeque<String> deque = new ConcurrentLinkedDeque<>();

//添加元素：
deque.add("First");
deque.add("Second");
deque.offer("Third"); // 在队尾添加元素


//移除元素：
String firstElement = deque.poll(); // 移除并返回队头元素
String lastElement = deque.pollLast(); // 移除并返回队尾元素


//获取元素：
String peekFirstElement = deque.peek(); // 获取但不移除队头元素
String peekLastElement = deque.peekLast(); // 获取但不移除队尾元素


//遍历元素：
for (String element : deque) {
    System.out.println(element);
}


//其他操作：
int size = deque.size(); // 获取队列大小
boolean isEmpty = deque.isEmpty();