Java数组和java.util包容器(上)——数组要点整理

学一门编程语言,几乎都要从变量这个概念开始。可当程序变得复杂而庞大的时候,会涉及到很多变量。如果只用变量名来表示这些变量,那代码中可能会到处飞舞着各式各样的变量名称。这就好比,如果一个姓刘的家庭如果有两个孩子,父母会叫名字,比如刘文、刘武,可孩子要是多了,一般就直接叫老大、老二、老三……了。在Java里,能够承载各个类型变量的“容器”主要有自带的数组和各式各样的容器类等,我们这篇主要说说数组。

容器结构

(上图截取自《Thinking in Java》第四版,更新更详细的结构关系可以参看实现的源码)

数组不是Java所特有的,几乎所有编程语言都有自己的数组实现。在Java中,数组本身就是一个class。一个数组是一个类对象。

1. 数组有很多种初始化的方式,在初始化的时候时刻要记得数组本身是一个对象,通常需要new一个这样的对象才行。一种特殊的情况是类似于这段代码的声明时隐式初始化:

        Integer[] a = {new Integer(0),new Integer(0),new Integer(0)};

而这样不行:

        Integer[] a;
        a = {new Integer(0),new Integer(0),new Integer(0)};

2. 多维数组,依次确定各维度长度,同一维度下不同数组可以长度不同

3. 数组和容器类三点区别:效率、类型限定和对于基本类型的处理。

效率肯定是内建的数组效率更高一些。在泛型出来之前,容器类都是存取Object,而数组规定了确定类型。在自动封包解包前,容器类不支持基本类型,而数组支持。

4. 两个和顺序比较有关的接口java.lang.Comparablejava.util.Comparator

两者均支持泛型。顾名思义,前者是“可比较的”,即对象本身要和其它的比,有一个单参数的比较方法。而后者是“比较器”,即本身不参与比较,而是为其它对象提供比较服务,有两个方法,其中比较重要的方法是compare(),返回类型解释和前一个接口一样,都是小了返回负数,相等0,大了返回正数。

5. Arrays提供的方法(fill  equals sort binarySearch)和System.arraycopy()

Arrays提供了丰富的方法,包括sort和binarySearch,binarySearch不必说了,是二分查找,注意需要数组有序。而sort方法的实现占据了Arrays类的很大篇幅,可以简单探讨下其算法采用策略。

Arrays中的排序算法大致是这样一个思路,分类型+分数组长度。Arrays的sort方法针对7个基本类型的数组和Object以及泛型T数组分别给出了多种不同的重载实现。基本类型数组,对于数组长度较短的使用插入排序,而对于长度较大的基本都采用了经过改进的快速排序算法。对象类型排序,对于短数组一样采用了插入排序,而较长的数组则使用了归并排序。对基本类型和对象类型排序算法的不同,个人了解到主要是由于考虑到排序算法的稳定性,快速排序是不稳定的算法,而这对基本类型没什么影响,对于对象类型则不然,故采取了稳定的归并排序算法。

需要注意到的是:

  • 较短和较长数组的区分,Arrays里的方法实现设定了一些特定的阈值常量
  • 对于float和double浮点排序,排序算法做了一些特殊处理,进行了排序初始化处理
  • 在(Oracle)Sun jdk 1.7中,细节上做了进一步修改,分离出DualPivotQuicksort、TimSort和ComparableTimSort几个类,对原来版本的阈值和排序细节有了改进,详细的可以参看最新的jdk源码
  • 后续提到的容器方法类Collections中对List的排序采用了Arrays中的排序算法

数组就简单整理到这。下篇文章会用更多篇幅,对java.util包中的List、Set、Queue和Map做详细整理。

 

此条目发表在 Java, 开发, 计算机技术 分类目录,贴了 , , , , , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>