Java容器Collections介绍

    Java类库的集合类层次结构：

      

 

   这个类包含了专门的静态方法来操作或者返回集合。它包含了多种算法来操作集合或者包装器，来返回一个新的特殊的集合和一些其他的东西。如果集合或者类对象提供给的是为null，则这个类的方法都抛出一个NullPoninterException。在这个类中也包含了破坏性的(destructive)算法，这些算法能够修改他们操作的集合，如果这个集合不支持合适的原语改变，比如set方法，将会抛出UnsupportedOperationException异常。如果一个调用没有影响这个集合，这些算法也许不是必须抛出这个异常。例如，在一个已经排好序的不可改变的列表调用sort方法获取将抛出UnsupportedOperation异常。下面将简单介绍一下所含方法的功能及用法，不包含详细分析。

   

    public static <T extends Comparable<? super T>> void sort(List<T> list) {    }

    根据元素的可比较自然顺序将给定的list排位升序。list里的所有元素必须实现Comparable接口。此外，list里的所有原色必须是相互可比较的，比如对于list里的任意元素e1和e2，e1.compareTo(e2)不能抛出ClassCastException。 这个排序确保是稳定的，即相等的元素的顺序将不受排序的影响。给定的list必须是可修改的，但是不是一定需要大小可调整。

    实现小提醒：这个实现是稳定的，适应性的，可迭代的归并排序，当输入的数组是部分有序的需要比n*log(n)更小的比较，当输入的数组是随机顺序的，将是传统归并排序的性能。如果输入的数组是几乎有序的，这个实现需要将近n次比较。临时存储空间从几乎有序的输入数组的一个小的常量变到输入数组是随机顺序的n/2个对象引用。

    针对输入数组的升序和降序这个实现采用平等的优势。也能够在相同输入的不同部分使用升序和降序。它适合于合并两个或者更多已排序的数组：仅仅连接说组然后对结果数组进行排序。

     这个实现将给定的list放入一个数组，对数组进行排序，然后从数组的相关位置重新设置list的每一个元素。这避免了可能会导致对一个链表进行排序的n2*log(n)的性能。

 

根据给定的元素排序规则进行排序，其他的与上说的类似。  

public static <T> void sort(List<T> list, Comparator<? super T> c) {   }

   

public static <T>  int binarySearch(List<? extends Comparable<? super T>> list, T key) {   }     

     利用二分查找算法对在给定的列表中搜索 给定的对象。这个list必须优先于这个方法的调用根据元素的自然比较顺序被排序成升序或者降序。如果它不是已排序的，结果将无法定义。如果这个list包含了多个等给定对象的元素，不会保证哪个将被找到。

     这个方法对对于随机访问需要log(n)的时间复杂度(提供了将近常熟时间的访问)。如果给定的列表没有实现RandomAccess接口，并且很大，这个方法将会给予迭代器进行二分查找，从而将花费O(n)数量级的遍历和O(log n)的元素比较。

    如果元素在给定的list里，调用完成后将返回搜索key的索引，否则将返回插入点。插入点是list中key可以被插入的点。第一个元素的索引要大于key，或者如果list中的所有元素都小于给定的key是list.size()。注意，这保证了返回值大于等于0.

 

 可以根据自定义的比较器进行二分查找

 public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {   }

 

 public static void reverse(List<?> list) {    }

 将给定的list进行逆序。

 

public static void shuffle(List<?> list) {}

使用一个默认的随机源来随机的排列给定的list。所有的排列以将近相等的可能性发生。

 

 public static <T> void fill(List<? super T> list, T obj) { }

 用给定的元素替换给定列表的所有元素。这个方法以线性时间运行。

 

public static <T> void copy(List<? super T> dest, List<? extends T> src) {}

从一个列表拷贝所有元素到另一个列表。在拷贝完成之后，目标list的每个被拷贝元素的索引与源list的索引相同。目标list至少和源list相同。如果更长则目标list的其余元素不受影响。这个方法是线性复杂度的。

 

public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {}

根据元素的自然顺序返回给定集合的最小元素。在集合中的所有元素必须实现Comparable接口。而且集合中的所有元素必须相互可比较，即对于任意的元素e1和e2，e1.compareTo(e2)不能抛出ClassCastException。这个方法迭代整个集合，因此它需要与集合大小成比例的时间。

 

public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {}

给定比较条件取最小元素。

 

 public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) { }

求最大给定集合的最大元素。

 

 public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {  }

根据给定的条件求最大元素。

 

public static void rotate(List<?> list, int distance) {}

        根据给定的距离对给定的list进行旋转。调用这个方法之后，在i处的元素将成为之前在(i-distance)对(list.size()-1)取模处的元素。对于集合中所有的i值都包含在0和list.size()-1之间(这个方法不影响list的大小)。

例如：假设list包含[t,a,n,k,s]，在调用了Collections.rotate(list, 1)之后(或者Collections.rotate(list, -4))，list成为[s,t,a,n,k]。

        注意这个方法通常被用于子表在保存剩余元素的同时在表中移动一个或者多个元素。例如，下面一个常见的例子，将在j处的元素向前移动到k(k必须大于或者等于j)，Conllections.rotate(list.subList(j,k+1),-1)。

为了证实这一点，假设list的元素为[a,b,c,d,e]。将位置为1的元素向前移动两位，用如下调用：

 Collections.rotate(l.subList(1,4),-1)，得到的结果是[a,c,d,b,e]。为了增加向前移动的步数，可以增加移动距离的绝对值。为了向后移动，可以使用一个整数的距离。如果给定的list很小或者实现了RandomAccess接口，这个实现交换第一个元素到它应该去的地方，然后重复交换被替代的元素到它应该在的地方知道一个被替换的还交换到第一个元素。如果需要，这个过程会在连续的两个元素上重复。如果这个list很大，并且没有实现RandomAccess接口，这个实现将根据-distance对size取模把list分成两个子list视图。然后对每个子list视图调用reverse方法，最后在整个list上调用这个方法。

 

public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {}

用另一个值来替换list中所有出现的给定值。更正式的说，用newVal替换list中的每个元素e.如下：

oldVal==null ? e == null :oldVal.equals(e)。这个方法不影响list的大小。

 

public static int indexOfSubList(List<?> source, List<?> target) { }

返回在给定的源list中给定的目标list第一次出现的位置，如果没有出现则返回-1。更正式的说，返回最小的索引i，比如source.subList(i, i+target.size()).equals(target)否则返回-1如果没有这个索引(如果target.size()>source.size())。这个实现使用了暴力法来扫描源list来查找匹配目标list的位置。

 

public static int lastIndexOfSubList(List<?> source, List<?> target) {}

返回给定目标list在给定源list中最后出现的开始位置，如果没有则返回-1。更正式的说，是返回最大的索引i，例如source.subList(i,i+target.size()).equals(target),如果没有这样的索引则返回-1(return -1如果target.size()>source.size())

 

public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {}      无法改变的封装器。返回给定集合的无法返回的视图。这个方法提供给用户容器内部只有“只读”的权限。可以对给定的集合返回的集合进行查询操作，如果尝试去修改返回的集合，不管是直接还是通过迭代器，都会产生UnsupportedOperationException异常。

      返回的集合不会将hashCode和equals操作传递到原始的集合，但是依赖Object的equals和hashCode方法。这是需要的来保存这些操作的约定在原始的集合是一个集合或者是一个list。如果给定的集合是可序列化的则返回的集合也将是可序列化的。

 

public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {}

功能与上面类似。

 

public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {}

功能同上，但是如果给定的list实现了RandomAccess则返回的list也将实现

 

public static <T> List<T> unmodifiableList(List<? extends T> list) {}

功能同上，但是如果给定的list实现了RandomAccess则返回的list也将实现

 

public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m) {}

功能同上，是对map的包装。

 

public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {}

返回对SortedMap的不可变包装。

 

下面是一些同步包装器：

public static <T> Collection<T> synchronizedCollection(Collection<T> c) {}

返回一个依据给定容器的同步(线程安全的)容器。为了保证串行存取，通过返回容器对给定容器的所有存取都是完成的是非常重要的。当通过迭代器遍历它的时候有必要对返回的容器进行手动的同步。如下：

 

Collection c = Collections.synchronizedCollection(myCollection);
     *     ...
     *  synchronized (c) {
     *      Iterator i = c.iterator(); // Must be in the synchronized block
     *      while (i.hasNext())
     *         foo(i.next());
     *  }

 不听取这个建议将可能导致不确定性的问题。返回的容器将不会将hashCode和equals操作传递到原来的容器，但是依赖于Object的equals和hashCode方法。

 

 

static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) {}

功能同上面类似，但是用户可以提供互斥元，或者说锁对象。

 

public static <T> Set<T> synchronizedSet(Set<T> s) {}

static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) {}功能跟上面类似，但是被同步是Set。

 

public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {}

public static <T> List<T> synchronizedList(List<T> list) {}

static <T> List<T> synchronizedList(List<T> list, Object mutex) {}

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {}

public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {}

功能跟上面的类似，但是被同步的是不同的容器。

 

下面是动态类型安全的集合包装：

public static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type) {}

      返回一个给定集合的动态类型安全视图。任何一个类型错误元素的插入操作都将导致一个直接的ClassCastException异常。假如一个集合优先于动态类型安全视图生成的时间包含了没有错误的类型元素，那么所有随后对集合的访问都通过视图来发生，它保证了集合没有包含一个错误类型的元素。

      语言中的泛型机制提供了编译器的类型检查，但是未经检查的类型转换将使这种机制失效。通常这不是一个问题，因为编译器会对这些未受检查的操作进行警告。有时候，只有静态类型检查是不够的。例如，假设一个集合被传递到了第三方类库，类库代码不可避免的会通过插入一个类型错误的元素来破坏集合。

      另一个使用动态类型安全视图的debug。假如一段程序以ClassCastException的异常失败了，指出一个不会正确的类型元素被加入到一个参数化的集合中了。很不幸，这个异常可以发生在错误元素被插入的任何时间，因此，它将提供很少或者没有与真正有问题代码有关的信息。如果问题再次发生，可以通过临时的修改程序来包装集合让它拥有动态类型安全视图从而来快速的确定发生问题的代码，例如下面代码：

 

 Collection<String> c = new HashSet<String>();

  可以被替换为：

 

 

 Collection<String> c = Collections.checkedCollection(
     *         new HashSet<String>(), String.class);

  再次运行程序，在错误类型元素插入到集合的地方将引起失败，清楚的指明出问题代码的位置。一旦问题修复了，被修改的地方就可以返回原来的状态。

 

   由于null被当做是所有引用类型的值，所以返回的集合允许不管原来的集合进行什么操作都可以插入null元素。

 

public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) {}

public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s, Class<E> type) {}

public static <E> List<E> checkedList(List<E> list, Class<E> type) {}

public static <K, V> Map<K, V> checkedMap(Map<K, V> m,Class<K> keyType,  Class<V> valueType) {}

public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m,Class<K> keyType,Class<V> value）{}

以上方法与上面介绍的类型检查功能类似，只是需要检查的容器不同。

 

清空集合的方法：

 public static <T> Iterator<T> emptyIterator() {}

 返回一个没有元素的迭代器，更确切的说是hasNext总是返回false，next总是抛出NoSuchElementException，remove总是抛出IllegalStateException，可以实现这个方法，但是没有必要。这是1.7才提供的方法。

 

public static <T> ListIterator<T> emptyListIterator() {}

public static <T> Enumeration<T> emptyEnumeration() {}

public static final <T> Set<T> emptySet() {}

public static final <T> List<T> emptyList() {}

public static final <K,V> Map<K,V> emptyMap() {}

这些方法的功能与上面介绍的功能相同，只是清空的容器类型不同。

 

单例容器：

public static <T> Set<T> singleton(T o) {}

返回一个包含给定对象的不可变的集合，返回的集合是可序列化的。

 

public static <T> List<T> singletonList(T o) {}

public static <K,V> Map<K,V> singletonMap(K key, V value) {}

这两个方法与上面的功能一样，只是传入的容器不同。

 

其他方法：

public static <T> List<T> nCopies(int n, T o) {}

返回一个包含n个给定对象拷贝的不可变列表。新分配的数据对象是小的(它包含了数据对象的一个引用)。这个方法用在使用List.addAll方法来合并list以扩大list。返回的list是可序列化的。

 

public static <T> Comparator<T> reverseOrder() {}

返回一个强加于反转实现了Comparable接口的一个对象集合的自然顺序的比较器(自然顺序是被对象自己的compareTo方法强加的顺序)。这能够使对一个实现了Comparable接口反转自然顺序的对象的集合排序(或者保持)。例如，假设a是一个字符串的数组。

 

Arrays.sort(a, Collections.reverseOrder());

 这会对数组以字典顺序的反序排序。返回的Coparator是可序列化的。

public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {}

返回一个强制给定比较器顺序反序的一个比较器。如果给定的比较器是null，这个方法就相当于reverseOrder（）。

 

public static <T> Enumeration<T> enumeration(final Collection<T> c) {}

返回一个基于给定集合的枚举。

 

public static <T> ArrayList<T> list(Enumeration<T> e) {}

根据给定枚举的顺序返回一个包含枚举元素的数组列表。这个方法提供了返回枚举的API和需要集合的API的互操作。

 

public static int frequency(Collection<?> c, Object o) {}

返回在给定集合中等于给定对象的元素个数。更正式的说：返回如下这种情况下的元素个数：

(o == null ? e == null : o.equals(e))

 

 public static boolean disjoint(Collection<?> c1, Collection<?> c2) {}

 如果给定的两个集合没有相同的元素则返回true。如果这个方法用到了不遵守通常的集合约定的集合就必须注意了。实现通过遍历一个集合然后在另一个集合看是否包含第一集合的元素(或者使用相等比较)。如果一个集合使用了一个非标准的相等比较(比如SortSet的顺序不是通过equals比较，或者IdntityHashMap的key集合)，这两种集合必须使用相同的飞标准的相等比较，否则这个方法的结果将是没有定义。注意：可以将两个参数都传为相同的集合，这种情况下，如果集合是空的这个方法将返回true。

 

public static <T> boolean addAll(Collection<? super T> c, T... elements) {}

将给定的元素全部添加到给定的集合。被添加的元素可以是一个或者是一个数组。这个便利方法的行为等同于c.addAll(Arrays.asList(elements))，但是这个方法可能比大多数方法运行的更快。当给定的元素时独立的，这个方法提供了一种方便的方法来增加一些元素到一个给定的集合中。例如：

Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");

 

 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {}

           返回一个基于给定map的集合。这个集合保持相同的顺序，并发，执行特点。本质上，这个工厂方法提供了一个与Map实现相关的Set实现。没有必要在已经有与之相关的Set实现的map实现使用这个方法(例如HashMap或者TreeMap)。在这个方法返回的集合的每一次方法调用都会恰好的在原来的map或者是他的keySet视图产生一次方法调用。AddAll方法被实现为在原来map上调用一系列的put调用。当这个方法被调用的时候给定的map必须是空的，在这个方法返回之后不应该被直接访问。如果这个map被创建为空，直接传到这个方法，map中没有应用被保存，这些条件要被保证。

    

public static <T> Queue<T> asLifoQueue(Deque<T> deque) {}

以一个后进先出的队列返回一个双端队列的视图。add方法映射到push，remove映射到pop等。当你想用一个需要队列的方法，但是你需要后进先出的顺序，这个视图就很有用。在这个方法返回结果上的每一个方法调用都会引起原始双端队列的一次方法调用，并伴随着异常。AddAll方法被实现为原始队列上的一系列Deque#addFirst方法。