Java中集合框架层次结构

Collection

Collection是所有单列集合的父接口

Collection中定义了List和Set通用的方法这些方法可用于操作所有的单列集合

List接口

List接口继承自Collection接口，将实现了List接口的对象称为List集合。

List集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，通过索引来访问集合中的指定元素。

List集合还有一个特点就是元素有序，即元素的存入顺序和取出顺序一致。

ArrayList集合

ArrayList是List接口的一个实现类

ArrayList内部封装了一个长度可变的数组对象，当存入的元素超过数组长度时，ArrayList会在内存中分配一个更大的数组来存储这些元素。

可以将ArrayList集合看作一个长度可变的数组

ArrayList集合大部分方法都是从Collection和List继承过来的。

add()方法和get()方法用于实现元素的存取。

LinkedList集合

List接口的另一个实现类LinkedList，克服了ArrayList集合在查询元素时速度很快，但在增删元素时效率较低的局限性。

该集合内部维护了一个双向循环链表，链表中的每一个元素都使用引用的方式来记住它的前一个元素和后一个元素，从而可以将所有的元素彼此连接起来。

当插入一个新元素时，只需要修改元素之间的这种引用关系即可，删除一个节点也是如此。

LinkedList集合添加元素和删除元素的过程

LinkedList集合针对增删操作定义的方法

Iterator

Iterator接口也是Java集合框架中的一员。

Collection接口与Map接口主要用于存储元素。

Iterator主要用于迭代访问（即遍历）Collection中的元素，Iterator对象也被称为迭代器。

通过迭代器获取ArrayList集合中的元素时，将元素当做Object类型来看待，如果想得到特定类型的元素，则需要进行强制类型转换。

Iterator使用hasNext()和next()访问集合元素

注意：

Iterator迭代器对集合中的元素进行迭代时，若调用集合对象的remove()方法去删除元素，ConcurrentModificationException异常产生。

异常的原因是集合中删除了元素会导致迭代器预期的迭代次数发生改变，导致迭代器的结果不准确。

JDK5.0新特性——foreach循环

foreach循环是一种更加简洁的for循环，也称增强for循环。

foreach循环用于遍历数组或集合中的元素。

foreach循环不需要获得容器的长度，也不需要根据索引访问容器中的元素，但它会自动遍历容器中的每个元素。

foreach循环遍历集合和数组时，只能访问集合中的元素，不能对其中的元素进行修改。

ListIterator接口

Iterator迭代器提供的hasNext()方法和next()方法实现集合中元素的迭代时，迭代的方向是从集合中的第一个元素向最后一个元素迭代，也就是所谓的正向迭代。

ListIterator迭代器是Iterator的子类，它使迭代方式更加多元化。

Enumeration接口

JDK1.2以前还没有Iterator接口的时候，遍历集合需要使用Enumeration接口，它的用法和Iterator类似。

JDK中提供了一个Vevtor集合，该集合是List接口的一个实现类，用法与ArrayList完全相同，区别在于Vector集合是线程安全的，而ArrayList集合是线程不安全的。在Vector类中提供了一个elements()方法用于返回Enumeration对象，通过Enumeration对象可以遍历该集合中的元素。

Set接口

Set接口简介

Set接口继承自Collection接口，与Collection接口中方法基本一致，并没有对Collection接口进行功能上的扩充，仅比Collection接口更加严格了。

Set接口中元素无序，且元素不重复。

Set接口主要有两个实现类：HashSet和TreeSet。

HashSet根据对象的哈希值来确定元素在集合中的存储的位置，具有良好的存取和查找性能。

TreeSet以二叉树的方式来存储元素，可以实现对集合中的元素进行排序。

HashSet集合

HashSet是Set接口的一个实现类。

HashSet存储的元素是不可重复的，并且元素都是无序的。

当向HashSet集合中添加一个对象时，首先会调用该对象的hashCode()方法来确定元素的存储位置，然后再调用对象的equals()方法来确保该位置没有重复元素。

为保证HasheSet正常工作，存入对象时需要重写Object类中的hashCode()和equals()方法。

重写hashCode()方法 的基本规则：

在程序运行过程中，同一个对象多次调用hashCode()方法应返回相同的值。

当两个对象通过equals()方法比较返回true时，则它们的hashCode()方法返回值也应相等 。

对象中用作equals()方法比较标准的实例变量，都应该用于计算hashCode值。

TreeSet集合

TreeSet是Set接口的实现类，它内部采用平衡二叉树来存储元素，此结构可以保证TreeSet集合中没有重复的元素，并且可以对元素进行排序。

所谓二叉树就是说每个节点最多有两个子节点的有序树，每个节点及其子节点组成的树称为子树，通常左侧的子节点称为“左子树”，右侧的节点称为“右子树”，其中左子树上的元素应小于它的根结点，而右子树上的元素应大于它的根结点。

二叉树中元素的存储过程

假设向集合中存入8个元素，依次为13、8、17、17、1、11、15、25，在集合中的存储结构会形成一个树状结构。

TreeSet支持两种排序方法：

自然排序

如果把某对象添加到TreeSet，则该对象的类必须实现Comparabe接口，否则程序会抛出异常

TreeSet调用集合元素的compareTo(Object obj)方法比较元素的大小，并将集合元素按升序排列。

定制排序

如果要实现定制排序，如以降序排列，则可以通过Comparator接口实现(重写compare()方法)。

如果要实现定制排序,则需要在创建TreeSet集合对象时，提供一个Comparator对象与该TreeSet集合关联，由该Comparator对象负责集合元素的排序。