Java集合中级——AbstractList源码解析

大家好，欢迎来到IT知识分享网。

AbstractList

AbstractList是什么？

AbstractList是AbstractCollection和List的抽象子类，为一些通用的方法提供实现，并为所有List结构提供统一父类

继承结构

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { }

构造函数

protected AbstractList() { }

操作集合元素

添加元素

• add(int index, E element)抛出异常避免向AbstractList添加元素，其应由子类实现
• add(E e)默认添加在尾部
• addAll在指定位置添加传入的集合

public void add(int index, E element) { throw new UnsupportedOperationException(); } public boolean add(E e) { add(size(), e); return true; } 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; } 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(); }

获取元素

get()方法通过索引获取值

abstract public E get(int index);

设置元素

set()抛出异常避免向AbstractList设置元素

public E set(int index, E element) { throw new UnsupportedOperationException(); }

删除元素

remove()抛出异常避免从AbstractList删除元素

public E remove(int index) { throw new UnsupportedOperationException(); }

clear()方法边迭代边删除

public void clear() { removeRange(0, size()); } 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(); } }

获取下标

indexOf()从前往后遍历查找，lastIndexOf()从后往前遍历查找（可找null）

public int indexOf(Object o) { 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(); } 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; }

equals和hashCode

equals方法具体为：

• 先判断类地址是否相等
• 再判断是否是List子类，非List子类无listIterator
• 取出两者的listIterator循环比较其中的元素
• 若equals()方法执行过程中元素变多或变少则为false

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()); } public int hashCode() { int hashCode = 1; for (E e : this) hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); return hashCode; }

hashCode方法具体为 31*上一个元素hascode(最开始为1) + 下一个元素hashCode(null为0)

此域用于记录集合的修改次数，防止两个迭代器并发修改

protected transient int modCount = 0;

获取迭代器

• iterator()返回从实现 Iterator的迭代器Itr
• listIterator()返回实现 ListIterator且位置为0的迭代器ListItr
• listIterator(final int index)返回 指定位置的迭代器ListItr

public Iterator<E> iterator() { return new Itr(); } public ListIterator<E> listIterator() { return listIterator(0); } public ListIterator<E> listIterator(final int index) { rangeCheckForAdd(index); return new ListItr(index); }

迭代器——Itr内部类

• hasNext()判断当前cursor是否到了 size()

next()具体为

• 先判断集合是否已被并发修改
• 调用get()取出右边元素（ 用i保持原子性，避免get时cursor被修改，若被修改抛并发异常，否则抛遍历异常 ）
• 记录越过的元素位置
• 将游标加1

remove()具体为

• 先判断是否调用了next()
• 再判断是否已被并发修改
• 调用外部类的remove()移除上一个越过的元素（ remove报错则一定发生了并发修改 ）
• 游标减1（ 判断lastRet < cursor保持原子性，避免并发修改后仍然减游标 ）
• lastRet = -1避免连续调用remove()
• 记录修改次数

private class Itr implements Iterator<E> { int cursor = 0; int lastRet = -1; int expectedModCount = modCount; public boolean hasNext() { return cursor != size(); } public E next() { checkForComodification(); try { int i = cursor; E next = get(i); lastRet = i; cursor = i + 1; return next; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.remove(lastRet); if (lastRet < cursor) cursor--; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException e) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }

迭代器——ListItr内部类

ListItr 继承了 Itr（向后遍历） 且实现了 ListIterator（向前遍历）

• 构造函数获取指定位置的迭代器（从头开始则为0）
• hasPrevious()判断当前是否到了位置0
• nextIndex()和previousIndex()返回当前游标和上一个游标

previous()具体为

• 先判断集合是否已被并发修改
• 调用get获取迭代器左边元素（ 用i保持原子性，避免get时cursor被修改，若被修改抛并发异常，否则抛遍历异常 ）
• 记录越过元素的位置并让游标减1

private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { cursor = index; } 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; cursor = i + 1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }

set()具体为

• 先判断是否调用了next()或previous()
• 再判断是否已被并发修改
• 调用外部类的set覆盖上一个越过的元素（ set报错则一定发生了并发修改 ）
• （未lastRet = -1，说明可重复set，覆盖上一个）
• 记录修改次数

add()具体为

• 先判断是否已被并发修改
• 用外部类的add()在游标右侧添加元素（ 用i保持原子性，避免add时cursor被修改，若被修改抛并发异常 ）
• lastRet = -1避免调用set()、remove()，但可连续调用add()
• 游标加1
• 记录修改次数

获取子串

数组实现的List结构返回RandomAccessSubList，链表实现的List结构则返回SubList

public List<E> subList(int fromIndex, int toIndex) { return (this instanceof RandomAccess ? new RandomAccessSubList<>(this, fromIndex, toIndex) : new SubList<>(this, fromIndex, toIndex)); }

子串——SubList类（以下是类介绍）

继承结构

采用组合模式继承AbstractList

class SubList<E> extends AbstractList<E> {、 }

i 指向父串，offset父串开始截取的index，size为两个index之差， 此外还有一个从父串继承的modCount

private final AbstractList<E> l; private final int offset; private int size;

构造函数

构造函数判断位置是否越界，保存list（ 子串和原集合是互相影响的 ）、offset、size、modCount（ 同步子串父串修改 ）

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; }

• rangeCheck检查是否越界
• rangeCheckForAdd检查是否可添加（index = size意为添加到末尾）
• checkForComodification检查字串父串修改记录是否相等

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(); }

设置元素

检查是否越界，并发修改，后调用AbstractList.set方法（ 加上子串的偏移量 ）

public E set(int index, E element) { rangeCheck(index); checkForComodification(); return l.set(index+offset, element); }

获取元素

检查是否越界，并发修改，后调用AbstractList.get方法（ 加上子串的偏移量 ）

public E get(int index) { rangeCheck(index); checkForComodification(); return l.get(index+offset); }

获取大小

检查是否并发修改，后返回size（为两个index之差）

public int size() { checkForComodification(); return size; }

增加元素

• add()检查是否越界、并发修改，后调用AbstractList.add方法（ 加上子串的偏移量 ），同步修改次数，size+1
• addAll(Collection)添加到集合末尾
• addAll(int, Collection)检查是否越界、c.size是否为0、并发修改，后调用AbstractList.addAll方法（ 加上子串的偏移量 ），同步修改次数，size+c.size

public void add(int index, E element) { rangeCheckForAdd(index); checkForComodification(); l.add(index+offset, element); this.modCount = l.modCount; size++; } 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; }

删除元素

• remove检查是否越界、并发修改，后调用AbstractList.remove方法（ 加上子串的偏移量 ），同步修改次数，size-1
• removeRange检查并发修改，后调用AbstractList.removeRange方法（ 加上子串的偏移量），同步记修次数，size-（toIndex-fromIndex）

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(); l.removeRange(fromIndex+offset, toIndex+offset); this.modCount = l.modCount; size -= (toIndex-fromIndex); }

获取迭代器

• iterator()调用AbstractList.ListIterator()再调用AbstractList.listIterator(0)， 利用多态实际调用Sublist.listIterator(0)

listIterator(int)返回指定位置的listIterator（ 其为SubList类的匿名内部类 ），下面为介绍

• 域 i 保存AbstractList.listIterator( 加上偏移量 )，内部方法都是其间接调用
• nextIndex()和previousIndex()调用AbstractList相应方法减去偏移量
• hasNext()判断子串下一个下标是否小于size ，成立后next()返回AbstractList.next()
• hasPrevious()判断子串上一个下标是否大于0 ，成立后previous()返回AbstractList.previous()

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++; } }; }

• remove()调用AbstractList.remove()，同步修改记录，size–
• add()调用AbstractList.add()，同步修改记录，size++
• set()调用AbstractList.set()

获取子串的子串

subList()调用自身的构造方法，将自己截断

public List<E> subList(int fromIndex, int toIndex) { return new SubList<>(this, fromIndex, toIndex); }

子串——RandomAccessSubList类

RandomAccessSubList继承SubList实现RandomAccess，说明父串是RandomAccess，截取的字串仍是RandomAccess

• 构造函数调用SubList的构造函数
• 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); } }