03集合基础
目录
1.集合
在Java中，集合（也称为容器）是用于存储和操作一组对象的数据结构。Java提供了丰富的集合框架（Java Collections Framework，简称JCF），这些集合类和接口位于 java.util 包中。主要需要了解掌握的是它们的特点、用途和线程安全性。
tips：Idea工具的快捷键Ctrl+H，展开hierarchy(层次体系)窗口，逐级梳理下结构可以帮助理解。
集合有两个顶级接口：Collection和Map
-
Collection
-
Map
-
常用集合
List 接口及其实现
-
ArrayList 特点：基于动态数组实现，随机访问速度快，但插入和删除操作较慢。 线程安全性：非线程安全。 适用场景：需要快速随机访问的场景。
-
LinkedList 特点：基于双向链表实现，插入和删除操作快，但随机访问较慢。 线程安全性：非线程安全。 适用场景：需要频繁插入和删除操作的场景。
-
Vector 特点：类似于 ArrayList，但所有方法都是同步的，因此是线程安全的。 线程安全性：线程安全。 适用场景：需要线程安全且性能要求不高的场景。 CopyOnWriteArrayList 特点：基于写时复制技术实现，读操作不需要加锁，写操作会创建一个新的副本。 线程安全性：线程安全。 适用场景：读多写少的场景。
Set 接口及其实现
-
HashSet 特点：基于哈希表实现，插入、删除和查找操作平均时间复杂度为 O(1)。 线程安全性：非线程安全。 适用场景：需要快速查找、插入和删除操作的场景。
-
LinkedHashSet 特点：基于哈希表和链表实现，保留插入顺序。 线程安全性：非线程安全。 适用场景：需要保留插入顺序的场景。
-
TreeSet 特点：基于红黑树实现，元素自动排序。 线程安全性：非线程安全。 适用场景：需要排序的场景。
-
CopyOnWriteArraySet 特点：基于 CopyOnWriteArrayList 实现，读操作不需要加锁，写操作会创建一个新的副本。 线程安全性：线程安全。 适用场景：读多写少的场景。
Map 接口及其实现
-
HashMap 特点：基于哈希表实现，插入、删除和查找操作平均时间复杂度为 O(1)。 线程安全性：非线程安全。 适用场景：需要快速查找、插入和删除操作的场景。
-
LinkedHashMap 特点：基于哈希表和链表实现，保留插入顺序。 线程安全性：非线程安全。 适用场景：需要保留插入顺序的场景。
-
TreeMap 特点：基于红黑树实现，键自动排序。 线程安全性：非线程安全。 适用场景：需要排序的场景。
-
Hashtable 特点：类似于 HashMap，但所有方法都是同步的，因此是线程安全的。 线程安全性：线程安全。 适用场景：需要线程安全且性能要求不高的场景。
-
ConcurrentHashMap 特点：基于分段锁技术实现，允许多个线程同时访问不同的段，提高了并发性能。 线程安全性：线程安全。 适用场景：需要高并发性能的场景。
Queue 接口及其实现
-
LinkedList 特点：实现了 Queue 接口，可以作为队列使用。 线程安全性：非线程安全。 适用场景：需要队列功能的场景。
-
PriorityQueue 特点：基于优先级堆实现，元素按优先级排序。 线程安全性：非线程安全。 适用场景：需要按优先级处理元素的场景。
-
ConcurrentLinkedQueue 特点：基于无锁算法实现，允许多个线程同时访问。 线程安全性：线程安全。 适用场景：需要高并发性能的队列场景。
-
ArrayDeque 特点：基于数组实现的双端队列，支持高效的插入和删除操作。 线程安全性：非线程安全。 适用场景：需要双端队列功能的场景。
Deque 接口及其实现
-
ArrayDeque 特点：基于数组实现的双端队列，支持高效的插入和删除操作。 线程安全性：非线程安全。 适用场景：需要双端队列功能的场景。
-
LinkedList 特点：实现了 Deque 接口，可以作为双端队列使用。 线程安全性：非线程安全。 适用场景：需要双端队列功能的场景。
Stack类
Stack 是一个后进先出（LIFO）的集合，继承自 Vector。特点：基于 Vector 实现，所有方法都是同步的，因此是线程安全的。 线程安全性：线程安全。 适用场景：需要栈功能的场景。
并发集合类
-
ConcurrentHashMap 特点：基于分段锁技术实现，允许多个线程同时访问不同的段，提高了并发性能。 线程安全性：线程安全。 适用场景：需要高并发性能的场景。
-
CopyOnWriteArrayList 特点：基于写时复制技术实现，读操作不需要加锁，写操作会创建一个新的副本。 线程安全性：线程安全。 适用场景：读多写少的场景。
-
CopyOnWriteArraySet 特点：基于 CopyOnWriteArrayList 实现，读操作不需要加锁，写操作会创建一个新的副本。 线程安全性：线程安全。 适用场景：读多写少的场景。
-
ConcurrentLinkedQueue 特点：基于无锁算法实现，允许多个线程同时访问。 线程安全性：线程安全。 适用场景：需要高并发性能的队列场景。
-
ConcurrentLinkedDeque 特点：基于无锁算法实现，允许多个线程同时访问。 线程安全性：线程安全。 适用场景：需要高并发性能的双端队列场景。
工具类
Collections - 特点：提供了一些静态方法，可以将非线程安全的集合类包装成线程安全的集合类。
- 方法：
- synchronizedList(List<T> list)
- synchronizedSet(Set<T> set)
- synchronizedMap(Map<K,V> map)
2.ArrayList
1.ArrayList构造方法: a.ArrayList() 构造一个初始容量为10的空列表 b.ArrayList(int initialCapacity) 构造具有指定初始容量的空列表 2.ArrayList源码总结: a.不是一new底层就会创建初始容量为10的空列表,而是第一次add的时候才会创建初始化容量为10的空列表 b.ArrayList底层是数组,那么为啥还说集合长度可变呢? ArrayList底层会自动扩容-> Arrays.copyOf c.扩容多少倍? 1.5倍
源码分析：
ArrayList() 构造一个初始容量为10的空列表
=========================================
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Object[] elementData; ->ArrayList底层的那个数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
=========================================
list.add("a");
public boolean add(E e) {
modCount++;
add(e, elementData, size);// e->要存的元素 elementData->集合数组,长度开始为0,size->0
return true;
}
private void add(E e->元素, Object[] elementData->集合数组, int s->0) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity->1) {
int oldCapacity = elementData.length;//0
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY->10, minCapacity->1)];
}
}
==========================================
假设ArrayList中存了第11个元素,会自动扩容-> Arrays.copyOf
private Object[] grow(int minCapacity) {//11
int oldCapacity = elementData.length;//10
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity(15) = ArraysSupport.newLength(oldCapacity->10,
minCapacity - oldCapacity->1, /* minimum growth */
oldCapacity >> 1 ->5 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
public static int newLength(int oldLength->10, int minGrowth->1, int prefGrowth->5) {
// preconditions not checked because of inlining
// assert oldLength >= 0
// assert minGrowth > 0
int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // 15
if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
return prefLength;
} else {
// put code cold in a separate method
return hugeLength(oldLength, minGrowth);
}
}
ArrayList(int initialCapacity) 构造具有指定初始容量的空列表
ArrayList<String> list = new ArrayList<>(5);
==============================================
public ArrayList(int initialCapacity->5) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];//直接创建长度为5的数组
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
ArrayList<String> list = new ArrayList<String>() -> 现在我们想用都是new
但是将来开发不会想使用就new集合,都是调用一个方法,查询出很多数据来,此方法返回一个集合,自动将查询出来的数据放到集合中,我们想在页面上展示数据,遍历集合
而且将来调用方法,返回的集合类型,一般都是接口类型
List<泛型> list = 对象.查询方法()
3.LinkedList
手写一个链表数据结构就理解了
单向链表的实现
1. 节点类（Node）
首先，定义一个节点类 Node，它包含数据和指向下一个节点的引用。
java深色版本
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
2. 链表类（LinkedList）
接下来，定义一个链表类 LinkedList，它包含头节点和一些基本操作方法。
java深色版本
public class LinkedList {
private Node head;
public LinkedList() {
this.head = null;
}
// 插入节点到链表头部
public void insertAtHead(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
// 插入节点到链表尾部
public void insertAtTail(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
// 删除节点
public void delete(int data) {
if (head == null) {
return;
}
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null && current.next.data != data) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}
// 查找节点
public Node find(int data) {
Node current = head;
while (current != null) {
if (current.data == data) {
return current;
}
current = current.next;
}
return null;
}
// 遍历链表
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
3. 测试代码
最后，编写一个测试类来验证链表的各种操作。
java深色版本
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
// 插入节点
list.insertAtHead(3);
list.insertAtHead(2);
list.insertAtHead(1);
list.insertAtTail(4);
list.insertAtTail(5);
// 打印链表
System.out.println("初始链表:");
list.printList(); // 输出: 1 2 3 4 5
// 查找节点
Node foundNode = list.find(3);
if (foundNode != null) {
System.out.println("找到节点: " + foundNode.data); // 输出: 找到节点: 3
} else {
System.out.println("未找到节点");
}
// 删除节点
list.delete(3);
System.out.println("删除节点后的链表:");
list.printList(); // 输出: 1 2 4 5
// 再次查找已删除的节点
foundNode = list.find(3);
if (foundNode != null) {
System.out.println("找到节点: " + foundNode.data);
} else {
System.out.println("未找到节点"); // 输出: 未找到节点
}
}
}
解释
-
节点类
Node：-
data：存储节点的数据。 -
next：指向下一个节点的引用。
-
-
链表类
LinkedList：-
head：指向链表的头节点。 -
insertAtHead：在链表头部插入节点。 -
insertAtTail：在链表尾部插入节点。 -
delete：删除指定数据的节点。 -
find：查找指定数据的节点。 -
printList：遍历并打印链表中的所有节点。
-
-
测试代码：
-
创建一个
LinkedList实例。 -
插入节点到链表头部和尾部。
-
打印链表。
-
查找节点。
-
删除节点。
-
再次查找已删除的节点。
-
4.迭代器
Iterator接口的主要作用是遍历集合，主要包含的方法：
boolean hasNext() // 判断集合有没有下一个元素 E next() // 获取下一个元素
常规简单用法：
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("orange");
list.add("grape");
list.add("pear");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String fruit = iterator.next();
System.out.println(fruit);
}
}
2个需要注意的点：
a.next方法在获取的时候不要连续使用多次，会抛出NoSuchElementException:没有可操作的元素异常
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("orange");
list.add("grape");
list.add("pear");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String fruit = iterator.next();
System.out.println(fruit);
String fruit1 = iterator.next();
System.out.println(fruit1);
}
}
-
5个元素都会遍历打印到控制台
-
单次循环遍历两个元素
-
第三次遍历中的第二个判断抛出异
根据next()方法的源码理解：
b.使用迭代器迭代集合的过程中,不要随意修改集合长度,容易出现并发修改异常：ConcurrentModificationException
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("orange");
list.add("grape");
list.add("pear");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String fruit = iterator.next();
if("orange".equals(fruit)) {
list.add("watermelon");
}
}
}
结论:当预期操作次数和实际操作次数不相等了,会出现"并发修改异常"。
原因:next()方法里checkForComodification()会检查expectedModCount和modCount是否相等，add和remove都会改变modCount，但是没有变更expectedModCount，所以会抛出异常。
5.增强for
1.作用:
遍历集合或者数组
2.格式:
for(元素类型 变量名:要遍历的集合名或者数组名){
变量名就是代表的每一个元素
}
3.注意：
a.增强for遍历集合时,底层实现原理为迭代器，错误的操作也会触发iterator的NoSuchElementException和ConcurrentModificationException
b.增强for遍历数组时,底层实现原理为普通for
6.泛型
泛型是一种类型安全的机制，它允许在定义类、接口和方法时使用类型参数。主要有3个好处：
-
复用代码：重用相同的代码处理不同的参数类型
-
类型安全：确保编译时类型正常，减少运行时类型参数转换异常
-
消除类型转换异常：减少显式转换类型带来的异常
定义泛型类
public class Box<T> {
private T item;
public T getItem() {
return item;
}
public void setItem(T item) {
this.item = item;
}
}
定义泛型方法
public class Util {
public static <T> void printArray(T[] array) {
for (T element : array) {
System.out.print(element + " ");
}
System.out.println();
}
}
使用通配符
通配符（wildcards）用于表示未知的类型。使用通配符可以使泛型更加灵活。
-
无界通配符：
?表示未知类型。 -
上界通配符：
? extends T表示某个未知类型，该类型是T的子类型。 -
下界通配符：
? super T表示某个未知类型，该类型是T的父类型。
例如
public void process(List<? extends Number>) { // 可以接收任何Number的子类型列表
// ...
}
public void addNumbers(List<? super Integer>) { // 可以接收Integer或其父类型的列表
// ...
}
7.树
树是一种常用的数据结构，用于存储层次化的数据。树结构有许多变体，其中一些常见的树结构包括二叉树、平衡树和红黑树等。下面将详细介绍这些树结构的特点和应用场景。
1. 二叉树（Binary Tree）
二叉树是一种每个节点最多有两个子节点的树结构。这两个子节点通常被称为左子节点和右子节点。根据节点的排列方式，二叉树可以进一步分为以下几种类型：
-
普通二叉树：没有特定的顺序要求。
-
二叉搜索树（Binary Search Tree, BST）：对于任意节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。
-
完全二叉树：除了最后一层外，其他各层上的所有节点都被完全填充，且最后一层元素是从左到右顺序填充。
-
满二叉树：每一层上的所有节点都有两个子节点。
2. 平衡树（Balanced Tree）
平衡树是一种特殊的二叉搜索树，它的特点是树的高度保持在一个较小的范围内，从而保证了插入、删除和查找操作的时间复杂度为 O(logn)O(logn)。常见的平衡树有：
-
AVL 树：一种自平衡二叉搜索树，任何节点的两个子树的高度最大差别为1。如果插入或删除操作导致不平衡，会通过旋转操作来恢复平衡。
-
红黑树：一种自平衡二叉搜索树，通过颜色（红色或黑色）来保证树的平衡。红黑树的每个节点都有一个颜色属性，通过一系列规则来确保树的高度保持在 O(logn)O(logn)。
3. 红黑树（Red-Black Tree）
红黑树是一种自平衡二叉搜索树，具有以下特性：
-
每个节点要么是红色，要么是黑色。
-
根节点是黑色。
-
所有叶子节点（NIL节点，空节点）是黑色。
-
如果一个节点是红色的，则它的两个子节点都是黑色的（即不存在两个连续的红色节点）。
-
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树通过这些规则确保了树的高度保持在 O(logn)O(logn)，从而保证了高效的操作性能。
4. 其他常见树结构
-
B 树：一种自平衡的多路搜索树，常用于文件系统和数据库索引。每个节点可以有多个子节点。
-
B+ 树：B 树的一种变体，所有的数据都存储在叶子节点上，叶子节点之间有指针连接，适合范围查询。
-
Trie 树（字典树）：用于存储字符串集合的数据结构，常用于搜索引擎和拼写检查。
-
堆（Heap）：一种特殊的完全二叉树，分为最大堆和最小堆，常用于实现优先队列。
总结
每种树结构都有其特定的应用场景和优势：
-
二叉树：适用于简单的层次化数据存储。
-
平衡树：适用于需要高效插入、删除和查找操作的场景。
-
红黑树：广泛应用于各种编程语言的标准库中，如 C++ STL 中的
std::map和std::set。 -
B 树和 B+ 树：常用于文件系统和数据库索引，适合磁盘存储。
-
Trie 树：适用于字符串匹配和前缀搜索。
-
堆：适用于实现优先队列和堆排序算法。
8.Set集合
Set接口并没有对Collection接口进行功能上的扩充,而且所有的Set集合底层都是依靠Map实现
HashSet 和 LinkedHashSet 都是 Java 集合框架中用于存储唯一元素的集合类，它们都实现了 Set 接口。尽管它们的功能相似，但在内部实现和性能特性上有显著的区别。下面是它们的详细对比：
HashSet
-
内部实现：
-
HashSet内部使用哈希表（实际上是HashMap的实例）来存储元素。 -
每个元素都被映射到一个桶（bucket）中，桶的位置由元素的哈希码（
hashCode）决定。
-
-
性能：
-
插入、删除和查找操作的时间复杂度为 O(1)O(1)（平均情况下）。
-
哈希表的性能依赖于哈希函数的质量，一个好的哈希函数可以减少冲突，提高性能。
-
-
迭代顺序：
-
HashSet不保证元素的迭代顺序，即每次遍历集合时，元素的顺序可能会不同。 -
这是因为元素的存储位置取决于其哈希码，而哈希码通常是随机的。
-
-
内存使用：
-
HashSet的内存使用相对较低，因为它只需要存储元素及其哈希码。
-
LinkedHashSet
-
内部实现：
-
LinkedHashSet内部也是使用哈希表来存储元素，但它额外维护了一个双向链表，记录元素的插入顺序。 -
这个双向链表确保了元素的迭代顺序与插入顺序一致。
-
-
性能：
-
插入、删除和查找操作的时间复杂度仍然是 O(1)O(1)（平均情况下）。
-
但由于额外的链表维护，
LinkedHashSet在某些操作上可能会稍微慢一些。
-
-
迭代顺序：
-
LinkedHashSet保证元素的迭代顺序与插入顺序一致。 -
这使得
LinkedHashSet在需要按插入顺序遍历元素的场景中非常有用。
-
-
内存使用：
-
LinkedHashSet的内存使用略高于HashSet，因为它需要额外的空间来维护双向链表。
-
使用场景
-
HashSet：
-
当你只需要存储唯一的元素，而不关心元素的迭代顺序时，使用
HashSet。 -
适用于高性能的集合操作，尤其是当集合很大时。
-
-
LinkedHashSet：
-
当你需要保持元素的插入顺序时，使用
LinkedHashSet。 -
适用于需要按插入顺序遍历元素的场景，例如缓存最近使用的项。
-
原文地址：https://blog.csdn.net/Elaine2391/article/details/143500610
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！