本文正在参加「金石计划 . 分割6万现金大奖」

前语

这次算一个总结，咱们平时都会用到各种各样的数据结构，可是或许从未看过它们内部是怎么去完成的。只有了解了它们内部大约的一个完成原理，才能在不同的场景中能选出最适合这个场景的数据结构。

虽然标题说是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<?> c = (Collection<?>) 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 >= 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，它的完成就许多，假如去讲的话就要花费大篇幅，而且它们内部的源码不杂乱，所以我认为没必要去详细的讲解，感兴趣的能够去看源码还比看文章快，首要便是讲这些结构的规划和一些表现出它们特色的操作。

Android数据结构全面分析（上）

前语

Collection

Set和List

Queue和Deque

Map

ArrayList

LinkedList

Vector

Stack

ArraySet

HashSet

TreeSet

Set小结

SparseArray

PriorityQueue

总结

作者信息

Android数据结构全面分析（上）

前语

Collection

Set和List

Queue和Deque

Map

ArrayList

LinkedList

Vector

Stack

ArraySet

HashSet

TreeSet

Set小结

SparseArray

PriorityQueue

总结

相关文章

[CleanArchitecture] Google官方的Nowinandroid是如何抽出数据层(Data Layer)的

Android 加固方案实践系列1-《第一代加固》

Android中PendingIntent的使用

羡慕大劳星空顶？不如跟我一起使用 Jetpack compose 绘制一个星空背景（带流星动画）

作者信息