前言
这次算一个总结，我们平时都会用到各种各样的数据结构，但是可能从未看过它们内部是如何去实现的。只有了解了它们内部大概的一个实现原理，才能在不同的场景中能选出最适合这个场景的数据结构。
虽然标题说是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 数据结构全面总结分析的详细内容，更多关于Android数据结构的资料请关注编程网其它相关文章！
