微信号:laoma_shuo

介绍:从入门到高级; 深入浅出; 老马和你一起探索编程及计算机技术的本质; 篇篇原创; 用心写作.

(54) 剖析Collections - 设计模式 / 计算机程序的思维逻辑

2016-11-07 18:10 老马

查看历史文章,请点击上方链接关注公众号。



上节我们提到,类Collections中大概有两类功能,第一类是对容器接口对象进行操作,第二类是返回一个容器接口对象,上节我们介绍了第一类,本节我们介绍第二类。


第二类方法大概可以分为两组:

  1. 接受其他类型的数据,转换为一个容器接口,目的是使其他类型的数据更为方便的参与到容器类协作体系中,这是一种常见的设计模式,被称为适配器

  2. 接受一个容器接口对象,并返回一个同样接口的对象,目的是使该对象更为安全的参与到容器类协作体系中,这也是一种常见的设计模式,被称为装饰器(不过,装饰器不一定是为了安全)。


下面我们就来介绍这两组方法,以及对应的设计模式。


适配器

适配器就是将一种类型的接口转换成另一种接口,类似于电子设备中的各种USB转接头,一端连接某种特殊类型的接口,一段连接标准的USB接口。Collections类提供了几组类似于适配器的方法:

  • 空容器方法:类似于将null或"空"转换为一个标准的容器接口对象

  • 单一对象方法:将一个单独的对象转换为一个标准的容器接口对象

  • 其他适配方法:将Map转换为Set等


空容器方法

Collections中有一组方法,返回一个不包含任何元素的容器接口对象,如下所示:

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

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

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

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


分别返回一个空的List, Set, Map和Iterator对象。比如,可以这么用:

List<String> list = Collections.emptyList();
Map<String, Integer> map = Collections.emptyMap();
Set<Integer> set = Collections.emptySet();


一个空容器对象有什么用呢?经常用作方法返回值。比如,有一个方法,可以将可变长度的整数转换为一个List,方法声明为:

public static List<Integer> asList(int... elements)


在参数为空时,这个方法应该返回null还是一个空的List呢?如果返回null,方法调用者必须进行检查,然后分别处理,代码结构大概如下所示:

int[] arr = ...; //从别的地方获取到的arr
List<Integer> list = asList(arr);
if(list==null){
    ...
}else{
    ....
}


这段代码比较啰嗦,而且如果不小心忘记检查,则有可能会抛出空指针异常,所以推荐做法是返回一个空的List,以便调用者安全的进行统一处理,比如,asList可以这样实现:

public static List<Integer> asList(int... elements){
    if(elements.length==0){
        return Collections.emptyList();
    }
    List<Integer> list = new ArrayList<>(elements.length);
    for(int e : elements){
        list.add(e);
    }
    return list;
}


返回一个空的List,也可以这样实现:

return new ArrayList<Integer>();


这与emptyList方法有什么区别呢?emptyList返回的是一个静态不可变对象,它可以节省创建新对象的内存和时间开销。我们来看下emptyList的具体定义:

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


EMPTY_LIST的定义为:

public static final List EMPTY_LIST = new EmptyList<>();


是一个静态不可变对象,类型为EmptyList,它是一个私有静态内部类,继承自AbstractList,主要代码为:

private static class EmptyList<E>
    extends AbstractList<E>
    implements RandomAccess {
    public Iterator<E> iterator() {
        return emptyIterator();
    }
    public ListIterator<E> listIterator() {
        return emptyListIterator();
    }

    public int size() {return 0;}
    public boolean isEmpty() {return true;}

    public boolean contains(Object obj) {return false;}
    public boolean containsAll(Collection<?> c) { return c.isEmpty(); }

    public Object[] toArray() { return new Object[0]; }

    public <T> T[] toArray(T[] a) {
        if (a.length > 0)
            a[0] = null;
        return a;
    }

    public E get(int index) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }

    public boolean equals(Object o) {
        return (o instanceof List) && ((List<?>)o).isEmpty();
    }

    public int hashCode() { return 1; }
}


emptyIterator和emptyListIterator返回空的迭代器,emptyIterator的代码为:

public static <T> Iterator<T> emptyIterator() {
    return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
}


EmptyIterator是一个静态内部类,代码为:

private static class EmptyIterator<E> implements Iterator<E> {
    static final EmptyIterator<Object> EMPTY_ITERATOR
        = new EmptyIterator<>();

    public boolean hasNext() { return false; }
    public E next() { throw new NoSuchElementException(); }
    public void remove() { throw new IllegalStateException(); }
}


以上这些代码都比较简单,就不赘述了。


需要注意的是,EmptyList不支持修改操作,比如:

Collections.emptyList().add("hello");


会抛出异常UnsupportedOperationException。


如果返回值只是用于读取,可以使用emptyList方法,但如果返回值还用于写入,则需要新建一个对象。


其他空容器方法与emptyList类似,我们就不赘述了。它们都可以被用于方法返回值,以便调用者统一进行处理,同时节省时间和内存开销,它们的共同限制是返回值不能用于写入。


我们将空容器方法看做是适配器,是因为它将null或"空"转换为了容器对象。


单一对象方法

Collections中还有一组方法,可以将一个单独的对象转换为一个标准的容器接口对象,如下所示:

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)


比如,可以这么用:

Collection<String> coll = Collections.singleton("编程");
Set<String> set = Collections.singleton("编程");
List<String> list = Collections.singletonList("老马");
Map<String, String> map = Collections.singletonMap("老马", "编程");


这些方法也经常用于构建方法返回值,相比新建容器对象并添加元素,这些方法更为简洁方便,此外,它们的实现更为高效,它们的实现类都针对单一对象进行了优化。比如,我们看singleton方法的代码:

public static <T> Set<T> singleton(T o) {
    return new SingletonSet<>(o);
}


新建了一个SingletonSet对象,SingletonSet是一个静态内部类,主要代码为:

private static class SingletonSet<E>
    extends AbstractSet<E>
{
    private final E element;

    SingletonSet(E e) {element = e;}

    public Iterator<E> iterator() {
        return singletonIterator(element);
    }

    public int size() {return 1;}

    public boolean contains(Object o) {return eq(o, element);}
}


singletonIterator是一个内部方法,将单一对象转换为了一个迭代器接口对象,代码为:

static <E> Iterator<E> singletonIterator(final E e) {
    return new Iterator<E>() {
        private boolean hasNext = true;
        public boolean hasNext() {
            return hasNext;
        }
        public E next() {
            if (hasNext) {
                hasNext = false;
                return e;
            }
            throw new NoSuchElementException();
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    };
}


eq方法就是比较两个对象是否相同,考虑了null的情况,代码为:

static boolean eq(Object o1, Object o2) {
    return o1==null ? o2==null : o1.equals(o2);
}


需要注意的是,singleton方法返回的也是不可变对象,只能用于读取,写入会抛出UnsupportedOperationException异常。


其他singletonXXX方法的实现思路是类似的,返回值也都只能用于读取,不能写入,我们就不赘述了。


除了用于构建返回值,这些方法还可用于构建方法参数。比如,从容器中删除对象,Collection有如下方法:

boolean remove(Object o);

boolean removeAll(Collection<?> c);


remove方法只会删除第一条匹配的记录,removeAll可以删除所有匹配的记录,但需要一个容器接口对象,如果需要从一个List中删除所有匹配的某一对象呢?这时,就可以使用Collections.singleton封装这个要删除的对象,比如,从list中删除所有的"b",代码如下所示:

List<String> list = new ArrayList<>();
Collections.addAll(list, "a", "b", "c", "d", "b");
list.removeAll(Collections.singleton("b"));
System.out.println(list);


其他方法

除了以上两组方法,Collections中还有如下适配器方法:

//将Map接口转换为Set接口

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

//将Deque接口转换为后进先出的队列接口

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

//返回包含n个相同对象o的List接口

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


这些方法实际用的相对比较少,我们就不深入介绍了。


装饰器

装饰器接受一个接口对象,并返回一个同样接口的对象,不过,新对象可能会扩展一些新的方法或属性,扩展的方法或属性就是所谓的"装饰",也可能会对原有的接口方法做一些修改,达到一定的"装饰"目的。


Collections有三组装饰器方法,它们的返回对象都没有新的方法或属性,但改变了原有接口方法的性质,经过"装饰"后,它们更为安全了,具体分别是写安全、类型安全和线程安全,我们分别来看下。


写安全

这组方法有:

public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c)

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

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

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

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

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


顾名思义,这组unmodifiableXXX方法就是使容器对象变为只读的,写入会抛出UnsupportedOperationException异常。为什么要变为只读的呢?典型场景是,需要传递一个容器对象给一个方法,这个方法可能是第三方提供的,为避免第三方误写,所以在传递前,变为只读的,如下所示:

public static void thirdMethod(Collection<String> c){
    c.add("bad");
}

public static void mainMethod(){
    List<String> list = new ArrayList<>(Arrays.asList(
            new String[]{"a", "b", "c", "d"}));
    thirdMethod(Collections.unmodifiableCollection(list));
}


这样,调用就会触发异常,从而避免了将错误数据插入。


这些方法是如何实现的呢?每个方法内部都对应一个类,这个类实现了对应的容器接口,它内部是待装饰的对象,只读方法传递给这个内部对象,写方法抛出异常。我们以unmodifiableCollection方法为例来看,代码为:

public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
    return new UnmodifiableCollection<>(c);
}


UnmodifiableCollection是一个静态内部类,代码为:

static class UnmodifiableCollection<E> implements Collection<E>, Serializable {
    private static final long serialVersionUID = 1820017752578914078L;

    final Collection<? extends E> c;

    UnmodifiableCollection(Collection<? extends E> c) {
        if (c==null)
            throw new NullPointerException();
        this.c = c;
    }

    public int size()                   {return c.size();}
    public boolean isEmpty()            {return c.isEmpty();}
    public boolean contains(Object o)   {return c.contains(o);}
    public Object[] toArray()           {return c.toArray();}
    public <T> T[] toArray(T[] a)       {return c.toArray(a);}
    public String toString()            {return c.toString();}

    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private final Iterator<? extends E> i = c.iterator();

            public boolean hasNext() {return i.hasNext();}
            public E next()          {return i.next();}
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }
    public boolean remove(Object o) {
        throw new UnsupportedOperationException();
    }

    public boolean containsAll(Collection<?> coll) {
        return c.containsAll(coll);
    }
    public boolean addAll(Collection<? extends E> coll) {
        throw new UnsupportedOperationException();
    }
    public boolean removeAll(Collection<?> coll) {
        throw new UnsupportedOperationException();
    }
    public boolean retainAll(Collection<?> coll) {
        throw new UnsupportedOperationException();
    }
    public void clear() {
        throw new UnsupportedOperationException();
    }
}


代码比较简单,其他unmodifiableXXX方法的实现也都类似,我们就不赘述了。


类型安全

所谓类型安全是指确保容器中不会保存错误类型的对象。容器怎么会允许保存错误类型的对象呢?我们看段代码:

List list = new ArrayList<Integer>();
list.add("hello");
System.out.println(list);


我们创建了一个Integer类型的List对象,但添加了字符串类型的对象"hello",编译没有错误,运行也没有异常,程序输出为:

[hello]


之所以会出现这种情况,是因为Java是通过擦除来实现泛型的,而且类型参数是可选的。正常情况下,我们会加上类型参数,让泛型机制来保证类型的正确性。但,由于泛型是Java 1.5以后才加入的,之前的代码可能没有类型参数,而新的代码可能需要与老的代码互动。


为了避免老的代码用错类型,确保在泛型机制失灵的情况下类型的正确性,可以在传递容器对象给老代码之前,使用如下方法"装饰"容器对象:

public static <E> Collection<E> checkedCollection(Collection<E> c, 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 <E> Set<E> checkedSet(Set<E> s, Class<E> type)

public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m, Class<K> keyType, Class<V> valueType)

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


使用这组checkedXXX方法,都需要传递类型对象,这些方法都会使容器对象的方法在运行时检查类型的正确性,如果不匹配,会抛出ClassCastException异常。比如:

List list = new ArrayList<Integer>();
list = Collections.checkedList(list, Integer.class);
list.add("hello");


这次,运行就会抛出异常,从而避免错误类型的数据插入:

java.lang.ClassCastException: Attempt to insert class java.lang.String element into collection with element type class java.lang.Integer


这些checkedXXX方法的实现机制是类似的,每个方法内部都对应一个类,这个类实现了对应的容器接口,它内部是待装饰的对象,大部分方法只是传递给这个内部对象,但对添加和修改方法,会首先进行类型检查,类型不匹配会抛出异常,类型匹配才传递给内部对象。以checkedCollection为例,我们来看下代码:

public static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type) {
    return new CheckedCollection<>(c, type);
}


CheckedCollection是一个静态内部类,主要代码为:

static class CheckedCollection<E> implements Collection<E>, Serializable {
    private static final long serialVersionUID = 1578914078182001775L;

    final Collection<E> c;
    final Class<E> type;

    void typeCheck(Object o) {
        if (o != null && !type.isInstance(o))
            throw new ClassCastException(badElementMsg(o));
    }

    private String badElementMsg(Object o) {
        return "Attempt to insert " + o.getClass() +
            " element into collection with element type " + type;
    }

    CheckedCollection(Collection<E> c, Class<E> type) {
        if (c==null || type == null)
            throw new NullPointerException();
        this.c = c;
        this.type = type;
    }

    public int size()                 { return c.size(); }
    public boolean isEmpty()          { return c.isEmpty(); }
    public boolean contains(Object o) { return c.contains(o); }
    public Object[] toArray()         { return c.toArray(); }
    public <T> T[] toArray(T[] a)     { return c.toArray(a); }
    public String toString()          { return c.toString(); }
    public boolean remove(Object o)   { return c.remove(o); }
    public void clear()               {        c.clear(); }

    public boolean containsAll(Collection<?> coll) {
        return c.containsAll(coll);
    }
    public boolean removeAll(Collection<?> coll) {
        return c.removeAll(coll);
    }
    public boolean retainAll(Collection<?> coll) {
        return c.retainAll(coll);
    }

    public Iterator<E> iterator() {
        final Iterator<E> it = c.iterator();
        return new Iterator<E>() {
            public boolean hasNext() { return it.hasNext(); }
            public E next()          { return it.next(); }
            public void remove()     {        it.remove(); }};
    }

    public boolean add(E e) {
        typeCheck(e);
        return c.add(e);
    }
}


代码比较简单,add方法中,会先调用typeCheck进行类型检查。其他checkedXXX方法的实现也都类似,我们就不赘述了。


线程安全

关于线程安全我们后续章节会详细介绍,这里简要说明下。之前我们介绍的各种容器类都不是线程安全的,也就是说,如果多个线程同时读写同一个容器对象,是不安全的。Collections提供了一组方法,可以将一个容器对象变为线程安全的,如下所示:

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

public static <T> List<T> synchronizedList(List<T> list)
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)

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

public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m)
public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)


需要说明的,这些方法都是通过给所有容器方法加锁来实现的,这种实现并不是最优的,Java提供了很多专门针对并发访问的容器类,我们留待后续章节介绍。


小结

本节介绍了类Collections中的第二类方法,它们都返回一个容器接口对象,这些方法代表两种设计模式,一种是适配器,另一种是装饰器,我们介绍了这两种设计模式,以及这些方法的用法、适用场合和实现机制。


至此,关于容器类,我们就要介绍完了,下一节,让我们一起来回顾一下,进行简要总结。



-- 长文连载,未完待续,敬请关注(点击文章头部公众号链接,或公众号搜索"老马说编程"或"laoma_shuo",或长按下图二维码关注)



用心原创,保留所有版权。

 
老马说编程 更多文章 (29) 剖析String / 计算机程序的思维逻辑 (30) 剖析StringBuilder / 计算机程序的思维逻辑 (31) 剖析Arrays / 计算机程序的思维逻辑 (32) 剖析日期和时间 / 计算机程序的思维逻辑 (33) Joda-Time / 计算机程序的思维逻辑
猜您喜欢 异构智能宣布打造最强围棋AI 挑战世界冠军柯洁 iOS最佳实践 PHP 类自动加载机制 怎样才能叫高级程序员? 25行Python代码完成人脸识别