Java数组与容器类的分析资料

[来源] 达内    [编辑] 达内   [时间]2013-01-04

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

  Java数组与容器类分析资料

  看书的时候思考了一个问题,对于java中的array与list有什么样的区别呢?网上找了一篇文章分享下。

  数组是 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 。

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

  2.使用散列的价值:速度,散列使得查询可以快速进行。散列将 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 的初始化容量。

资源下载