Useful Java Coding Tips (1)- Collection

原创
2014/07/20 11:09
阅读数 44

Java集合框架相关的类是日常编码经常使用的工具类, 包括Deque, List, Set, Queue和Map等,集合类定义了一系列通用的方法,如add()/put(),contains()/get(), remove()等。下面总结了一些针对Java集合框架操作的小技巧。 

  1. 对List进行遍历,使用Iterator而不要通过下标访问。因为当List的实现是LinkedList,遍历操作会退化成O(n*n);如果在遍历过程中需要知道元素的下标,在循环外定义下标变量。

    private void visitList(List<String> foo) {
            // Bad Practice, Don't do that    
            for (int i = 0; i < foo.size(); i++) {
                String bar = foo.get(i);
            }
        }
  2. 当创建可以自动扩展的集合对象,比如ArrayList和Hashmap,如果它的元素个数是固定的,应该选择包含初始大小的构造方法,这样可以避免add()/put()操作时数组自动扩展/Rehash。一种常见的场景是把某种集合对象的元素复制到另外一种集合对象。

  3. 方法需要返回空的集合对象时,使用Collections.EMPTY_LIST, Collections.EMPTY_MAP, Collections.EMPTY_SET,避免使用new操作创建新的空集合。

    private Map<String, String> copyProperties(Properties foo) {
            if (foo == null || foo.isEmpty()) {
                return Collections.EMPTY_MAP;
            }
    
            Map<String, String> bar = new HashMap<String, String>(foo.size());
            for (Object key : foo.keySet()) {
                bar.put(String.valueOf(key), String.valueOf(foo.get(key)));
            }
    
            return bar;
        }
  4. 如果在遍历集合的过程中需要删除某些元素,需要注意对集合的改变会导致Iterator非法,抛出java.util.ConcurrentModificationException,但是对Iterator调用自身的remove()方法则不会

    private void removeOddBad(List<Integer> foo) {
            int i = 0;
            for (Integer bar : foo) {
                if (bar % 2 != 0) {
                    foo.remove(i);
                }
                i++;
            }
    
        }
    
        private void removeOddGood(List<Integer> foo) {
            Iterator<Integer> bar = foo.iterator();
            while (bar.hasNext()) {
                if (bar.next() % 2 != 0) {
                    bar.remove();
                }
            }
    
        }
  5. 如果要返回一个不允许修改的集合对象,可以使用Collections.unmodifiableXXX()系列方法来封装原始的集合对象,不需要再定制自己的集合类来限制修改操作。

  6. Apache Commons和Google Gauva提供了非常丰富的集合类API, 比如对集合进行取交集,并集,补集,差集,可使用Apache Commons的CollectionUtils;实现In-Process 的LRU Cache可使用Google Gauva的Loading Cache。避免重复发明轮子。

  7. 集合框架的接口有不同的实现,选择哪个实现,首先需要明确业务逻辑对增加,删除,查找的频率,然后基于实现类的底层数据结构,选择对最频繁的操作提供最优时间复杂度的实现。

  8. PriorityQueue是数据结构中堆的实现,往PriorityQueue里添加元素,当元素类型实现了Comparable接口,在默认情况下,PriorityQueue是一个小根堆(堆顶的元素最小),可以通过实现自定义Comparator实现大根堆。

    下面的例子,是一个TOP K问题的实现,给定N个乱序排列的元素,找出顺序排列的最小K个元素(K << N):

    // find the smallest K elements in a given array with N elements
        private void findSmallestElements(List<Integer> list, int k) {
            // define the compare result for integer
            Comparator<Integer> compartor = new Comparator<Integer>() {
                @Override
                public int compare(Integer x, Integer y) {
                    return x.compareTo(y) * -1;
                }
    
            };
    
            PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, compartor);
    
            for (Integer val : list) {
                if (maxHeap.size() == k) {
                    int top = maxHeap.peek();
                    if (val < top) {
                        maxHeap.poll();
                        maxHeap.add(val);
                    }
                } else {
                    maxHeap.add(val);
                }
            }
    
            while (maxHeap.size() > 0) {
                System.out.print(maxHeap.poll() + " ");
            }
    
        }
    
        private void test() {
            int n = 100;
            int k = 10;
    
            List<Integer> list = new ArrayList<Integer>(n);
    
            for (int i = 0; i < n; i++) {
                list.add(i);
            }
    
            // re-arrange the list randomly
            for (int i = 1; i < n; i++) {
                // generate a random position j between [i, n-1]
                int j = (int) Math.random() * (n - 1 - i) + i;
                // swap value at i and j
                int tmp = list.get(i);
                list.set(i, list.get(j));
                list.set(j, tmp);
            }
            // find the smallest 10 elements: {9 8 7 6 5 4 3 2 1 0 }
            findSmallestElements(list, k);
        }


       








展开阅读全文
打赏
0
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部