Java认证之Java数组与容器类的分析资料（3）

会计考友

Java认证之Java数组与容器类的分析资料（3）
  O1 X) A; f" a4 G. N& ^2.List 的功能方法
0 @* v) B) U+ G  e/ S! n　　List（interface）： 次序是 List 最重要的特点；它确保维护元素特定的顺序。 List 为 Collection 添加了许多方法，使得能够向 List 中间插入与移除元素 （ 只推荐 LinkedList 使用 ） 。一个 List 可以生成 ListIterator ，使用它可以从两个方向遍历 List ，也可以从 List 中间插入和删除元素。
' f: ^9 z/ w1 Q( f5 z+ l　　ArrayList： 由数组实现的 List 。它允许对元素进行快速随机访问，但是向 List 中间插入与移除元素的速度很慢。 ListIterator 只应该用来由后向前遍历 ArrayList ，而不是用来插入和删除元素，因为这比 LinkedList 开销要大很多。
　　LinkedList： 对顺序访问进行了优化，向 List 中间插入与删除得开销不大，随机访问则相对较慢 （ 可用 ArrayList 代替 ） 。它具有方法 addFirst（） 、 addLast（） 、 getFirst（） 、 getLast（） 、 removeFirst（） 、 removeLast（） ，这些方法 （ 没有在任何接口或基类中定义过 ） 使得 LinkedList 可以当作堆栈、队列和双向队列使用。
　　3.Set 的功能方法
6 S% G3 s) C. ~* Z4 d, w0 @9 F/ J　　Set （interface）： 存入 Set 的每个元素必须是唯一的，因为 Set 不保存重复元素。加入 Set 的 Object 必须定义 equals（） 方法以确保对象的唯一性。 Set 与 Collection 有完全一样的接口。 Set 接口不保证维护元素的次序。
/ X& `. w6 W& @1 s7 c4 EHashSet： 为快速查找而设计的 Set 。存入 HashSet 的对象必须定义 hashCode（） 。
　　TreeSet： 保持次序的 Set ，底层为树结构。使用它可以从 Set 中提取有序的序列。
* Z; i9 q* w6 d. h: |9 O　　LinkedHashSet： 具有 HashSet 的查询速度，且内部使用链表维护元素的顺序 （ 插入的次序 ） 。于是在使用迭代器遍历 Set 时，结果会按元素插入的次序显示。
　　HashSet 采用散列函数对元素进行排序，这是专门为快速查询而设计的； TreeSet 采用红黑树的数据结构进行排序元素； LinkedHashSet 内部使用散列以加快查询速度，同时使用链表维护元素的次序，使得看起来元素是以插入的顺序保存的。需要注意的是，生成自己的类时， Set 需要维护元素的存储顺序，因此要实现 Comparable 接口并定义 compareTo（） 方法。
　　Java 容器分析--Map
7 _8 k; N, {& x/ {6 l) U' x' h　　标准的Java 类库中包含了几种类型的 Map ，它们都拥有同样的基本接口 Map ，但是行为特性各不相同，主要表现在效率、键值对的保存、元素呈现次序、对象的保存周期和判定键是否等价的策略等方面。
. T5 O9 ^/ m0 s5 y2 O5 J　　1.Map 的功能方法
　　Map（interface）： 维护 label 和 value 的关联性，使得可以通过 label 查找 value 。
: k+ o( ]1 z1 s& I　　HashMap： Map 基于散列表的实现，取代了 Hashtable 。插入和查询 label/value 的开销是固定的，并且可以通过构造器设置容量和负载因子，以调整容器的性能。
* K) C/ x9 k) m* i+ h) _( g　　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 时，通常犯一个错误。
& j# u  O& c! w$ Y& I& H　　在 HashMap 中通过 label 查找 value 时，实际上是计算 label 对象地址的散列码来确定 value 的。一般情况下，我们是使用基类 Object 的方法 hashCode（） 来生成散列码，它默认是使用对象的地址来计算的，因此由第一个对象 new Apple（5） 和第二个对象 new Apple（5） 生成的散列码是不同的，不能完成正确的查找。通常，我们可以编写自己的 hashCode（） 方法来覆盖基类的原始方法，但与此同时，我们必须同时实现 equals（） 方法来判断当前的 label 是否与表中存在的 label 相同。正确的 equals（） 方法满足五个条件：
　　（1） 自反性。对于任意的 x ， x.equals（x） 一定返回 true 。
  V0 e/ I- [- {　　（2） 对称性。对于任意的 x 和 y ，如果 y.equals（x） 返回 true ，则 x.equals（y） 也返回 true 。
! F4 d5 K4 O) ^! S0 O　　（3） 传递性。对于任意的 x 、 y 、 z ，如果有 x.equals（y） 返回 true ， y.equals（z） 返回 true ，则 x.equals（z） 一定返回 true 。
( b3 ~. D' z$ j8 a" H4 _　　（4） 一致性。对于任意的 x 和 y ，如果对象中用于等价比较的信息没有改变，那么无论调用 x.equals（y） 多少次，返回的结果应该保持一致，要么一直是 true ，要么一直是 false 。
4 c' i' ^8 p+ A7 T* \9 P8 ^) p5 @　　（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 中的某个位置，提高了整体速度。
( G# _, e$ U7 g　　散列表中的 slot 通常称为 bucket ，为了使散列分步均匀， bucket 的值一般取质数。但事实证明，质数实际上并不是散列 bucket 的理想容量，近来 Java 散列实现都使用 2 的幂，具体如何验证以后再续。