java集合接口(4)

6、java.util.TreeMap
java.lang.Object
   java.util.AbstractMap
       java.util.TreeMap
所有已实现的接口：Serializable, Cloneable, Map, SortedMap
SortedMap 接口的基于红黑树的实现。此类保证了映射按照升序顺序排列关键字，根据使用的构造方法不同，可能会按照键的类的自然顺序 进行排序（参见 Comparable），或者按照创建时所提供的比较器进行排序。
此实现为 containsKey、get、put 和 remove 操作提供了保证的 log(n) 时间开销。这些算法是 Cormen、Leiserson 和 Rivest 的《Introduction to Algorithms》中的算法的改编。
注意，如果有序映射要正确实现 Map 接口，则有序映射所保持的顺序（无论是否明确提供比较器）都必须保持与等号一致。（请参见与等号一致 的精确定义的 Comparable 或 Comparator。）这也是因为 Map 接口是按照等号操作定义的，但映射使用它的 compareTo（或 compare）方法对所有键进行比较，因此从有序映射的观点来看，此方法认为相等的两个键就是相等的。即使顺序与等号不一致，有序映射的行为仍然是 定义良好的；只不过没有遵守 Map 接口的常规约定。
注意，此实现不是同步的。如果多个线程同时访问一个映射，并且其中至少一个线程从结构上修改了该映射，则其必须 保持外部同步。（结构上修改是指添加或删除一个或多个映射关系的操作；仅改变与现有键关联的值不是结构上的修改。）这一般通过对自然封装该映射的某个对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的不同步访问，如下所示：
     Map m = Collections.synchronizedMap(new TreeMap(...));
由所有此类的“collection 视图方法”所返回的迭代器都是快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就完全失败，而不是冒着在将来不确定的时间任意发生不确定行为的风险。
注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测 bug。
此类是Java Collections Framework 的成员。
从以下版本开始： 1.2
7、java.util.TreeSet
java.lang.Object
   java.util.AbstractCollection
       java.util.AbstractSet
           java.util.TreeSet
所有已实现的接口：Serializable, Cloneable, Iterable, Collection, Set, SortedSet
此类实现 Set 接口，该接口由 TreeMap 实例支持。此类保证排序后的 set 按照升序排列元素，根据使用的构造方法不同，可能会按照元素的自然顺序 进行排序（参见 Comparable），或按照在创建 set 时所提供的比较器进行排序。
此实现为基本操作（add、remove 和 contains）提供了可保证的 log(n) 时间开销。
注意，如果要正确实现 Set 接口，则 set 所维护的顺序（是否提供了显式比较器）必须为与等号一致（请参阅与等号一致 精确定义的 Comparable 或 Comparator）。这是因为 Set 接口根据 equals 操作进行定义，但 TreeSet 实例将使用其 compareTo（或 compare）方法执行所有的键比较，因此，从 set 的角度出发，该方法认为相等的两个键就是相等的。即使 set 的顺序与等号不一致，其行为也是 定义良好的；它只是违背了 Set 接口的常规协定。
注意，此实现不是同步的。如果多个线程同时访问一个 set，而其中至少一个线程修改了该 set，那么它必须 保持外部同步。通常通过对某个自然封装该 set 的对象进行同步来实现此操作。如果不存在此类对象，则 set 就应该使用 Collections.synchronizedSet 方法进行“包装”。此操作最好在创建时进行，以防止对 set 的意外非同步访问：
     SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
此类的 iterator 方法返回的迭代器是快速失败的：如果在迭代器创建后的任意时间修改 set（通过迭代器本身 remove 方法之外的任何其他方式），迭代器将抛出 ConcurrentModificationException。因此，在并发修改时，迭代器将快速而彻底地失败，而不会在以后的不确定时间有出现任意、无法确定行为的危险。
注意，无法保证迭代器的快速失败行为，因为通常来说，不可能在非同步并发修改的情况下提供任何硬性保证。快速失败的迭代器将尽量抛出 ConcurrentModificationException。因此，为了获得其准确性而编写依赖此异常的程序的做法是错误的：迭代器的快速失败行为应当仅用于检测 bug。
8、java.util.HashSet
java.lang.Object
   java.util.AbstractCollection
       java.util.AbstractSet
           java.util.HashSet
所有已实现的接口：
Serializable, Cloneable, Iterable, Collection, Set
直接已知子类：
JobStateReasons, LinkedHashSet
此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证集合的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。
此类为基本操作提供了稳定性能，这些基本操作包括 add、remove、contains 和 size，假定哈希函数将这些元素正确地分布在桶中。对此集合进行迭代所需的时间与 HashSet 实例的大小（元素的数量）和底层 HashMap 实例（桶的数量）的“容量”的和成比例。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
注意，此实现不是同步的。 如果多个线程同时访问一个集合，而其中至少一个线程修改了该集合，那么它必须 保持外部同步。这通常是通过对自然封装该集合的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSet 方法来“包装”集合。最好在创建时完成这一操作，以防止对 HashSet 实例进行意外的不同步访问：
     Set s = Collections.synchronizedSet(new HashSet(...));
此类的 iterator 方法返回的迭代器是快速失败 的：在创建迭代器之后，如果对集合进行修改，除非通过迭代器自身的 remove 方法，否则在任何时间以任何方式对其进行修改，Iterator 都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒将来在某个不确定时间发生任意不确定行为的风险。
注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器在尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误做法：迭代器的快速失败行为应该仅用于检测程序错误。