Java集合概念

说说 List, Set, Queue, Map 四者的区别？

• List: 存储的元素是有序的、可重复的，典型代表就是封装了动态数组的ArrayList和封装了链表的 LinkedList
• Set: 无序、不可重复的集合，典型代表就是 HashSet 和 TreeSet；
• Queue: 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的，典型代表就是双端队列 ArrayDeque，以及优先级队列 PriorityQueue
• Map: 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，"x" 代表 key，"y" 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

集合框架底层数据结构总结

List

• ArrayList是容量可变的非线程安全列表，其底层使用数组实现。当几何扩容时，会创建更大的数组，并把原数组复制到新数组。ArrayList支持对元素的快速随机访问，但插入与删除速度很慢。
• LinkedList本质是一个双向链表，与ArrayList相比，，其插入和删除速度更快，但随机访问速度更慢。

Set

• HashSet 底层用 HashMap 实现：元素作为 Key，统一绑定一个虚拟值 PRESENT。通过 Key 的唯一性保证元素不重复，但无序；由于依赖 HashMap，线程不安全
• LinkedHashSet继承自HashSet，通过LinkedHashMap实现，使用双向链表维护元素插入顺序。
• TreeSet通过TreeMap实现的，添加元素到集合时按照比较规则将其插入合适的位置，保证插入后的集合仍然有序。

Queue

• PriorityQueue: Object[] 数组来实现小顶堆
• elayQueue:PriorityQueue
• ArrayDeque: 可扩容动态双向数组。

Map

• HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
• LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的
• TreeMap：红黑树（自平衡的排序二叉树）
• ConcurrentHashMap：Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后volatile + CAS 或者 synchronized）

集合遍历的方法有哪些？

在Java中，集合的遍历方法主要有以

下几种：

• 普通 for 循环： 可以使用带有索引的普通 for 循环来遍历 List。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

for (int i = 0; i < list.size(); i++) {
    String element = list.get(i);
    System.out.println(element);
}

• 增强 for 循环（for-each循环）： 用于循环访问数组或集合中的元素。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

for (String element : list) {
    System.out.println(element);
}

• Iterator 迭代器： 可以使用迭代器来遍历集合，特别适用于需要删除元素的情况。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

Iterator<String> iterator = list.iterator();
while(iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}

• ListIterator 列表迭代器： ListIterator是迭代器的子类，可以双向访问列表并在迭代过程中修改元素。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

ListIterator<String> listIterator= list.listIterator();
while(listIterator.hasNext()) {
    String element = listIterator.next();
    System.out.println(element);
}

• 使用 forEach 方法： Java 8引入了 forEach 方法，可以对集合进行快速遍历。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

list.forEach(element -> System.out.println(element));

• Stream API： Java 8的Stream API提供了丰富的功能，可以对集合进行函数式操作，如过滤、映射等。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

list.stream().forEach(element -> System.out.println(element));