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

作者: Java弟中弟 | 来源:发表于2021-12-09 13:09 被阅读0次

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

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

AbstractList

AbstractList是什么？

继承结构

构造函数

操作集合元素

添加元素

获取元素

设置元素

删除元素

获取下标

equals和hashCode

获取迭代器

迭代器——Itr内部类

迭代器——ListItr内部类

获取子串

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

继承结构

构造函数

设置元素

获取元素

获取大小

增加元素

删除元素

获取迭代器

获取子串的子串

子串——RandomAccessSubList类

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

大数据

Java