我要啦免费统计

jdk7源码剖析之标准库(2)—— 从AbstractList到AbstractCollection

由于在上篇文章中,我们已经详细的看过ArrayList的代码以及实现,所以在之后的分析中,对于类似的代码,我们只是给出重点方法的signature,除非在实现方面和ArrayList有很大的不同。

在ArrayList的实现中,除了它继承了AbstractList外还有一点值得在意的是它还实现了一个叫做List的接口。实际上如果我们再去看看其他的集合类,就会发现至少在Collection这一块,带有“Abstract”的类和相应的接口联系的非常紧密。下面我们看看对于ArrayList及其父类AbstractList与AbstractCollection之间的关系。

Deepin-jdk_1

从上图看出,AbstractCollection实现了Collection接口,而AbstractList实现了List接口。我们似乎可以看出来整个Collection在设计时的思路:现在接口中定义若干方法,比如作为一个Collection,就需要增、删、toArray,而作为一个List,还要实现在任意位置增、删、改、查、indexOf、subList,还要有一个iterator实现。而作为最终我们可用的数据结构,我们不会在每次都去实现Collection或List接口,因为其中的大多数的方法的实现都是相同的,所以这时我们就需要AbstractCollection和AbstractList来分别实现部分接口方法,之后在通过继承关系重用这些代码。

既然AbstractList仅仅是一些方法的集合,而并没有给出这个List的实现方式,那么我们就可以猜到类似于ArrayList的数组实现并非是AbstractList的唯一子类。如果我们去查阅sdk,我们就会发现除了ArrayList外,还有LinkedList和Vector也继承了AbstractList。

LinkedList与Vector

Deepin-jdk_2

在LinkedList之前,我们还会看到一个AbstractSequentialList类,这个AbstractSequentialList类其实没什么新鲜的,只不过把整个数据结构的增删改查全部都引用到iterator处,也就是通过iterator的增删改查来实现此数据结构的增删改查,而这个iterator的类型就是ListIterator。到这时我们似乎发现了诡异的一点:在AbstractList中,listIterator的默认实现时依据此类的get、set等方法来实现的,而到了继承AbstractList类的子类AbstractSequentialList中,却恰好反了过来,这个类中的增删改查是通过iterator来的!这样的设计不一致性令人奇怪,不过后来总算还是想通了一些,毕竟这个类就是强调Sequential的,既然是sequential,那么用iterator作为根本实现是理所当然的。

不过我们还会发现,这个LinkedList类不仅继承了AbstractSequentialList类,同时还实现了Deque接口。Deque(Double Ended Queue)从名字上来看也知道是做什么的。所谓double ended,就是一个能从一个List的两端读、取数据的数据结构。我们通过deque的signature也可以看出这一点。所以说,LinkedList似乎是一种更为通用的数据结构,不仅可以实现传统的链表数据结构,似乎还被有意识的包装成了队列的实现。

Deque的signature相对来说用途是比较明确的,其最大特征是没有提供用index来访问一个列表的方法。还有一点是取元素可以用remove或者offer,查看元素element或者peek,区别是前者的方法在Deque为空时会抛出异常,而后者只会返回null。

下面我们就来看LinkedList的一些关键实现:

上面的代码我去掉了大多数显而易见或非关键部分(假设读者已经学过了数据结构:-))。我们发现,之所以在Collection的级别就要定义toArray方法,是为了基础数据结构的构造函数只用。因为当还是一个Collection,我们并无法确定其实现,所以我们就通过toArray方法产生一个和原Collection相等价的数组,之后在使用collection构造另一个collection时,就会利用这个数组来构造了(可以看看没有泛型数组的Java在93行时是多么苦逼)。链表中的节点都是有Node构成的,在get一项时,实际是去查找该项的node的item。

接下来是Vector了。从这篇文章开始的那张图就可以看出来,Vector的整个signature和ArrayList是非常相似的。我原本也以为Vector既然和ArrayList不同但又基于AbstractList和RandomAccess,应该是一种链表实现的类似具有ArrayList功能的东西。但是我们会看到,Vector几乎和ArrayList一模一样,都是采用数组的实现方式,而且其中的方法也和ArrayList差别不大(比如移动数组时用的也是System.arrayCopy方法)。唯一的区别是Vector的所有方法都含有syncronized关键字,也就是对Vector的每一次操作,都会进行同步。所以说,对于Vector来说,效率就成了最大的问题。而且毕竟ArrayList已经在线程安全方面有所保护(还记得上一篇文章中的modCount?而且,如果真的关心线程安全的话,可以使用Collections类中的synchronizedCollection方法来),所以真正用到Vector的地方很少。而Stack也只是对Vector很简单的扩充(增添了push、pop、peak)等方法,用的也不是很多,我们完全可以用LinkedList来代替。(是的,Deque这货竟然也实现了push和pop方法!)

关于Deque这种数据结构,java中还有另一种基于数组的实现方式ArrayDeque,它是继承于AbstractCollection下的。

ArrayDeque的各种操作方式也类似于ArrayList,不过其中有一些比较带有hack性质的位运算。比如上一段代码就是用来找到大于给定的数的最小2的整数次幂的。我们可以看到里面的关键就是每次都把原来的数字右移,并且做或运算,就是为了能够保留最高位的1,并且将剩余所有低位全部置为1,之后再加1,就可以找到一个2的整数次幂了。(更多方法见此处:http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 :))

除了Deque外,AbstractCollection下面还有一个AbstractQueue。AbstractQueue很简单,只是定义了一个普通FIFO的Queue所需要的方法:add、remove、element、clear、addAll,前三者分别对应于Queue这个接口的add、poll、peek方法。
AbstarctQueue毕竟不能直接使用,在jdk中,继承AbstractQueue的只有一个类,就是PriorityQueue,也就是我们数据结构中所熟悉的“堆”。

jdk中的堆也采用了数组实现(事实上大多数的堆都会用数组),其中最重要的两个方法莫过于siftUp和siftDown。siftUp就是将一个元素和其父元素相比较,并将如果此元素“大”一些,则和父元素交换位置,之后再找换过位置后的此元素的父元素,以此类推。而要判断元素的大小,jdk给出了指定和未指定comparator的情况。如果制定了comparator,则用comparator进行比较,否则则直接用元素自己的compareTo方法进行比较(此处必须要求元素实现了comparable接口)。siftDown则是siftUp的逆运算(不过这时需考虑左右child哪个大的问题)。初始化方法heapify则是通过对所有元素进行siftDown实现的。

Set&Map

Deepin-jdk_3

Set也是有iterator的,只不过Set确实不注重顺序。从Set的HashCode方法就可以看出来,和ArrayList中将每个元素都乘以31并右移不同,Set的HashCode就是Set中的每个元素的HashCode相加而成。
进一步查看HashSet、LinkedHashSet以及TreeSet,就会发现它们都是按照HashMap、LinkedHashMap以及TreeMap实现的。所以说要想了解Set,我们必须先跳出AbstractCollection类,去AbstractMap类中一探究竟。

Deepin-jdk_4

看Map的类关系结构就和Set非常相似,都是由AbstractXXX扩展出来HashXXX和TreeXXX,又由HashXXX扩展出LinkedHashXXX。
Map整体上是由Map.Entry构成的,而每个Map.Entry都含有一对key和value。HashMap整体上是把每个Entry都存放在一个名为table的数组中。不过既然是“Hash”Map,那么存放每个Entry的位置也是根据Hash函数来放的(而不是以前的顺序存放)。这就产生了一个问题,我们如何确定开始数组的大小?如果我们以后存放的元素多了,那么我们是否可以扩展这个数组,那么又怎么保证扩展之后的数组仍然能够保持原来的Hash映射?

其实java本来就应经给每个对象提供了一个天然的hash函数,那就是hashCode方法。我们都知道hashCode可以用在==的实现中来判断对象引用的同一性,所以放在同样要求不能有重复key的Map中也是合适不过。但hashCode方法很有可能是用户重写过的,为了避免脑残的hashCode的实现(太多collision),所以java又加了一层hash方法来对对象做二次映射(我也不懂,文档里说这样就可以了,求告知),最后再对新的hash取个模就可以了。(由于在HashMap中,保存Entry的数组长度一定是2的整数次幂,所以就可以用h & (length-1)来代替h % length。所以在HashMap的方法中我们经常会看到类似于hash = hash(a.hashCode())table[indexFor(hash,table.length)]这样的代码。

既然有Hash就会有Collision。每个Entry不仅存放着Key和Value,还有一个Next字段存放着对另一Entry的引用。所以说HashMap是通过链表的形式来解决冲突的。我们看到put方法中,先检查当前是否含有传进来的key,如果有就修改其内容,如果没有就调用addEntry,并且把第一个偏移的i传了进去。在addEntry中,就会将新Entry的next字段设置成table[i].

在扩容时,先会调用resize函数分配新的长度为newCapacity的数组,之后调用transfer讲原来的数据重新迁移映射到新数组中,并且计算出下次扩容时需要的长度newCapacity * loadFactor

有了HashMap,我们也就有了HashSet。因为HashMap的key都是唯一的,恰好符合关于Set的定义。当我们打开源代码的时候,我们也被惊呆了:HashSet其实就是一个HashMap,只不过所有的key被映射成了HashSet中的元素,而Value部分,则干脆是用一个final的new Object()来代替!而对于LinkedHashMap,则是在Entry中添加了before和after这两个对其他Entry的引用来更方便的进行遍历(默认遍历顺序就是添加顺序)。至于主体数据结构则还是HashMap中的数组,否则就没办法hash了啊。LinkedHashSet同理。

而TreeMap则是一种基于红黑树的Map方式(怒复习数据结构)。如果一开始就去看TreeMap的signature,会被直接吓傻。但把数据结构从数组换到树本来就不是一件轻松的事情啊。一个TreeMap在开始保存数据唯一的成员就是一个名字为“root”的Entry引用,这就是我们整棵树的根节点。(鉴于篇幅已经太长,就不贴代码了)。当我们放入一对key-value pair时,它会根据Comparator或者Comparable的比较方法进行比较,向下寻找左子树和右子树,之后再合适的位置修改或插入即可(类似于搜索二叉树)。之后调用fixAfterInsertion()方法,对整个树进行平衡。同样在remove一个节点后,也会调用fixAfterDeletion()进行调节

上面这段代码作者也承认是从CLRS中抄来的(问题是S哪去了?)我再看看红黑树以后再更新这里吧(数据结构是渣啊:()

TreeMap还提供很丰富的接口,比如getCeilingEntry、getFloorEntry、getHigherEntry、getLowerEntry等等。具体实现的方法就不细说了,因为这毕竟更偏向于具体的数据结构的实现,而且新意不大。TreeMap的iterate倒是可以看一下,此时它是根据key的大小来遍历的,所以要寻找某个元素的后继,就是要找到这个元素的右子树的最左节点或者其右侧父节点。

而TreeSet的实现就和HashMap如出一辙,都是借助一个value为固定的一个空Object的Map来实现的。

平时我们经常拿来和HashMap相对比的,还有java.util.Hashtable类。虽然这个类继承了AbstractCollection下面的Dictionary子类,却实现了Map接口,实在让人诧异。不过既然实现了Map接口,那么其实它的功能和HashMap是非常相似的。只不过如果我们去具体观察它的实现,我们就会发现它的hash算法和HashMap不同(似乎也不如HashMap优雅)。而且在调用各种方法时,都采用了Sychronized修饰(有一种Vector的既视感)。

这下我们就分析了AbstractCollection、AbstractMap和Dictionary下面的所有的类。从这两篇文章我们可以感受到,java的类关系似乎比我们设想的要混乱一些。其实这很大程度上是由于历史遗留问题导致的。比如刚才说到的Hashtable,它是从jdk1.0就已经被发明的,而HashMap则是在jdk1.2中引入(类似的问题还有Vector)。因为Hashtable和Hashmap在Sychronization方面代价太大,所以要引入新的类型来替代。但同时又为了向下兼容,所以就保留原来的实现和类关系不变,从而发展成今天这个样子。在下一篇文章中,我打算简单的研究一下jdk从1.0到现在的1.7(或者1.8?)中Collection类的演变历程。

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

{ Leave a Reply ? }

  1. 蒋子凡

    hash方法也被脑残的重写怎么办,为什么不加个final

      • 蒋子凡

        只是单个方法不让重写没问题把

  2. 蒋子凡

    记得以前学这些库时也觉得乱,大多过时的类和方法,swing里也是

  3. synapse5

    博主,请问你那个图是用什么画的?能直接解析 Java 文件中的类吗?

Leave a Reply

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