岁月如哥
人生非梦
posts - 50,comments - 144,trackbacks - 0

Java容器类分析-数组(转载)

数组是Java语言内置的类型,除此之外,Java有多种保存对象引用的方式。Java类库提供了一套相当完整的容器类,使用这些类的方法可以保存和操纵对象。下面分别进行讨论,在研究Java容器类之前,先了解一下Java数组的基本功能和特性

1.  数组的基本特性

         数组与其它种类的容器(List/Set/Map)之间的区别在于效率、确定的类型和保存基本类型数据的能力。数组是一种高效的存储和随机访问对象引用序列的方式,使用数组可以快速的访问数组中的元素。但是当创建一个数组对象(注意和对象数组的区别)后,数组的大小也就固定了,当数组空间不足的时候就再创建一个新的数组,把旧的数组中所有的引用复制到新的数组中。

         Java中的数组和容器都需要进行边界检查,如果越界就会得到一个RuntimeException异常。这点和C++中有所不同,C++中vector的操作符[]不会做边界检查,这在速度上会有一定的提高,Java的数组和容器会因为时刻存在的边界检查带来一些性能上的开销。

         Java中通用的容器类不会以具体的类型来处理对象,容器中的对象都是以Object类型处理的,这是Java中所有类的基类。另外,数组可以保存基本类型,而容器不能,它只能保存任意的Java对象。

         一般情况下,考虑到效率与类型检查,应该尽可能考虑使用数组。如果要解决一般化的问题,数组可能会受到一些限制,这时可以使用Java提供的容器类。

2.  操作数组的实用功能

         在java.util.Arrays类中,有许多static静态方法,提供了操作数组的一些基本功能:

         equals()方法----用于比较两个数组是否相等,相等的条件是两个数组的元素个数必须相等,并且对应位置的元素也相等。

         fill()方法----用以某个值填充整个数组,这个方法有点笨。

         asList()方法----接受任意的数组为参数,将其转变为List容器。

         binarySearch()方法----用于在已经排序的数组中查找元素,需要注意的是必须是已经排序过的数组。当Arrays.binarySearch()找到了查找目标时,该方法将返回一个等于或大于0的值,否则将返回一个负值,表示在该数组目前的排序状态下此目标元素所应该插入的位置。负值的计算公式是“-x-1”。x指的是第一个大于查找对象的元素在数组中的位置,如果数组中所有的元素都小于要查找的对象,则x = a.size()。如果数组中包含重复的元素,则无法保证找到的是哪一个元素,如果需要对没有重复元素的数组排序,可以使用TreeSet或者LinkedHashSet。另外,如果使用Comparator排序了某个对象数组,在使用该方法时必须提供同样的Comparator类型的参数。需要注意的是,基本类型数组无法使用Comparator进行排序。

         sort()方法----对数组进行升序排序。

         在Java标准类库中,另有static方法System.arraycopy()用来复制数组,它针对所有类型做了重载。


3.  数组的排序

         在Java1.0和1.1两个版本中,类库缺少基本的算法操作,包括排序的操作,Java2对此进行了改善。在进行排序的操作时,需要根据对象的实际类型执行比较操作,如果为每种不同的类型各自编写一个不同的排序方法,将会使得代码很难被复用。一般的程序设计目标应是“将保持不变的事物与会发改变的事物相分离”。在这里,不变的是通用的排序算法,变化的是各种对象相互比较的方式。

Java有两种方式来实现比较的功能,一种是实现java.lang.Comparable接口,该接口只有一个compareTo()方法,并以一个Object类为参数,如果当前对象小于参数则返回负值,如果相等返回零,如果当前对象大于参数则返回正值。另一种比较方法是采用策略(strategy)设计模式,将会发生变化的代码封装在它自己的类(策略对象)中,再将策略对象交给保持不变的代码中,后者使用此策略实现它的算法。因此,可以为不同的比较方式生成不同的对象,将它们用在同样的排序程序中。在此情况下,通过定义一个实现了Comparator接口的类而创建了一个策略,这个策略类有compare()和equals()两个方法,一般情况下实现compare()方法即可。

使用上述两种方法即可对任意基本类型的数组进行排序,也可以对任意的对象数组进行排序。再提示一遍,基本类型数组无法使用Comparator进行排序。

Java标准类库中的排序算法针对排序的类型进行了优化——针对基本类型设计了“快速排序”,针对对象设计的“稳定归并排序”。一般不用担心其性能。

Java容器分析--List和Set

容器类可以大大提高编程效率和编程能力,在Java2中,所有的容器都由SUN公司的Joshua Bloch进行了重新设计,丰富了容器类库的功能。

         Java2容器类类库的用途是“保存对象”,它分为两类:

Collection----一组独立的元素,通常这些元素都服从某种规则。List必须保持元素特定的顺序,而Set不能有重复元素。

Map----一组成对的“键值对”对象,即其元素是成对的对象,最典型的应用就是数据字典,并且还有其它广泛的应用。另外,Map可以返回其所有键组成的Set和其所有值组成的Collection,或其键值对组成的Set,并且还可以像数组一样扩展多维Map,只要让Map中键值对的每个“值”是一个Map即可。

1.迭代器

       迭代器是一种设计模式,它是一个对象,它可以遍历并选择序列中的对象,而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象,因为创建它的代价小。

       Java中的Iterator功能比较简单,并且只能单向移动:

(1)    使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时,它返回序列的第一个元素。

(2)    使用next()获得序列中的下一个元素。

(3)    使用hasNext()检查序列中是否还有元素。

(4)    使用remove()将迭代器新返回的元素删除。

Iterator是Java迭代器最简单的实现,为List设计的ListIterator具有更多的功能,它可以从两个方向遍历List,也可以从List中插入和删除元素。

2.List的功能方法

List(interface): 次序是List最重要的特点;它确保维护元素特定的顺序。List为Collection添加了许多方法,使得能够向List中间插入与移除元素(只推荐LinkedList使用)。一个List可以生成ListIterator,使用它可以从两个方向遍历List,也可以从List中间插入和删除元素。

ArrayList: 由数组实现的List。它允许对元素进行快速随机访问,但是向List中间插入与移除元素的速度很慢。ListIterator只应该用来由后向前遍历ArrayList,而不是用来插入和删除元素,因为这比LinkedList开销要大很多。

LinkedList: 对顺序访问进行了优化,向List中间插入与删除得开销不大,随机访问则相对较慢(可用ArrayList代替)。它具有方法addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast(),这些方法(没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用。

3.Set的功能方法

Set(interface): 存入Set的每个元素必须是唯一的,因为Set不保存重复元素。加入Set的Object必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。

HashSet: 为快速查找而设计的Set。存入HashSet的对象必须定义hashCode()。

TreeSet: 保持次序的Set,底层为树结构。使用它可以从Set中提取有序的序列。

LinkedHashSet: 具有HashSet的查询速度,且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时,结果会按元素插入的次序显示。

       HashSet采用散列函数对元素进行排序,这是专门为快速查询而设计的;TreeSet采用红黑树的数据结构进行排序元素;LinkedHashSet内部使用散列以加快查询速度,同时使用链表维护元素的次序,使得看起来元素是以插入的顺序保存的。需要注意的是,生成自己的类时,Set需要维护元素的存储顺序,因此要实现Comparable接口并定义compareTo()方法。



Java容器分析--Map

标准的Java类库中包含了几种类型的Map,它们都拥有同样的基本接口Map,但是行为特性各不相同,主要表现在效率、键值对的保存、元素呈现次序、对象的保存周期和判定键是否等价的策略等方面。

1.Map的功能方法

Map(interface): 维护label和value的关联性,使得可以通过label查找value。

HashMap: Map基于散列表的实现,取代了Hashtable。插入和查询label/value的开销是固定的,并且可以通过构造器设置容量和负载因子,以调整容器的性能。

LinkedHashMap: 在HashMap的基础上做了一些改进,在迭代遍历它时,取得label/value的顺序是其插入的次序,或者是最近最少使用(LRU)的次序,速度上比HashMap要慢一点,但在迭代访问时速度会更快,主要原因是它使用了链表维护内部次序。

TreeMap: 查看label或label/value时,元素会被排序,其次序由Comparable或Comparator决定,因此查询所得到的结果是经过排序的。另外,它是唯一带有subMap()方法的Map具体类,即返回一个子树。它也是SortedMap接口的唯一实现,subMap()方法也是从该接口继承的。

WeakHashMap: Weak Key映射,允许释放映射所指向的对象。当映射之外没有引用指向某个label时,此label可以被垃圾收集器回收。

IdentityHashMap: 使用==代替equals()对label进行比较的散列映射。

2.hashCode()

         当使用标准库中的类Integer作为HashMap的label时,程序能够正常运行,但是使用自己创建的类作为HashMap的label时,通常犯一个错误。

         在HashMap中通过label查找value时,实际上是计算label对象地址的散列码来确定value的。一般情况下,我们是使用基类Object的方法hashCode()来生成散列码,它默认是使用对象的地址来计算的,因此由第一个对象new Apple(5)和第二个对象new Apple(5)生成的散列码是不同的,不能完成正确的查找。通常,我们可以编写自己的hashCode()方法来覆盖基类的原始方法,但与此同时,我们必须同时实现equals()方法来判断当前的label是否与表中存在的label相同。正确的equals()方法满足五个条件:

(1)     自反性。对于任意的x,x.equals(x)一定返回true。

(2)     对称性。对于任意的x和y,如果y.equals(x)返回true,则x.equals(y)也返回true。

(3)     传递性。对于任意的x、y、z,如果有x.equals(y)返回true,y.equals(z)返回true,则x.equals(z)一定返回true。

(4)     一致性。对于任意的x和y,如果对象中用于等价比较的信息没有改变,那么无论调用x.equals(y)多少次,返回的结果应该保持一致,要么一直是true,要么一直是false。

(5)     对任何不是null的x,x.equals(null)一定返回false。

equals()比较的是对象的地址,如果要使用自己的类作为HashMap的label,必须同时重载hashCode()和equals()方法。

使用散列的目的:想要使用一个对象来查找另一个对象。使用TreeSet或TreeMap也能实现此目的。另外,还可以自己实现一个Map,此时,必须提供Map.entrySet()方法来生成Map.Entry对象的Set。

使用散列的价值:速度,散列使得查询可以快速进行。散列将label保存载数组中方便快速查询,因为存储一组元素最快的数据结构是数组,用它来表示label的信息(后面有信息的描述),而不是label本身。通过label对象计算得到一个数字,作为数组的下标,这个数字就是散列码(即前面所述的信息)。该散列码具体是通过定义在基类Object中,可能由程序员自定义的类覆盖的hashCode()方法,即散列函数生成。为了解决数组容量带来的限制,可以使不同的label生成相同的下标,保存在一个链表list中,每一个链表就是数组的一个元素。查询label时就可以通过对list中的信息进行查找,当散列函数比较好,数组的每个位置中的list长度较短,则可以快速查找到数组元素list中的某个位置,提高了整体速度。

散列表中的slot通常称为bucket,为了使散列分步均匀,bucket的值一般取质数。但事实证明,质数实际上并不是散列bucket的理想容量,近来Java散列实现都使用2的幂,具体如何验证以后再续。

3.HashMap的性能因子

容量(capacity): 散列表中bucket的数量。

初始化容量(initial capacity): 创建散列表时bucket的数量。可以在构造方法中指定HashMap和HashSet的初始化容量。

尺寸(size): 散列表中记录的数量。(数组的元素个数,非list中元素总和)

负载因子(load factor): 尺寸/容量。负载因子为0,表示空的散列表,0.5表示半满的散列表。轻负载的散列表具有冲突少,适宜插入与查询的特点,但是使用迭代器遍历会比较慢。较高的负载会减少所需空间大小。当负载达到指定值时,容器会自动成倍地增加容量,并将原有的对象重新分配,存入新的bucket中,这个过程称为“重散列”。

4.重写hashCode()的关键

(1)     对同一个对象调用hashCode()都应该生成同样的值。

(2)     hashCode()方法不要依赖于对象中易变的数据,当数据发生变化时,hashCode()就会生成一个不同的散列码,即产生了一个不同的label。

(3)     hashCode()不应依赖于具有唯一性的对象信息,例如对象地址。

(4)     散列码应该更关心速度,而不是唯一性,因为散列码不必是唯一的。

(5)     好的hashCode()应该产生分步均匀的散列码。在Effective Java(Addison-Wesley 2001)中,Joshua Bloch给hashCode()给出了设计指导,可以参考。

编写正确高效的hashCode()和equals()可以参考Apache的Jakarta Commons项目中的工具。

posted on 2007-08-14 19:56 岁月如歌 阅读(583) 评论(0)  编辑  收藏 所属分类: java

只有注册用户登录后才能发表评论。


网站导航: