ArrayList
基本属性
private static final int DEFAULT_CAPACITY = 10; //初始化大小
private static final Object[] EMPTY_ELEMENTDATA = {}; //空数组
transient Object[] elementData; //存放元素的数组
private int size; //数组当前的元素个数
public ArrayList(int initialCapacity) { //指定长度的构造方法
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() { //不带参数，默认长度的构造函数
super();
this.elementData = EMPTY_ELEMENTDATA;
}
如图所示：
image.png
get方法
public E get(int index) {
if (index >= size) //检查是否越界
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index]; // 直接根据index返回对应位置的元素（底层elementData是个数组）
}
由于底层是数组实现的，判断index是否越界，然后直接返回对应索引位置的元素即可。
set方法
public E set(int index, E element) {
if (index >= size) //检查是否越界
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index]; // 根据index获取指定位置的元素
elementData[index] = element; // 用传入的element替换index位置的元素
return oldValue; // 返回index位置原来的元素
}
add方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 将modCount+1，并校验添加元素后是否需要扩容
elementData[size++] = e; // 在数组尾部添加元素，并将size+1
return true;
}
public void add(int index, E element) {
if (index > size || index < 0) // 校验索引是否越界
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // 将modCount+1，并校验添加元素后是否需要扩容
System.arraycopy(elementData, index, elementData, index + 1, // 将index位置及之后的所有元素向右移动一个位置（为要添加的元素腾出1个位置）
size - index);
elementData[index] = element; // index位置设置为element元素
size++; // 元素数量+1
}
remove方法
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) 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;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
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
}
clear方法
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
扩容
上文add方法在添加元素之前会先调用ensureCapacityInternal方法，主要是有两个目的：1.如果没初始化则进行初始化；2.校验添加元素后是否需要扩容。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //判断是否是null数组
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //设置为初始容量
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //修改次数+1
if (minCapacity - elementData.length > 0) //如果添加元素后大小超过容量，则扩容
grow(minCapacity); //扩容
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //数组允许的最大长度
private void grow(int minCapacity) { //数组扩容
// overflow-conscious code
int oldCapacity = elementData.length; //老的容量
int newCapacity = oldCapacity + (oldCapacity >> 1); //新容量 = 老容量 + 老容量 / 2
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果新容量比最大允许容量大
newCapacity = hugeCapacity(minCapacity); // 则调用hugeCapacity方法设置一个合适的容量
// 将原数组元素拷贝到一个容量为newCapacity的新数组（使用System.arraycopy），
// 并且将elementData设置为新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
面试遇见的问题
arraylist可以设置容量，arraylist不设置容量时，默认的容量是10。设置容量为10，和默认的有区别吗？
设置了容量之后，直接初始化了对应长度的空间。而默认的没有，在add之后会再初始化。无论是否设置长度都会进行扩容。
LinkedList
基本属性
transient int size = 0; //节点数量
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;
}
}
add方法
public boolean add(E e) {
linkLast(e); //调用linkLast方法，将节点添加到尾部
return true;
}
public void add(int index, E element) {
checkPositionIndex(index); //
if (index == size) //如果索引为size，即将element插入链表尾部
linkLast(element);
else // 否则，将element插入原index位置节点的前面，即：将element插入index位置，将原index位置节点移到index+1的位置
linkBefore(element, node(index));
}
linkLast方法
void linkLast(E e) { //将e放到尾节点
final Node<E> l = last; //l设置为尾节点
final Node<E> newNode = new Node<>(l, e, null); //新建一个节点，前节点为l，下个节点为null
last = newNode; //尾节点指向新建的node
if (l == null) //如果l为null，代表最初链表为null。则first为新建的node
first = newNode;
else //如果l不为null。则l的next设置为newNode
l.next = newNode;
size++;
modCount++;
}
linkBefore方法
void linkBefore(E e, Node<E> succ) { //将e插入succ节点之前
// assert succ != null;
final Node<E> pred = succ.prev; //pre为succ前一个节点
final Node<E> newNode = new Node<>(pred, e, succ); //使用e创建一个新的节点newNode，其中prev属性为pred节点，next属性为succ节点
succ.prev = newNode; //将succ的prev设置为newNode
if (pred == null) //如果pred为null，则首节点为newNode
first = newNode;
else //否则，pred的下一个节点是newNode
pred.next = newNode;
size++;
modCount++;
}
get方法
public E get(int index) {
checkElementIndex(index); //检查index是否越界
return node(index).item;
}
Node<E> node(int index) {
if (index < (size >> 1)) { //如果index小于size/2,从first往后开始查找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { //否则从last开始往前开始查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
set方法
public E set(int index, E element) { //替换index位置节点的值为element
checkElementIndex(index); //检查index是否越界
Node<E> x = node(index); //获取index的目标节点
E oldVal = x.item; //保存旧值
x.item = element; //当x的值修改为element
return oldVal; //返回之前的值
}
remove方法
public boolean remove(Object o) {
if (o == null) { //如果o为空, 则遍历链表寻找item属性为空的节点, 并调用unlink方法将该节点移除
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else { //如果o不为空, 则遍历链表寻找item属性跟o相同的节点, 并调用unlink方法将该节点移除
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
public E remove(int index) { // 移除index位置的节点
checkElementIndex(index); // 检查index是否越界
return unlink(node(index)); // 移除index位置的节点
}
public E remove() {
return removeFirst(); //移除第一个节点
}
clear方法
public void clear() { //清除链表的所有节点
for (Node<E> x = first; x != null; ) { //从头开始遍历所有节点，属性清空
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null; //头尾节点都设为null
size = 0;
modCount++;
}
unlink方法
E unlink(Node<E> x) { //移除链表上的x节点
// assert x != null;
final E element = x.item; //x节点的值
final Node<E> next = x.next; //下一个节点
final Node<E> prev = x.prev; //上一个节点
if (prev == null) { //如果上一个节点为null，则x为第一个节点
first = next; //将first移动到x.next节点即可
} else {
prev.next = next; //x不是首节点，则前节点的next为x的下一个节点，跳过x
x.prev = null; //x的前节点为null
}
if (next == null) { //如果next为null，则x为尾节点
last = prev; //尾节点指向x的前节点
} else {
next.prev = prev; //x不是尾节点，x的后节点的pre为x的前节点，跳过x
x.next = null; //x的后节点为null
}
x.item = null; //将x的值清空
size--;
modCount++;
return element;
}
image.png
ArrayList 和 LinkedList 的区别
- ArrayList 底层基于动态数组实现，LinkedList 底层基于链表实现。
- 对于按 index 索引数据（get/set方法）：ArrayList 通过 index 直接定位到数组对应位置的节点，而 LinkedList需要从头结点或尾节点开始遍历，直到寻找到目标节点，因此在效率上 ArrayList 优于 LinkedList。
- 对于随机插入和删除：ArrayList 需要移动目标节点后面的节点（使用System.arraycopy 方法移动节点），而 LinkedList 只需修改目标节点前后节点的 next 或 prev 属性即可，因此在效率上 LinkedList 优于 ArrayList。
- 对于顺序插入和删除：由于 ArrayList 不需要移动节点，因此在效率上比 LinkedList 更好。这也是为什么在实际使用中 ArrayList 更多，因为大部分情况下我们的使用都是顺序插入。
HashMap
总结
史上最详细的 JDK 1.8 HashMap 源码解析
面试阿里，HashMap 这一篇就够了
以上两篇文章已经说的很清楚了，做一下简单的整理。
- HashMap是基于Map接口实现的一种键值对<key,value>的存储结构，允许null值，同时非有序，非同步（非线程安全）。
- HashMap的底层实现是数组 + 链表 + 红黑树（JDK1.8增加了红黑树部分）。
- 它存储和查找数据时，是根据键key的hashCode的值计算出具体的存储位置。
- HashMap最多只允许一条记录的键key为null。
- HashMap增删改查等常规操作都有不错的执行效率，是 ArrayList 和 LinkedList 等数据结构的一种折中实现。
HashSet
基本属性
private transient HashMap<E,Object> map; //内部含有一个map
private static final Object PRESENT = new Object(); //虚拟对象，用于作为value放在map里面
总结
- HashSet 内部使用 HashMap 的 key 存储元素，以此来保证元素不重复;
- HashSet 是无序的，因为 HashMap 的 key 是无序的;
- HashSet 中允许有一个 null 元素，因为 HashMap 允许 key 为 null;
- HashSet 是非线程安全的;
- HashSet 是没有 get()方法的;
SparseArray
基本属性
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys; //key的数组
private Object[] mValues; //value的数组
private int mSize; //大小
构造函数
public SparseArray() {
this(10); //不带参数，初始化默认容量为10的集合
}
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
get函数
public E get(int key) {
return get(key, null); //找不到则返回为null
}
@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //数组查询
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound; //返回默认值参数
} else {
return (E) mValues[i]; //返回对应的value
}
}
ArrayMap
ArrayMap对象的数据储存格式如图所示：
mHashes是一个记录所有key的hashcode值组成的数组，是从小到大的排序方式；
mArray是一个记录着key-value键值对所组成的数组，是mHashes大小的2倍；
image.png
