ArrayList
2019-05-03 本文已影响0人
Tomy_Jx_Li
前期自己对于源码解析，以为看过既可以，然后就是类似翻译的动作而已。后期发现这种形式并没有什么好的。所以需要重新思考。
看源码前的准备。
1.ArrayList是什么
首先根据如下图：
ArrayList类图
1.最顶级接口Iterable，这个是迭代器模式的顶级接口，忽略
2.Collection接口，这个就是集合类的顶级接口了
3.List接口，列表类顶级接口，于set集合区分
4.RandomAccess接口，是一个标记接口。表明当前类可以进行快速随机访问。忽略
5.Cloneable接口，标记接口。表明深拷贝。忽略
6.其他的序列化接口，和集合的抽象实现，列表的抽象实现。
所以从ArrayList的类图可以看出，ArrayList就是一个集合类。且是一个列表集合，即支持可重复的集合元素。
2.ArrayList能干什么
通过前面的分析，知道ArrayList是一个列表集合的具体实现。那么列表集合能干什么呢。最基础的应用就是存储。将数据存储到内存中。且存储的内容是按照存入的先后顺序进行存储的。
3.分析准备
在进行ArrayList分析之前，ArrayList是什么，能干什么我们已经很清楚了。那么首先我们自己先分析下，如果自己去写一个集合都需要干什么呢。
3.1类比
这种分析一般都是需要对照到生活中的例子进行类比分析，然后进行代码实现，才能更好的理解类。首先集合类似于我们生活中的仓库。
3.2操作
既然是仓库那么就需要存储货物。而存储货物的时候最基本的操作。
1.入库
2.出库
3.清点货物总数
4.查看货物
3.3自己实现
根据自己的思路实现一个ArrayList
package com.jiyx.test.collect;
/**
*
* auther: jiyx
* date: 2019-05-02
*/
public class MyArrayList {
private Object[] items = new Object[64];
private int currIndex;
/**
* 入库
* @param item
*/
public void add(Object item) {
rangeCheckOut(currIndex);
items[currIndex++] = item;
}
/**
* 查看，不出库
* @param index
* @return
*/
public Object get(int index) {
rangeCheckOut(index);
return items[index];
}
/**
* 出库
* @param index
* @return
*/
public Object remove(int index) {
rangeCheckOut(index);
Object value = items[index];
if (items.length - index - 1 > 0) {
System.arraycopy(items, index + 1, items, index, items.length - index - 1);
}
currIndex--;
return value;
}
/**
* 当前存储的元素个数
* @return
*/
public int size() {
return currIndex;
}
/**
* 角标越界校验
* @param currIndex
*/
private void rangeCheckOut(int currIndex) {
if (currIndex > items.length - 1) {
throw new ArrayIndexOutOfBoundsException();
}
}
public static void main(String[] args) {
MyArrayList list = new MyArrayList();
list.add(1);
list.add("aaa");
list.add(list);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
list.remove(1);
list.add("bbb");
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}
4.分析
好了进入正题，进行ArrayList源码浅析。这里ArrayList无非也是上面的几个操作，不过可能比我写的更加完善，功能更多而已。
那么同样的，还是按照基本功能，外加一个初始化进行分析。
4.1初始化
因为仓库是没有的，所以我们需要自己手动创建一个仓库的。那么new的过程就是创建这个仓库的过程。
初始化分为三种，无参构造、传入初始容量构造器、传入老的集合的构造器。其实初始化的过程很简单。可以自行查看。不过这里有两个变量需要注意。EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA。因为在创建的过程无参构造时需要用到后者。其他两个构造都是用到了前者。这两个虽然值和存在的意义都一样。区别是，在第一个元素添加的时候。前者的第一次扩容为1。而后者的第一次扩容为10。
4.1入库
Arraylist的入库入口为add方法。重载了两个方法。
public boolean add(E e) {
// 判断容量是否足够，如果不足进行扩容
ensureCapacityInternal(size + 1);
// 添加元素
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
// 判断容量是否足够，如果不足进行扩容
ensureCapacityInternal(size + 1);
// 腾出需要插入元素的位置，也就是将元素后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 添加元素
elementData[index] = element;
size++;
}
而且这里面必须介绍下方法ensureCapacityInternal及其设计到的方法，都不是很复杂。如下：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 计算最小容量
* @param elementData
* @param minCapacity
* @return
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* 根据最小容量确认是否需要进行扩容
* @param minCapacity
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 具体的扩容操作
* @param 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);
}
4.2出库
出库的动作是由remove完成的。这个也比较简单了。但是呢，重载了两个，因为在从仓库中移除物品的时候。可能根据编号，也可能根据某个物品。
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);
// 将最后一位设置为null
elementData[--size] = null;
return oldValue;
}
/**
* 移出，不返回对象。因为我们知道要移出的是哪个对象
* @param o
* @return
*/
public boolean remove(Object o) {
if (o == null) {
// 移除null值
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// 真正的移出数据
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
// 对象的移出，是根据equals进行判断的，所以对象要重写这个方法
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/**
* 相对于remove(int index)方法，少了角标校验，也没有返回值
* 因为调用方法的也就remove(Object o)，而他是在循环遍历中调用的，所以这里不做角标校验
* @param index
*/
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;
}
4.3清点货物总数
因为一般我们的仓库管理时，在物品入库的时候，会做一个记录。所以直接查看记录就知道有多少物品了。
public int size() {
return size;
}
4.4查看货物
get方法，比较简单
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
4.5其他方法
当然了，ArrayList中还有很多实用的方法。如
/**
* 是否包含某对象
* @param o
* @return
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* 查看对象在仓库arrayList中的位置
* @param o
* @return
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 查找最近入库的相同的对象
* @param o
* @return
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 批量的入库
* @param c
* @return
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* 从指定位置开始批量入库
* @param index
* @param c
* @return
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
5.可修改的问题
1.方法中会出现a-b>0这种代码。感觉没有a>b来的清晰明了
2.代码中存在很多重复代码。如remove(Object o)就是修改为如下
public boolean remove(Object o) {
for (int index = 0; index < size; index++) {
if ((o == null && elementData[index] == null)
|| (o != null && o.equals(elementData[index]))) {
fastRemove(index);
return true;
}
}
return false;
}
