Android的数据结构1——List

2018-05-02 本文已影响26人 MinuitZ

一个 List 是一个元素有序的、可以重复、可以为 null 的集合。
Java 集合框架中最常使用的几种 List 实现类是 ArrayList，LinkedList 和 Vector。

集合

在各种 List 中，最好的做法是以 ArrayList 作为默认选择。当插入、删除频繁时，使用 LinkedList，Vector 总是比 ArrayList 慢，所以要尽量避免使用它，具体实现后续文章介绍。

ArrayList

ArrayList应该是接触集合框架的人第一个遇到的数据结构，记得老师当年把它叫做可变长度的数组，接下来就布置了作业，让大家自己实现可扩展长度的数组型数据结构。
当时的我是这么做的：
首先需要几个标记：总长度totalNum，当前长度currentNum。然后总长度总要比实际长度的最大值大于一，当等于1时自动扩容（其实就是new一个新的数组并拷贝）。作为课代表的自己觉得也是有点稳。

今天我们来看看ArrayList是怎么实现的。

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

构造函数中，将elementData初始化为空，这个elementData就是其中的一个数组了object[] elementData>，无参构造方法构造的ArrayList的容量默认为10。
private static final int DEFAULT_CAPACITY = 10
接下来我们直接看add()方法.

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

在执行add方法时, 首先调用了ensureCapacityInternal方法, 我们可以猜到这个方法是用于数组的扩充的, 接下来才将传入的元素放到size处。
跟进ensureCapacityInternal，在方法中有各种的判断，最后我们可以看到这样的代码

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

这里的grow函数就是实现数组扩容的方法。
我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求，扩容数量为oldCapacity的0.5倍，即右移1位。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
这里的Arrays.copyOf()是复制数组的操作, 会消耗较多的时间

此外ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现。代码如下：

public void trimToSize() {  
   modCount++;  
   int oldCapacity = elementData.length;  
   if (size < oldCapacity) {  
       elementData = Arrays.copyOf(elementData, size);  
   }  
    }

由于elementData的长度会被拓展，size标记的是其中包含的元素的个数。所以会出现size很小但elementData.length很大的情况，将出现空间的浪费。trimToSize将返回一个新的数组给elementData，元素内容保持不变，length和size相同，节省空间。

Vector

和ArrayList不同，Vector中的操作是线程安全的。其方法大多数都含有synchronized 关键字, 在多编程操作是建议使用，但是开销略大
来看看vector的add方法中的增长方式

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

这里的capacityIncrement 为增长因子 , 当增长因子大于0时 , 每次扩充的长度为增长因子 , 当为0是 , 默认扩充为原数组的2倍.

LinkedList

LinkedList 是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于ArrayList.当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比。

双链表的插入操作和删除操作, 相对于数组来说要简单的多 , 只需要挪动两个指针即可，但是改数据结构相比于ArrayList更占用内存，因为需要多出两个指针来作为前指针和后指针来维持数据结构

它还实现了 Queue 接口,该接口比List提供了更多的方法,包括 offer(),peek(),poll()等方法.

当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(即其它线程通过add、remove、clear等方法，改变了modCount的值)；这时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

这种情况经常发生在请求数据之后 , 对数据本身进行新一轮的操作. 如果线程没有主意好的话 , 会抛出异常: ConcurrentModificationException. 以前我直接会在一开始就将数据结构选择为CopyOnWriteArrayList , 待会来看看这个数据结构到底是什么。

CopyOnWriteArrayList

CopyOnWrite容器即写时复制的容器。

通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。
既然是在增删是不会抛出异常，我们来看看它的add方法以及其它会引起数组长度变化的方法都做了什么

public boolean add(E e) {
        synchronized (lock) {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        }
    }

public E remove(int index) {
        synchronized (lock) {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        }
    }

我们可以看到，在添加与移除的方法体中都是用到了synchronized关键字，也就是同一时间，只允许持有锁的线程去执行这段代码，其他线程会被阻塞，这样就达到了线程安全读写List。
在添加的最后都有setArray()方法:

final void setArray(Object[] a) {
        elements = a;
    }

add函数中拷贝了原来的数组并在最后加上了新元素，并调用setArray函数将引用链接到新数组.
其它用法与ArrayList类似，毕竟都是List的实现类。

缺点

内存占用问题。因为CopyOnWrite的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存）。如果这些对象占用的内存比较大，比如说200M左右，那么再写入100M数据进去，内存就会占用300M，那么这个时候很有可能造成频繁的Yong GC和Full GC。之前我们系统中使用了一个服务由于每晚使用CopyOnWrite机制更新大对象，造成了每晚15秒的Full GC，应用响应时间也随之变长。
数据一致性问题。CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。

Android的数据结构1——List

ArrayList

Vector

LinkedList

CopyOnWriteArrayList

猜你喜欢

热点阅读