集合

集合体系结构/分类

Collection单列集合

Map双列集合

ArrayList

为什么 new ArrayList<>（）时建议指定初始化容量值
如果设置的初始化值比较合适，就可以尽量避免数组的扩容（每次扩容需创建新数组并复制旧数据），避免了扩容就可以提高性能，也可以避免内存浪费。

为什么默认情况下的扩容机制是扩容为原数组的1.5倍
这是内存使用和性能之间的权衡，它是一个经验值，适合大多数场景。
如果扩容因子太大，可能使用不到这么多内存，造成内存浪费
如果扩容因子太小，可能需要频繁的进行扩容，造成性能的浪费损耗

ArrayList是线程的安全吗
如果 ArrayList 作为多线程的共享数据，比如单实例的成员变量、静态变量等
那么多线程并发修改ArrayList时，是会出现线程不安全的问题的，
例如同时add()导致元素覆盖、同时扩容数据丢失。
解决方案：
●使用 synchronized 代码块包裹操作
●使用 CopyOnWriteArrayList

CopyOnWriteArrayList 的实现原理

1首先 CopyOnWriteArrayList 内部也是用数组来实现的，在向 CopyOnWriteArrayList 添加元素时，会复制一个新的数组，写操作在新数组上进行，读操作在原数组上进行，读写分离的设计
2并且，写操作会加锁，防止出现并发写入时元素覆盖的问题
3写操作结束之后会把原数组指向新数组
优点：CopyOnWriteArrayList 允许在写操作时来读取数据（不加锁）大大提高了读的性能，因此适合读多写少的应用场景
缺点：CopyOnWriteArrayList 会比较占内存，且读到的数据可能不是实时最新的数据，因此不适合实时性要求很高的场景

HashMap

底层的数据结构
JDK1.7 实现是 数组+链表
JDK1.8 实现是 数组+链表+红黑树

添加元素流程
●调用map.put(键，值)时，用 (数组长度-1)&键的哈希值 计算出元素在数组中应存入的下标位置
●如果数组该位置为null，直接把元素添加进去
●如果数组该位置不为null，会遍历该桶位置下的链表或者红黑树，调用equals方法，比较键
●如果比较时，键是一致的，就会覆盖数组中原有的Entry对象的value值，然后返回
●如果遍历完时，没有一致的键，则把元素加入链表（JDK7:头插法，JDK8：尾插法）或红黑树
●JDK8以后，链表长度 ≥ 8 且 数组长度 ≥ 64：将链表转为红黑树。

扩容加载因子0.75
Hashmap 中的元素达到数组长度的0.75倍就会扩容为原来的两倍，为什么是0.75呢？
负载因子 0.75 是基于 泊松分布 的统计规律：当负载因子为 0.75 时，哈希冲突的概率显著降低。
0.75 是经过大量测试的折中值，
能在 减少哈希冲突 (保持O(1)的查询时间复杂度) 和 控制内存占用 之间达到最佳平衡。

扩容为数组长度的2倍
Hashmap 中的元素达到数组长度的0.75倍就会扩容为原来的两倍，为什么是2倍呢？
数组长度扩容为两倍即数组长度是2的次幂
因为在插入键值对元素时，有这样一个公式去确定元素存储的下标位置: （数组长度-1）& key的hash值，
而数组长度如果是2的次幂，那么公式的左半部分用二进制表示就是全1的，
此时公式变成 全1的二进制串&key的hash值，结果完全取决于key的hash值，
而这样可以降低Hash碰撞的概率，提高查询效率。

HashMap是线程的安全吗
如果 HashMap 作为多线程的共享数据，比如单实例的成员变量、静态变量等
那么多线程并发修改 HashMap 时，是会出现线程不安全的问题的
1在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
2在jdk1.8中，在多线程环境下，插入元素到空桶会发生数据覆盖的情况。
解决方案：
●使用 synchronized 代码块包裹操作
●使用 ConcurrentHashMap

ConcurrentHashMap的实现原理

JDK1.7 版本底层是 数组+链表 实现，使用分段锁来保证线程安全，它默认是将数组分成了16段，同时给每一段来配一把锁，因此最多只有16个线程去同时操作集合不同段。这样降低了并发操作时的锁竞争，提高并发性能。

JDK1.8 版本底层是数组+链表+红黑树，在并发处理方面去掉了分段锁的设计，而是使用 CAS + synchronized 来实现一种更加细粒度的锁。
从源码上看：添加元素时首先会判断数组是否为空，如果数组为空则使用 CAS 来初始化数组。如果数组不为空则判断元素要存入的桶位置上是否为空，如果桶位置上为空则使用 CAS 设置桶上的头节点；如果桶位置上不为空则使用 synchronize 加锁，锁住桶位置上的头节点，遍历桶中的数据，替换或新增节点到桶中，并且再判断链表是否需要转为红黑树

锁粒度细化：锁的粒度从段缩小到单个桶（链表/树的头节点），减少竞争概率。
JDK 1.8 的 ConcurrentHashMap 设计体现了 无锁化编程 和 锁粒度细化 的优化思想，是 Java 并发容器的经典实现。

为什么不全部用CAS或者全部用synchronized加锁实现线程安全，为什么不同操作用不同的方式去保证线程安全
我们可以看不同的方式中做的事情是什么：
●CAS保证线程安全时，它做的事情是初始化数组或者初始化头节点
●synchronized保证线程安全时，它做的事情是遍历桶下的结点，比较key是否相等，然后再插入元素或者替换元素，再判断链表是否转为红黑树
所以可以看出是后者耗时更长
●CAS无锁就适合做短时间的任务，因为如果任务执行时间长，就会有线程不断的自旋尝试，过度占用CPU
●synchronized就适合做长时间、高竞争的任务，加锁后，其余线程会进入休眠，不会占用CPU
●这是两者的特点不同，适用的场景不同。
这种设计体现了对 不同场景的精细化控制，是现代并发编程中“无锁优先，锁为补充”思想的典型实践。

迭代器

迭代器的实现原理

集合的遍历方式：迭代器遍历、增强for遍历、Lambda表达式遍历等等
增强for遍历的底层实现也是调用迭代器的方法遍历

迭代器的好处：它提供了一种统一的方式来遍历不同类型的集合（如 List、Set、Map 等），而无需暴露底层数据结构的实现细节。
迭代器出现的原因：如果没有迭代器，假设有10种不同数据结构的集合，那么我们就需要掌握10种集合遍历的方式，有了迭代器，只需要掌握一种迭代器遍历的方式即可。这里的思想核心也是一种设计模式：迭代器模式。

// 定义迭代器的基本行为  
public interface Iterator {  
    boolean hasNext();  // 检查是否还有下一个元素  
    E next();           // 获取下一个元素  
    void remove();      // 删除当前元素（可选操作）  
}

迭代器遍历的原理：
●ArrayList类里有内部类实现Iterator接口，利用数组索引实现hasNext()、next()、remove()方法
●LinkedList类里有内部类实现Iterator接口，利用双向链表指针实现hasNext()、next()、remove()方法
●HashMap......
●......
总结：
1统一接口：通过 Iterator 和 Iterable 接口标准化集合遍历方式。
2内部类实现：每个集合类 通过内部类 结合 自身的数据结构定制迭代逻辑（如数组索引、链表指针）。