亲宝软件园·资讯

展开

Android 数据结构全面总结分析

流浪汉kylin 人气:0

前言

这次算一个总结,我们平时都会用到各种各样的数据结构,但是可能从未看过它们内部是如何去实现的。只有了解了它们内部大概的一个实现原理,才能在不同的场景中能选出最适合这个场景的数据结构。

虽然标题说是Android,但其实有一半是属于java的,由于涉及得比较多,所以打算分篇来写会比较好,我不会把全部的源码都进行分析,主要做的是分析一些能表现这些数据结构的特征。

Collection

一切数据结构的最顶层,是一个接口,继承迭代器Iterable,主要是定义所有数据结构的公共行为,比如说boolean contains(Object o)方法,可能在hashmap用得多,很多人都觉得这个是hashmap才有的方法,其实它是在Collection中定义的,不同的数据结构可以去重写。

AbstractCollection是它的抽象实现类,里面有实现一些基本的行为,还是拿contains方法来说

public boolean contains(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}

其实就是遍历和判断,其它的方法也差不多,都比较简单,就不多说了。

Set和List

这两个也都是接口,抽象的实现分别是AbstractSet和AbstractList。最简单来说,它们两个的区别就在于是否有重复元素,和“宏观”上的有序和无序(因为TreeSet红黑树是有序的,所以不能说全部Set都是无序),举个例子,比如说equest方法,两边的实现就不同。

先看AbstractSet的

public boolean equals(Object o) {
    ......
    Collection&lt;?&gt; c = (Collection&lt;?&gt;) o;
    if (c.size() != size())
        return false;
    try {
        return containsAll(c);
    } catch (ClassCastException unused)   {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
}

可以看到,它其实内部是只要判断到传进来的Set内部的所有元素都能在这个Set中找到一样的就行(包含)。再看看AbstractList

public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;
    ListIterator<E> e1 = listIterator();
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

看得出其实它是作了一个迭代,然后一个一个元素去判断是否相同。光看这两个方法你就知道Set的equest方法只要判断有包含就行,不会在意顺序,而List需要元素的顺序相同。

其他的方法也是,存在一些差异,所以很多人会和你总结Set和List的区别,但是只有当你去了解它的内部实现,你才能更好的感受到这区别是什么。

Queue和Deque

有点基础我们都知道数据结构有栈和队列,一个是后进先出,一个是先进先出。而Queue就是队列,它是一个接口,定义了入队列出队列这些方法。而Deque是一个双向队列,java 这里是可以使用双向队列来实现栈的效果,Deque也是一个接口继承Queue。

这里的内容肯能会有点无聊,但是是比较重要的基础内容。队列定义的Queue方法有入队列的方法add和offer,出队列的方法remove和poll,还有拿队列头的方法element和peek。

可以看到它的操作是有2组,它们的差别是:

所以如果你不了解这些,你只会无脑add,这样就很不好。但其实对于LinkedList来说add()和offer()区别不大。可能区别比较大的地方在你自定义数据结果实现Queue和Deque的时候该怎么处理这两个方法。

说完Queue再简单介绍一下Deque,Deque因为是双向队列,所以它能实现栈和队列。

Map

Mao是另一种数据结构,它独立于Collection,它的是一个接口,它的抽象实现是AbstractMap,它内部是会通过Set来实现迭代器

Set<Map.Entry<K, V>> entrySet();

是和Set有关联的,思想上主要以key-value的形式存储数据,但是具体的实现会交给子类去实现。

上层的数据结构大概就这些,接下来会介绍一些常用的实现类。

ArrayList

我们常用的ArrayList来实现列表,它内部其实就是一个对象数组

// Android-note: Also accessed from java.util.Collections
transient Object[] elementData; // non-private to simplify nested class access
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

添加元素的时候主要就是扩容和添加元素到数组的指定位置

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

数组为空的时候第一次会初始化10的容量

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);
}

然后之后的扩容是旧的容量加旧的容量右移一位,其实就是扩容当前容量的一半(旧版本也是这样吗?不记得了),扩容后会复制当前数组的元素到新的数组中。再看看add到指定位置的操作

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

能看到也有一个System.arraycopy复制数组的操作。所以ArrayList的劣势就体现在这里,复制数组是耗时的操作,频繁的进行复制数组会得不偿失。

懂得他里面的这些实现的话我们就可以在使用的时候进行优化,比如使用的时候初始化定好数组的大小,防止频繁扩容。比如插入、删除这些操作更多的话,我们可以选择使用其它更合适的数据结构。

LinkedList

这东西就厉害了,用得少你会叫它链表,其实它是双向链表,实现我们上面的Deque,能实现的功能挺庞大的。

既然实现Deque,那它就有offer、poll、peek、push、pop、peel这些操作。不会吧不会吧,不会只有人用它的add方法吧。

内部两个结点表示链表头和链表尾(链表在代码中的体现就是结点,比如MessageQueue的Message)

transient Node<E> first;
transient Node<E> last;

功能非常庞大,非常建议没看过源码的人去熟悉一下,因为比较多,我这里就只举几个例子。看看我们常用的add方法

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
Node<E> node(int index) {
    // assert isElementIndex(index);
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

它这里就先做了一步优化处理,查找结点的时候根据下标去决定从头开始查找还是从尾开始查找,看着觉得这操作也没啥好厉害的,我只想说看别人的和自己想的是两码事。

public boolean offer(E e) {
    return add(e);
}

offer其实是调用了add,上面也有说LinkedList的这两个操作一样,但是接口定义的这两个操作的含义是不同的。可以看看到插入操作只是做了节点指针的变化,不会像ArrayList一样每次插入到中间位置都需要数组位置移动。

Vector

Vector就更简单了,内部也是一个Object数组Object[] elementData,可以看看它的add方法

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

看得出出ArrayList的操作一样,只不过加了个synchronized,所以它是线程安全的。

Stack

Stack继承Vector,所以它的操作也是线程安全的。可以看看他的push方法

public E push(E item) {
    addElement(item);
    return item;
}
    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

从这里可以看出,按照栈的思想是后进先出,而它这里是把数组的最后的位置当成栈顶,相应的pop就是拿数组的最后一个元素,然后再移除。而我们用LinkedList实现的栈的效果,是把头当成栈顶(再回顾一下)

public void push(E e) {
    addFirst(e);
}

他们都实现栈的数据结构,但是是用不同的方法去实现的。

ArraySet

这个东西可能平时我们开发用得比较少,但是如果你看源码比较多的话,你会发现android有些地方也是会用到ArraySet或者ArrayMap,Map我打算下篇文章写,这里可以提前说一下,ArraySet我们可以拿去和后面的ArrayMap做比较,他们的实现其实是一样的。

内部是两个数组,一个用来存对象,一个用来存对象的hash

    int[] mHashes;
    Object[] mArray;

我们可以从add方法中具体去看出它的设计思想

public boolean add(E value) {
    final int oSize = mSize;
    final int hash; 
    int index;
    if (value == null) {
        hash = 0;
        index = indexOfNull();
    } else {
        // 根据Object生成它对应的hash
        hash = mIdentityHashCode ? System.identityHashCode(value) : value.hashCode();
        index = indexOf(value, hash);
    }
    index = ~index; // indexOf里面会取反,这里要转回来
    ......
    mHashes[index] = hash;
    mArray[index] = value;
    mSize++;
    return true;
}

我把简单的步骤写出来,就是根据object去计算它的hash,然后再根据hash去计算数组的下标index,把object和hash分别存到对应数组的对应位置,所以这两个数组的元素是对应的。indexOf里面主要的操作是int index = binarySearch(mHashes, hash),它其实就是一个二分查找的操作,代码比较简单,这里就不扩展说了。

HashSet

HashSet的内部实现是HashMap

private transient HashMap<E,Object> map;

它把值作为HashMap的key,而HashMap的values是用一个Object常量。

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

所以它这里就体现出Set的一个特征,没有重复元素。

TreeSet

TreeSet内部的数据结构是TreeMap

public TreeSet() {
    this(new TreeMap<>());
}

和TreeMap不同的是,它和HashSet一样,用传进来的Object当key,用Object常量当values

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

Set小结

Set的数据结构当然还有其它,比如LinkedHashSet这些。但是比较有代表性的就是这3个,其中Set和Map其实是有一定的联系,我们上面讲Map的时候说,它内部是持有Set,而ArraySet和ArrayMap的数据结构一样,都是双数组,HashSet内部的实现是HashMap,TreeSet的内部实现是TreeMap。他们的不同在于Set把传进来的value当成key,而Map是会传key和value独立开(下篇会讲)。

ArraySet、HashSet、TreeMap看着没有关联,其实是有一定的联系,没错,就是hash,它们都会去计算hash,所以这就是没有重复元素的原因,因为相同的对象,它们的hash是相同的。

上面讲了比较经典的List和Set的数据结构,接下来会讲几个比较特殊的数据结构。

SparseArray

这个数据结构可能很多人没见过,它是属于Android的,上面我们说的那些都是java的。

他的内部也是两个数组构成。

private int[] mKeys;
private Object[] mValues;

但它和ArraySet不同,它是传两个值

public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
        mValues[i] = value;
    } else {
        ......
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

看到它也用了binarySearch,但是它是根据key去做二分查找,而ArraySet是根据hash去做二分查找找到下标。那他们谁快? 当然是SparseArray,它少了一步操作,它不需要计算hash。所以能看出它是传一个整形来表示key,那既然是key-value的形式,那又可以去和HashMap比较有什么不同了。其实都能很明显的看出HashMap的key是Object,会去计算hash,它的key是直接传尽量的整形。HashMap的查找是根据Key去计算hash,再去计算下标,最后可能变量链表(红黑树),而SparseArray是通过二分查找。 从理论上来说,它的速度比HashMap快,特别是数据量大的情况下能体现出来。

还有一个特征是它有一系列的兄弟结果,比如SparseBooleanArray、SparseIntArray之类的,他们和SparseArray的结构一样,比如SparseIntArray

private int[] mKeys;
private int[] mValues;

不同在于他们的mValues都是基础数据类型数组,这有什么用? 这还真有用,如果你存的是基础数据类型的话,使用这些数据结构,就能省去装箱的操作。

PriorityQueue

这个东西也用得比较少,它表示优先队列,内部也是一个object数组

transient Object[] queue

什么是优先队列,简单来说,有种结构叫最大堆,最小堆。有种排序叫堆排序。他能实现这个效果,它的内部是用堆排序去实现,它能自定义排序的条件。比如它默认实现最小堆,如果你要实现最大堆的话,可以写

PriorityQueue<T> heap = new PriorityQueue<>(Collenctions.reverseOrder())

因为是队列,所以它实现Queue的那些操作,比如offer

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i &gt;= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

siftUp是个堆排的操作,这里就不详细去说了,感兴趣官方的堆排是怎么实现的,可以去看看源码,但它也不是纯堆排的操作,会有些许不同。

总结

这篇主要讲了一些java中顶层的数据结构,包括Collection、Queue和Deque,这些顶层的结构主要是定义一些行为,他们还有自己的抽象实现类。

除了这些,还讲了List和Set里面一些比较经典的数据结构,他们的内部是如何实现的,他们有什么相同点和不同点,他们是如何体现出接口List或Set的特点的。

除了List或Set之外,还讲了一些比较常用的数据结构,包含SparseArray和PriorityQueue,主要是我比较常用,如果有大佬还会用到什么其它的,觉得比较实用的,也可以在评论留言。

之后的文章会分开讲Map和线程安全的数据结构,Concurrent、同步队列和CopyOnWriteArrayList。而Map中的HashMap比较经典所以会花更多的笔墨去写。这些文章我都是主要讲一些特点为主,不会去完全解析各种数据结构,比如LinkedList,它的实现就很多,如果去讲的话就要花费大篇幅,而且它们内部的源码不复杂,所以我认为没必要去详细的讲解,感兴趣的可以去看源码还比看文章快,主要就是讲这些结构的设计和一些体现出它们特点的操作。

加载全部内容

相关教程
猜你喜欢
用户评论