本文正在参加「金石计划 . 分割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组，它们的差别是：

1. add() ： 无回来值
2. offer()： 有回来值
3. remove()：移除失利抛出异常
4. poll()：移除失利回来null
5. element()：行列为空抛出异常
6. peek()：行列为空回来null

所以假如你不了解这些，你只会无脑add，这样就很不好。但其实对于LinkedList来说add()和offer()差异不大。或许差异比较大的当地在你自界说数据成果完成Queue和Deque的时分该怎样处理这两个办法。

说完Queue再简略介绍一下Deque，Deque由于是双向行列，所以它能完成栈和行列。

1. 行列：入行列offer；出行列poll；获取行列头peek
2. 栈：入栈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，它的完成就许多，假如去讲的话就要花费大篇幅，而且它们内部的源码不杂乱，所以我认为没必要去详细的讲解，感兴趣的能够去看源码还比看文章快，首要便是讲这些结构的规划和一些表现出它们特色的操作。