！！！本文是基于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.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;
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
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，两者有什么不同吗？
transient Object[] elements;
transient int head;
transient int tail;
- 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();
}
- ArrayDeque是在jdk1.6才被引入的；LinkedList早就存在
- ArrayDeque 插入时存在扩容过程
- ArrayDeque性能更好
图片 from javaGuide
3. PriorityQueue有什么特点？⭐️⭐️⭐️
特点：元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队
PriorityQueue会出现在手撕算法应用当中 --》堆排序、第K大的数、带权图的遍历等
Set 接口
Map 接口
简述HashMap
- Map里面存放的是KV对，且Key值不可重复（这一点很重要，事关HashSet为啥不可重复，因为HashSet直接把值存到Key上了，Value则赋值为一个虚拟的Object对象）
- 这篇文章很详细，不过比较老了：
（1）HashMap查询、删除的时间复杂度⭐️⭐️⭐️⭐️
处理：直接插入元素或者直接返回未找到
时间复杂度：O（1）
处理：沿着链表遍历
时间复杂度：O（n）
时间复杂度O（longn）
（2）HashMap的底层实现⭐️⭐️⭐️⭐️⭐️
- 基于Map接口实现
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {...}
- 非线程安全
- HashMap的存储方法；解决哈希冲突
- JDK1.8之前，HashMap由 数组+链表 组成的，数组是HashMap的主题，链表则主要是为了解决哈希冲突而存在的（“拉链法”）；
- JDK1.8以后得HashMap在解决哈希冲突时有了较大的变化，
-- 当链表的长度大于等于阈值（默认为8）时，
-- 会判断当前数组的长度是否小于，
-- 如果小于，则先进行数组扩容，
-- 如果大于，则将链表转化为红黑树，以减少搜索时间
- HashMap默认初始化大小为16，之后每次扩充，容量变为原来的2倍。并且，HashMap总是使用2的幂作为哈希表的大小
1. HashMap和HashTable的区别
注 ： HashTable基本被淘汰了
HashMap 线程不安全
HashTable 线程安全（HashTable内的方法基本都被synchronized修饰）
因为线程安全问题，所以HashTable的效率会低一些
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;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
...
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
实现NavigableMap接口让TreeMap有了对集合内元素的搜索能力
- NavigableMap接口提供了丰富的方法来探索和操作键值对
实现SortedMap接口让TreeMap有了对集合中的元素根据键排序的能力。
- 默认是按照key的升序排序，不过我们也可以指定排序的比较器
4. CocurrentHashMap线程安全的具体实现方式/底层具体实现⭐️⭐️⭐️⭐️
分两个阶段——jdk1.8之前；1.8及以后
首先将数据分成一段一段（这个“端”就是Segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问
ConcurrentHashMap是由Segment数据结构和HashEntry数据结构组成
Segment的结构和1.8以前的HashMap类似
