Collections

Collection的工具类

List sort

调用数组的排序,即Arrays.sort,可以自定义Comparator

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

List binarySearch

对于随机访问的List(如ArrayList)及数据量比较小的非随机访问List(小于5000),采用基于下标的binarySearch,其他(比较大的非随机访问List),采用基于iterator的binarySearch

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        //BINARYSEARCH_THRESHOLD = 5000
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
}

基于下标的binarySearch,和数组的binarySearch很相似:

private static <T>
    int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key)
    {
    int low = 0;
    int high = list.size()-1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable<? super T> midVal = list.get(mid);   //不一定是随机访问的get
        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // 找到
    }
    return -(low + 1);  // 没找到
}

采用基于iterator的binarySearch:

private static <T>
    int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
    {
    int low = 0;
    int high = list.size()-1;
    ListIterator<? extends Comparable<? super T>> i = list.listIterator();

    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable<? super T> midVal = get(i, mid); //Iterator i开始的第mid个元素
        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid;
    }
    return -(low + 1);
}

List reverse

对于随机访问的List(如ArrayList)及数据量比较小的非随机访问List(小于18),采用基于下标的翻转,其他(比较大的非随机访问List),采用基于iterator的翻转

public static void reverse(List<?> list) {
    int size = list.size();
    //REVERSE_THRESHOLD = 18
    if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
            swap(list, i, j);
    } else {
        ListIterator fwd = list.listIterator();
        ListIterator rev = list.listIterator(size);
        for (int i=0, mid=list.size()>>1; i<mid; i++) {
        Object tmp = fwd.next();
            fwd.set(rev.previous());
            rev.set(tmp);
        }
    }
}

List shuffle

List的打乱顺序,需要一个全局的随机数发生器(Random),打乱的逻辑就是将第i个元素和[0, i)之间的随机位置元素交换.对于随机访问List或者大小很小的List(小于5),直接进行交换,对于比较大的非随机访问List,将其转换为数组再进行shuffle过程.

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    //SHUFFLE_THRESHOLD = 5
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

List fill

public static <T> void fill(List<? super T> list, T obj) {
    int size = list.size();
    //FILL_THRESHOLD = 25
    if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
        for (int i=0; i<size; i++)
            list.set(i, obj);
    } else {
        ListIterator<? super T> itr = list.listIterator();
        for (int i=0; i<size; i++) {
            itr.next();
            itr.set(obj);
        }
    }
}

List copy

public static <T> void copy(List<? super T> dest, List<? extends T> src) {
    int srcSize = src.size();
    if (srcSize > dest.size())
        throw new IndexOutOfBoundsException("Source does not fit in dest");
    //COPY_THRESHOLD = 10
    if (srcSize < COPY_THRESHOLD ||
        (src instanceof RandomAccess && dest instanceof RandomAccess)) {
        for (int i=0; i<srcSize; i++)
            dest.set(i, src.get(i));
    } else {
        ListIterator<? super T> di=dest.listIterator();
    ListIterator<? extends T> si=src.listIterator();
        for (int i=0; i<srcSize; i++) {
            di.next();
            di.set(si.next());
        }
    }
}

Collection min max

List rotate

旋转,可以左旋或者右旋,第二参数为正数表示右旋,负数表示左旋. 如list = [t, a, n, k, s],则Collections.rotate(list, 1)之后变为[s, t, a, n, k]. Collections.rotate(list, 1)等效于Collections.rotate(list, -4)

随机访问或者小于100的非随机访问List,采用循环设置的方法.

比较大的非随机访问List采用三次reverse的方法,在编程珠玑中专门介绍了这种方法

public static void rotate(List<?> list, int distance) {
    //ROTATE_THRESHOLD = 100
    if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
        rotate1((List)list, distance);
    else
        rotate2((List)list, distance);
}

private static <T> void rotate1(List<T> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    distance = distance % size;
    if (distance < 0)
        distance += size;
    if (distance == 0)
        return;
    //总共肯定只有size次设置
    for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
        T displaced = list.get(cycleStart);
        int i = cycleStart;
        do {
            i += distance;
            if (i >= size)
                i -= size;
            displaced = list.set(i, displaced);
            nMoved ++;
        } while(i != cycleStart);
    }
}

private static void rotate2(List<?> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    int mid =  -distance % size;
    if (mid < 0)
        mid += size;
    if (mid == 0)
        return;

    reverse(list.subList(0, mid));      //左侧翻转
    reverse(list.subList(mid, size));   //右侧翻转
    reverse(list);                      //全部翻转
}

List replaceAll

List indexOfSubList lastIndexOfSubList

indexOfSubList : target子序列在source序列中第一次出现的位置 lastIndexOfSubList : target子序列在source序列中最后一次出现的位置

unmodifiable系列

指元素不可变更的集合,是对原始集合的一个包装,需要支持原始集合的所有方法. unmodifiableCollection,unmodifiableSet,unmodifiableSortedSet,unmodifiableList等实现原理都是使用内部类,不支持的操作(如List的add,remove等)直接抛出UnsupportedOperationException异常.

static class UnmodifiableList<E> extends UnmodifiableCollection<E>
                      implements List<E> {
    final List<? extends E> list;
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }
    public E remove(int index) {
        throw new UnsupportedOperationException();
    }
    //其他方法
}

synchronized系列

指保证同步的集合,原理是对原始集合的一个包装,另外加上一个mutex,对原始集合每个方法的操作都会用synchronized(mutex)保证同步. synchronizedCollection,synchronizedSet,synchronizedSortedSet,synchronizedList等.

//注意SynchronizedCollection定义了mutex
tatic class SynchronizedCollection<E> implements Collection<E>, Serializable {
    final Collection<E> c;  // Backing Collection
    final Object mutex;     // Object on which to synchronize
    //...
}
static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> {
    final List<E> list;
    public E get(int index) {
        synchronized(mutex) {return list.get(index);}
    }
    public E set(int index, E element) {
        synchronized(mutex) {return list.set(index, element);}
    }
    //...
}

checked系列

获取一个集合的保证类型安全的试图,任何一个试图向集合中插入错误类型的元素会抛出ClassCastException异常实现原理很简单,构造函数需要传入集合及一个类型(Class),每次插入操作是会额外增加一次类型检查的操作.

static class CheckedCollection<E> implements Collection<E>, Serializable {
    final Collection<E> c;
    final Class<E> type;    //支持的类型
    //类型检查
    void typeCheck(Object o) {
        if (!type.isInstance(o))
            throw new ClassCastException("Attempt to insert " +
               o.getClass() + " element into collection with element type "
               + type);
    }
}

static class CheckedList<E> extends CheckedCollection<E> implements List<E>
{
    final List<E> list;

    public E set(int index, E element) {
        typeCheck(element); //类型检查
        return list.set(index, element);
    }

    public void add(int index, E element) {
        typeCheck(element);
        list.add(index, element);
    }
    //...
}

empty系列

EMPTY_LIST, EMPTY_MAP 对get和contain等获取元素操作重写.

singleton系列

值包含一个元素的聚合 SingletonSet, singletonList, singletonMap等

List nCopies

返回一个包含n个o的List, 用一个类CopiesList实现,特制了get等操作

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

Comparator reverseOrder

获取一个比较器的反向比较器,ReverseComparator实现,实现很简单,compare的顺序颠倒一下

private static class ReverseComparator<T>
    implements Comparator<Comparable<Object>>, Serializable {
    public int compare(Comparable<Object> c1, Comparable<Object> c2) {
        return c2.compareTo(c1);
    }
}
private static class ReverseComparator2<T> implements Comparator<T>,
        Serializable
{
    private Comparator<T> cmp;

    ReverseComparator2(Comparator<T> cmp) {
        assert cmp != null;
        this.cmp = cmp;
    }

    public int compare(T t1, T t2) {
        return cmp.compare(t2, t1); //比较顺序颠倒一下
    }
}

Collection frequency

集合中对象出现的次数,支持对象为null

Collection disjoint

判断两个集合是否无交集,即无相同的元素

Collection addAll

AsLIFOQueue

即返回Deque的一个后进先出(Last-in-first-out, Lifo)的视图.

public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
        return new SetFromMap<E>(map);
    }

xiaobaoqiu Blog

Think More, Code Less

Java Collection