10.6 关于Java 的collections 十大问题

以下是在*上讨论的Java集合中最受欢迎的问题。 你在查看这些问题之前，最好先查看类层次结构图。

1、什么时候用LinkedList 什么时候用ArrayList

ArrayList 本质是一个数组。它的元素可以通过下标直接访问。但是如果数组满了，新的数组需要被分配，需要从旧的数组移动所有元素到新的数组，这需要耗费O（n）时间。此外，添加或删除元素需要移动数组中的现有元素。这可能是使用ArrayList的最大缺点。
LinkedList 是一个双向链表。因此，要访问中间元素，必须从链表的头进行搜索，另一方面，在添加和删除元素的时候，只需要更改链表指向，所以速度更快。
总之，时间复杂度比较的最坏情况如下：

method	Arraylist	LinkedList
get(index)	O(1)	O(n)
add(E)	O(n)	O(1)
add(E, index)	O(n)	O(n)
remove(index)	O(n)	O(n)
Iterator.remove()	O(n)	O(1)
Iterator.add(E)	O(n)	O(1)

在运行期间，如果是大型列表需要考虑内存的使用情况。在LinkedList中，每个节点至少需要两个额外的指针来链接前一个元素和下一个元素，而在ArrayList中，只需要一个元素数组。

2、在迭代过程中有效地删除元素

在迭代时修改集合的唯一正确方法是使用iterator.remove(),比如：

Iterator<Integer> itr = list.iterator();
while(itr.hasNext()) {
   // do something
   itr.remove();
}

一个最常见的错误代码如下：

for(Integer i: list) {
  list.remove(i);
}

你在运行上面代码的时候，会得到一个叫做ConcurrentModificationException的异常。这是因为在遍历列表的时候生成一个迭代器，但是iterator.remove()更改了列表。在Java中不准许在另外一个线程迭代集合的时候，另一个线程修改它。

3、如何把List转成int []

最简单的方法是使用Apache Commons Lang Library 进行转换。

int [] arry = ArrayUtils.toPrimitive(list.toArray(new Integer[0]);

在JDK中，没有捷径可走，你不能用List.toArray()，因为这样将把List转换成Integer[],正确的方法如下：

int[] array = new int[list.size()];
for(int i=0; i < list.size(); i++) {
  array[i] = list.get(i);
}

4.如何将int []转换为List？

最简单的方法可能仍然是在Apache Commons Lang库中使用ArrayUtils，如下所示。
List list = Arrays.asList(ArrayUtils.toObject(array));
在JDK中，如下：

int [] array = {1,2,3,4,5};
List <Integer> list = new ArrayList <Integer>（）;
for（int i：array）{
  list.add（ⅰ）;
}

5.过滤集合的最佳方法是什么？

同样，您可以使用第三方软件包，如Guava或Apache Commons Lang来完成此功能。 两者都提供了filter（）方法（在Guava的Collections2和Apache的CollectionUtils中）。 filter（）方法将返回与给定Predicate匹配的元素。

在JDK中，事情变得更加困难。 一个好消息是，在Java 8中，将添加Predicate。 但是现在你必须使用Iterator来遍历整个集合。

Iterator<Integer> itr = list.iterator();
while(itr.hasNext()) {
   int i = itr.next();
   if (i > 5) { // filter all ints bigger than 5
      itr.remove();
   }
}

当然，你可以通过引入一个新的界面谓词来模仿Guava和Apache所做的事情。 这也可能是大多数高级开发人员所做的。

public interface Predicate<T> {
   boolean test(T o);
}
 
public static <T> void filter(Collection<T> collection, Predicate<T> predicate) {
    if ((collection != null) && (predicate != null)) {
       Iterator<T> itr = collection.iterator();
          while(itr.hasNext()) {
            T obj = itr.next();
            if (!predicate.test(obj)) {
               itr.remove();
            }
        }
    }
}

然后我们可以这样运用下面代码：

filter(list, new Predicate<Integer>() {
    public boolean test(Integer i) { 
       return i <= 5; 
    }
});

6、把List转成Set最简单方法

有两种方法可以这样做，具体取决于您希望如何定义。 第一段代码将列表放入HashSet。 然后主要通过hashCode（）识别复制。 在大多数情况下，它会起作用。 但是如果需要指定比较方式，最好使用第二段代码来定义自己的比较器。

Set<Integer> set = new HashSet<Integer>(list);
Set<Integer> set = new TreeSet<Integer>(aComparator);
set.addAll(list);

7.如何从ArrayList中删除重复的元素？

这个问题与上述问题密切相关。
如果您不关心ArrayList中元素的排序，一种聪明的方法是将列表放入一个集合中以删除重复，然后将其移回列表。 这是代码

ArrayList ** list = ... //初始化具有重复元素的列表
Set<Integer> set = new HashSet <Integer>（list）;
list.clear（）;
list.addAll（set）;

如果您关心排序，可以通过将列表放入标准JDK中的LinkedHashSet来保留顺序。

8.排序集合

有几种方法可以在Java中维护已排序的集合。它们都提供自然排序的集合或指定的比较器。通过自然排序，您还需要在元素中实现Comparable接口。

Collections.sort（）可以对List进行排序。正如javadoc中指定的那样，这种类型是稳定的（稳定的即相同元素的位置顺序保持不变），并保证n log（n）性能。
PriorityQueue提供有序队列。 PriorityQueue和Collections.sort（）之间的区别在于，PriorityQueue始终维护一个订单队列，但您只能从队列中获取head元素。您不能随机访问其元素，如PriorityQueue.get（4）。
如果集合中没有重复，TreeSet是另一种选择。与PriorityQueue相同，它始终维护有序集。您可以从TreeSet中获取最低和最高元素。但是你仍然无法随机访问它的元素。
简而言之，Collections.sort（）提供了一次性有序列表。 PriorityQueue和TreeSet始终维护有序集合，代价是没有元素的索引访问。

9. Collections.emptyList（）vs new instance()

同样的问题适用于emptyMap（）和emptySet（）。
两个方法都返回一个空列表，但Collections.emptyList（）返回一个不可变的列表。 这意味着您无法将新元素添加到“空”列表中。 在后台，每次调用Collections.emptyList（）实际上都不会创建空列表的新实例。 相反，它将重用现有的空实例。 如果您在设计模式中熟悉Singleton，您应该知道我的意思。 因此，如果频繁调用，这将为您提供更好的性能。(不过这种又有何用那？空列表没办法添加？)

10.Collections.copy

有两种方法可以将源列表复制到目标列表。 一种方法是使用ArrayList构造函数
ArrayList <Integer> dstList = new ArrayList <Integer>(srcList);
另一种是使用Collections.copy()（如下所示）。 注意第一行，我们至少与源列表一样分配列表，因为在集合的javadoc中，它表示目标列表必须至少与源列表一样长。

ArrayList <Integer> dstList = new ArrayList <Integer>（srcList.size（））;
Collections.copy(dstList，srcList);

两种方法都是浅拷贝。 那么这两种方法有什么区别呢？
首先，即使dstList没有足够的空间来包含所有srcList元素，Collections.copy（）也不会重新分配dstList的容量。 相反，它将抛出IndexOutOfBoundsException。
人们可能会质疑它是否有任何好处。 一个原因是它保证了方法在线性时间内运行。 当你想重用数组而不是在ArrayList的构造函数中分配新内存时，它也适用。
Collections.copy（）只能接受List作为源和目标，而ArrayList接受Collection作为参数，因此更通用。