关于Java集合最被关注的10 个问题

jopen 10年前
 下面是stackoverflow关于Java集合方面讨论最多的几个问题，在这里整理出来供大家参考。

1.关于LinkList和ArrayList
  • ArrayList：内部实现是个数组，其中的元素可以通过index获取。但是，如果一个数组满了的话，我们就必须重新分配一个更大的数组然后把所有元素移动到这个新数组，其时间复杂度为O(n)。添加或删除一个元素时也需要移动数组中的其它元素。这就是ArrayList的缺点。
  • LinkedList：是一个双向链表。因此如果我们要获取中间元素的话，我们就需要从头开始遍历；另一方面，添加或删除一个元素就变得很简单，因为只需要对这个链表本身操作即可。
    总的来说，最坏的情况下两者时间复杂度的对比如下：
                   | 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)
    除了考虑时间复杂度之外，当List比较大时，空间复杂度也不可忽略：
  • LinkList：每个节点还需要额外的两个指针，分别指向前一个节点和下一个节点
  • ArrayList：只需要一个数组

2.最有效移除集合元素的方式
    唯一正确的移除集合元素的方式就是使用Iterator.remove()方法：
Iterator<Integer> itr = list.iterator();  while(itr.hasNext()) {     // do something     itr.remove();  }
下面这种处理方式是错误的，会报出这么一个异常：ConcurrentModificationException 
for(Integer i: list) {    list.remove(i);  }
3.如何将一个List转换成一个int[] 数组？ 最简单的方式就是使用Apache Commons Lang工具包下的ArrayUtils：
int[] array = ArrayUtils.toPrimitive(list.toArray(new Integer[0]));
如果用jdk的话是没有捷径的,注意我们不能使用List.toArray()方法，因为这样得到的是Integer[]，正确的方法应该是：
int[] array = new int[list.size()];  for(int i=0; i < list.size(); i++) {    array[i] = list.get(i);  }
4.如何将int[] 转换成List？ 和上面类似，我们可以使用ArrayUtils工具类：
List list = Arrays.asList(ArrayUtils.toObject(array));
或者依然没有捷径：
int[] array = {1,2,3,4,5};  List<Integer> list = new ArrayList<Integer>();  for(int i: array) {    list.add(i);  }
5.最好的过滤集合的方法？   当然，最方便最好的方式就是使用第三方jar包，比如 Guava or Apache Commons Lang ，这两者都提供了filter()方法。在jdk中，事情就变得没那么简单了（不过Java8已经支持Predicate了），但是在Java8之前，比较通常的方式是我们必须遍历集合中的所有元素：
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 Commons Lang，通过引入一个新的Predicate接口，这是很多高级工程师的方法：
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的最简单的方式有两种方式：
Set<Integer> set = new HashSet<Integer>(list);
Set<Integer> set = new TreeSet<Integer>(aComparator);  set.addAll(list);
7.如何移除ArrayList中的重复元素   和上面方法类似，如果不关心顺序的话：
ArrayList** list = ... // initial a list with duplicate elements  Set<Integer> set = new HashSet<Integer>(list);  list.clear();  list.addAll(set);
如果关心顺序，把上面那个HashSet换成LinkedHashSet即可。 8.给集合排序   给集合排序的实现方法有很多种 1.Collections.sort():进行一次排序 2.PriorityQueue ：始终保持队列的顺序，但是只能从队列的头获取元素 3.TreeSet：始终保持队列的顺序，元素不重复，你可以从最顶端或最低端获取元素，但也不能随机获取元素 9.Collections.emptyList() vs new Instance   上面两个方法都会返回空的List，但是Collections.emptyList()返回的List是不可变的，每次方法调用不会重新创建一个实例，而是复用原来的实例（即单例模式），所以这样效率会高些。 10.Collections.copy   有两种方式复制一个List，第一种：
ArrayList<Integer> dstList = new ArrayList<Integer>(srcList);
第二种是利用Collections.copy()方法：
ArrayList<Integer> dstList = new ArrayList<Integer>(srcList.size());  Collections.copy(dstList, srcList);
那两者有何区别呢？   如果目标集合（dstList）小于源集合，使用Collections.copy()会抛出IndexOutOfBoundsException，那它有什么好处呢？首先它保证运行效率和集合大小线性相关，第二就是可以实现集合的重用。