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 的初始化容量。