Java基础系列（四十二）：集合之AbstractList
Java基础系列（四十二）：集合之AbstractList
山禾说
发布于 2019-01-21 10:14:10
发布于 2019-01-21 10:14:10
前言
AbstractList是实现List接口的一个抽象类，它的地位之与List类似于AbstractCollection之与Collection，同事，AbstractList继承了AbstractCollection，并针对List接口给出了一些默认的实现。而且它是针对随机访问储存数据的方式的，如果需要使用顺序访问储存数据方式，还有一个AbstractSequentialList是AbstractList的子类，顺序访问时应该优先使用它。
框架图
源码
接下来，我们来看一下AbstractList的源码，看看他针对于List接口相较于AbstractCollection给出了哪些不同的实现方法。
package java.util;
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
//只提供了一个protected修饰的无参构造器，供子类使用。
protected AbstractList() {
}
//添加一个元素，实际上并没有实现。
public boolean add(E e) {
//实际上，size()在这个方法中并没有实现，交由子类去实现。
add(size(), e);
return true;
}
//抽象方法，需要子类去实现，根据索引值获取集合中的某个元素(随机访问)
abstract public E get(int index);
//由于该集合是不可变的，所以一切可能会改变集合元素的操作都会抛出一个UnsupportedOperationException()
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
public E remove(int index) {
throw new UnsupportedOperationException();
}
// Search Operations
//获取某个元素在集合中的索引
public int indexOf(Object o) {
//这里是由AbstractList内部已经提供了Iterator, ListIterator迭代器的实现类，分别为Itr，ListItr。这里是调用了一个实例化ListItr的方法
ListIterator<E> it = listIterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return it.previousIndex();
} else {
while (it.hasNext())
if (o.equals(it.next()))
return it.previousIndex();
}
//如果集合中不存在该元素，返回-1
return -1;
}
//获取某个元素在集合中最后一次出现的索引
public int lastIndexOf(Object o) {
ListIterator<E> it = listIterator(size());
if (o==null) {
while (it.hasPrevious())
if (it.previous()==null)
return it.nextIndex();
} else {
while (it.hasPrevious())
if (o.equals(it.previous()))
return it.nextIndex();
}
return -1;
}
// Bulk Operations
//清除集合中的元素
public void clear() {
removeRange(0, size());
}
//从某个索引开始，将c中的元素全部插入到集合中
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
boolean modified = false;
for (E e : c) {
add(index++, e);
modified = true;
}
return modified;
}
// Iterators
//获取Iterator接口Itr实现类迭代器
public Iterator<E> iterator() {
return new Itr();
}
//获取从0开始（初始位置）的ListIterator的实现类ListItr
public ListIterator<E> listIterator() {
return listIterator(0);
}
//获取从索引等于index的位置的迭代器
public ListIterator<E> listIterator(final int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
/**
* 内部实现了Iterator接口的实现类Itr
*/
private class Itr implements Iterator<E> {
//光标位置
int cursor = 0;
//上一次迭代到的元素的光标位置，如果是末尾会置为-1
int lastRet = -1;
//并发标志，如果两个值不一致，说明发生了并发操作，就会报错
int expectedModCount = modCount;
//判断是否存在下一条数据，即迭代器的位置是否走到尾
public boolean hasNext() {
//如果光标位置不等于集合个数，说明迭代器没有走到末尾，返回true
return cursor != size();
}
//获取下一个元素
public E next() {
//判断是否有并发操作
checkForComodification();
try {
int i = cursor;
//通过索引位置来获取元素
E next = get(i);
lastRet = i;
//每次将+1，将迭代器位置向后移动一位
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
//时刻检查是否有并发操作
checkForComodification();
throw new NoSuchElementException();
}
}
//删除上一次迭代器越过的元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//调用需要子类去实现的remove方法
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
//每次删除后，将lastRet置为-1，防止连续的删除
lastRet = -1;
//将修改次数赋给迭代器对对象的结构修改次数这个会在下面进行详解
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
//如果出现索引越界，说明发生了并发的操作导致，所以抛出一个并发操作异常。
throw new ConcurrentModificationException();
}
}
//判断是否发生了并发操作
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
//继承自Itr的ListIterator的实现类ListItr
private class ListItr extends Itr implements ListIterator<E> {
//指定光标位置等于索引的迭代器构造
ListItr(int index) {
cursor = index;
}
//如果不是第一位，返回true
public boolean hasPrevious() {
return cursor != 0;
}
//获取上一位的元素，这里在后面会有画图帮助理解
public E previous() {
checkForComodification();
try {
//这里和父类的写法略有不同，先将光标的位置进行减一
int i = cursor - 1;
E previous = get(i);
//因为需要返回的是前一位的元素，所以这里的光标值和上一次迭代到的光标的位置实际上是一样的
lastRet = cursor = i;
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
//下一位的索引值等于光标值
public int nextIndex() {
return cursor;
}
//上一位的索引值等于光标值减一
public int previousIndex() {
return cursor-1;
}
//设置元素
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//默认设置的位置是上一次迭代器越过的元素
AbstractList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//添加元素
public void add(E e) {
checkForComodification();
try {
//设置添加的位置为当前光标所在的位置
int i = cursor;
AbstractList.this.add(i, e);
//这里讲lastRet设置为-1，即添加的元素不允许立即删除
lastRet = -1;
//添加后，将光标移到
cursor = i + 1;
//迭代器并发标志和集合并发标志统一
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
//如果出现了索引越界，说明发生了并发操作
throw new ConcurrentModificationException();
}
}
}
//切取子List
public List<E> subList(int fromIndex, int toIndex) {
//是否支持随机访问
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}
// Comparison and hashing
//通过迭代器来遍历进行判断每项是否相等来重写equals方法
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof List))
return false;
ListIterator<E> e1 = listIterator();
ListIterator<?> e2 = ((List<?>) o).listIterator();
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
return !(e1.hasNext() || e2.hasNext());
}
//重写hashCode
public int hashCode() {
int hashCode = 1;
for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}
//使用迭代器成段删除集合中的元素
protected void removeRange(int fromIndex, int toIndex) {
ListIterator<E> it = listIterator(fromIndex);
for (int i=0, n=toIndex-fromIndex; i<n; i++) {
it.next();
it.remove();
}
}
//？
protected transient int modCount = 0;
//判断索引是否越界
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size())
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size();
}
}
//继承自AbstractList的内部类SubList，代表了它父类的一部分
class SubList<E> extends AbstractList<E> {
private final AbstractList<E> l;
private final int offset;
private int size;
//根据父类来构造一个SubList
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;
//修改次数（并发标志）和父类保持一致
this.modCount = l.modCount;
}
//实际上还是调用的父类的set方法和get方法
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
return l.set(index+offset, element);
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
return l.get(index+offset);
}
//size = toIndex - fromIndex;
public int size() {
checkForComodification();
return size;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
//实际上还是在父类上进行添加
l.add(index+offset, element);
this.modCount = l.modCount;
//然后把size + 1
size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
//实际上还是在父类上进行删除
E result = l.remove(index+offset);
this.modCount = l.modCount;
size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
//调用父类的removeRange方法
l.removeRange(fromIndex+offset, toIndex+offset);
this.modCount = l.modCount;
size -= (toIndex-fromIndex);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
//在当前的子集合开始的位置进行插入
l.addAll(offset+index, c);
this.modCount = l.modCount;
size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
//返回的是一个匿名内部类
return new ListIterator<E>() {
private final ListIterator<E> i = l.listIterator(index+offset);
public boolean hasNext() {
return nextIndex() < size;
}
public E next() {
if (hasNext())
return i.next();
else
throw new NoSuchElementException();
}
public boolean hasPrevious() {
return previousIndex() >= 0;
}
public E previous() {
if (hasPrevious())
return i.previous();
else
throw new NoSuchElementException();
}
public int nextIndex() {
return i.nextIndex() - offset;
}
public int previousIndex() {
return i.previousIndex() - offset;
}
public void remove() {
i.remove();
SubList.this.modCount = l.modCount;
size--;
}
public void set(E e) {
i.set(e);
}
public void add(E e) {
i.add(e);
SubList.this.modCount = l.modCount;
size++;
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
return new SubList<>(this, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
private void checkForComodification() {
if (this.modCount != l.modCount)
throw new ConcurrentModificationException();
}
}
//相较于SubList内部类，多了一个是否可以随机访问的标志
class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
super(list, fromIndex, toIndex);
}
public List<E> subList(int fromIndex, int toIndex) {
return new RandomAccessSubList<>(this, fromIndex, toIndex);
}
}通过源码，我们可以发现，AbstractList的源码在结构上分为了两种内部迭代器，两种内部类以及AbstractList本身的代码，接下来，我们来分别解释在阅读源码中遇到的一些问题
索引和游标的关系
这里我画了一个图，然后对照着这个图，我们再来看一下ListItr中的一些代码：
//下一位的索引值等于光标值
public int nextIndex() {
return cursor;
}
//上一位的索引值等于光标值减一
public int previousIndex() {
//其实这里并不理解，为啥不去检查索引越界。。
return cursor-1;
}假定迭代器现在运行到1所在的位置，可以很容易的看出当迭代器处于这个位置的时候，去调用nextIndex()方法得到的是1，而调用previousIndex得到的就是0。这是完全符合我们的逻辑的，接下来，我们再来看previous()方法的源码：
//获取上一位的元素，这里在后面会有画图帮助理解
public E previous() {
checkForComodification();
try {
//这里和父类的写法略有不同，先将光标的位置进行减一
int i = cursor - 1;
E previous = get(i);
//因为需要返回的是前一位的元素，所以这里的光标值和上一次迭代到的光标的位置实际上是一样的
lastRet = cursor = i;
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}其实这里我在分析的时候是存在疑问的（为什么这里的lastRet等于cursor，而Itr中的next()方法的实现中cursor实际上等于lastRet - 1），在画完图分析索引和游标的关系之后又来看一遍才恍然大悟，
这里的lastRet代表的是上一次迭代到的元素的光标位置，所以，我们来举个例子，当迭代器在4的位置的时候，使用了previous()方法，这时的迭代器的位置是在3，而上次迭代到的元素的游标位置也是3，而如果使用了next()方法，使用之后，迭代器的位置在5，而上一次迭代到的元素确是4。这也印证了nextIndex()和previousIndex()的逻辑。
expectedModCount 和 modCount
从源码中我们可以看到
//这个变量是transient的，也就说序列化的时候是不需要储存的
protected transient int modCount = 0;这个变量代表着当前集合对象的结构性修改的次数，每次进行修改都会进行加1的操作，而expectedModCount代表的是迭代器对对象进行结构性修改的次数，这样的话每次进行结构性修改的时候都会将expectedModCount和modCount进行对比，如果相等的话，说明没有别的迭代器对对对象进行修改。如果不相等，说明发生了并发的操作，就会抛出一个异常。而有时也会不这样进行判断：
//删除上一次迭代器越过的元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//调用需要子类去实现的remove方法
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
//每次删除后，将lastRet置为-1，防止连续的删除
lastRet = -1;
//将修改次数赋给迭代器对对象的结构修改次数这个会在下面进行详解
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
//如果出现索引越界，说明发生了并发的操作导致，所以抛出一个并发操作异常。
throw new ConcurrentModificationException();
}
}这里的设计在于，进行删除操作后，将修改次数和迭代器对象进行同步，虽然在方法的开始进行了checkForComodification()方法的判断，但是担心的是再进行删除操作的时候发生了并发的操作，所以在这里进行了try...catch...的处理，当发生了索引越界的异常的时候，说明一定是发生了并发的操作，所以抛出一个ConcurrentModificationException()。
关于SubList和RandomAccessSubList
通过阅读源码我们可以知道，这个类实际上就是一个啃老族。基本上方法全是直接去加上offset后去调用的父类的方法，而RandomAccessSubList只是在此基础上实现了RandomAccess的接口，而这个接口是干嘛的呢？
package java.util;
/**
* Marker interface used by <tt>List</tt> implementations to indicate that
* they support fast (generally constant time) random access. The primary
* purpose of this interface is to allow generic algorithms to alter their
* behavior to provide good performance when applied to either random or
* sequential access lists.
*/
public interface RandomAccess {
}通过阅读英文注释后我们可以知道，这个接口仅仅是一个标志性接口，用来标志是否可以随机访问的。
下节预告
接下来，我们终于要接触到第一个真正意义上的实现类了，敬请期待哟~
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-11-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录