Android中常⽤的数据结构
interface Collection<E> // 集，⼀组数据
|--> interface Set<E> // 集合，不允许重复元素
| |--> interface SortedSet<E> // 对元素进⾏排序
| | |--> interface NavigableSet<E> // 可获得离指定元素最近的元素
| | | |--> class TreeSet<E> // 使⽤TreeMap<E, Object>实现，⾮线程安全
| | | |--> class ConcurrentSkipListSet<E> // 使⽤ConcurrentSkipListMap实现，线程安全好榜样
| |
| |--> class HashSet<E> // 使⽤HashMap<E, Object>实现，⾮线程安全
| | |--> class LinkedHashSet<E> // 维护元素的添加顺序，使⽤LinkedHashMap<E, Object>实现，⾮线程安全
| |
| |--> class CopyOnWriteArraySet<E> // 使⽤CopyOnWriteArrayList实现，线程安全
| |--> class ArraySet<E> // Android类，内存优化（相⽐于HashSet），不保证线程安全
|
|
|--> interface List<E> // 序列，可以控制元素的插⼊位置，通过序号访问元素，以及查找元素
| |--> class ArrayList<E> // 使⽤可变数组(resizable-array)实现，⾮线程安全
| |--> class LinkedList<E> // 使⽤双向链表(doubly-linked list)实现，⾮线程安全
| |--> class CopyOnWriteArrayList<E> // 类似ArrayList，线程安全
| |--> class Vector<E> // 类似ArrayList，线程安全
| | |--> class Stack<E> // LIFO
|
|
|--> interface Queue<E> // 队列，FIFO（典型⽽⾮必须），不⽀持对元素进⾏索引访问
| |--> interface BlockingQueue<E> // 阻塞队列，线程安全
| | |--> class ArrayBlockingQueue<E> // 基于数组的定长阻塞队列
| | |--> class LinkedBlockingQueue<E> // 基于链表的定长或不定长阻塞队列
| | |--> class PriorityBlockingQueue<E> // 基于堆(heap)的不定长阻塞队列
| | |--> class SynchronousQueue<E> // 不存储元素的阻塞队列
| | |--> class DelayQueue<E extends Delayed> // ⽆界的延迟元素阻塞队列
| | |
| | |--> interface BlockingDeque<E> // 双端阻塞队列
| | | |--> class LinkedBlockingDeque<E> // 基于链表的定长或不定长双端阻塞队列
| | |
| | |--> interface TransferQueue<E> // ⽣产者等待消费者接收元素
| | | |--> class LinkedTransferQueue<E> // 基于链表的⽆界传输队列
| |
| |--> class PriorityQueue<E> // 优先队列，元素保持优先级排列，基于堆(heap)实现，⾮线程安全
| |--> class ConcurrentLinkedQueue<E> // 基于链表的⽆界队列，线程安全
| |
| |--> interface Deque<E> // 双端队列(double ended queue)，可⽤作队列或栈
| | |--> class ArrayDeque<E> // 基于数组的双端队列，⾮线程安全
| | |--> class LinkedList<E> // 基于链表的双端队列，⾮线程安全
| | |--> class ConcurrentLinkedDeque<E> // 基于链表的⽆界双端队列，线程安全
| | |--> interface BlockingDeque<E>
interface Map<K, V> // 映射，不允许重复键值，⼀个键值对应最多⼀个数据
|--> interface SortedMap<K, V> // 键全排序
| |--> interface NavigableMap<K,V> // 导航⽅法返回离给定查找⽬标最近的匹配
| | |--> class TreeMap<K, V> // 使⽤红⿊树实现，⾮线程安全
含羞草的描写
| | |--> interface ConcurrentNavigableMap<K,V>
|
|--> class HashMap<K, V> // 基于散列表（hash table，数组+链表）实现，⾮线程安全
| |--> class LinkedHashMap<K, V> // 使⽤散列表和链表实现，维持⼀个双向链表来记录键值对的插⼊顺序，⾮线程安全|
|--> interface ConcurrentMap<K,V> // 原⼦性保证，线程安全
| |--> class ConcurrentHashMap<K,V> // 类似HashTable
| |--> interface ConcurrentNavigableMap<K,V> // ⼦映射可导航
| | |--> class ConcurrentSkipListMap<K,V> // 基于跳跃列表实现
|
|--> class EnumMap<K extends Enum<K>, V> // 使⽤双数组实现，其中键是枚举型，⾮线程安全
|--> class IdentityHashMap<K,V> // 使⽤散列表（数组）实现，⽐较键以及值时使⽤引⽤⽐较代替值⽐较，⾮线程安全
|--> class WeakHashMap<K,V> // 使⽤散列表实现，其中键是弱引⽤，⾮线程安全
|
|
|--> class Hashtable<K, V> // 类似HashMap，线程安全
|--> class ArrayMap<K, V> // Android类，内存优化（相⽐于HashMap）
class Collections // 作⽤于或返回集的⼯具类
class Arrays // 作⽤于或返回数组的⼯具类
class LruCache<K, V> // Android类，使⽤LinkedHashMap<K, V>实现，线程安全
class SparArray<E> // Android类，使⽤双数组实现，将整型映射⾄对象
简介：
1. Collection
boolean add(E e)：确保该集包含指定元素，当该集发⽣变化时返回true
boolean remove(Object o)：从该集移除指定元素的⼀个实例，当该集包含指定元素时返回true
boolean addAll(Collection<? extends E> c)：添加指定集的所有元素⾄该集，当该集发⽣变化时返回true
boolean removeAll(Collection<?> c)：从该集移除全部存在于指定集的元素，当该集发⽣变化时返回true
boolean retainAll(Collection<?> c)：在该集中仅保留存在于指定集的元素，当该集发⽣变化时返回tru
e
2. Set
boolean equals(Object o)：当指定物件同样是个集合，两个集合⼤⼩⼀致，且该集合包含指定集合的每⼀个成员时返回true。该定义确保此⽅法适⽤于集合的不同实现。Overrides: equals in interface Collection
3. SortedSet
获取⼦集指的是得到⼦集的视图，对⼦集的修改会反映到该集，反之亦然。
五个严禁
SortedSet<E> subSet(E fromElement, E toElement)：获取⼦集[fromElement, toElement)
SortedSet<E> headSet(E toElement)：获取严格⼩于toElement的⼦集
SortedSet<E> tailSet(E fromElement)：获取⼤于等于fromElement的⼦集
E first()：获取当前最⼩的元素
E last()：获取当前最⼤的元素
4. NavigableSet
E lower(E e)：获取⼩于e的最⼤元素，没有则为空帝王菜
E floor(E e)：获取⼩于等于e的最⼤元素，没有则为空
E ceiling(E e)：获取⼤于等于e的最⼩元素，没有则为空
E higher(E e)：获取⼤于e的最⼩元素，没有则为空
E pollFirst()：获得最⼩元素并移除
E pollLast()：获得最⼤元素并移除
5. List
boolean equals(Object o)：当且仅当指定物件同样是个序列，两个序列⼤⼩⼀致，且两个序列的所有对应元素也相等时返回true。换句话说，当两个序列有相同顺序的相同元素时定义为相等。该定义确保此⽅法适⽤于序列的不同实现。Overrides: equals in interface Collection
E t(int index, E element)：替代指定位置元素并返回旧元素
E remove(int index)：移除指定位置元素并返回旧元素
List<E> subList(int fromIndex, int toIndex)：获取⼦序列[fromIndex，toIndex)，这⾥得到的是⼦序列的视图，对⼦序列的⾮结构性修改会反映到该序列，反之亦然。
6. ArrayList
7. Vector
boolean removeElement(Object obj)：从该向量中移除参数的⾸次出现，功能上等同于remove(Object)
8. Stack
E peek()：获取栈顶元素
int arch(Object o)：返回离栈顶最近的相同元素⾄栈顶的距离，栈顶元素距离为1
9. Queue
boolean add(E e)：如果可以⽴即往该队列⾥插⼊指定元素且不违反容量限制则返回true，若当前没有
可⽤空间则抛出异
常。Overrides: add in interface Collection
boolean offer(E e)：同add，如果元素能加⼊队列则返回true，否则返回fal。
E remove()：检索并移除队列头部，当队列为空时抛出异常。
E poll()：同remove，当队列为空时返回null。
E poll()：同remove，当队列为空时返回null。
E element()：检索队列头部但并不移除，当队列为空时抛出异常。
E peek()：同element，当队列为空时返回null。
10. BlockingQueue
void put(E e)：往该队列插⼊指定元素，必要时等待空间变得可⽤。
boolean offer(E e, long timeout, TimeUnit unit)：同put，最多等待指定时间。
E take()：检索并移除队列头部，必要时等待直到有元素变得可⽤。
E poll(long timeout, TimeUnit unit)：同take，最多等待指定时间。
int remainingCapacity()：返回该队列在⽆需阻塞下能理想接收的额外的元素数⽬。
int drainTo(Collection<? super E> c)：从该队列移除所有可⽤元素并添加⾄给定集，返回传输元素的数⽬。dj老歌
Throws exception Special value Blocks Times out Inrt add(e)offer(e)put(e)offer(e, time, unit) Remove remove()poll()take()poll(time, unit) Examine element()peek()不适⽤不适⽤
1. PriorityQueue
2. Deque
void push(E e)：往双端队列表现的栈推⼊元素，等价于addFirst。
E pop()：从双端队列表现的栈推出元素，等价于removeFirst。
3. Map
V put(K key, V value)：将指定值联系⾄指定键，返回键联系的先前的值或null。
V remove(Object key)：移除键对应的键值对，返回键联系的先前的值或null。
Set<K> keySet()：返回所有键的集合视图。
Collection<V> values()：返回所有值的集视图。
Set<Map.Entry<K, V>> entrySet()：返回所有键值对的集合视图。
boolean equals(Object o)：当给定物件也是⼀个映射且两个映射包含相同键值对时返回true，该定义确保此⽅法适⽤于映射的不同实现。
4. SortedMap
以下⽅法的功能与SortedSet相应的⽅法类似：
SortedMap<K,V>subMap(K fromKey, K toKey);
SortedMap<K,V>headMap(K toKey);
SortedMap<K,V>tailMap(K fromKey);
K firstKey();
K lastKey();
15. NavigableMap
Map.Entry<K,V> lowerEntry(K key)：返回严格⼩于给定键的最⼤键对应的键值对，当没有这样的键时返回null。
K lowerKey(K key)：返回严格⼩于给定键的最⼤键，当没有这样的键时返回null。
NavigableSet<K> navigableKeySet()：返回所有键的可导航集合视图。
16. TreeMap
17. HashMap
（编者注：原⽂扩容机制中，key = 3、7、5，put顺序依次为 5、7、3有误，顺序应为3、7、5。）
18. ConcurrentHashMap
19. EnumMap
20. HashTable
boolean contains(Object value)：等价于boolean containsValue(Object value)
21. LruCache
22. SparArray
类似的还有：
map key value
SparArray int Object
SparBooleanArray int boolean
SparIntArray int int
SparLongArray int long
LongSparArray long Object
⽐较：
1. ArrayList & ArrayBlockingQueue & ArrayDeque
加勒比海盗h三者都是基于数组来实现，ArrayList在数组中间index位置插⼊和删除元素时，index后的元素都要通过System.arraycopy来搬动，⽽ArrayBlockingQueue通过takeIndex和putIndex两个标志位来标记定长数组的实际队⾸和队尾，⽽且当标志位到达数组末尾时会返回到数组头部，ArrayDeque也是通过head和tail来标记队⾸和队尾，这⾥head指头部元素的序号，tail指可以添加下⼀个元素到尾部的序号，即最后⼀个元素的下⼀个序号。简单介绍一下自己
2. LinkedList & LinkedBlockingQueue & LinkedBlockingDeque
两者都是基于链表来实现，LinkedList和LinkedBlockingDeque的头节点或尾节点如果⾮空，则该节点的元素⾮空，
⽽LinkedBlockingQueue的头节点⾮空且节点的元素为空，也就是第⼆个节点才真正装载第⼀个元素，尾节点⾮空并装载最后⼀个元素，当尾节点和头节点是同⼀个节点时，尾节点的元素也可以是空。
3. ArrayList & PriorityQueue
对ArrayList进⾏排序之后，所有元素是全排序的。⽽PriorityQueue的优先级排序并⾮是全排序，仅仅是符合⼩根堆的结构，即⽗节点⼩于⼦节点，所以每次获取到的头节点都是权值最⼩的。
空气质量日报4. Vector与CopyOnWriteArrayList
5. ArraySet & ArrayMap
