Java集合类库之Collection

下表列出了Java类库中的主要集合类，为了便于区分，这个表里面没有包括线程安全集合。在下表中，以Map结尾的类实现了Map接口，而其它类都实现了Collection接口。

1 ArrayList

ArrayList 内部是一个对象数组，在添加和删除元素时，ArrayList能够自动调整数组容量，把装满的数组移到新建的更大的数组中。

老版本Java中，Vector类也可以实现动态数组，但是在单线程中使用ArrayList更加高效。只有在多线程中才使用Vector。

ArrayList 的容量（capacity）和大小（size）有重要的区别。大小是 ArrayList 对象实际包含的元素个数，它等价于普通数组的 length。容量是 ArrayList 对象内部数组的长度，这个长度总是大于或等于size，并且可以变化。
ArrayList 是AbstractList的子类，实现了Iterable<E>, Collection<E>, List<E>, RandomAccess, Serializable, Cloneable 接口。Collection的add, addAll, remove, removeAll, removeIf, contains, size, isEmpty方法，List的get, set, indexOf, lastIndexOf, subList, iterator, listIterator方法都可以直接用。
从Collection继承来的add方法有返回值，因为Colletion要兼顾Set（不允许重复元素），添加操作可能不会改变Set对象，需要区分true或false。而List中add操作一定成功，除非抛异常或内存用尽。

2 LinkedList

与数组的连续存储不同，链表每个元素都是独立的节点，每个节点还存放着下一个节点的引用。Java里的链表都是双向链表——即每个节点还存放着前驱节点的引用。得益于链表的结构，从链表中间增删元素非常快。
LinkedList 是 AbstractSequentialList 的子类，实现了 Collection<E>, List<E>, Iterable<E>, ``Serializable, Cloneable, Deque<E>, Queue<E>接口。可以在LinkedList上进行队列的操作。
虽然LinkedList也可以像ArrayList一样，用整数索引进行添加，删除，查找，替换的操作，但是每次都要从头开始搜索，效率很低，应该尽量避免使用以索引表示链表中位置的方法。
listIterator 方法返回一个实现了 ListIterator 接口的对象，可以用它来遍历链表元素，参看ListIterator。
LinkedList 拥有的方法和ArrayList基本一样（只不过没有ensureCapacity, trimToSize），下面是一些不一样的

3 HashSet

如果想查看指定的元素，却不记得它的位置，就要在集合里一个一个查找，效率很低。当不需要关心元素的顺序时，可以用散列表来组织数据。散列表存储每个元素的散列码，散列码是一个由数据元素的实例字段算出来的整数。可以用hashCode方法得到这个整数。Java用链表数组实现散列表，每个链表称为桶（bucket）。查找一个元素，要先计算它的散列码，然后对桶的总数取余，余数就是这个元素所在的桶的索引。散列码相同的元素被放到一个桶中。每次添加新元素，要将它与桶里所有元素进行比较，查看对象是否已经存在。最好的情况是，散列码均匀地随机分布，桶的数目也很多，一个桶里只装一个元素，所以添加元素只要比较一次。
Java8开始，桶满时（达到8个元素）从链表变成平衡二叉树，来提高查找的性能。而元素减少到6个时变回来。
当一个散列表中，有75％的桶装填了元素，就会自动对所有元素再次散列，创建一个两倍桶数的散列表。0.75叫做装填因子，是一个默认值。散列表总的桶数默认为16个。
HashSet 是 AbstractSet 的子类，实现了 Iterable<E>, Collection<E>, Set<E>, Serializable, Cloneable 接口。

最后强调一下，HashSet 中的元素没有顺序。

4 TreeSet

TreeSet是一个有序集合，每次向TreeSet对象添加一个元素时，都会自动将其放在正确的序列位置上。因此迭代器总是以有序的方式访问元素。向树集添加元素比较慢，但是在树集中查询元素比在链表中快很多。正如类名一样，TreeSet的排序是用树状数据结构实现的，当前Java使用的是红黑树。

向树集添加的元素必须能够被比较，这些元素要么实现Comparable接口，要么在构造树集时提供一个Comparator对象。 另外，从原则上来说，Set接口约定使用equals方法来判定两个元素是否相等，而TreeSet实际上采用的是compareTo方法或Comparator来判定。因此，为了保持概念上的一致性，应该尽可能保证compareTo 和equals 有同样的相等性规则。还有 hashCode 也要考虑在内。

/** 示例：如果要按字符串长度进行排序，可以定义这样一个类来实现Comparaor接口
 *  它的compare方法返回两个字符串长度的差值
*/
class LengthComparator implements Comparator<String> {
    public int compare(String first, String second) {
        return first.length() - second.length();
    }
}
...
TreeSet<String> ts = new TreeSet<String>(new LengthComparator);

TreeSet 是 AbstractSet 的子类，实现了 Iterable<E>, Collection<E>, Set<E>, SortedSet<E>, NavigableSet<E>, Serializable, Cloneable 接口。NavigableSet 增加了几个查找元素以及反向遍历的方法。

返回一个子集，所有元素小于(当inclusive为true时可以等于) toElement
子集是对源集元素的直接引用！
| | SortedSet tailSet(E fromElement)
NavigableSet tailSet(E fromElement, boolean inclusive) | 返回一个子集，所有元素大于等于fromElement
返回一个子集，所有元素大于(当inclusive为true时可以等于) fromElement
子集是对源集元素的直接引用！ | | SortedSet subSet(E fromElement, E toElement)
NavigableSet subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) | 返回包含两个值之间的元素的集，默认是包含fromElement，不包含toElement；
也可以用boolean参数设定包不包含 |