Java集合（八股）

集合有两大接口Collection和Map，Collection中存单一元素，Map中存放kv对

（图片 from javaGuide）

Collection 接口

List 接口

ArrayList 简述

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{...}

ArrayList
继承了AbstractList类；
实现了List，RandomAccess，Cloneable，Serializable接口

• List：表明他是一个列表，支持增删查等操作、
• RandomAccess：表明List集合是支持快速随机访问。

注：
这只是一个标志接口，不是实现了它就能快速随机访问,
还要看类的底层逻辑
（如LinkedList就算继承了RandomAccess，也无法实现随机访问，因为它底层是链表，内存地址是不连续的 , 所以注定不可能）

• Cloneable：表明它具有拷贝能力，可以进行深拷贝和浅拷贝
• Serializable：表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输

1. ArrayList 和 LinkedList 区别？⭐️⭐️⭐️⭐️

首先说明 :
貌似绝大多数情况都是使用ArrayList , 就算是需要用到LinkedList的情况 ,也是可以用ArrayList替代掉的 , 且性能会更好

• 是否线程安全

都不是线程安全的，因为他俩都是不同步的（源码中没有任何“同步”的想法）

• 底层数据结构

• ArrayList 底层使用的是Object数组
• ListedList 底层使用的是双向链表

• 插入和删除是否受元素位置的影响

• ArrayList 采用数组存储，所以插入和删除的时间复杂度 受元素位置的影响。

比如：
执行 `add(E e)`方法时，ArrayList会默认在末尾追加元素，时间复杂度是O（1）
执行`add(int index, E element)`，ArrayList会让第i个及以后元素 全部移动一位，时间复杂度是O（n）

• ListedList 采用链表存储，插入、删除头尾元素不受影响，指定索引的插入删除操作受影响

执行`add(E e)` `addFirst(E e)``addLast(E e)``removeFirst()``removeLast()` 时间复杂度为O（1）
执行`add(int index, E element)` `remove(Object o)` `remove(int index)`时间复杂度为O（n），因为需要先移动到指定位置再插入和删除 

• 是否支持快速随机访问

ArrayList 支持 --> 实现了RandomAccess的接口
ListedList不支持

• 内存空间占用

• ArrayList 的空间浪费主要体现在 : list列表结尾会预留一定容量的空间
• LinkedList 的空间花费则体现在 : 每个元素都需要消耗比ArrayList更多的空间 (因为都要存放直接后继和直接前驱以及数据)

2. ArrayList 和 Array 的区别？⭐️⭐️⭐️

• Array

Array(数组) 就是一个可以自定义固定长度的数组 , 只能按照下标访问元素 , Array里面没有定义什么便于使用的方法
最常用的可能就是Array.length() 和 Array.sort()

• ArrayList
  ArrayList<Integer> list = new ArrayList();

ArrayList 内置了丰富的API操作方法 , 比如add() , remove()等
它会根据实际存储的元素动态扩容
允许使用泛型 来确保类型安全
只能存储对象

ArrayList 和 Vector 区别？⭐️⭐️

它们底层都是使用Object()存储

• Vector比较老了 , 但它是线程安全的(很少使用了)
• ArrayList , 适用于频繁的查找工作 ; 线程不安全

ArrayList 的扩容机制？⭐️⭐️⭐️

• ArrayList的默认长度是10，当然也可以自定义
• 当数组存储的元素 数量大于10的时候，就会触发扩容机制（也就是grow（）方法）
• grow（）方法 会创建一个新的数组，这个新数组的长度大约是原来的1.5倍（grow中的移位运算 算出来的）
• 然后通过Arrays.copyOf()方法将老数组赋值到新数组当中
• 以此类推

ArrayList的扩容机制的核心其实是grow()方法

/**
 * 要分配的最大数组大小
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * ArrayList扩容的核心方法。
 */
private void grow(int minCapacity) {
    // oldCapacity为旧容量，newCapacity为新容量
    int oldCapacity = elementData.length;
    // 将oldCapacity 右移一位，其效果相当于oldCapacity /2，
    // 我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // 然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
    // 如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Queue 接口

1. Queue和Deque的区别？⭐️⭐️⭐️

主要区别就是

Queue是单端队列
Deque是双端队列

本质上

• Queue : public interface Queue<E> extends Collection<E> {...}
• Deque : public interface Deque<E> extends Queue<E> {...}
• Deque继承了Queue接口，并且扩展了在队头和队尾增删元素的方法
• 事实上，Deque还提供有push（）和pop（）等其他方法，可用于模拟栈

2. ArrayDeque与LinkedList区别？⭐️⭐️⭐️

ArrayDeque和LinkedList都继承了Deque，两者有什么不同吗？

• ArrayDeque

1. ArrayDeque是基于可变数组和双指针实现的；LinkedList是基于链表实现

//ArrayDeque
transient Object[] elements;	//数组	
transient int head;	//头指针
transient int tail;	//尾指针

2. ArrayDeque 不能添加null值，原因如下（源码）；LinkedList可以

public void addFirst(E e) {
       if (e == null)
           throw new NullPointerException();
       elements[head = (head - 1) & (elements.length - 1)] >= e;
       if (head == tail)
      	   doubleCapacity();
}

3. ArrayDeque是在jdk1.6才被引入的；LinkedList早就存在
4. ArrayDeque 插入时存在扩容过程
5. ArrayDeque性能更好

图片 from javaGuide

3. PriorityQueue有什么特点？⭐️⭐️⭐️

特点：元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队

PriorityQueue会出现在手撕算法应用当中 --》堆排序、第K大的数、带权图的遍历等

Set 接口

Map 接口

简述HashMap

• Map里面存放的是KV对，且Key值不可重复（这一点很重要，事关HashSet为啥不可重复，因为HashSet直接把值存到Key上了，Value则赋值为一个虚拟的Object对象）
• 这篇文章很详细，不过比较老了：深入Java集合学习系列：HashMap的实现原理

（1）HashMap查询、删除的时间复杂度⭐️⭐️⭐️⭐️

• 如果没有元素

处理：直接插入元素或者直接返回未找到
时间复杂度：O（1）

• 如果有元素（链表）

处理：沿着链表遍历
时间复杂度：O（n）

• 红黑树

时间复杂度O（longn）

（2）HashMap的底层实现⭐️⭐️⭐️⭐️⭐️

1. 基于Map接口实现

public class HashMap<K,V> extends AbstractMap<K,V>
   implements Map<K,V>, Cloneable, Serializable {...}

2. 非线程安全
3. HashMap的存储方法；解决哈希冲突

- JDK1.8之前，HashMap由 数组+链表 组成的，数组是HashMap的主题，链表则主要是为了解决哈希冲突而存在的（“拉链法”）；
- JDK1.8以后得HashMap在解决哈希冲突时有了较大的变化，
-- 当链表的长度大于等于阈值（默认为8）时，
-- 会判断当前数组的长度是否小于64，
-- 如果小于64，则先进行数组扩容，
-- 如果大于64，则将链表转化为红黑树，以减少搜索时间

4. HashMap默认初始化大小为16，之后每次扩充，容量变为原来的2倍。并且，HashMap总是使用2的幂作为哈希表的大小

1. HashMap和HashTable的区别

注 ： HashTable基本被淘汰了

• 线程安全

HashMap 线程不安全
HashTable 线程安全（HashTable内的方法基本都被synchronized修饰）

• 效率

因为线程安全问题，所以HashTable的效率会低一些

• 对Null key和Null value的支持

HashMap可以存储null的key和value，但null作为键只能有一个，null作为值可以有多个
HashTable不允许有null键和null值

• 其他区别可以从上面写的HashMap来说（HashTable几乎不用了）

2. HashMap和HashSet区别⭐️⭐️⭐️⭐️

HashSet<Object> objects = new HashSet();
HashMap<Object, Object> objectObjectHashMap = new HashMap();

• 区别：

HashMap里面存的是KV对 ；HashSet里存的是对象
HashMap的Key不可重复，Value可重复；HashSet不可重复
HashSet的add方法调用了HashMap中的put方法

// HashSet部分源码

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }
    ...
    // 这里，调用了map的put方法，把e存到key上---》不能重复
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
}

可以看出，HashSet底层就是基于HashMap实现的（HashSet的源码非常少，因为除了clone() , writeObject() , readObject() 是HashSet自己不得不实现之外，其他方法都是直接调用HashMap中的方法）

3. HashMap和TreeMap的区别？⭐️⭐️⭐️⭐️

相比于HashMap来说，TreeMap主要多了对集合中元素根据键排序以及对于集合内元素的搜索的能力

//HashMap

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

//TreeMap

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

• TreeMap实现了NavigableMap接口

实现NavigableMap接口让TreeMap有了对集合内元素的搜索能力

• NavigableMap接口提供了丰富的方法来探索和操作键值对

• TreeMap实现了SortedMap接口

实现SortedMap接口让TreeMap有了对集合中的元素根据键排序的能力。

• 默认是按照key的升序排序，不过我们也可以指定排序的比较器

4. CocurrentHashMap线程安全的具体实现方式/底层具体实现⭐️⭐️⭐️⭐️

分两个阶段——jdk1.8之前；1.8及以后

• jdk1.8以前
  

首先将数据分成一段一段（这个“端”就是Segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问

ConcurrentHashMap是由Segment数据结构和HashEntry数据结构组成

Segment的结构和1.8以前的HashMap类似

• jdk1.8及以后