Java集合(Collection)类是我们在工作中运用最多的、最频繁的类。并且集合可以动态扩容。方便开发需求。
集合类通常存在于java.util包中，主要由Collection和Map两个体系构成。
- Collection主要有三个子接口，分别为List(列表)、Set(集)、Queue(队列)。其中，List、Queue中的元素有序可重复，而Set中的元素无序不可重复；
- List中主要有ArrayList、LinkedList两个实现类；Set中则是有HashSet(底层HashMap)，treeSet(底层TreeMap)实现类；
- Map中都是以key-value的形式存在，其中key必须唯一，主要有HashMap、HashTable(线程安全)、TreeMap(红黑树)三个实现类。
- set的底层是维护了map，只用了map的key,这便是为什么元素无序，并且不能重复，另一面也反应出了，map允许value的为null;反而List、Queue的底层是数组或者链表，可以允许元素的有序可重复。
有兴趣可以看一下LinkedList的源码，他实现了Queue接口，同时也实现了List，具有两者的特性。
A collection represents a group of objects
collection类型用来表示表示一组对象。
所以map不符合Collection类的要求，map没有继承Collection接口，而是重新定义了map接口，符合接口隔离原则。
List
在List集合中，我们常用到ArrayList和LinkedList这两个类。
其中，ArrayList底层通过数组实现，随着元素的增加而动态扩容。而LinkedList底层通过链表来实现，随着元素的增加不断向链表的后端增加节点。
这里可以看出，当数据量比较大的时候，ArrayList读取速度高于LinkedList，而写入的数据低于LinkedList的。
所以我们今天便要借鉴源码实现一个ArrayList。
List接口
可以看出源码继承了Collection接口
public interface List<E> extends Collection<E> {
}
我们先定义一个MyList类，将源码的方法提取放到类中
public interface MyList<E> {
boolean add(E e);
void add(int index,E e);
int size();
boolean isEmpty();
boolean contains(E e);
void clear();
E remove(int index);
//这个方法是list添加
E get(int index);
}
其中 void add(int index,E e); E get(int index);属于list添加的方法
List实现类
定义一个MyArrayList类实现MyList接口，并且实现接口的方法
public class MyArrayList<E> implements MyList<E> {
}
变量
在实现方法之前，我们先定义几个常量和构造方法
transient Object[] elementData;
由于ArrayList底层是数组，先定义数组变量
private int size;
//数组的默认大小
private static final int DEFAULT_CAPACITY = 10;
//数组的最多扩容大，一般达不到，会直接内存溢出
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
以上三个变量，用于list的容量上，定义了数组的大小和扩容的上限
private static final Object[] EMPTY_ELEMENTDATA = {};
定义默认的空对象
构造方法
public MyArrayList(int initialCapacity) {
if(initialCapacity<0){
throw new IllegalArgumentException("初始化大小异常"+initialCapacity);
}
elementData=new Object[initialCapacity];
}
public MyArrayList() {
this.elementData = new Object[DEFAULT_CAPACITY];
}
从这里的源码可以看出，ArrayList默认数组大小为10，也可以自定义数组的大小，要求数组不能小于，不然会抛出初始化的异常，不过，如果能确定list的长度时，还是建议最好定义ArrayList的大小，避免数组的频繁扩容
实现方法
add
不指定数组的下标
@Override
public boolean add(Object e) {
//扩容数组
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
指定数组下标
@Override
public void add(int index, Object element) {
//校验下标是否正常
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
//调用系统的方法进行复制，这里将index的位置后移，不过，存在浅拷贝的问题
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
可以看出无论那种方法的添加元素，list都会先进行扩容ensureCapacityInternal然后再插入，这里就会出现一个问题了？会不会频繁扩容导致资源的消耗？
答案是不会 ，可以看一下源码中ensureCapacityInternal的实现，可以看到源码中一共4个方法完成了数组的扩容。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
- 如果数组为一个空对象，则默认从当前的需要扩容的大小和默认大小比较，取其中大的一个值，进行扩容，所以数组的默认大小是10，除非进行了数组的大小定义。
private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
- 只要当扩容大小大于当前的数据大小才能进行扩容，这里边可以看出数组，并不是每次都进行扩容的，假设当前数组大小是15，我存入第13个元素，数组还有空余位置，先存入，并不进行扩容
elementData.length的扩容大小默认为elementData.length的1.5倍，假设数组当前大小为10，当存入第11个元素时，触发扩容的添加大小，会变成15
这是源码的写法int newCapacity = oldCapacity + (oldCapacity >> 1);
位运算a>> 1。右移1一位，相当于a/2，如果a>> 2，类似a/4，相当于后面的移动的n，a/2^n；
如果左移动就是相乘。
1<< a=22；2<<2=24
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩容大小在之前的数组大小的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//扩容到 Integer.MAX_VALUE - 8 大小
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//数组扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
超大的扩容判断，这里可以看出，list并不是无限，最大扩容大小为 Integer.MAX_VALUE， 不过一般不会有一个list的大小能达到这个，首先内存就可能会溢出
其次，一个list的个数达到Integer.MAX_VALUE，它的读取和存入可以想象
可以认为list是一个无限大，虽然存在一个无法达到的边界
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
size/isEmpty
这两个方法实现比较简单
@Override
public int size() {
return size;
}
返回当前的size即可，虽然全文并没有初始化size，如果是int变量定义的全局变量或者静态变量，未初始化的话就是0.
@Override
public boolean isEmpty() {
return size == 0;
}
判断当前的list是否为空，只要判断size是否大于0即可
contains
判断是否包含某元素，由于list是允许重复的，在源码执行的时候，会遍历整个数组，然后equals数组的值，存在返回下标，然后判断下标是否大于0
@Override
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
//list 可以空值
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
1.从源码看，list允许存入null值
2.如果list存在重复值的话，默认返回第一个元素的下标
clear
@Override
public void clear() {
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
遍历将数组的每个元素清空，同时将size归零,但是数组并没有进行清空，这里避免了数组的再次添加元素后再次扩容，如果后期不进行操作add操作，还是存在资源的浪费,所以如果list只用一次，那么可以在调用clear之后把list也设置为null来释放全部的内存。便于gc进行回收
list.clear();
list = null;
remove
对list元素的remove，从底层来看还是对数组的操作，即将数组下标的后一个元素，往前移动一位到需要移除的数组下标位置，同时数组的最后一位的元素清空。
@Override
public E remove(int index) {
rangeCheck(index);
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//复制数组
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//移除最后一位
elementData[--size] = null;
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
//检查下标
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
get
get方法就比较简单了，返回相应的数组下标的元素就可以了
@Override
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
测试
public static void main(String[] args) {
MyList<Integer> list=new MyArrayList<>();
for (int i = 0; i <10 ; i++) {
list.add(i);
}
list.add(11);
System.out.println("读取");
System.out.println("i="+list.contains(50));
System.out.println("i="+list.remove(1));
//由于移除了一位，会抛出下标越界的异常
for (int i = 0; i <10 ; i++) {
System.out.println("i="+list.get(i));
}
}
扩展
1.fail-fast
在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。
那怎么知道在遍历过程中了出现了修改操作？
modCount记录了使用ArrayList的添加、修改、删除的更改次数
The number of times this list has been structurally modified.
expectedModCount 在源码可以看到如下代码
int expectedModCount = ArrayList.this.modCount;
当迭代器在遍历对象的时候，会将存储的expectedModCount和当前的modCount进行对比，出现不等于的时候，便抛出异常。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
2.线程不安全
ArrayList是线程不安全，从源码便可以看到，没有加锁的操作，也没有任何原子操作，当多线程操作类的时候，可能会出现下标越界的问题或者覆盖的原来的值的问题
我们可以进行测试
public static void main(String[] args) {
List<Integer> list=new ArrayList<>();
Thread A= new Thread(()-> {
for (int i = 0; i < 1000 ; i++) {
list.add(i);
try {
Thread.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
// 线程B将1000-2000添加到列表
Thread B=new Thread(()->{
for (int i = 1000; i < 2000 ; i++) {
list.add(i);
try {
Thread.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
A.start();
B.start();
try {
A.join();
B.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("赋值结束");
System.out.println("list的大小"+list.size());
// 打印所有结果
/* for (int i = 0; i < list.size(); i++) {
System.out.println("第" + (i + 1) + "个元素为：" + list.get(i));
}*/
}
运行结果
换成线程安全的Vector和CopyOnWriteArrayList进行测试
//List<Integer> list=new Vector<>();
List<Integer> list=new CopyOnWriteArrayList<>();
源码
public class MyArrayList<E> implements MyList<E> {
private static final Object[] EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
private static final int DEFAULT_CAPACITY = 10;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public MyArrayList(int initialCapacity) {
if(initialCapacity<0){
throw new IllegalArgumentException("初始化大小异常"+initialCapacity);
}
elementData=new Object[initialCapacity];
}
public MyArrayList() {
this.elementData = new Object[DEFAULT_CAPACITY];;
}
@Override
public boolean add(Object e) {
//扩容数组
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩容大小在之前的数组大小的1/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//扩容到 Integer.MAX_VALUE - 8 大小
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
@Override
public void add(int index, Object element) {
//校验下标是否正常
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
//list 可以空值
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
@Override
public void clear() {
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
@Override
public E remove(int index) {
rangeCheck(index);
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@Override
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
}
结尾(解决线程安全问题）
目前，笔者在看JUC这块的源码，拖了两周才写了这篇源码的读书笔记，其实ArrayList的源码整体上去掉Iterator这块的代码，其实并不是很复杂，在抽取出关键代码后，大概200行不到，
从源码中，可以看出，
1.当数据量很大的情况下，ArrayList存在很大的性能问题，比如当数组的grow、remove方法，当数据量比较大的时候，在数组的复制上比较占用时间；
2.取值快，由于底层是维护了一个数组，只要下标就可以获取到值,反观LinkedList的取值需要遍历链表，查询的速度比ArrayList慢
3.线程不安全，这是Vector源码add方法的操作，使用synchronized 保证了方法的独占
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
CopyOnWriteArrayList使用了lock 方法
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
Collections.synchronizedList，使用了synchronized锁对象
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
实现CAS
其实也可以使用CAS的方式实现一个无锁线程安全的list(其实和直接使用lock差不多)，贴上基于unsafe类实现CAS锁的代码，这里是一个独占锁的写法，也可以考虑基于AQS，使用LockSupport实现线程的阻塞和唤醒，但是都无法脱离unsafe类这个基石，希望在某一天，可以自己写一个unsafe类，接下来，我想查看AQS源码，然后基于它实现lock
private static final Unsafe unsafe;
private static final long valueOffset;
private volatile int value;
static {
try {
Field f = Unsafe.class.getDeclaredField("theUnsafe");
f.setAccessible(true);
unsafe = (Unsafe) f.get(null);
valueOffset = unsafe.objectFieldOffset
(MySafeArrayList.class.getDeclaredField("value"));
} catch (Exception ex) {
throw new Error(ex);
}
}
//尝试获取许可
void tryAcquire() {
for (; ; ) {
if (value == 1) {
//当发现其他线程获取到锁，线程释放掉当前的cpu时间，继续等待
Thread.yield();
} else if (compareAndSet(value, 1))
break;
}
}
private boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
//释放资源
void tryRelease() {
compareAndSet(value, 0);
}
调用的时候类似lock
@Override
public boolean add(Object e) {
tryAcquire();
//扩容数组
ensureCapacityInternal(size + 1);
elementData[size++] = e;
tryRelease();
return true;
}
然后测试一下，我们的锁，测试方法和上面的测试代码一样，使用两个线程进行插入
