JAVA面试必问之Collection要点
JAVA集合之Collection
JAVA提供的数组是用来存储固定大小的同类型元素。其具有以下两个缺点：
1.数组一旦初始化后，长度就确定了，无法进行数组的动态扩展；
2.数组存储元素是确定的，且一个数组中只能存储同一类型的。
为了改进以上缺点，JAVA提供了一个集合框架供我们使用，其中最主要的接口为Collection和Map，集合框架图如下：
集合和数组的区别
| 属性 | 数组 | 集合 |
|---|---|---|
| 长度 | 固定 | 动态扩展 |
| 存储内容 | 同一类型元素 | 不同类型元素（但一般不会这样做） |
| 存储元素类型 | 基本类型和引用类型 | 引用类型 |
Collection常用方法
| 方法名 | 说明 |
|---|---|
| boolean add(E e) | 向集合添加元素e，若指定集合元素改变了则返回true |
| boolean addAll(Collection<? extends E> c) | 把集合C中的元素全部添加到集合中，若指定集合元素改变返回true（相当于集合取并） |
| void clear() | 清空所有集合元素 |
| boolean contains(Object o) | 判断指定集合是否包含对象o |
| boolean containsAll(Collection<?> c) | 判断指定集合是否包含集合c的所有元素 |
| boolean isEmpty() | 判断指定集合的元素size是否为0 |
| boolean remove(Object o) | 删除集合中的元素对象o,若集合有多个o元素，则只会删除第一个元素 |
| boolean removeAll(Collection<?> c） | 删除指定集合包含集合c的元素（集合取补） |
| boolean retainAll(Collection<?> c) | 从指定集合中保留包含集合c的元素,其他元素则删除（集合取交） |
| int size() | 集合的元素个数 |
| T[] toArray(T[] a) | 将集合转换为T类型的数组 |
| Interator it = collection.iterator() | 获取集合迭代器 |
Collection中的List
Collection中的List常用的实现类有两个：ArrayList和LinkedList。其两者区别如下：
| 属性 | ArrayList | LinkedList |
|---|---|---|
| 扩容方式 | 1.5倍扩容 | 直接增加 |
| 默认空实例初始化方式 | 懒惰（即第一次添加元素之后才初始化数组，之前任为空数组） | 不同类型元素（但一般不会这样做） |
| 初始容量 | 10 | 引用类型 |
| 支持随机访问 | 是 | 否 |
| 随机访问的时间复杂度 | O(1) | O(n) |
| 增删元素的时间复杂度 | O(n) | O(1) |
| 内存要求 | 必须连续 | 不连续 |
ArrayList源码部分分析
ArrayList源码比较长，在这里不全部展示，只挑选一些经典方法进行分析。
从源码中可以看出ArrayList 实现了RandomAccess 接口， RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
ArrayList 实现了Cloneable 接口，即覆盖了函数 clone()，能被克隆。
ArrayList 实现java.io.Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输。
ArrayList 中的操作不是线程安全的！所以，建议在单线程中才使用 ArrayList，而在多线程中可以选择 Vector 或者 CopyOnWriteArrayList。
1.ArrayList初始化
// 默认初始容量大小为10 private static final int DEFAULT_CAPACITY = 10; //默认空实例 private static final Object[] EMPTY_ELEMENTDATA = {}; //用于默认大小空实例的共享空数组实例。 //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //保存ArrayList数据的数组，即ArrayList底层实际上还是一个数组 transient Object[] elementData; //ArrayList 所包含的元素个数 private int size; //带初始容量参数的构造函数。（用户自己指定容量） public ArrayList(int initialCapacity) { if (initialCapacity > 0) { //创建initialCapacity大小的数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //创建空数组 this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } //默认构造函数，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }2.扩容机制
ArrayList的扩容机制提高了性能，如果每次只扩充一个，那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制使用每次扩容1.5倍大小的方式避免了这种情况。
//扩容函数，确保ArrayList能容纳元素，其中minCapacity 为所需的最小容量 public void ensureCapacity(int minCapacity) { //若当前ArrayList还没有初始化时，minExpand=0 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; //若所需大于当前的容量，则扩容 if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } //得到最小扩容量 private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 获取默认的容量和传入参数的较大值 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } //判断是否需要扩容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果说minCapacity也就是所需的最小容量大于保存ArrayList数据的数组的长度的话，就需要调用grow(minCapacity)方法扩容。 //这个minCapacity到底为多少呢？举个例子在添加元素(add)方法中这个minCapacity的大小就为现在数组的长度加1 if (minCapacity - elementData.length > 0) //调用grow方法进行扩容，调用此方法代表已经开始扩容了 grow(minCapacity); } //要分配的最大数组大小 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; //再检查新容量是否超出了ArrayList所定义的最大容量， //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE， //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); } //比较minCapacity和 MAX_ARRAY_SIZE private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }ArrayList中的数组拷贝方法：System.arraycopy()和Arrays.copyof()
在ArrayList的add(int index, E element)方法中使用到了 arraycopy() 方法让数组自己复制自己实现让index开始之后的所有成员后移一个位置:
//在此列表中的指定位置插入指定的元素。
public void add(int index, E element) {
//先调用 rangeCheckForAdd 对index进行界限检查
rangeCheckForAdd(index);
//然后调用 ensureCapacityInternal 方法保证capacity足够大
ensureCapacityInternal(size + 1);
//arraycopy()方法实现数组自己复制自己:从最后开始将成员后移一个位置，直到将element插入index位置；最后size加1
//elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中的起始位置； size - index：要复制的数组元素的数量；
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
} 在ArrayList的toArray()方法中用到了 copyOf() 方法：
//以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。
//该方法必须分配一个新的数组
public Object[] toArray() {
//elementData：要复制的数组；size：要复制的长度
return Arrays.copyOf(elementData, size);
} 以上二者的联系：看两者源代码可以发现copyOf()内部调用了System.arraycopy()方法
以上二者的区别：arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位；copyOf()是系统自动在内部新建一个数组，并返回该数组。
LinkedList源码部分分析
LinkedList是一个实现了List接口和Deque接口的双端链表。 LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有队列的特性; LinkedList不是线程安全的。
LinkedList的内部节点Node
LinkedList会将存入的对象包装为一个节点Node，并记录其前驱节点和后继节点，因此LinkedList是一个双端队列，其插入和删除都可以指明方向。
private static class Node<E> {
E item;//节点值
Node<E> next;//后继节点
Node<E> prev;//前驱节点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
} LinkedList的增加元素的方法
- add（E e）：将元素添加到链表尾部
public boolean add(E e) {
linkLast(e);//这里就只调用了这一个方法
return true;
}
//linkLast方法：链接使e作为最后一个元素。
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;//新建节点
if (l == null)
first = newNode;
else
l.next = newNode;//指向后继元素也就是指向下一个元素
size++;
modCount++;
} - addFirst(E e)： 将元素添加到链表头部
public void addFirst(E e) {
linkFirst(e);
}
//linkFirst方法：链接使e作为第一个元素。
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);//新建节点，以头节点为后继节点
first = newNode;
//如果链表为空，last节点也指向该节点
if (f == null)
last = newNode;
//否则，将头节点的前驱指针指向新节点，也就是指向前一个元素
else
f.prev = newNode;
size++;
modCount++;
} addLast(E e)： 将元素添加到链表尾部，与 add(E e) 方法一样
public void addLast(E e) { linkLast(e); }add(int index, E e):在指定位置添加元素
public void add(int index, E element) { checkPositionIndex(index); //检查索引是否处于[0-size]之间 if (index == size)//添加在链表尾部 linkLast(element); else//添加在链表中间 linkBefore(element, node(index)); } //返回下标为index的node节点 Node<E> node(int index) { //使用对半查找，如果在index前半部分，则从头部使用next开始找 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //如果在index后半部分，则从尾部prev开始找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
LinkedList的获取元素的方法
根据索引获取元素
- get(int index)： 根据指定索引返回数据
public E get(int index) { //检查index范围是否在size之内 checkElementIndex(index); //调用Node(index)去找到index对应的node然后返回它的值(node源码见上) return node(index).item; }获取头节点
- getFirst():获取链表头节点，若链表为空抛出异常；
- element():本质就是getFirst(),性质同上。
- peekFirst():获取链表头节点，若链表为空返回null；
- peek():本质就是peekFirst()，性质同上；
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E element() {
return getFirst();
}
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
} 获取尾节点
- getLast()：获取尾节点，在链表为空时，会抛出NoSuchElementException；
- peekLast() : 获取尾节点，在链表为空时，返回null;
public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; }根据对象获取对应索引
- int indexOf(Object o)： 从头遍历找
public int indexOf(Object o) { int index = 0; if (o == null) { //从头遍历 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { //从头遍历 for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } - int lastIndexOf(Object o)： 从尾遍历找
public int lastIndexOf(Object o) { int index = size; if (o == null) { //从尾遍历 for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { //从尾遍历 for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }LinkedList检查是否包含某对象的方法
- contains(Object o)： 检查对象o是否存在于链表中
public boolean contains(Object o) { return indexOf(o) != -1; }LinkedList删除元素
- remove() ,removeFirst(),pop(): 删除头节点，本质都是removeFirst()，若为空链表则抛出异常；
- removeLast(),pollLast(): 删除尾节点，区别在于在空链表时前者抛出异常，后者只返回null；
- remove(Object o): 删除指定元素，且一次只会删除一个匹配的对象，如果删除了匹配对象，返回true，否则false。
- remove(int index)：删除指定位置的元素
ArrayList和LinkedList的线性安全
ArrayList和LinkedList都不是线性安全，如果想要使用线性安全的集合，可以调用静态类Collections类中的synchronizedList方法，在里面传入相应的集合。例子如下：
List list=Collections.synchronizedList(new LinkedList(...));
最后是广告时间~
我们阿里云最核心部门弹性计算21年暑假实习招聘还在火热进行中。我可继续帮助大家内推简历。收到同学们的简历后，会进行评估，合适的话后续会由面试官进行进一步的交流！所以欢迎大家踊跃投递，越早投递越先人一步抓住机会！
部门简介：
这里是 阿里云最核心的ECS团队，这里能接触到众多大佬，与王坚院士做同事！在这里你将体验极致性能与架构的复杂挑战；在这里你将体验超大规模集群调度及管理。暑期实习可能是你最容易进入阿里的渠道！ 同学们也可提前了解下 阿里云 ，阿里云 官方网站： https://www.aliyun.com/ ，看看弹性计算的位置就知道我们的部门有多么的核心！而且在实习期间每位实习生都会分配师兄一对一负责，帮助实习生更快更好的成长，能够参与甚至负责具有挑战性的实习项目！
招聘对象及要求：
毕业于985/211或者海外知名高校，计算机或相关专业，2021年11月-2022年10月毕业，具备良好的计算机专业基础，包括操作系统与计算机网络，熟悉常见的数据结构和算法；熟悉至少一种编程语言，包括但不限于Java、C++、JavaScript、Golang、Python、Node.js、Php、C#、Rust、Typescript或者操作系统开发。
招聘岗位：
研发工程师java
研发工程师C++
Web前端开发工程师
算法工程师-机器学习
算法工程师
基础平台研发工程师
数据挖掘分析
实习地点：北京/杭州 任选
投递邮箱：kate_yan4@163.com (我是2020年的转正的实习生，因为离职后公司邮箱冻结了，只能先用个人邮箱啦😂)
注：邮件名称或备注请按“职位+学校+姓名+手机号+实习地点”格式，因工作时间，每天在饭后及早晚集中处理大家邮件， 有任何问题可以直接留言或私聊我。投递成功后也在请帖子下面回复“已投递”
#内推##实习##阿里巴巴##春招##字节跳动##腾讯##面经#
投递旷视等公司10个岗位 >
