锁屏面试题百日百刷-java大厂八股文(day3)
为了有针对性的准备面试，锁屏面试题百日百刷开始每日从各处收集的面经中选择几道经典面试题分享并给出答案供参考，答案中会做与题目相关的扩展，并且可能会抛出一定问题供思考。这些题目我会标注具体的公司、招聘类型(校招、社招、实习)以及面试阶段。下面是今日面试题:
====ArrayList 和 LinkedList 实现原理和前者的扩容机制？[阿里云][校招][一面]
以下内容均是以jdk1.8来讲:
ArrayList实现原理:
Arraylist底层是用一个Object数组elementData来保存数据的:
transient Object[] elementData; // non-private to simplify nested class access
从创建一个ArrayList开始看，一般都是通过new即通过构造函数来创建一个ArrayList看源码:
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
很简单，无非就是无参构造只会创建一个空的数组，带初始化数组大小的构造器会创建一个知道容量的ArrayList,以及用另一个ArrayList初始化新的ArrayList的构造函数。
再看ArrayList的操作:
1)添加:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
这里，modCount是我们每次对ArrayList做改变大小的时候会做一次自增操作的变量，记录下修改次数。核心的常问的一个方法就是这个grow()方法，这是当ArrayList中元素的数组(上面讲到的存储数据的)elementData容量不够时做的扩容操作。这里我们以用空参构造器创建ArrayList时，第一次向ArrayList添加元素时会做一次扩容操作来讲:
判断容量是否足够的就是这么一句:if (minCapacity – elementData.length > 0)
在grow中，核心的一段就是int newCapacity = oldCapacity + (oldCapacity >> 1);新的容量是旧的容量的1.5倍(oldCapacity >> 1实际上是一次oldCapacity除2操作)
注意这里扩容触发条件是在使用无参构造器第一次添加元素，以及添加元素时，判断发现数组长度不够时。
2) 删除：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
看代码很简单，就是做一次数组复制，移动要删除的某一位置元素的后面的元素，并且将旧数组置为null做垃圾回收。指定remove(Object O)这个方法也是先找对应元素的下标，然后做与上面代码差不多的操作。有兴趣的可以看下源码。
查询就没啥好讲的了，底层是数组存储，查询很容易做到。可自行看源码。
LinkedList实现原理:
LinkedList存储是通过双向链表实现的:
transient Node<E> first;
transient Node<E> last;
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(Collection<? extends E> c)也是着重体现在添加元素的操作，所以直接讲它的一些操作，这里需要大家能够懂链表的增删改查的操作，因为LinkedList的这些操作就是根据这些来的。希望大家能够找一下资料了解下，这里篇幅有限，不作讲解。
1) 添加：
头部添加:
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
看下上面关于LinkedList一开始讲的，可以看到LinkedList成员变量就有保存first和last，这里从头部插入和从尾部插入基本上操作一致，只是保存位置不同，看代码很容易看懂，就是对链表的操作，至于add()方法是在尾部插入新的元素。
2) 删除
removeFirst()和removeLast()以及remove()(remove和removeFirst()操作一致)，都是简单去链表表头或表尾的操作，可以自己看源码，熟悉链表操作的同学很容易就能看懂，不作赘述。说一说remove(int index)：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
Node<E> node(int index) {
// assert isElementIndex(index);
// 这里是做了一个加速查找的操作
// 获取index处的节点。
// 若index < 双向链表长度的1/2,则从前先后查找;
// 否则，从后向前查找。
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
这里是先根据index找到LinkedList中存储的节点，见上图node()方法，然后开始删除元素操作，见unlink()方法，熟悉链表的删除操作，很容易能看懂，判断删除的元素是否是表头后表尾，是的话简单的赋值一下即可，不是的话做相应的删除操作。Remove(Object o)这个方法也是先找到这个list中是否有这个元素，先通过查找，再调用unlink()方法删除。
3）查找
LinkedList查找操作在上面的删除操作中，先查找在做删除的步骤中已经讲过(上面的node方法)，请自行对照源码查看查找操作。