2024年java面试准备--集合篇（一）https://developer.aliyun.com/article/1393077
Map的put方法的是怎么实现的?
通过调用key的hashCode方法获取哈希值找到存放的数组下标，通过遍历此位置的key与插入的key通过equals比较，如果已存在则替换
值，不存在则插入进来。
Map如何遍历
Map实现类调用entrySet方法获得一个Entry类型的Set，通过遍历这个Set集合获取Entry调用getKey或者getValue获取值
HashMap和HashTable有什么区别?其底层实现是什么?
区别：
- HashMap方法没有synchronized修饰，线程非安全，HashTable线程安全;
- HashMap允许key和value为null，而HashTable不允许
ConcurrentHashMap
可以通过ConcurrentHashMap 和 Hashtable来实现线程安全；Hashtable 是原始API类，通过synchronize同步修饰，效率低下；ConcurrentHashMap 通过分段锁实现，效率较比Hashtable要好；
ConcurrentHashMap的底层实现：
- ConcurrentHashMap是基于Segment分段实现的
- 每个Segment相对于一个小型的HashMap
- 扩容时，对待扩容Segment内部会进行扩容，不影响其他Segment对象
- 扩容时，先生成新的数组，然后转移元素到新数组中
- 扩容的判断也是每个Segment内部单独判断的，判断是否超过阈值
JDK1.7的 ConcurrentHashMap 底层采⽤ ReentrantLock和分段的数组+链表 实现；采用 分段锁（Sagment） 对整个桶数组进⾏了分割分段(Segment默认16个)，每⼀把锁只锁容器其中⼀部分数据，多线程访问容器⾥不同数据段的数据，就不会存在锁竞争，提⾼并发访问率。
元素查询
采用两次hash的方式进行元素查询。第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部
- ConcurrentHashMap不再基于Segment实现
- 当某个线程进行put时，如果发现ConcurrentHashMap正在进行扩容那么该线程一起进行扩容
- 如果某个线程put时，发现没有正在进行扩容，则将key-value添加到ConcurrentHashMap中， 然后判断是否超过阈值，超过了则进行扩容
- ConcurrentHashMap是支持多个线程同时扩容的。扩容前也是生成一个新数组，在转移元素时，会按照不同的线程进行分组
- 在转移元素时，先将原数组分组，将每组分给不同的线程来进行元素的转移，每个线程负责一组或多组的元素转移工作
JDK1.8的 ConcurrentHashMap 采⽤的数据结构跟HashMap1.8的结构⼀样，数组+链表/红⿊树；摒弃了Segment的概念，⽽是直接⽤ Node 数组+链表+红⿊树的数据结构来实现，通过并发控制 synchronized 和CAS（乐观锁）来操作保证线程的安全。每次插入数据时判断在当前数组下标是否是第一次插入，是就通过CAS方式插入，然后判断f.hash是否=-1，是的话就说明其他线程正在进行扩容，当前线程也会参与扩容；删除方法用了synchronized修饰，保证并发下移除元素安全
相关面试题
ConcurrentHashMap 是如何保证线程安全的？ ConcurrentHashMap 使用分段锁的方式来实现线程安全，它将一个大的哈希表分成多个小的哈希表（段），每个小的哈希表都有自己的锁。这样，不同的线程可以同时访问不同的小哈希表，从而避免了多个线程同时竞争同一个锁的情况，提高了并发性能。
ConcurrentHashMap 的扩容机制是怎样的？ ConcurrentHashMap 的扩容机制与 HashMap 类似，它会在哈希表的负载因子达到阈值时进行扩容。扩容的过程中，ConcurrentHashMap 会将原来的小哈希表逐一复制到新的大哈希表中，这个过程中仍然可以保证线程安全。扩容后，ConcurrentHashMap 会继续使用分段锁的方式来维护新的小哈希表。
ConcurrentHashMap 的 get() 方法是否需要加锁？ ConcurrentHashMap 的 get() 方法不需要加锁，因为它是线程安全的。在并发访问时，ConcurrentHashMap 使用了 volatile 和 CAS 等机制来保证数据的一致性和可见性，所以可以保证多个线程同时访问时不会出现数据竞争和不一致的情况。
ConcurrentHashMap 与 Hashtable 有什么区别？ ConcurrentHashMap 和 Hashtable 都是线程安全的哈希表，但是它们有很大的区别。ConcurrentHashMap 使用了分段锁的方式来提高并发性能，而 Hashtable 使用了一个全局锁来保证线程安全，所以并发性能比 ConcurrentHashMap 差很多。此外，ConcurrentHashMap 允许空键和空值，而 Hashtable 不允许。另外，ConcurrentHashMap 支持更多的操作，比如 ConcurrentHashMap 支持的批量操作和原子操作等，Hashtable 不支持。
红黑树
红黑树是一种特殊的二叉查找树。红黑树的每个结点上都有存储位表示结点的颜色，可以是红(Red)或黑(Black)。
红黑树的每个结点是黑色或者红色。当是不管怎么样他的根结点是黑色。每个叶子结点（叶子结点代表终结、结尾的节点）也是黑色 [注意：这里叶子结点，是指为空(NIL或NULL)的叶子结点！
如果一个结点是红色的，则它的子结点必须是黑色的。
每个结点到叶子结点NIL所经过的黑色结点的个数一样的。[确保没有一条路径会比其他路径长出俩倍，所以红黑树是相对接近平衡的二叉树的！]
红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的结点之后，红黑树的结构就发生了变化，可能不满足上面三条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转和变色，可以使这颗树重新成为红黑树。简单点说，旋转和变色的目的是让树保持红黑树的特性。
解决哈希冲突的四种方式
1. 开放定址法
当关键字key的哈希地址p =H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，若p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
即：Hi=（H（key）+di）% m （i=1，2，…，n）
开放定址法有下边三种方式：
线性探测再散列 顺序查看下一个单元，直到找出一个空单元或查遍全表 di=1，2，3，…，m-1 二次(平方)探测再散列 在表的左右进行跳跃式探测，直到找出一个空单元或查遍全表 di=1^2，-1^2，2^2，-2^2，…，k^2，-k^2 ( k<=m/2 ) 伪随机探测再散列 建立一个伪随机数发生器，并给一个随机数作为起点 di=伪随机数序列。具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。
优点
容易序列化 若可预知数据总数，可以创建完美哈希数列
缺点
占空间很大。（开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间） 删除节点很麻烦。不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
2. 再哈希法
提供多个哈希函数，如果第一个哈希函数计算出来的key的哈希值冲突了，则使用第二个哈希函数计算key的哈希值。
优点
- 不易产生聚集
缺点
- 增加了计算时间
3. 链地址法（hashmap使用此法）
对于相同的哈希值，使用链表进行连接
优点
处理冲突简单，无堆积现象。即非同义词决不会发生冲突，因此平均查找长度较短； 适合总数经常变化的情况。（因为拉链法中各链表上的结点空间是动态申请的） 占空间小。装填因子可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计 删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
缺点
查询时效率较低。（存储是动态的，查询时跳转需要更多的时间） 在key-value可以预知，以及没有后续增改操作时候，开放定址法性能优于链地址法。 不容易序列化
4. 建立公共溢出区
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
Java集合的快速失败机制 “fail-fast”？
是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。 例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时 候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这 个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。 原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集 合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next() 遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍 历；否则抛出异常，终止遍历。 解决办法： 在遍历过程中，所有涉及到改变modCount值的地方全部加上synchronized。 使用CopyOnWriteArrayList来替换ArrayList
序列化和反序列化
序列化的意思就是将对象的状态转化成字节流，以后可以通过这些值再生成相同状态的对象。对象序列化是对象持久化的一种实现方法，它是将对象的属性和方法转化为一种序列化的形式用于存储和传输。反序列化就是根据这些保存的信息重建对象的过程。
序列化： 将java对象转化为字节序列的过程。
反序列化： 将字节序列转化为java对象的过程。
优点：
a、实现了数据的持久化，通过序列化可以把数据永久地保存到硬盘上（通常存放在文件里）Redis的RDB
b、利用序列化实现远程通信，即在网络上传送对象的字节序列。 Google的protoBuf
反序列化失败的场景：
序列化ID：serialVersionUID不一致的时候，导致反序列化失败
队列
Queue接口与List和Set同一级别，都是继承Collection接口。LinkedList实现了Deque接口
非阻塞队列
非阻塞队列不能阻塞，多线程时，当队列满或者队列空时，只能使用队列 wait()，notify() 进行队列消息传送。
- LinkedList LinkedList 除了实现的 List 接口，也实现了 Deque 接口，可以当做双端队列来使用。
- PriorityQueue PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。该队列不允许使用 null 元素也不允许插入不可比较的对象
PriorityQueue 队列的头指排序规则最小那个元素。如果多个元素都是最小值则随机选一个。 PriorityQueue 是一个无界队列，但是初始的容量（实际是一个Object[]），随着不断向优先级队列添加元素，其容量会自动扩容，无需指定容量增加策略的细节。
- ConcurrentLinkedQueue ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列（CAS）。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大小，ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。同样此队列不允许使用null元素
阻塞队列
- 阻塞队列 ArrayBlockingQueue ：一个由数组支持的有界队列。 LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。 PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。 DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。 SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。
优先队列实现原理
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，这里主要使用PriorityQueue。
大顶堆和小顶堆
