Array源码分析
首先分析new ArrayList<>()
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
public ArrayList() {
// 初始化数组的容量为{}
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
new ArrayList()时，会创建一个Object[] elementData = {} 的数组。由此可以知道list底层是通过Object[]数量来存储数量的
分析通过无参构造函数初始化ArrayList时第一次调用add()方法
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // 存储list数据的数组
private int size; //当前arrayList的size(集合容量)
private static final int DEFAULT_CAPACITY = 10;
public boolean add(E e) {
// 判断容器是否够大，如果超出容器大小需要进行扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算容器需要多大的容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果 elementData 数组的容器为{}
// 如果通过new ArrayList<>()无参构造函数初始化时，第一次调用add()方法时会进行扩容，将容量变从{}为10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// DEFAULT_CAPACITY=10 大于 minCapacity = 1，所以会取DEFAULT_CAPACITY
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// 这个字段用于判断是否执行快速失败原则(fail-fast)
//相当于乐观锁的版本号，因为arraylist是线程不安全的，
//当在进行Iterator迭代遍历时，首先获取modCount的值保存到本地变量中，当遍历时会判断本地变量和modCount(全局变量)是否相等，
//如果不相等(有其他线程改变了集合的结构，会修改modCount的值)，就会抛出ConcurrentModificationException异常
modCount++;
// overflow-conscious code
// 这里传进来的minCapacity是当前add元素时需要的最小容器(size+1)
// 当需要的最小容器大于当前容器的容量时，就需要进行扩容
if (minCapacity - elementData.length > 0)
// 对容器进行扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // 当前容量大小
// 需要扩容到多大 >>1表示/2
//相当于oldCapacity + (oldCapacity / 2)，也就是需要扩展到原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1); 0+0/2=0
// 因为上面方法调用时将minCapacity变为10传过来的
// 0-10<0，所以会进入下面的第一个if
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; // 10
// int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 最大容量可设置为Integer.MAX_VALUE (2的32次方)
newCapacity = hugeCapacity(minCapacity);
// 这方法会进行扩容，会将原数据copy到一个容器大小为newCapacity新的list中，然后返回
elementData = Arrays.copyOf(elementData, newCapacity);
}
当通过无参构造函数初始化ArrayList时，在第一次add时会将list的容量扩容到10，之后每次扩容都是原来的1.5倍，比如当add到第11个元素时，会再次进行扩容，将容量扩容到15
分析get()方法
public E get(int index) {
// 判断坐标是否越界
rangeCheck(index);
// 获取元素并返回
return elementData(index);
}
private void rangeCheck(int index) {
// size为list中元素的数量
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 获取Object数组中index坐标的值，强转成E类型并返回
E elementData(int index) {
return (E) elementData[index];
}
get方法很简单，先判断坐标是否越界，然后获取elementData数组中元素并返回
这里要提一下size与elementData.length的区别
就相当于new arrayList(10) 与Object[] o = new Object[10]的区别
在没进对arrayList进行add添加元素的时候，不管容器大小是多少 size都为0的，所以就算new arrayList(10)，在get(0)时都会报坐标越界。
而new Object[10]在没有添加元素是，o[0]获取到的是null
分析remove方法
public E remove(int index) {
// 判断坐标是否越界
rangeCheck(index);
modCount++;
// 获取需要删除的元素，删除成功后会方法返回
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 对数组进行元素并对坐标进行重新排序，这个方法是jvm底层的native方法
// 需要5个参数,
1. src:源数组；
2.srcPos:源数组要复制的起始位置；
3.dest:目标数组；
4.destPos:目标数组放置的起始位置；
5.length:复制的长度。
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 数组元素的坐标重新排序后，需要对最后一个坐标设置为null，因为删除了一个元素，它后面的元素就会向前移动一位
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
ArrayList总结
1.list集合底层是通过Object[]数组来存储的
2.new ArrayList()时，初始化的容器是没有容量大小(相当于0)的，在第一次add时会将容器扩容到10，之后每次扩容数为原来的1.5倍。因为new ArrayList()初始化的容器是没有容量的，在第一次add时会进行扩容，而扩容会降低效率，所以阿里巴巴规范也有提到，一般在使用arrayList时，都会估算需要容量，初始化容器的大小，比如new ArrayList(10)，这样在add时会减少扩容的次数
3.在删除元素时，会将元素删除，并将这个元素后面的元素向前移动，然后置null最后一个位置
比如第一个图为原数组，删除 C后，会将D和E向前移动，然后将最后一个位置置为null
image.png
4.arrayList是线程不安全的，在Iterator迭代遍历时，如果modCount被修改了，会执行快速失败原则(fail-fast)，抛出ConcurrentModificationException异常
5.如果想解决4问题，可以使用Vector集合或者Collections.synchronizedList(new ArrayList<>());或者CopyOnWriteArrayList集合类
6.查询速度快，查询时间复杂度小(O(1)，直接通过index到数组上找)，空间复杂度大
LinkedList源码分析
transient int size = 0; // size表示当前集合元素的大小，add会size++ remove会size--
transient Node<E> first; // 当前集合的第一个节点
transient Node<E> last; // 当前集合的最后一个节点
public LinkedList() {
}
new LinkedList只是初始化一个空的list，LinkedList是通过链表结构的node(节点)来存储的，首先看看Node<E>的结构
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中增加A B C三个元素，它的存储结构如下图，每个元素对会封装成Node节点对象来存储
LinkedList的add方法
transient Node<E> first; // 当前集合的第一个节点
transient Node<E> last; // 当前集合的最后一个节点
public boolean add(E e) {
// 在链表的最后增加元素
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last; // 获取当前集合的最后一个节点
final Node<E> newNode = new Node<>(l, e, null); // 封装当前需要添加的节点
last = newNode; // 将需要添加的节点设置为当前链表的最后一个节点
if (l == null) // 如果last为null(表示当前元素没有node对象)
first = newNode; 第一个node设置为当前增加的节点对象
else
l.next = newNode; // 否则在最后一个节点的下一个位置加上当前需要增加的节点对象
size++;
modCount++;
}
调用add时会在链表的最后增加一个节点来存储这个元素,这里提一点linkedList.add(null);在增加是会添加一个Node对象来存储，这个null值是赋值在node.item=null，不要理解成node=null
LinkedList的get方法
public E get(int index) {
// 检查坐标是否越界
checkElementIndex(index);
// 获取这个坐标的元素并返回
return node(index).item;
}
Node<E> node(int index) {
// 通过折半查找(二分查找)法来查询node节点所在的位置
// 如果index小于size的一半，就从第一个元素开始找，不断向下一个元素找
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;
}
}
LinkedList不像数组那样每个元素都有一个索引标识，只能从第一个node对象或者最后一个node对象遍历index次(first.next或last.next执行index次)找到这个元素，比如链表长度为100 需要查询index 60的元素 如果从first节点开始找，就需要循环遍历60次。linkedList底层通过折半查找(二分查找)法，60大于50(一半)，从100开始循环遍历40次就能定位到，提高查询效率
LinkedList的remove方法
public E remove(int index) {
// 检查坐标是否越界
checkElementIndex(index);
// 先查询出node节点，然后删除这个节点
return unlink(node(index));
}
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;
}
LinkedList删除元素，其实就是将这个元素的node节点对象的prev(上一下)node节点对象和next(下一个)节点对象的所关联的prev和node的指向修改，然后将当前node节点的属性都置空(便于GC回收)
LinkedList总结
1.LinkedList底层是通过双向链表结构node节点对象来存储的，node对象有三个属性item(当前元素值)，prev(上一个node对象)，next(下一个node对象)。
2.linkedList.add(null)，存储的是node.item=null，而不是node=null。
3.增加和删除的速度快，空间复杂度小(不需要记录节点的位置)，查询时间复杂度大(查询相对慢 O(n)，比如有100个元素，找第30个。就需要把链表的node从第一个开始node.next循环30次才能找出来)
set集合
public HashSet() {
map = new HashMap<>();
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
set集合底层用的是map，HashSet用的是HashMap，TreeSet用的是TreeMap
set.add时会把元素值存到map的key中，value为new Object()对象
因为map中的key是唯一的，所以set集合可以保存元素的唯一性
