Java _ JDK _ Arrays, LinkedList, ArrayList, Vector 及Stack

时间:2023-03-08 15:56:49

(最近在看JDK源码,只是拿着它的继承图在看,但很多东西不记录仍然印象不深,所以开始记录JDK阅读系列。)

(一)Arrays

  • Arrays比较特殊,直接继承自Arrays -》List(Interface) -》Collection(Interface)。
  • (Maybe因为Java中的数组本身就比较特殊?)
  • 包含一些用来操作数组的一些方法,比如排序,搜索,复制,填充,toString方法等;
    • 搜索使用二分搜索;
    • 排序:使用DualPivotQuickSort中的排序算法,基本是改进版的快速排序,但里面做了很多性能改进。
      • 当数组元素比较少时使用插入排序,或者改进后的插入排序(每次两个元素一起插);
      • 当数组元素较大时才会使用快排,使用两个pivot,将数组划分成四部分:<pivot1, pivot1<x<pivot2, 未排序, >pivot2
      • 整个排序过程看起来有些麻烦,但确实提高了排序性能,下面会写专门一篇排序的(数组排序应该也是Arrays类中的关键及精髓了)

(二)LinkedList

  • 继承关系为:LinkedList -》Abstract Sequential List -》 Abstract List
  • 使用链表的各种操作,其中为了提高效率,类中有first和last变量记录链表的首部和尾部;每个节点都会有前驱和后继;
  • 这里要注意的是序列化的问题:
    • 所有的私有成员变量都标识为transient,表示这些变量不会使用统一的序列化方法,而是由用户自己定制。
    • 序列化与反序列化:对象的序列化是指将Object对象转化为byte序列,反之叫做对象的反序列化
      • 序列化:ObjectOutputStream,  反序列化:ObjectInputStream
      • 序列化的好处:能够自动弥补不同操作系统之间的差异。可以在运行Windows操作系统的计算机上创建一个对象,将其序列化,通过网络将它发送给一台运行Unix系统的计算机,然后在那里能够准确的重新组装,而不必担心数据在不同机器上的表示会不同,也不必关心字节的顺序或者其他任何细节;

(三)Vector

  • 继承关系为:vector -》 List(Interface), RandomAccess(Interface), AbstractList
  • 使用数组存储所有元素;
  • 扩容:可以在构造函数中指定扩容大小;当容量溢出时扩容则为2倍扩;
  • 大部分读写方法都是synchronized,所以是线程安全的。

(四)ArrayList

  • 继承关系为:ArrayList -》 List(Interface), RandomAccess(Interface), AbstractList
  • 扩容:每次扩容为原来的1.5倍
  • 基本如同数组的操作。

(五)Stack

  • 继承关系为:Stack-》Vector
  • 所以使用了vector类的很多方法,然后封装在pop,push,peek等方法中,实现stack的基本要求。