目录
1.集合
Collection
Map
常用集合
List 接口及其实现
Set 接口及其实现
Map 接口及其实现
Queue 接口及其实现
Deque 接口及其实现
Stack类
并发集合类
工具类
2.ArrayList
3.LinkedList
单向链表的实现
1. 节点类(Node)
2. 链表类(LinkedList)
3. 测试代码
4.迭代器
5.增强for
6.泛型
7.树
1. 二叉树(Binary Tree)
2. 平衡树(Balanced Tree)
3. 红黑树(Red-Black Tree)
4. 其他常见树结构
总结
8.Set集合
HashSet
LinkedHashSet
使用场景
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->0return 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;//0if (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) {//11int oldCapacity = elementData.length;//10if (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); // 15if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {return prefLength;} else {// put code cold in a separate methodreturn 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和ConcurrentModificationExceptionb.增强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
。 -
适用于需要按插入顺序遍历元素的场景,例如缓存最近使用的项。
-