本人本科毕业，21届毕业生，一年工作经验，根据简历，并根据所学知识复习准备面试。
记录日期：2021.12.28
大部分知识点只做大致介绍，具体内容根据推荐博文链接进行详细复习。
集合包
List
博文参考链接: 再也不担心问到Java集合了，一文讲透Java中的数据结构
1. ArrayList
本人博文链接: Java1.8源码阅读摘记-集合(1)-ArrayList
1.1 介绍
java.util.ArrayList，基于数组实现，使用连续的内存空间。
线程不安全。
构造参数上，无参时使用默认容量为10，有参为Integer时传入作为容量，有参为Collection时传入调用Arrays.copyOf()复制集合。
底层操作的对象是 Object[] elementData数组。
1.2 ArrayList关注点
1.2.1 时间复杂度
底层数组存/取元素效率非常的高(get/set)，时间复杂度是O(1)，而查找，插入和删除元素效率似乎不太高，时间复杂度为O(n)，频繁进行插入和删除会造成频繁的数组复制。
1.2.2 扩容
默认扩容到原数组的1.5倍。
方法调用链 : ensureCapacity -> ensureExplicitCapacity -> grow -> hugeCapacity
/** * ArrayList 的主要扩容方法 * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * 译文 : 增加容量以确保它至少可以容纳由最小容量参数指定的数量的元素。 * * @param minCapacity the desired minimum capacity */
private void grow(int minCapacity) {
int oldCapacity = elementData.length; // 原数组的长度
int newCapacity = oldCapacity + (oldCapacity >> 1); // 原数组的长度 + 原数组的长度 / 2 即原长度1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; // 1.5倍原长度扩容量 < 传入的扩容量时，使用传入的扩容量
if (newCapacity - MAX_ARRAY_SIZE > 0) // 要更新的扩容量长度大于最大长度，则扩容到 Integer 的最大长度
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); // 数组复制扩容并赋值
}
1.2.3. baseRemove方法
baseRemove方法：在714行，该方法有两个作用，一个是用于批量删除，另一个是用于求交集，通过布尔值complement来控制是否求交集，代码如下。
/** * 批量删除的方法 * @param c 传入的集合 * @param complement 补充字段 true时求交集，false求不包括c集合的所有元素 * @return */
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false; // 是否修改成功的标识符
try {
for (; r < size; r++) // 遍历elementData数组
if (c.contains(elementData[r]) == complement) // 如果在c集合中存在对应索引的元素
/** * complement为 true 时，说明有交集元素 * 则elementData对应索引的元素替换成共同存在的元素 * 遍历完成之后，在 < w 的位置都是他们的共同元素 */
elementData[w++] = elementData[r];
} finally {
// 遍历完成之后
// Preserve behavioral compatibility with AbstractCollection <=> 保持与 AbstractCollection 的行为兼容性
// even if c.contains() throws. <=> 即使 c.contains() 抛出
/** * 这里的 r 必定会自增到 r == size */
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
/** * 到此时 * 如果complement == true，此时的 r == size，< w 的都是共同元素，>= w 的都是多余的位置 * 如果complement == false，此时的 r == size， w == 0，此时可以进行删除所有元素 */
if (w != size) {
// w == size 时，说明数组相同， w ！= size时，清空 >= w 的所有元素被垃圾回收
// 清空 w 后面的所有元素，保证被gc回收
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w; // 添加修改次数
size = w; // 缩长，去除多余的容量
modified = true; // 更改为已修改标识
}
}
return modified;
}
1,2.4 序列化
数组被transient修饰的原因，在序列化中有说明，ArrayList的序列化，主要是过滤掉所有空位，减少多余的占用空间。
/** * Save the state of the <tt>ArrayList</tt> instance to a stream (that * is, serialize it). * 译文 : 将 ArrayList 实例的状态保存到一个流中（即，将它序列化）。 * * @serialData The length of the array backing the <tt>ArrayList</tt> * instance is emitted (int), followed by all of its elements * (each an <tt>Object</tt>) in the proper order. */
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
// 防止在序列化完成后被修改，抛出异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/** * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, * deserialize it). * 译文 : 从流中重构 ArrayList 实例（即反序列化） */
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
2. LinkedList
博文参考链接: LinkedList详解
1.1 介绍
java.util.LinkedList，基于链表实现的双向链表（实现了Deque<E>接口），使用不连续的内存空间。
线程不安全。
每一个节点封装成Node私有类，LinkedList中保存头节点、尾节点、size
1.2 LinkedList关注点
1.2.1 复杂度
在于头尾和已知节点的插入和删除时间复杂度都是o(1)。但是涉及到先确定位置再操作的情况，则时间复杂度会变为o(n)。
3.Vector(不做重点)
1.1 介绍
java.util.Vector，基于数组实现，使用连续的内存空间。
线程安全，线程安全的保证方式是通过在方法上添加synchronized关键字，效率低。
1.2 Vector关注点
1.2.1 线程安全
synchronized关键字修饰方法。
1.2.2 扩容
源码第257行，默认扩容2倍。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity); // 扩容2倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Set
1. HashSet
1.1 介绍
直接看代码吧，底层使用了HashMap的key不重复来实现，PRESENT用来作为value值。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
......
}
Map
需要了解各map的实现以及关注各个map的使用场景。
1. HashMap（重点）
线程不安全的<k,v> map，内容太多，直接看大佬的文章吧，以及很详细了，主要关注扩容的计算以及实现、各个变量的含义、红黑树链表的转换、1.7与1.8的区别等…
博客参考链接:
1.2 HashMap关注点
1.2.1 负载因子等参数含义
见博文
1.2.2 扩容
默认扩容2倍，通过位运算，具体参考囧辉的文章。
1.2.3 1.7与1.8的区别
1.7的bug需要注意。
1.2.4 红黑树与链表的转换
size达到64时才会进行红黑树和链表的转换，否则自动扩容。
链表转红黑树阈值为8
红黑树退化阈值为6
2. CocurrentMap（重点）
线程安全的<k,v> map，内容太多，直接看文章吧，一些博主已经整理的比较详细了，主要关注各个变量的意义、1.7与1.8的区别、并发扩容的实现等…
博客参考链接：
“J.U.C”之collections框架：ConcurrentHashMap扩容迁移等方法的源码分析
1.2 CocurrentMap关注点
1.2.1 sizeCtl变量
它用于数组初始化与扩容控制，另一个需要注意的Ctl变量有关的在线程池中，这里可以在面试中引申到线程池的Ctl变量。
1.2.2 counterCells变量
这是用来保存在并发大量CAS的情况下，一个变量会因为比较大的冲突下影响count增量计算的性能，通过数组分片记录大小，最后进行总和相加。
1.2.3 1.7和1.8的区别
1.7的Segment分段锁，1.8参照HashMap
1.2.4 并发扩容
见博文…
3. HashTable
线程安全的<k,v> map，具体内容见博文
博文参考链接：HashTable详解
1.1 介绍
java.util.HashTable，基于数组+链表，底层封装Entry<K,V>，里面next指针。
线程安全，通过方法上的synchronized关键字和同步代码块来实现。
1.2 HashTable关注点
1.2.1 线程安全
方法上的synchronized关键字和同步代码块。
1.2.2 hash冲突的四种解决方式（延申）
- 开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
- 链地址法
- 再哈希法
- 建立公共溢出区
博文参考链接：哈希详解以及实现（开放定址法和拉链法）
4. LinkedHashMap
博文参考链接：Map 综述（二）：彻头彻尾理解 LinkedHashMap
1.1 介绍
LinkedHashMap 是 HashMap 的子类，内部类 Entry 是 HashMap.Node 的子类，主要是在节点中添加了前后指针，同时在LinkedHashMap中也保存了头尾指针的引用。
1.2 LinkedHashMap关注点
1.2.1 标志位accessOrder
值为true时，表示按照访问顺序迭代；值为false时，表示按照插入顺序迭代。
1.2.2 重写迭代器
private abstract class LinkedHashIterator<T> implements Iterator<T> {
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
/** * The modCount value that the iterator believes that the backing * List should have. If this expectation is violated, the iterator * has detected concurrent modification. */
int expectedModCount = modCount;
public boolean hasNext() {
// 根据双向列表判断
return nextEntry != header;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
Entry<K,V> nextEntry() {
// 迭代输出双向链表各节点
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
}
// Key 迭代器，KeySet
private class KeyIterator extends LinkedHashIterator<K> {
public K next() {
return nextEntry().getKey(); }
}
// Value 迭代器，Values(Collection)
private class ValueIterator extends LinkedHashIterator<V> {
public V next() {
return nextEntry().value; }
}
// Entry 迭代器，EntrySet
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry(); }
}
5.TreeMap
博文参考链接：Java提高篇（二七）-----TreeMap
主要是由红黑树实现，不做具体介绍，详情见博文。
总结
我一直写文章但是坚持不下来。。。因为觉得其他博主的文章比我所认知的要详细，现在准备面试的话，大部分知识点会通过链接方式推荐觉得写的较好的文章去阅读复习。
视频以及大部分文章都是学习的入门以及补充，更深层次以及全面的知识点应通过优良博主的文章和编程书籍中学习。
京公网安备 11010502036488号