集合
集合是一种用于存储多个元素的数据结构。
集合分类
List：ArrayList、LinkedList...
Collection：单列集合（List：可重复 set：不能重复）{ Set：HashSet、TreeSet...
集合{ Queue：LinkedList、PriorityQueue...
Map：双列集合：HashMap...
Collection
Collection是单例集合的顶级接口，表示一组对象，这些对象也被称为Collection的元素，JDK不提供此接口的任何直接实现，它提供更具体的子接口(如List、set)实现。
Collection相关方法
- 添加元素
boolean add(E e)：将指定的元素添加到集合中。如果集合因为调用此方法而发生改变，则返回true；如果集合不允许重复元素且元素已存在，则返回false。
Collection<String> collection = new ArrayList<>();
boolean result = collection.add("apple");
boolean addAll(Collection<? extends E> c)：将指定集合中的所有元素添加到当前集合中。如果当前集合因为调用此方法而发生改变，则返回true。
Collection<String> collection1 = new ArrayList<>();
collection1.add("apple");
collection1.add("banana");
Collection<String> collection2 = new ArrayList<>();
collection2.add("cherry");
boolean result = collection1.addAll(collection2);- 删除元素
boolean remove(Object o)：从集合中移除指定元素的单个实例(如果存在)。如果集合因为调用此方法而发生改变，则返回true。
Collection<String> collection = new ArrayList<>();
collection.add("apple");
boolean result = collection.remove("apple");
boolean removeAll(Collection<?> c)：从当前集合中移除包含在指定集合中的所有元素。如果当前集合因为调用此方法而发生改变，则返回true。
Collection<String> collection1 = new ArrayList<>();
collection1.add("apple");
collection1.add("banana");
Collection<String> collection2 = new ArrayList<>();
collection2.add("apple");
boolean result = collection1.removeAll(collection2);
void clear()：移除列表中的所有元素。
Collection<String> collection = new ArrayList<>();
collection.add("apple");
collection.add("banana");
collection.clear();
default boolean removeIf(Predicate<? super E> filter)：移除集合中满足指定条件的所有元素。如果集合因为调用此方法而发生改变，则返回true。
Collection<String> collection = new ArrayList<>();
collection.add("apple");
collection.add("banana");
boolean result = collection.removeIf(s -> s.startsWith("a"));- 查询元素
boolean contains(Object o)：检查集合中是否包含指定元素。如果包含则返回true。
Collection<String> collection = new ArrayList<>();
collection.add("apple");
boolean result = collection.contains("apple");
boolean containsAll(Collection<?> c)：检查当前集合是否包含指定集合中的所有元素。如果包含则返回true。
Collection<String> collection1 = new ArrayList<>();
collection1.add("apple");
collection1.add("banana");
Collection<String> collection2 = new ArrayList<>();
collection2.add("apple");
boolean result = collection1.containsAll(collection2);- 返回元素数
int size()：返回集合中元素的数量。
Collection<String> collection = new ArrayList<>();
collection.add("apple");
int size = collection.size();- 判空
boolean isEmpty()：检查集合是否为空。如果集合不包含任何元素，则返回true。
Collection<String> collection = new ArrayList<>();
boolean result = collection.isEmpty();- 转为数组
Object[] toArray()：返回一个包含集合中所有元素的数组。
Collection<String> collection = new ArrayList<>();
collection.add("apple");
Object[] array = collection.toArray();
<T> T[] toArray(T[] a)：返回一个包含集合中所有元素的数组，数组的运行时类型与指定数组的运行时类型相同。
Collection<String> collection = new ArrayList<>();
collection.add("apple");
//new String[0]：传入一个长度为0的String类型数组。当传入的数组长度小于集合的大小时，toArray方法会创建一个新的、与集合大小相同的String类型数组，并将集合中的元素复制到这个新数组中，然后返回该新数组。new String[0]的目的是让toArray方法自动创建合适大小的数组。
String[] array = collection.toArray(new String[0]);- 迭代集合
Iterator<E> iterator()：返回一个用于遍历集合元素的迭代器。
Collection<String> collection = new ArrayList<>();
collection.add("apple");
collection.add("banana");
Iterator<String> iterator = collection.iterator();
while (iterator.hasNext()) {
String element = iterator.next();
System.out.println(element);
}
List
List 接口表示有序、可重复的集合，操作者可以精确控制列表中每个元素的插入位置，还可以通过索引访问元素。
ArrayList
基于动态数组实现，支持随机访问，即可以通过索引快速访问元素，时间复杂度为O(1)。但在插入和删除元素时，尤其是在列表中间位置，可能需要移动大量元素，时间复杂度为O(n)。
ArrayList相关方法
- 构造方法：
ArrayList()：创建一个初始容量为10的空列表。
ArrayList<String> list = new ArrayList<>();
ArrayList(int initialCapacity)：创建一个具有指定初始容量的空列表。
ArrayList<String> list = new ArrayList<>(20);
ArrayList(Collection<? extends E> c)：创建一个包含指定集合元素的列表，元素顺序按照集合的迭代器返回顺序。
List<String> collection = Arrays.asList("apple", "banana", "cherry");
ArrayList<String> list = new ArrayList<>(collection);- 添加元素
boolean add(E e)：将指定的元素添加到此列表的尾部。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
void add(int index, E element)：将指定的元素插入此列表中的指定位置。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
//插入到第二个位置
list.add(1, "cherry");
boolean addAll(Collection<? extends E> c)：将指定集合中的所有元素添加到此列表的尾部。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
List<String> collection = Arrays.asList("banana", "cherry");
list.addAll(collection);
boolean addAll(int index, Collection<? extends E> c)：将指定集合中的所有元素插入到此列表的指定位置。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
List<String> collection = Arrays.asList("banana", "cherry");
list.addAll(1, collection);- 访问元素
E get(int index)：返回此列表中指定位置的元素。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
String element = list.get(0);- 修改元素
E set(int index, E element)：用指定的元素替换此列表中指定位置的元素。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.set(0, "grape");- 删除元素
E remove(int index)：移除列表中指定位置的元素。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
String removed = list.remove(0);
boolean remove(Object o)：移除列表中首次出现的指定元素。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
boolean removed = list.remove("apple");
boolean removeAll(Collection<?> c)：从此列表中移除包含在指定集合中的所有元素。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("cherry");
List<String> collection = Arrays.asList("apple", "cherry");
//只要移除一个就返回TRUE，移除元素集合中没有不会爆错，会移除满足条件的所有元素
boolean removed = list.removeAll(collection);
void clear()：移除列表中的所有元素。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.clear();- 查询元素
boolean contains(Object o)：如果列表包含指定的元素，则返回true。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
boolean contains = list.contains("apple");
int indexOf(Object o)：返回此列表中首次出现的指定元素的索引，如果列表不包含该元素，则返回 -1。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
int index = list.indexOf("apple");
int lastIndexOf(Object o)：返回此列表中最后一次出现的指定元素的索引，如果列表不包含该元素，则返回 -1。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("apple");
int lastIndex = list.lastIndexOf("apple");- 返回元素数
int size()：返回此列表中的元素数。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
int size = list.size();- 判空
boolean isEmpty()：如果列表不包含元素，则返回true。
ArrayList<String> list = new ArrayList<>();
boolean isEmpty = list.isEmpty();- 转为数组
Object[] toArray()：返回按适当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
Object[] array = list.toArray();
<T> T[] toArray(T[] a)：返回按适当顺序(从第一个元素到最后一个元素)包含此列表中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
//new String[0]：传入一个长度为0的String类型数组。当传入的数组长度小于ArrayList的大小时，toArray方法会创建一个新的、与ArrayList大小相同的String类型数组，并将ArrayList中的元素复制到这个新数组中，然后返回该新数组。new String[0]的目的是让toArray方法自动创建合适大小的数组。
String[] array = list.toArray(new String[0]);
LinkedList
基于双向链表实现，插入和删除元素的效率较高，时间复杂度为O(1)，但随机访问元素的效率较低，时间复杂度为O(n)。
LinkedList特有方法
- 插入元素
addFirst(E e)：将指定元素插入到列表的开头。
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.addFirst("Cherry");
addLast(E e)：将指定元素插入到列表的末尾。该方法与add(E e)功能相同。
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.addLast("Cherry");
offerFirst(E e)：将指定元素插入到列表的开头。如果成功插入则返回true，否则返回false。通常在容量受限的队列中使用，对于LinkedList来说，一般都会插入成功。
LinkedList<String> list = new LinkedList<>();
boolean result = list.offerFirst("Apple");
offerLast(E e)：将指定元素插入到列表的末尾。如果成功插入则返回true，否则返回false。
LinkedList<String> list = new LinkedList<>();
boolean result = list.offerLast("Apple");- 获取元素相关方法
getFirst()：返回列表的第一个元素。如果列表为空，则抛出NoSuchElementException异常。
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
try {
String first = list.getFirst();
} catch (NoSuchElementException e) {
System.out.println("List is empty");
}
getLast()：返回列表的最后一个元素。如果列表为空，则抛出NoSuchElementException异常。
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
try {
String first = list.getLast();
} catch (NoSuchElementException e) {
System.out.println("List is empty");
}
peekFirst()：返回列表的第一个元素，如果列表为空，则返回null。
LinkedList<String> list = new LinkedList<>();
String first = list.peekFirst();
peekLast()：返回列表的最后一个元素，如果列表为空，则返回null。
LinkedList<String> list = new LinkedList<>();
String first = list.peekLast();- 删除元素相关方法
removeFirst()：移除并返回列表的第一个元素。如果列表为空，则抛出NoSuchElementException异常。
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
try {
String removed = list.removeFirst();
} catch (NoSuchElementException e) {
System.out.println("List is empty");
}
removeLast()：移除并返回列表的最后一个元素。如果列表为空，则抛出NoSuchElementException异常。
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
try {
String removed = list.removeLast();
} catch (NoSuchElementException e) {
System.out.println("List is empty");
}
Set
Set是一个不包含重复元素的集合接口，它没有带索引的方法，不能使用普通for循环遍历。
Set常用方法
- 添加元素
boolean add(E e)：将指定的元素添加到集合中，如果集合中不包含该元素，则添加成功并返回true；如果集合中已经包含该元素，则不添加并返回false。
Set<String> set = new HashSet<>();
boolean result = set.add("apple");- 删除元素
boolean remove(Object o)：从集合中移除指定的元素，如果集合中包含该元素，则移除成功并返回true；否则返回false。
HashSet
- 底层数据结构是哈希表；
- 对集合的迭代顺序不作任何保证，也就是不保证存储和取出的元素顺序一致；
- 没有带索引的方法，所以不能使用普通for循环遍历④因是Set集合，故是不包含重复元素集合。
哈希值
哈希值：是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值
Object类中有一个方法(hashCode)可以获取对象的哈希值(对象.hashCode())(同一个对象多次调用hashCode方法返回的值相同)
(默认情况下，不同对象的hashCode值是不同的，通过方法重写可实现不同对象相同哈希值)
哈希表
JDK8之前，底层采用数组加链表实现(元素为链表的数组)，在 JDK8及之后的版本中，HashMap的底层实现做了优化，引入了红黑树。当链表长度达到一定阈值(默认为 8)，并且数组长度达到 64 时，链表会转换为红黑树；当树节点数量小于 6 时，红黑树又会转换回链表。
优化
哈希表示例："hello":99162322 "world":113318802 "java":3254818 "world":113318802 "童话":1179395 "寓言":1179395
①对哈希值进行16的取余，第一排全为2，第二排全为3，第一排内容只存在索引为二的位置，第二排内容只存在索引为三的位置
②2、3最开始为空，先分别存入hello与童话
③world与java的哈希值与hello及两者间不同，依次存入world与java
④第二个world的哈希值与第一个world相同，然后看内容，也相同，不存
⑤寓言与童话哈希值相同，看内容，不同，存入寓言
0 1 2 3 4 ... 15
hello 童话
world 寓言
java
LinkedHashSet
哈希表和链表实现Set接口，具有可预测的迭代次序；由链表保证元素有序，元素的存储和取出一致；由哈希表保证元素唯一，无重复的元素。
TreeSet
元素有序，不是指存储或取出的顺序，而是按照一定规则进行排序，具体取决于构造方法(TreeSet():根据元素自然排序进行排序)(TreeSet(Comparator comparator)：根据指定比较器进行排序）
没有带索引的方法，所以不能使用普通for循环遍历；Set集合，不包含重复元素集合。自然排序Comparable的使用：用TreeSet集合存储自定义对象，无参构造方法使用的是自然排序对元素进行排序的；自然排序是让元素所属的类实现Comparable接口，重写compareTo(To)方法；重写方法时一定要注意排序规则必须按照要求的主要和次要条件写(小->大)。
比较器排序Comparable的使用：用TreeSet集合存储自定义对象，带参构造方法使用的是比较器排序对元素进行排序的；比较器排序，是让集合构造方法接收Comparator的实现类对象，重写compare(T o1,T o2)方法；重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写。
TreeSet<Student> ts = new TreeSet<Student>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
int num = o2.getChinese()+o2.getMath()-o1.getChinese()-o1.getMath();
int num2 = num==0?o2.getName().compareTo(o1.getName()):num;
return num2;
}
});
队列
队列：一种遵循先进先出(First-In-First-Out，FIFO)原则的线性数据结构，在Java中，Queue 是一个接口，它继承自 Collection 接口，并提供了处理队列数据结构的方法。
Map
Map是一种用于存储键值对(key - value pairs)的数据结构，也被称作映射、字典或关联数组，其核心思想是通过一个唯一的键(key)来快速查找对应的值(value)。
Map常用方法
- 添加键值对
V put(K key, V value)：将指定的键值对插入到Map中。如果键已经存在，则用新值替换旧值，并返回旧值；如果键不存在，则插入该键值对并返回null。
Map<String, Integer> map = new HashMap<>();
Integer oldValue = map.put("apple", 1);- 获取值
V get(Object key)：根据指定的键获取对应的value。如果键存在，则返回对应的value；如果键不存在，则返回null。
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
Integer value = map.get("apple");- 删除键值对
V remove(Object key)：根据指定的键删除对应的键值对，并返回被删除的值。如果键不存在，则返回null。
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
Integer removedValue = map.remove("apple");- 检查键是否存在
boolean containsKey(Object key)：检查Map中是否包含指定的键。如果包含则返回true，否则返回false。
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
boolean result = map.containsKey("apple");- 检查值是否存在
boolean containsValue(Object value)：检查 Map 中是否包含指定的值。如果包含则返回 true，否则返回 false。
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
boolean result = map.containsValue(1);- 获取键的集合
Set<K> keySet()：返回Map中所有键的集合。
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
Set<String> keySet = map.keySet();
for (String key : keySet) {
System.out.println(key);
}- 获取值的集合
Collection<V> values()：返回Map中所有值的集合。
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
Collection<Integer> values = map.values();
for (Integer value : values) {
System.out.println(value);
}- 获取键值对的集合
Set<Map.Entry<K, V>> entrySet()：返回Map中所有键值对的集合，每个键值对封装在Map.Entry对象中。
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
for (Map.Entry<String, Integer> entry : entrySet) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}- 集合大小
int size()：返回Map中键值对的数量。
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
int size = map.size();- 清空集合
void clear()：移除Map中的所有键值对，使Map变为空。
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.clear();- 检查集合是否为空
boolean isEmpty()：如果Map中不包含任何键值对，则返回true；否则返回false。
Map<String, Integer> map = new HashMap<>();
boolean result = map.isEmpty();
Map遍历
方式一：
Set<String> keySet = map.keySet();
for (String s : keySet) {
String k = map.get(s);
System.out.println(s+","+k);
}
方式二：
Set<Map.Entry<String, String>> entries = map.entrySet();
for (Map.Entry<String, String> a : entries) {
String key = a.getKey();
String value = a.getValue();
System.out.println(key+""+value);
}
ArrayList中嵌套HashMap：
ArrayList<HashMap<String,String>> array = new ArrayList<>();
for(HashMap<String,String> map : array){
Set<String> keySet = map.ketSet();
for(String s : keySet){
String cur = map.get(s);
System.out.println(s+","+cur);
}
}
HashMap中嵌套ArrayList：
HashMap<String,ArrayList<String>> hm = new HashMap<>();
Set<String> keySet = hm.getSet();
for(String key : keySet()){
System.out.println(key);
ArrayList<String> value = hm.get(key);
for(String curValue : value){
System.out.println(curValue);
}
}
TreeMap中进行比较器排序
//创建一个 Comparator 对象，title为key，price为value，按照书的价格从高到低排序，如果价格相同则按书名排序
Comparator<Book> bookComparator = new Comparator<Book>() {
@Override
public int compare(Book b1, Book b2) {
int result = Double.compare(b2.price, b1.price);
if (result == 0) {
return b1.title.compareTo(b2.title);
}
return result;
}
};
// 创建 TreeMap 实例，传入 Comparator 对象
TreeMap<Book, String> treeMap = new TreeMap<>(bookComparator);
// 向 TreeMap 中添加元素
treeMap.put(new Book("Java Programming", 50.0), "Category A");
treeMap.put(new Book("Python Basics", 30.0), "Category B");
treeMap.put(new Book("Data Structures", 50.0), "Category C");
HashMap
基于哈希表实现，不保证键值对的顺序，允许存储null键和null值，插入、删除和查找操作的时间复杂度为O(1)。
LinkedHashMap
继承自 HashMap，基于哈希表和链表实现，保证键值对的插入顺序，允许存储null键和null值，插入、删除和查找操作的时间复杂度为O(1)。
TreeMap
基于红黑树实现，保证键按照自然顺序(或指定的比较器顺序)排序，不允许存储null键，插入、删除和查找操作的时间复杂度为O(log n)。
Hashtable
基于哈希表实现，线程安全，不允许存储null键和null值，插入、删除和查找操作的时间复杂度为O(1)。
