Java编程思想（十四）

第17章 容器深入探究

之前我们在第11章里面介绍过容器，分两类，Collection&Map，其中 Collection包括 List/Set/Queue等。
这一章是在之前介绍容器的基础知识之上，从底层实现的角度来对容器进行讲解。

17.2 填充容器

之前在数组相关的小节（16.6），介绍了填充数组的方法，分别用 Arryas.fill()方法 和 生成器的方法来进行填充。
这里对容器也是一样的，填充容器，也下面几种方法。

• Collection.fill()
  该方法使用于List对象，而且只能替换已经存在的 List 元素，不能产生元素。
• Collection.nCopies()
  顾名思义，copy n次。用在构造器中。

public class FillingLists {
    public static void main(String argsp[]){
        List<Integer> list = new ArrayList<Integer>(Collections.nCopies(4,0));
        System.out.println(list);
        Collections.fill(list,1);
        System.out.println(list);
    }
}

除了上面两种之外，在11.3小节我们还给出了 Arrays.asList()方法 & Collections.addAll() 方法。

• Generator 解决方案
  下面还讲了在容器这里 Generator 的应用，由于之前在数组那一章的 Generator 我们没有看，这里也不看，以后用到的时候再看。

17.3 Collection 的功能方法

这里给出了 Collection类中一些常用的方法。

• add()
• clear()
  移除所有元素
• contains()
  包含某个元素，返回 true
• containsAll(Collection<?>)
  包含参数中所有元素，返回 true
• isEmpty()
• iterator()
  迭代器，可以遍历元素，前面说过
• Boolean remove(Object)
  有该元素就移除，做了移除返回 true
• boolean removeAll(Collection<?>)
  移除参数中的所有元素，做了移除返回 true
• Boolean reatainAll(Collection<?>)
  保存参数集合中元素（应用于做交集），只要 Collection 发生了改变就返回 true。
• Object[] toArray()
  将容器变成一个数组。
• <T> toArray(T[] a)
  返回一个数组。跟上一个方法的区别在于这里返回的数组是有类型的，比如这里 写 .toArray(int[] a)，最终返回的是一个 int数组，而上一个方法是 Object 数组。

17.4 可选操作

这里主要说了一下 UnsupportedOperationException这个异常，给了一个例子，当我们 用 Arrays.asList() 方法将一个数组转成 List之后，我们对这个引用再做一些改变其长度的操作，由于底层还是一个数组，所以就会报这样的错。这叫做“使用了不正确的接口实现”。
这里正确的做法，跟我们之前说过的一样，将 Arrays.asList()方法结果作为构造器，这样就会生成新的可以改变大小的底层对象了。

17.5 List的功能方法

这里作者给出了一个例子，说明了一下 List中不常用的一些方法。

17.6 Set 和存储顺序

首先来说，存入Set的每个元素都需要保证唯一性，这是通过 equals() 方法来保证的。
这里 Set 包含了：

• HashSet
  为快速查找而设计的 Set，存入 HashSet 的元素必须定义 hashCode()
• TreeSet
  保持次序的 Set，底层是树结构。使用它可以从 Set中提取有序的序列。元素必须实现 Comparable接口。
• LinkedHashSet
  有 HashSet的查询速度，且内部使用链表维护元素的顺序。在使用迭代器遍历时，会按照元素插入顺序显示。元素也必须定义 hashCode() 方法。

这里在书上给出了关于上述几个点的总结。

总结

这一个小节说的是什么意思呢？在书上作者给出了一段代码，说我们如果定义 一个 SetType，在定义相关的 HashType/ TresType 等这种基于第一种的新的数据结构时，需要重写的方法。
实际上是从底层代码向我们解释了一下，Set/HashSet/TreeSet/LinkedHashSet之间的 关系。

17.7 队列

• 除了并发应用，Queue在Java SE5中仅有的两个实现是 LinkedList & PriorityQueue，二者仅有 排序行为的差异，性能上面没有差异。
• 优先级队列 PriorityQueue 的排列顺序也是通过实现 Comparable 而进行控制的。

这一个小节都是说一些底层的东西。

17.8 理解Map

这里书上给出了一个例子，说明了Map这种关联数组是如何实现的。

17.8.1 性能

HashMap 使用了特殊的值，称作 散列码 Hash Code，来取代对key的缓慢搜索。散列码是“相对唯一” 的、用以代表对象的 int 值，他是通过将该对象的某些信息进行转换而生成的。
hashCode() 是Object类中的方法，因此所有的对象都可以生成散列码。
对 Map 中使用的键的要求与对 Set 中的元素的要求是一样的：

• 任何键都必须有一个 equals() 方法
• 如果键被用于散列 Map，那么它必须还具有恰当的 hashCode() 方法；
• 如果键被用于 TreeMap，那么它必须实现 Comparable

17.9 散列与散列码

HashMap使用 equals() 判断当前的键是否与表中存在的键相同。
如果要使用自己的类作为 HashMap 的键，必须同时重写 hashCode() & equals().

17.9.1 散列概念

使用 hashCode() 的目的在于：想用一个对象来查找另外一个对象。
而Map的实现类使用散列是为了提高查询速度。

散列的价值在于速度：散列使得查询得以快速进行。由于瓶颈位于查询速度，因此解决方案之一就是保持键的排序状态，然后使用Collections.binarySearch()进行查询。
散列则更进一步，它将键保存在某处，以便能够很快找到。存储一组元素最快的数据结构是数组，所以用它来表示键的信息（请小心留意，我是说键的信息，而不是键本身）。但是因为数组不能调整容量，因此就有一个问题：我们希望在Map中保存数量不确定的值，但是如果键的数量被数组的容量限制了，该怎么办？
答案就是：数组并不保存键本身。而是通过键对象生成一个数字，将其作为数组的下标。这个数字就是散列码，由定义在Object中的、且可能由你的类覆盖的hashCode()方法（在计算机科学的术语中称为散列函数）生成。
为解决数组容量固定的问题，不同的键可以产生相同的下标。也就是说，可能会有冲突，即散列码不必是独一无二的。因此，数组多大就不重要了，任何键总能在数组中找到它的位置。

17.9.2 理解散列

综上来说，散列就是把一个对象（key）生成一个数字保存下来（作为数组的下标），然后在查找这个对象时，直接找到这个数字就可以了，所以散列就是为了提高查找速度。
手段就是将一个对象生成的数字与其关联并保存下来（通过数组，成为散列表），而这个生成的数字就是 散列码。生成这个散列码的方法就是散列函数 hashCode().
因此，HashMap中查询一个key的过程就是：

• 首先计算散列码
• 然后使用散列码查询数组（散列码作变数组下标）
• 如果没有冲突，即生成这个散列码的对象只有一个，则散列码对应的数组下标的位置就是这个要查找的元素
• 如果有冲突，则散列码对应的下标所在数组元素保存的是一个list，然后对list中的值使用equals()方法进行线性查询。

因此，不是查询整个list，而是快速地跳到数组的某个位置，只对很少的元素进行比较。这便是HashMap会如此快速的原因。

17.9.3 覆盖 hashCode()

这里书上说了如果编写自己的Map类的实现类，需要覆盖 hashCode() 方法和 equals() 方法。
作者给出了如何编写自己的 hashCode() 散列函数。
这里先不看了。