minkmui,进击的巨人94,泾县网
前言：在前面我们提到数据结构的。那么今天我们详细看下java源码是如何实现线性表的，这一篇主要讲解顺序表arraylist链式表下一篇在提及。
1：arraylist结构图
2：关于collection和list的区别
最好的比对就是查看他们的源码我们先看collection的所有接口
我要评论
public interface collection<e> extends iterable<e> {
int size();
boolean contains(object o);
iterator<e> iterator();
object[] toarray();
<t> t[] toarray(t[] a);
boolean add(e e);
boolean remove(object o);
boolean containsall(collection<?> c);
boolean addall(collection<? extends e> c);
boolean retainall(collection<?> c);
void clear();
boolean equals(object o);
int hashcode();
}
在看list接口
public interface list<e> extends collection<e> {
int size();
boolean isempty();
iterator<e> iterator();
object[] toarray();
<t> t[] toarray(t[] a);
boolean add(e e);
boolean remove(object o);
boolean containsall(collection<?> c);
boolean addall(collection<? extends e> c);
boolean addall(int index, collection<? extends e> c);
boolean removeall(collection<?> c);
boolean retainall(collection<?> c);
void clear();
boolean equals(object o);
int hashcode();
e get(int index);
e set(int index, e element);
void add(int index, e element);
e remove(int index);
int indexof(object o);
int lastindexof(object o);
listiterator<e> listiterator();
listiterator<e> listiterator(int index);
list<e> sublist(int fromindex, int toindex);
}
由于list是继承collection，所有具有collection所有的功能，从collection接口中我们也可以看出，collection不具有索引，不可以取元素的值，而list取可以，list是具有索引的，这样一来在获取元素方面远远好于collection。
3：iterable接口
从arraylist中我们可以看出，最顶端的接口就是iterable这个接口，这个是一个迭代器，接口如下
public interface iterable<t> {
iterator<t> iterator();
}
这个接口主要是返回一个对象，这个对象是iterator，那么我们在看看iterator接口里面的方法
public interface iterator<e> {
boolean hasnext();
e next();
void remove();
}
那么我们主要看arraylist是如何实现迭代器iterator的。iterator的实现在abstractlist这个抽象类中的一个私有类itr中。我们看看具体实现
private class itr implements iterator<e> {
int cursor = 0;
int lastret = -1;
int expectedmodcount = modcount;
public boolean hasnext() {
return cursor != size();
}
cursor：记录即将调用索引的位置
lastret：最后一个元素的索引
int expectedmodcount = modcount;目的是为了验证modcount后面会单独说下。
判断这个集合是否存在最后一个元素，通过cursor != size();size表示数组的长度，因为数组中元素索引从0开始，所以当最后一个索引等于数组长度的时候说明已经到数组的尾部了。
public e next() {
checkforcomodification();
try {
e next = get(cursor);
lastret = cursor++;
return next;
} catch (indexoutofboundsexception e) {
checkforcomodification();
throw new nosuchelementexception();
}
}
final void checkforcomodification() {
if (modcount != expectedmodcount)
throw new concurrentmodificationexception();
}
modcount：记录所有数组数据结构变动的次数，包括添加、删除、更改等，为了避免并发时候，当多个线程同时操作时候，某个线程修改了数组结构，而另一个线程恰恰读取这个数组，这样一来就会产生错误。所以在这段代码中加入了modcount != expectedmodcount，比如a线程对数据结构修改一次，那么modcount比如+1，而expectedmodcount并没有发生变化，所以这样就会抛出异常。
public void remove() {
if (lastret == -1)
throw new illegalstateexception();
checkforcomodification();
try {
abstractlist.this.remove(lastret);
if (lastret < cursor)
cursor--;
lastret = -1;
expectedmodcount = modcount;
} catch (indexoutofboundsexception e) {
throw new concurrentmodificationexception();
}
}
我们刚刚说了lastret记录的是最后一个元素，所以删除的时候直接按照索引删除即可，因为modcount会减一，所以重新对expectedmodcount 进行赋值，避免遍历时候产生错误。而且把lastred在次赋初始值。
4：分析arraylist
刚刚目的是为了更加连接arraylist做个铺垫，arraylist和我们以前数据结构中提到的顺序表一样，采用object[] 数组进行存储元素，用size来记录元素的元素的个数。
/** * the array buffer into which the elements of the arraylist are stored. * the capacity of the arraylist is the length of this array buffer. */ private transient object[] elementdata; /** * the size of the arraylist (the number of elements it contains). * * @serial */ private int size;
关于transient，一旦变量被transient修饰，变量将不再是对象持久化的一部分，那么为啥采用transient修饰呢，由于elementdata本身是一个缓存数组，通常会预留一些容量，当容量不够时然后进行扩充，比如现在elementdata容量是10，但是只有5个元素，数组中的最后五个元素是没有实际意义的，不需要储存，所以arraylist的设计者将elementdata设计为transient，然后在writeobject方法中手动将其序列化，并且只序列化了实际存储的那些元素，而不是整个数组。我们看下writeobject方法
private void writeobject(java.io.objectoutputstream s)
throws java.io.ioexception{
// write out element count, and any hidden stuff
int expectedmodcount = modcount;
s.defaultwriteobject();
// write out array length
s.writeint(elementdata.length);
// write out all elements in the proper order.
for (int i=0; i<size; i++)
s.writeobject(elementdata[i]);
if (modcount != expectedmodcount) {
throw new concurrentmodificationexception();
}
}
关于arraylist的初始化。arraylist的设计者采用3种方式初始化。（默认数组容量是10）
public arraylist(int initialcapacity) {
super();
if (initialcapacity < 0)
throw new illegalargumentexception("illegal capacity: "+
initialcapacity);
this.elementdata = new object[initialcapacity];
}
public arraylist() {
this(10);
}
public arraylist(collection<? extends e> c) {
elementdata = c.toarray();
size = elementdata.length;
// c.toarray might (incorrectly) not return object[] (see 6260652)
if (elementdata.getclass() != object[].class)
elementdata = arrays.copyof(elementdata, size, object[].class);
}
trimtosize方法，这个方法可能我们好多人用的少，其实意义蛮大的，它主要把没用的容量去除掉，这样一来可以减少内存的开销
public void trimtosize() {
modcount++;
int oldcapacity = elementdata.length;
if (size < oldcapacity) {
elementdata = arrays.copyof(elementdata, size);
}
ensurecapacity方法，我们知道数组如果满了就会进行扩容，这个方法就是扩容的。
public void ensurecapacity(int mincapacity) {
modcount++;
int oldcapacity = elementdata.length;
if (mincapacity > oldcapacity) {
object olddata[] = elementdata;
int newcapacity = (oldcapacity * 3)/2 + 1;
if (newcapacity < mincapacity)
newcapacity = mincapacity;
// mincapacity is usually close to size, so this is a win:
elementdata = arrays.copyof(elementdata, newcapacity);
}
modcount就是增加因子，记录操作数组结构的次数，首先和容量进行比对，如果不够了进行扩容。这是java1.6版本的就是在原来的基础上扩容1.5倍。1.7采用>>1也就是所有元素像右边移动一位然后加上原来的容量。其中
indexof方法，这个方法是获取元素索引。通过索引然后进行查询元素
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;
}
从中我们也可以看出arraylist是支持null的插入的。同样采用的是循环遍历来进行查找，时间复杂的为n。
contains方法，验证数组是否包含某元素，直接通过indexof验证返回值即可
public boolean contains(object o) {
return indexof(o) >= 0;
}
lastindexof方法，和indexof相对，indexof是从前往后，lastindexof是从后面往前查找如下
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;
}
toarray方法，就是把list转换成数组形式
public object[] toarray() {
return arrays.copyof(elementdata, size);
}
get和set方法，这个就很简单了大家看下就行
public e get(int index) {
rangecheck(index);
return (e) elementdata[index];
}
public e set(int index, e element) {
rangecheck(index);
e oldvalue = (e) elementdata[index];
elementdata[index] = element;
return oldvalue;
}
rangecheck方法是进行验证的，查询的索引不可以超过数组的长度如下
private void rangecheck(int index) {
if (index >= size)
throw new indexoutofboundsexception(
"index: "+index+", size: "+size);
}
add(e e)添加一个元素，这个采用尾插入，先验证容量，size+1是加入1个元素后长度，看原来数组容量是否够。
public boolean add(e e) {
ensurecapacity(size + 1); // increments modcount!!
elementdata[size++] = e;
return true;
}
add(int index, e element)按照索引进行插入，第一个还是一样进行扩容，然后把索引index后面的元素全部向后面移一位。system.arraycopy(elementdata, index, elementdata, index + 1,
size - index);的意思就是将elementdata的第index个元素移到第index+1个元素上，长度为size-index。
public void add(int index, e element) {
if (index > size || index < 0)
throw new indexoutofboundsexception(
"index: "+index+", size: "+size);
ensurecapacity(size+1); // increments modcount!!
system.arraycopy(elementdata, index, elementdata, index + 1,
size - index);
elementdata[index] = element;
size++;
}
addall(collection<? extends e> c)
public boolean addall(collection<? extends e> c) {
object[] a = c.toarray();
int numnew = a.length;
ensurecapacity(size + numnew); // increments modcount
system.arraycopy(a, 0, elementdata, size, numnew);
size += numnew;
return numnew != 0;
}
首先把集合c转换成a数组，然后计算要进行添加的数组长度，其它的基本和添加元素一致。arraycopy(object src, int srcpos,object dest, int destpos,int length)
参数次数依次 源数组，源数组起始位置，目标数组，目标数组起始位置，复制数组元素数目。
addall(int index, collection<? extends e> c)把数组插入到指定位置
public boolean addall(int index, collection<? extends e> c) {
if (index > size || index < 0)
throw new indexoutofboundsexception(
"index: " + index + ", size: " + size);
object[] a = c.toarray();
int numnew = a.length;
ensurecapacity(size + numnew); // increments modcount
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;
}
首先判断是是否越界，然后和上面的基本一样，就是进行扩容判断，然后index后面的值进行后移包括index，然后留下的空间插入集合a。所以2次进行复制元素。
e remove(int index)和add相对，删除这个元素然后把index后面的元素往前面移一位size - index - 1其中-1是因为index这个元素会被删除，会少一位元素。
public e remove(int index) {
rangecheck(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; // let gc do its work
return oldvalue;
}
remove(object o)这个就需要先进性验证然后找到这个元素的位置最后进行删除
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; // let gc do its work
}
clear就是把所有的原素置空
public void clear() {
modcount++;
// let gc do its work
for (int i = 0; i < size; i++)
elementdata[i] = null;
size = 0;
}
sublist方法，我们知道arraylist是有这个方法，在arraylist源码并不存在，因为是继承abstractlist而来的
public list<e> sublist(int fromindex, int toindex) {
return (this instanceof randomaccess ?
new randomaccesssublist<e>(this, fromindex, toindex) :
new sublist<e>(this, fromindex, toindex));
}
class sublist<e> extends abstractlist<e> {
private abstractlist<e> l;
private int offset;
private int size;
private int expectedmodcount;
sublist(abstractlist<e> list, int fromindex, int toindex) {
if (fromindex < 0)
throw new indexoutofboundsexception("fromindex = " + fromindex);
if (toindex > list.size())
throw new indexoutofboundsexception("toindex = " + toindex);
if (fromindex > toindex)
throw new illegalargumentexception("fromindex(" + fromindex +
") > toindex(" + toindex + ")");
l = list;
offset = fromindex;
size = toindex - fromindex;
expectedmodcount = l.modcount;
}
从代码中我们可以看出这个一个基本内部类的实现，sublist只是去list中的一段数据。但是关于sublist我们要注意几个事项。
第一：如果我们改变了list的数值，那么你获取的sublist中的值也随之改变，原因如下
public e get(int index) {
rangecheck(index);
checkforcomodification();
return l.get(index+offset);
}
因为获取的还是以前list中的数据。同样如果修改sublist获取的数值，list同样改变，
第二：如果改变了list结构，可能导致sublist的不可用，因为这些修改已然基于原来的list，他们共同用一个list数组。
public void add(int index, e element) {
if (index<0 || index>size)
throw new indexoutofboundsexception();
checkforcomodification();
l.add(index+offset, element);
expectedmodcount = l.modcount;
size++;
modcount++;
}
5：关于list删除错误分析
list在采用循环删除的时候会报concurrentmodificationexception异常，那么我们来看看具体原因，先看一段代码
list<string> list = new arraylist<string>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");
for (string str:list){
list.remove(str);
}
由于foreach遍历最终会for (iterator it=iterator;iterators.hasnext();)模式那么所以获取元素的时候必然会用到迭代器中的next方法，next方法我们前面说了会有if(modcount!= expectedmodcount)throw new concurrentmodificationexception()验证。因为调用remove(t x)方法时候modcount会+1,所以2次比较就会出现不一致。
正确写法如下
iterator iterator=list.iterator();
while (iterator.hasnext()){
iterator.next();
iterator.remove();
}
为啥迭代器中remove就可以呢，是由于在remove代码中有expectedmodcount = modcount这句代码。
6：arraylist是线程安全吗
线程不安全就是指多个线程同时操作造成脏读，错读情况，很明显arraylist是非线程安全的，比如说arraylist现在只有一个值后，如果a，b2个线程同时删除这个值，a线程判断得到size=1,而此时时间片段到，cpu调用b线程执行发现size也是1，开始删除操作，然后a继续进行发现arraylist已经空了就会报异常。或者添加等等。但是vector是线程安全的，因为里面所有方法都加入了synchronized，这样造成的结果就是所有线程执行arraylist方法都必须等待，直到获取同步锁才可以继续进行，这样一来性能大大降低。
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持移动技术网！
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
浅析我对 String、StringBuilder、StringBuffer 的理解
使用IDEA搭建SSM框架的详细教程(spring + springMVC +MyBatis)
Springboot整合freemarker 404问题解决方案
引入mybatis-plus报 Invalid bound statement错误问题的解决方法
网友评论