首先问的是ArrayList和LinkedList的区别。
先看ArrayList的相关源码：
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData;
可以看出ArrayList底层是实现了一个Object数组，并且初始容量为10
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);
}
可以看出ArrayList动态扩容是原本的1.5倍，而且扩容是把原本的数据复制到新的数组，这样很耗费时间，所以一般在建arraylist的时候，可以把数据长度定义为预想的1.5倍，这样就可以免去扩容导致的复制问题
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
在看ArrayList的插入和删除，都需要移动后面的元素，比较耗时
再看LinkedList的代码
public boolean add(E e) {
linkLast(e);
return true;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
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;
}
可以看到LinkedList的插入和删除其实也是需要通过for循环查找到具体位置的，所以并不一定比ArrayList的删除插入快。
再看HashMap的源码
这题答得比较烂，其实是了解的，我们先来看源码
DEFAULT_INITIAL_CAPACITY =16 默认容量为
MAXIMUM_CAPACITY =1 << 30 最大容量为
DEFAULT_LOAD_FACTOR = 0.75f 默认负载因子
TREEIFY_THRESHOLD=8 链表转换红黑树的阀值
UNTREEIFY_THRESHOLD=6 红黑树转换链表的阀值
MIN_TREEIFY_CAPACITY=64 桶中bin最小hash容量，如果大于这个值会进行
总结：
- 一个是数组实现，一个是链表实现。
- ArrayList可以快速查询，链表需要遍历。ArrayList插入删除需要移动元素，链表只需要改变节点指向就行
- ArrayList内存不足时需要动态扩容，每次是原来的1.5倍，LinkedList不需要动态扩容
- 这一题回答的时候，动态扩容以及插入删除的效率没有说出来
