我要啦免费统计

jdk7源码剖析之标准库(1)—— 从Arraylist到AbstractList

一切从ArrrayList开始

话说在上大学之前,也算是稍微接触过一些数据结构,所以一开始看到Java里面的ArrayList就觉得奇怪。以前见过的数据结构无非是Array或者List,怎么又出来个ArrayList,这到底是Array还是List啊。后来上课时发现,这从来没听说过的ArrayList貌似还用的挺多。众所周知,List算是和Array是不分伯仲的两种数据结构。Array擅长随机存储(RandomAccess),但是对在任意位置添加删除元素却很不在行。而List则相反,因为其本身是一个链表,只需要对节点的指针进行操作就可以了。那么ArrayList又是怎么实现的呢,我们不妨先看一看这货的signature:


嗯,貌似这货也就是一个实现了各种List方法的Array啊(还是Object的Array,谁让Array没有泛型呢)。下面我们再看看构造函数:

其中注意的一点就是Collection.toArray()没有遵守规范(因为用了clone()方法),导致由Collection的Array的类型并不是Object[]。所以这时就需要用Arrays.copyOf指定类型进行转换。还有一点是ArrayList的size是已经包含了已分配的元素的个数,而非内部的数组大小。所以在用initialCapacity初始化时,不要立刻用iterator去遍历,因为此时size还是0。

下面是ArrayList的核心功能,增删改查的实现。既然ArrayList的本质仍然是数组,那么对于改查自然是有独特的优势。

在get时,我们必须把数组里面存放的Object类转化为泛型类E。而set操作其实也是返回了修改前的值(不知道是否真的会在哪里用到)。还有一点是indexOf和lastIndexOf都用到了对象的equals方法,便于重载比较方法。

下面我们来看一看增删是怎么实现的。由于ArrayList本身为数组实现,所以增删必然要伴随着边界检查、数组移动,这之中也肯定会牵扯到效率问题。

从这段代码中我们可以看到,每当我们希望增加元素时,java总会至少分配1.5倍于原始容量的空间。当我们需要占用的总空间大于1.5倍的原空间时,就按我们需要的来分配。这样会减少分配的次数但是又不至于过多的占用无用的空间。而对于需要在特定位置的插入和删除操作,此时java用到了System.arraycopy方法。那么System.arraycopy方法是否要比我们所想的要高效很多呢,我们可以跟踪到System,之后我们会发现arraycopy是一个native方法,也就是说,是从外部的native代码调用过来的,而不是java级别的代码。经过了数次(次数大于5)的跟踪,我们会在hotspot/src/os_cpu找到针对不同架构和操作系统的不同arraycopy的实现版本(下面以linux为例):

在上一步中,jvm已经将需要复制的数组已经按照类型执行了不同的函数调用,在这一步中,就会针对不同的处理器架构进行调用。我们可以看出,对于稍微复杂点的数据类型,都会调用pd_conjoint_words或者_Copy_...的函数。前者是这样的:

后者是这样的:

所以从这个角度来看,前者调用了memmove,依赖于系统的实现,可谓是达到了最优化,而后者则用了汇编代码来移动。无论如何,当移动操作不再在jvm层面上进行时,效率自然会大大提高,因为不必再在移动的时候进行垃圾回收等jvm层面上的操作。这也就是为什么在ArrayList文档的一开始会提到add操作需要“amortized constant time”了。
接下来是batchRemove

batchRemove的作用是根据另一个集合算出两个集合的差集以及差集的补集,分别叫做RemoveAll和RetainAll。简单的说来其实就是计算ArrayList1.filter( x => x in ArrayList2)和ArrayList1.filter( x => x not in ArrayList2)(传说中的list comprehension是也)。

接下来是Iterator,Iterator里面最瞩目的就是checkForComodification()。因为modCount++似乎贯穿了整个ArrayList类,但我们一直不知道这个变量有什么用。实际上,如果我们观察的再仔细一些,就会注意到modCount只有在改变ArrayList时才会被修改。而在Iterator中,我们似乎明白了这么做的用意。

其实通过名称,我们也可以看出这个函数是做什么的。之所以在每次修改时都要改变modCount的值,就是要在Iterator进行遍历时检查,当前Iterator所操作的对象的长度时候还和原来时一样。否则一旦进行了并发的编辑,那么Iterator则很有可能指向错误的位置。比如下面这段代码就会报错(感谢翔神的提醒):

在ArrayList中,除了我们在数据结构中熟悉的Iterator外,还实现了一个对原有Iterator进行扩展的的ListIterator(可以通过arraylist.listIterator(...)获得:

可以看出,ListIterator的一大功能就是提供了显式的iterator所在的index,并且提供了双向的遍历方法。
最后是一个内部类Sublist。从下面的代码我们可以看出,sublist似乎几乎就是一个当前列表的副本,而sublist也并非类似于python或者其他语言当中的slice操作。sublist本身并不新建一个新的引用,对于sublist中的元素的操作,都会对原始(parent属性)的arraylist产生影响。所以可以只是把sublist当做一个对原始list进行便捷操作的一个工具(对于某一特定范围忽略offset):

到现在为止,ArrayList的源码差不多都读完了,除了剩下的readObjectwriteObject。这两个方法都和序列化(serialization)有关。我们会注意到在一开始的elementData是带有transient关键字的,也就是说在序列化时,并不序列化elementData这个引用。所以说,我们就需要显式地重载readObjectwriteObject这两个方法。当jvm在执行语句,看到某个类实现了serializable这个接口时,会通过反射机制查找这个类是否有自己的readObjectwriteObject方法。如果没有,则调用defaultReadObjectdefaultWriteObject方法来序列化(并且跳过transient字段)。由于我们要自定义elementData的序列化方法,而又想让其他部分默认序列化,所以在ReadObject的一开始,我们就先调用defaultReadObject来将其他部分序列化,之后再人工将array中的内容写入到输出流之中。

从ArrayList到AbstractList

上面我们分析了ArrayList中的所有代码。简而言之,ArrayList似乎就是可变长度的Array。但是当我们自己去设计时,我们也许会有这样的疑惑,为什么ArrayList要继承一个不知所云的AbstractList,而却要实现一个List接口。这是我们就要再来看看AbstractList类和List接口,来看里面到底哪些部分和ArrayList有关。

下面把AbstractList里面的主要内容列出来:

从代码中可以看到,其实ArrayList重载了很多东西。除了在最基本的增删改查方法作了实现外,addAll方法也用了System.arraycopy代替了循环的add,Iterator的next()方法也用了直接针对elementData的遍历代替了上层的get(),所以ArrayList在总体上,比AbstractList提高了很多效率。进一步说明,AbstractList并没有规定其中的数据的存放方式,而是提供了一个更通用的接口,所以其中的get、set、add、remove都没有具体实现。但其中有一点有意思的地方是:get采用了abstract的方式修饰,并没有给出默认实现,而set、add、remove却有一个抛出异常的默认实现。这似乎在说明,get在之后是必须实现的,而set、add、remove在之后可以在不需要的时候不必管它,它自会抛出异常。也就是说,在AbstractList中,根据index的set、add、remove不是必须实现的。

AbstractList的equals则是比较其中的每个元素是否equals,hashCode则是31倍的原hashCode加上下一个元素的hashCode作为新的hashCode。至于removeAll和retainAll等等,则已经在AbstractCollection类中被实现。

Post Footer automatically generated by wp-posturl plugin for wordpress.

{ Leave a Reply ? }

  1. 揭英泽

    沙发

  2. 蒋子凡

    arraycopy这个方法的实现是在.class文件里看的吗

  3. synapse5

    很好,收藏了!

  4. 歪妖内涵网

    虽然不懂在说什么,但看起来貌似很厉害的样子

  5. 最励志官网

    很好的网站,赞一个,加油!

  6. 爱奇趣分享网

    路过,留个脚印,网站很棒!

  7. 笑话大全

    好久没来了,过来转转

Leave a Reply

Your email address will not be published. Required fields are marked *