Android 数据结构全面总结分析

时间:2022-12-06 流浪汉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() ：无返回值
offer()：有返回值
remove()：移除失败抛出异常
poll()：移除失败返回null
element()：队列为空抛出异常
peek()：队列为空返回null

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

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

队列：入队列offer；出队列poll；获取队列头peek
栈：入栈push；出栈pop；获取栈顶peel

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，它的实现就很多，如果去讲的话就要花费大篇幅，而且它们内部的源码不复杂，所以我认为没必要去详细的讲解，感兴趣的可以去看源码还比看文章快，主要就是讲这些结构的设计和一些体现出它们特点的操作。

加载全部内容