前言
最近在某篇文章中偶然看到了LongSparseArray这个类，一开始我还以为是作者打错了，应该是SparseLongArray，我还在心里小小鄙视了一下这作者真不专业，结果一搜索，还真有LongSparseArray这个类，而且我居然第一次见到，也从来没用过。对不起打扰了，是本人孤陋寡闻了。于是我顺便回顾了一下android中的数据结构，发现居然还不少，索性就在这里记录总结一下
java中提供的数据结构类型主要有四种：List、Set、Map、Queue，这四个都是接口，我们平时用到的数据结构类型都是他们的实现类。除了java提供的数据结构外，android自己也实现了一些数据结构。下面是他们的继承关系树：
List
|__ArrayList
| |__Vector
| |__Stack
|__LinkedList
Set
|__HashSet
| |__LinkedHashSet
|__TreeSet
|__(A)ArraySet
Map
|__HashMap
| |__LinkedHashMap
|__TreeMap
|__WeakHashMap
|__IdentityHashMap
|__ConcurrentHashMap
|__ConcurrentSkipListMap
|__Hashtable
| |__Properties
|__(A)ArrayMap
Queue
|__LinkedList
|__LinkedBlockingQueue
|__SynchronousQueue
|__LinkedTransferQueue
|__ConcurrentLinkedQueue
|__ArrayBlockingQueue
|__LinkedBlockingDeque
|__ConcurrentLinkedDeque
|__ArrayDeque
|__PriorityQueue
|__PriorityBlockingQueue
|__DelayQueue
(A)SparseArray系列：SparseArray、SparseIntArray、SparseLongArray、SparseBooleanArray（上述四个类各自有其子类ParcelableXXX，这里就不列举了）
、LongSparseArray
说明：
-
本文为汇总文章不是解析文章，只汇总各数据结构类型的特点以及使用场景，暂不涉及底层实现原理，源码解析以及实现原理后续有时间会出专栏
-
上述继承树中只列出了最终的实现类，最终实现类与根接口之间的抽象类和接口实现关系不详细罗列（例如
TreeMap不是直接实现Map接口，而是继承自抽象类AbstractMap，AbstractMap实现了Map接口；TreeMap除了继承自AbstractMap外还实现了NavigableMap接口，NavigableMap接口继承自SortedMap接口，SortedMap接口继承自Map接口） -
上述继承树的实现类中前面有
(A)表示该类型是android中提供的数据结构类型，不是java中的
下面就来一一看一下这些数据结构类型
1、List：元素可重复
1. ArrayList和LinkedList
ArrayList基于数组实现，LinkedList基于双向链表实现，二者都是有序的（插入顺序）；效率上来说，从集合头部增删元素，LinkedList效率高于前者，从集合中部增删元素，ArrayList效率远高于后者，从集合尾部增删元素，二者效率相当；使用for循环方式遍历，ArrayList效率远高于后者，使用迭代器方式遍历，二者效率相当；随机查找ArrayList效率高于后者。不过LinkedList更多是用于实现队列需求，只是注重于数据的存储和读取，一般使用ArrayList
2. Vector
线程安全版的ArrayList，早期比较粗糙的实现类，现不建议使用，在多线程环境下可以使用Collections.synchronizedList(list)
3. Stack
顾名思义是栈结构，遵循先进后出原则，现不建议使用
2、Set：元素不可重复
1. HashSet和LinkedHashSet
前者存储的元素是无序的，后者有序，按插入顺序排序
2. TreeSet
元素有序，但不是插入顺序，是按自然顺序。例如依次插入元素：treeSet.add(2)、treeSet.add(5)、treeSet.add(8)、treeSet.add(3)，遍历结果为2、3、5、8。如果有特殊需求也可以自定义排序规则
3. ArraySet
基于数组实现，主要特点是占用内存小于前三者，这也是google为了移动端珍贵的内存而打造的数据容器；只适用于数据量小的场景，数据量大性能不佳
3、Map：键值对，key不可重复，value可重复
1. HashMap
元素无序；非线程安全；key和value均允许为null
2. LinkedHashMap
元素有序，插入顺序；非线程安全；key和value均允许为null
3. TreeMap
元素有序，按自然顺序，可自定义排序规则；非线程安全；key不可为null，value可为null
4. WeakHashMap
Weak表示WeakReference，所以它具有自清理的功能，如果该Map中的某个key在其他任何地方都没有引用了，则会自动清理丢弃该键值对；其他特点与HashMap相同
5. IdentityHashMap
它与HashMap的区别在于key的唯一性的检查上，判断key是否唯一，HashMap比较的是key的值（或者说内容），而该Map比较的是key的引用（或者说地址）。举个例子：假如向两种类型的Map中存入如下两个键值对：map.put(new String("test")，"value1")、map.put(new String("test")，"value2")，则最终HashMap中只有一个键值对test-value2，因为两个key的值都是"test"，判断为相同，所以将第二个value2覆盖掉第一个value1；而IdentityHashMap中有两个键值对，因为两个key是两个不同的对象，引用不一样，所以判断为不同
6. ConcurrentHashMap
看名字就能猜到它与HashMap相比是线程安全的，在多线程环境中使用
7. ConcurrentSkipListMap
与ConcurrentHashMap相比，该Map支持更高的并发，并且元素是有序的
8. Hashtable
与HashMap相比是线程安全的，它也是早期实现的一个比较粗糙的数据结构，现在基本已经被淘汰了，多线程环境可以使用ConcurrentHashMap
9. Properties
看到这个是不是很眼熟？没错，android studio项目中的配置文件有的就是这个格式，例如gradle.properties、local.properties。Properties的主要作用就是读写配置文件
10. ArrayMap
和ArraySet类似，它也是为了优化内存占用而打造出来的，适用于数据量小的场景，数据量大时性能会急剧下降
4、Queue：队列，遵循先进先出
上述三种数据结构类型注重的是数据的存储和读取，而Queue则注重的是数据的按序流动。Queue主要用于需要排队，先进先出的场景，比如多线程中等待处理的任务、排队等待获取某个锁的线程等。非常典型的例子就是Handler的message就是存储在Queue中。
队列可分为阻塞队列（BlockingQueue）和非阻塞队列（Queue），也可分为单向队列（Queue）和双向队列（Deque）
非阻塞队列有：
1. LinkedList
它在上面List中已经出现过了，LinkedList既实现了List接口，又实现了Deque接口；非线程安全
2. ArrayDeque
基于数组实现的双向队列，比LinkedList更加高效，建议优先选用ArrayDeque
3. PriorityQueue
该队列较为特殊，它打破了先进先出原则，内部的数据不是按插入顺序排队，而是按自定义的排序顺序进行排队，默认是最小优先队列，即小数据先出；非线程安全
4. ConcurrentLinkedQueue
线程安全，使用循环CAS实现非阻塞式并发
5. ConcurrentLinkedDeque
与ConcurrentLinkedQueue区别为前者是单向队列，后者为双向队列
阻塞队列有（因为阻塞机制，下面队列都是线程安全的）：
1. LinkedBlockingQueue
它与LinkedList相比没有实现List接口，不具备List的功能
2. LinkedBlockingDeque
与LinkedBlockingQueue相比是双向队列
3. SynchronousQueue
它内部没有存放数据的能力，或者说容量为0（无论调用多少次put方法，调用其size方法得到的都是0）；并且它是个特殊的阻塞队列，不同于其他阻塞队列（队列内数据满/空了才会阻塞put/take线程），每个向其put/take数据的线程都会被阻塞，直到能与之配对的take/put线程到来才会释放，原因也正是因为容量为0，所以队列可以一直看作是满的/空的。
打个比方：有一间屋子（阻塞队列）卖面包，面包师（put线程）做完一个面包要放到屋子里（向队列put数据），如果屋子里面包满了放不下了，面包师就会在这里等着（put线程被阻塞），直到屋子里有位置了再将面包放进去然后回去（put线程被释放）；顾客（take线程）来到屋子要买面包（从队列take数据），如果屋子里空了没有面包，顾客就会在这里等着（take线程被阻塞），直到屋子里有面包了再买完离开（take线程被释放）。前面描述的是普通阻塞队列，如果是SynchronousQueue，情形会是这样：面包师做完一个面包要放到屋子里，由于屋子里不能存放面包（即队列无法存放数据），所以任何一个面包师无论何时要将面包放进屋子里都会在这里等（被阻塞），等待有顾客来买面包；同样由于屋子里不能存放面包，也就是一直没有面包，所以任何一个顾客无论何时要来买面包也都会在这里等，等待有面包师做完面包送过来。或者可以理解为面包不会被放进屋子里，面包是从面包师手中直接给到顾客手中，屋子只是为面包师和顾客提供等待的地点（即SynchronousQueue只负责阻塞线程，不负责存放数据）而已
4. PriorityBlockingQueue
它与PriorityQueue区别是线程安全
5. ArrayBlockingQueue
基于数组实现，它的效率比LinkedBlockingQueue稍高
6. LinkedTransferQueue
它相当于LinkedBlockingQueue和SynchronousQueue的结合体，性能比LinkedBlockingQueue高，容量比SynchronousQueue大。当向其put数据时，如果有线程在等待，则直接交给等待线程，不会入队，否则才将数据入队
7. DelayQueue
该队列是基于PriorityQueue实现的，所以它也打破了先进先出原则。该队列按照过期时间顺序对数据进行排序。过期时间顺序排序规则由使用者自定义，通过实现Delayed接口进行自定义，需实现compareTo方法（该方法源自Comparable接口，Delayed接口继承自Comparable接口）。所以该队列中的元素必须实现Delay接口。
SparseArray系列：节省内存的‘Map’
该系列是google专为android移动平台打造的针对内存方面优化的数据容器，功能与Map类似，也是存储key-value键值对数据，不过key只能是int（注意不是Integer）型，相比Map省去了装箱的开销。同Map一样，key不可重复value可重复。SparseArray系列都不是线程安全的；元素都是有序的；适用于数据量小的场景，数据量大性能不佳
1. SparseArray
key固定为int型；value可用泛型指定类型；value可为null
2. SparseIntArray
与SparseArray区别是value固定为int型，不可用泛型指定
3. SparseLongArray
与SparseArray区别是value固定为long型，不可用泛型指定
4. SparseBooleanArray
与SparseArray区别是value固定为Boolean型，不可用泛型指定
5. LongSparseArray
与SparseArray区别是key固定为long型
网友评论