基于jdk8的集合源码学习(二):List集合家族研究(AbstractList)

zz/2024/4/20 0:25:58

List集合继承关系如图,我们将根据这层关系进行自上而下的分析,分析每个类出现的原因,拥有哪些方法,这些方法底层是如何实现的:

学习一:List接口与AbstractCollection的区别:

从这个继承关系图中,我们可以发现,List家族的长辈继承了Collection接口,但是于此同时,还有一个抽象类AbstractCollection实现了Collection,而AbstractList作为ArrayList/vector/stack/linkedList必须实现的继承的对象,它即实现了List接口,又继承了AbstractCollection类。

这种复杂的关系有点类似于叔叔和爹都是爹的情况,为什么会有这种情况?

1.1 作用的区别:

AbstractCollection的作用:

在AbstractCollection源码注解中有一段描述了AbstractCollection的作用的话,此话翻译为中文的意思是:AbstractCollection相当于是实现Collection接口的一个最低配置的模板,其实也就是说AbstractCollection是为了所有实现或继承了Collection的对象打的一个小样,同时它是一个抽象类,实现了Collection的一部分功能!

List的作用:

在List的源码注释中,讲述了List的作用,翻译成中文的大概啥意思就是,List集合是一个有序集合的标志,可以发Null值,可以放重复数据;原话中还说,你可以实现一个List集合,做到不能放重复数据,但是官方不推荐你那么做!而且List接口是一个接口,相当于一个集合的约束规范!

 

总结:AbstractCollection和List的作用是站在不同角度上的说的AbstractCollection是站在更加宽泛的角度(Collection集合接口实现上,用于样例)用的,而List的作用则是相对较详细的角度上(一个可以放Null值/重复元素的有序集合接口,用于规范)规定的

1.2 方法上的区别:

首先比较的是AbstractCollection和Collection接口的区别:

对比图中,绿色的部分为Ab实现了的Collection接口,在这个实现中,有几个及其需要注意的点:

第一个注意的点:首先是add方法,虽然Ab实现了该方法,但该方法的底层代码却扔了一个异常:

public boolean add(E e) {
        throw new UnsupportedOperationException();
    }
第二个注意的点:Ab并没有提供迭代器和size()方法的实现,但是里面的方法却很多都依赖于迭代器

第三个注意的点:Ab此时出现了一个常量值MAX_ARRAY_SIZE,顾名思义是数组的最大值,默认为private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

第四个注意的点,有个比较值得分析的方法toArray()和toArray(T[] a)方法,该方法的作用是将实现将集合转换成数组,或指定的数组,toArray(T[] a)的源码如下:
    public <T> T[] toArray(T[] a) {
        // Estimate size of array; be prepared to see more or fewer elements
        int size = size();
        T[] r = a.length >= size ? a :
                  (T[])java.lang.reflect.Array
                  .newInstance(a.getClass().getComponentType(), size);

上面代码的意思是创建一个大于或者等于集合大小的数组,下面这段的意思是迭代遍历集合,如果新创建的数组大于该集合的大小,那么调用
        Iterator<E> it = iterator();

        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) { // fewer elements than expected
                if (a == r) {
                    r[i] = null; // null-terminate
                } else if (a.length < i) {

   Arrays.copyOf和System.arraycopy是值得注意的两个方法,这两个方法都能实现数组的快速复制, Arrays.copyOf底层调用的也是System.arraycopy
                    return Arrays.copyOf(r, i);
                } else {
                    System.arraycopy(r, 0, a, 0, i);
                    if (a.length > i) {
                        a[i] = null;
                    }
                }
                return a;
            }
            r[i] = (T)it.next();
        }

     
        // more elements than expected
        return it.hasNext() ? finishToArray(r, it) : r;
    }

这段代码的含义就是将集合转换成固定的数组,如果数组的长度大于集合的容量,那么就扩容。小于的话就就截断

其次比较List集合和Collection之间的区别:

 

List和Collection接口功能区别:

从上面两张图来看,List接口于Collection接口的主要区别是增加了几个新的方法,这几个方法中值得注意的是ListIterator的迭代器/sort排序方法

小拓展:

上图中,List方法图中画红线的部分是Collection接口中也有的方法,因为两者都是接口,List集合是继承自Collection接口的,但我们都知道接口中的方法只是起到规范作用,既然List集合继承自Collection接口,那为什么还要重新写一遍Collection接口呢?

原因应该是:接口设计的原因,我们都知道接口的关系体系一直在改变,谁也不知道那一天List集合/Set集合/Queue会不会单独拎出来(毕竟,他们之间没有什么深层次联系),因此才造成了这种情况!这种情况有个好处,就是有一天三个集合独立了,那么就可以直接使用!当然,网上也有一个说法,那就是查看源代码方便,毕竟实现的接口越多,查看源代码越不方便

 

总结:List集合接口和AbstractCollection的功能区别:

AbstractCollection主要实现了Collection的功能,而List集合则是主要增加了一些隶属于List集合特有的方法定义

 

学习二:AbstractList抽象类的作用:

AbstractList即继承了AbstractCollection又实现了List接口,因此我们将从AbstractList与AbstractCollection以及AbstractList与List之间的区别入手,分析AbstractList的作用:

2.1AbstractList与AbstractCollection的区别:

 2.1.1作用上的区别:

从前面的分析中,我们知道AbstractCollection的主要作用是为Collection的子孙辈做了一个打样,一个是站在集合的Collection角度上的,而AbstractList的作用,经过对源码的粗浅翻译,他的作用主要是是为实现了List接口做了一个打样,他是站在List集合的角度上的。

2.1.2功能方法上的区别:

 

在上图中,画红线的部分就是AbCollection和AbList的共有的方法,也就是AbList对AbCollection重写方法,在前面的分析中,我们可以知道继承AbCollection的类必须要实现的几个条件:1.add方法重写;2.迭代器重写;而通过两者的对比,AbList果然是实现了add方法重写以及Iterator重写。

1.重写的add方法如下

public boolean add(E e) {
        add(size(), e);
        return true;
    }

我们可以看出来,其调用了add(size,e)方法,而该方法内部如下,这说明Ablist的子类必须实现add方法

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

2.迭代器重写:

迭代器实现如下:

public Iterator<E> iterator() {
        return new Itr();
    }

迭代器调用一个内部类Itr代码如下:

 

private class Itr implements Iterator<E> {
        /**
         * Index of element to be returned by subsequent call to next.
         */

        int cursor = 0;

        /**
         * Index of element returned by most recent call to next or
         * previous.  Reset to -1 if this element is deleted by a call
         * to remove.
         */

        int lastRet = -1;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */

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

由此可以看出Itr内部实现的原理是设置两个游标cursor和lastRet,cursor代表当前未开始的获取元素时的集合的下标,而lastRet代表着本次为获取元素时的游标位置,俩人相差为1。

判断当前迭代器是否还有元素时:就是判断当前游标cursor是否等于集合的size(),如果等于就没有了,如果不等于就是还有。

获取当前元素时:使用集合的get方法,获取当前游标对应的元素。获取完之后,lastRet设置为当前游标cursor,而当前游标cursor+1,组为下个遍历的当前游标!

删除元素:删除元素前必须先遍历,不然直接抛异常

注意:该迭代器还有一个并发检查,多线程环境下可能会抛出并发异常,实现的原理时但你使用迭代器迭代,另外一个线程修改了集合的大小,此时就会抛出异常。

3.remove()方法重载:

AbList重载了remove方法,其实准确的说,是实现了List集合的remove方法,虽然实现了List集合的remove方法,但是在该方法代码如下:

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

因此需要被子类实现,不然直接抛异常!

该方法与AbCollection的remove方法用处区别在于,Abcollection底层使用的迭代器移除的元素,传入的参数也是集合的元素,而此方法主要用于使用集合的下标去删除

4.clear方法,clear方法底层时调用的迭代器进行遍历删除的

2.2 AbstractList与List的区别:

通过对比图我们可以发现,AbList主要实现了List接口中的add、get....等方法,在这几个方法中,有如下几点值得我们关注:

第一点:add(E e)、E get(int index)、set(int index, E element)、remove(int index)等方法,虽然其内部是实现了List集合的方法,但这些方法都必须要在子类中进行重写,因为这些方法要不在方法体中抛了一个异常,要不就是直接将方法定义为Ab类型

第二点:AbList内部提供了iterator()和listIterator()和listIterator(final int index)方法的实现

{//开始进行第二点分析

iterator()底层调用了Itr的内部类实例化,而Itr上面已经分析过了!

而listIterator()、listIterator(final int index)底层则调用了ListItr的内部类实例化,怪就怪在“class ListItr extends Itr implements ListIterator<E>”,其继承了iterator()

那么一个集合的内部为何会出现这两种迭代器?这两种迭代器的优缺点是什么?

private class Itr implements Iterator<E> {
        /**
         * Index of element to be returned by subsequent call to next.
         */
        int cursor = 0;

        /**
         * Index of element returned by most recent call to next or
         * previous.  Reset to -1 if this element is deleted by a call
         * to remove.
         */
        int lastRet = -1;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        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();
        }
    }

《《《《《《《《《《《《《《《两个迭代器的代码分割点,上面是Iterator,下面是的ListIterator

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

 

通过两者的代码分析,我们可以发现两者迭代的区别如下:

区别一:各有各的用法,在作用上的区别:

Itr的作用是集合的迭代器,ListItr是服务于List集合的迭代器,两者的关系就好像Collection和List两个接口的关系一样,事实上,从他们的继承关系里就可以看出来这一点。

区别二:功能上的区别:

Itr主要对集合向后迭代,主要提供了三个功能,判断是否还有下一个元素、获取当前元素、将当前元素从集合中删除,而ListItr则是Itr进行了功能上的扩充,不仅向后迭代,还能向前迭代,而且还提供了增、删、改的操作,它比Itr更加强大,但是同时也更具有局限性(只能针对List集合),另外ListItr还提供了一个有参构造,可以做到从集合固定位置进行向前或者向后的遍历(该方方法一个应用场景就是removeRange方法,其底层使用了ListItr类在固定位置向后遍历删除)!

//结束进行第二点分析}

第三点:subList(int fromIndex, int toIndex)方法:

subList(int fromIndex, int toIndex)的源码如下:

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

通过这个源码我们可以发现,在subList的方法体内,竟然还有一个判断,而选择不同的截取方法,而这个判断的前提提交就是集合是否属于RandomAccess,如果该集合实现了RandomAccess那么就使用RandomAccessSubList进行截取,否则使用SubList进行截取,那么这两个方法有什么区别呢!

RandomAccess是标识接口,一般实现该接口的集合,都可以实现随机访问(数组),而随机访问使用for循环遍历比迭代器效率高。那么,回归上面的问题,subList和RandomAccessSubList<E>在subList里区别不大,因为RandomAccessSubList还继承了SubList,但是当截取之后的数据进行遍历时,就会有稍微区别,因为RandomAccessSubList实现了RandomAccess,因此标志着,使用for循环,遍历的效率更高。

注:其实在百万数据之下,迭代器和for循环难分伯仲

第三点:List默认提供了replaceAll(UnaryOperator<E> operator)、sort(Comparator<? super E> c)方法:

replaceAll(UnaryOperator<E> operator)的底层代码:

default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);

//这里调用引用对象的.listIterator()方法,生成一个迭代器
        final ListIterator<E> li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }

sort(Comparator<? super E> c)的底层代码:

default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

通过这个源码我们可以发现,replaceAll需要传入一个UnaryOperator类型参数,而UnaryOperator参数时函数接口Function的继承接口,代表传入一个参数类型,返回的也是那个参数类型,也就是如果想要看透该功能,还需看List继承类如何实现该方法!

sort(Comparator<? super E> c) 接口就很好明白了,它底层调用了数组的排序方法,根据排序规则,对集合进行重新排序

 

 

2.3 AbstractList与AbstractCollection、List的区别:

因为AbList继承了AbCollection,实现了List接口,因此作为AbList来说,因为他需要实现AbCollection和List接口要求实现的方法,通过上述三者的连线可以看出,对于List接口,AbList只有replaceAll和sort方法没有具体实现,剩余的方法都通过AbList直接或AbCollection间接实现了!

而通过2.1和2.2的总结我们可以对Ablist进行如下总结:

1.继承AbList的类必须重新对add(E e)、E get(int index)、set(int index, E element)、remove(int index)等方法进行重写!

2.继承AbList的类默认实现了迭代器及List专有迭代器

3.Ablist默认实现了size、isEmpty、contains、toArray、remove(删除元素)、containAll(包含集合)以及上述中AbCollection实现的方法以及AbList自己实现的方法。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


http://www.ngui.cc/zz/2700327.html

相关文章

Spring的BeanFactory重要属性之PropertyEditor,如何bean的属性转换

PropertyEditor是什么&#xff1f; PropertyEditor是JavaBean规范里&#xff0c;提供的一个高级接口&#xff0c;该接口提供了一些方法规范&#xff0c;这些方法可以将JavaBean的外部数据String类型的数据&#xff0c;转换成JavaBean的内部属性值。PropertyEditorSupport是什么…

传统企业如何搭上互联网+的大船

&#xfeff;&#xfeff; 2014年被称为互联网元年&#xff0c;自2000年互联网泡沫之后&#xff0c;互联网再次开始成为商界关注的热点话题&#xff0c;互联网也被上升到国家战略高度。唯恐被时代抛弃的传统企业也纷纷加入互联网大军&#xff0c;进行一系列业务调整和策略改革。…

ServerSAN解析(四):FusionStorage存储与计算分合灵活部署

&#xfeff;&#xfeff; FusionStorage也是款可以部署在X86服务器上的种分布式块存储软件&#xff0c;利用服务器的本地HDD、SSD等介质组织成一个大规模存储资源池&#xff0c;对上层的应用和虚拟机提供标准的iSCSI块存储接口。FusionStorage软件支持主流的服务器产品&#x…

EMC联邦帝国前世今生

 说起存储,我们不得不说EMC这一存储帝国的霸主,从初创公司到目前的行业领导者,其远见和创新一直被后来者模仿,也赢得世人称赞。还记得上个世纪七八十年代,IBM大型机控制整个存储市场,所有存储都是配套大型机;为此IBM推出磁盘存储系统,整个系统存储容量几百M,但其重…

虚拟化三剑客专题-VMware(上)

&#xfeff;&#xfeff; 什么是VMware vSphere vSphere是VMware推出的基于云的新一代数据中心虚拟化套件&#xff0c;提供了虚拟化基础架构、高可用性、集中管理、监控等一整套解决方案。 VMware vSphere 主要组成 ESX/ESXi&#xff1a; 物理服务器的虚拟化层&#xff0c;它将…

VMware用技术浇灌生态之花

 今天决定和大家聊一下VMware方案和认证体系,因为我对虚拟化的了解就是从VMware开始。虽然近几年VMware历经多次策略调整和人事变迁,但是无论在EMC联邦还是在Dell领带下独立运作,VMware在虚拟化和私有云领域的领导地位依然无法撼动。作为一个纯软件公司,VMware通…

Docker这么火,但你对它的原生网络知多少?

&#xfeff;&#xfeff; ICT架构师技术交流 分析和交流ICT行业最前沿技术&#xff0c;分享更多云计算、存储、服务器、数据中心、网络、软件定义和虚拟化等相关知识&#xff0c;旨在知识交流、开放共享和共同进步。 在云计算架构设计中&#xff0c;最复杂且最重要的组件就是…

【备份专题】虚拟机备份原理和架构

 虚拟机备份原理和架构 ICT架构师技术交流 分析和交流ICT行业最前沿技术,分享更多存储、服务器、数据中心、网络、软件定义和虚拟化等相关知识,旨在知识交流、开放共享和共同进步。 虚拟化备份技术最早是由VMware提供和发起的,随着虚拟化应用在企业和各个行业的普及,主…

[福利] 告诉你什么叫别人家的架构师

本文选自QCon对QCon北京2016大会的一些总结&#xff0c;虽然大会已经落幕&#xff0c;但大会中涉及很多架构方面的话题&#xff0c;希望能够给参会者带来一些参考和启发。点击阅读原文下载QCon大会技术架构相关资料。 通常&#xff0c;当我们看到别人家的架构师&#xff0c;以及…

HDD磁盘,非4K无以致远

机械硬盘的未来要靠高容量作为依托,在财报中,希捷表示未来18个月内它们将推出14和16TB机械硬盘,而2020年20TB机械硬盘就将诞生。也有资料显示,3.5英寸100TB硬盘大概在2025年就能面世。因此,机械硬盘与固态硬盘的拉锯战恐怕还会继续打下去。 3.5寸6TB以上容量等大容量磁盘,…