Android 常用数据结构总结
数据结构
数组：
优点：查询快，如果知道索引可以快速存取
缺点：删除慢，大小固定
有序数组：
优点：比无序数组查找块
缺点：删除和插入慢，大小固定
栈：
优点：提供后进先出的存取方式
缺点：存取其他项很慢
队列：
优点：提供先进先出的存取方式
缺点：存取其他项都很慢
链表（单链表、循环链表、双向链表）
优点：插入快，删除快
缺点：查找慢（一个个节点查）
二叉树
优点：查找、插入、删除都快（平衡二叉树）
缺点：删除算法复杂
红黑树
优点：查找，插入，删除都快，树总是平衡的（局部调整）
缺点：算法复杂
2-3-4树
优点：查找，插入，删除都快，树总是平衡的。类似的树对磁盘存储有用，
缺点：算法复杂
哈希表
优点：如果关键字已知则存取速度极快，插入快
缺点：删除慢，如果不知道关键字则存取很慢，对存储空间使用不补充
堆
优点：插入、删除快、对最大数据的项存取很快
缺点：对其他数据项存取很慢
图
优点：对现实世界建模
缺点：有些算法慢且复杂
常用集合类的继承结构如下：
Collection<--List<--Vector
Collection<--List<--ArrayList
Collection<--List<--LinkedList
Collection<--Set<--HashSet
Collection<--Set<--HashSet<--LinkedHashSet
Collection<--Set<--SortedSet<--TreeSet
Map<--SortedMap<--TreeMap
Map<--HashMap （补充一个HashMap的子类LinkedHashMap：）
注意这里的 Collection、List、Set和Map都是接口（Interface）
List
List是有序的Collection，使用此接口能够精确地控制每个元素插入的位置。类似于JAVA的数组
Vector
基于数组（array）的list，ArrayList其实是对数组的动态扩充，底层的数据结构使用的是数组结构（数组长度是可变的百分之百延长）：
特点：vector是线程同步的（sychronized）的，在add(), remove(), get()等方法中都加了同步，线程安全的。速度相对ArrayList慢些。
ArrayList
基于数组（array）的list，ArrayList其实是对数组的动态扩充，底层的数据结构使用的是数组结构（数组长度是可变的百分之五十延长）：
特点：查询很快，但增删较慢，线程不同步。性能上要比vector好一些，但是线程不安全。
Linkedlist
Linkedlist不同于前两个，基于单链表实现的。它的每一个节点（node）都包含两方面的内容：1，节点本身的数据（data）；2，下一个节点的信息（nextnode）。所以当对Linkedlist做添加，删除动作的时候就不用像基于数组的ArrayList一样，必须进行大量的数据移动。只要更改nextnode的相关信息就可以实现了，这是Linkedlist的优势
LinkedList根据序号获取数据，是二分进行遍历，如果序号小于总长度的一半，就从链表头部开始往后遍历，直到找到对应的序号。如果序号大于总长度的一半，就从链表尾部往前进行遍历，直到找到对应的序号。拿到数据。
List总结：
所有的List中只能容纳单个不同类型的对象组成的表，而不是Key－Value键值对。例如：[ tom,1,c ]
所有的List中可以有相同的元素，例如Vector中可以有 [ tom,koo,too,koo ]
所有的List中可以有null元素，例如[ tom,null,1 ]
基于Array的List（Vector，ArrayList）适合查询，而LinkedList 适合添加，删除操作
Set：
Set是一种不包含重复的元素的无序Collection。
HashSet：
虽然Set同List都实现了Collection接口，但是他们的实现方式却大不一样。List基本上都是以Array为基础。
HashSet是根据hashCode来决定存储位置的，是通过HashMap实现的，所以对象必须实现hashCode()方法，存储的数据无序不能重复，可以存储null,但是只能存一个。
但是Set则是在 HashMap的基础上来实现的，这个就是Set和List的根本区别。HashSet的存储方式是把HashMap中的Key作为Set的对应存储项。
看看 HashSet的add（Object obj）方法的实现就可以一目了然了。
Java代码
public boolean add(Object obj) {
return map.put(obj, PRESENT) == null;
}
这个也是为什么在Set中不能像在List中一样有重复的项的根本原因，因为HashMap的key是不能有重复的。
LinkedHashSet：
HashSet的一个子类，一个链表。
TreeSet：
SortedSet的子类，它不同于HashSet的根本就是TreeSet是有序的。它是通过SortedMap来实现的。
TreeSet是根据二叉树实现的，也就是TreeMap, 放入数据不能重复且不能为null,可以重写compareTo()方法来确定元素大小，从而进行升序排序。
Set总结：
Set实现的基础是Map（HashMap）
Set中的元素是不能重复的，如果使用add(Object obj)方法添加已经存在的对象，则会覆盖前面的对象
Map下面的概念和特性
Map 是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个Map，依次类推，这样就可形成一个多级映射。对于键对象来说，像Set一样，一个 Map容器中的键对象不允许重复，这是为了保持查找结果的一致性;如果有两个键对象一样，那你想得到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求，你可以将任意多个键都映射到一个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象）。
Map有两种比较常用的实现：HashMap和TreeMap。
HashMap
HashMap也用到了哈希码的算法，以便快速查找；HashMap是基于散列链表来实现的，简单的来说，根据key算出一个hash值，确定一个存放index,但是hash值有可能会冲突重复，所以如果冲突的hash值就需要以链表的形式在同一个index存放了。可以参考：http://blog.****.net/u011060103/article/details/51355763
LinkedHashMap继承自HashMap，特点是内部存入数据是有顺序的，增加了记住元素插入或者访问顺序的功能，这个是通过内部一个双向的循环链表实现的。与 HashMap 一样，它可以为基本操作（add、contains 和 remove）提供稳定的性能，假定哈希函数将元素正确分布到桶中。由于增加了维护链接列表的开支，其性能很可能比 HashMap 稍逊一筹，不过这一点例外：LinkedHashMap 的 collection 视图迭代所需时间与映射的大小 成比例。HashMap 迭代时间很可能开支较大，因为它所需要的时间与其容量 成比例。
TreeMap
TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。 键和值的关联很简单，用put(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。
TreeMap是有序的，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
TreeMap的使用大致跟HashMap类似，但是内部实现是根据红黑树来实现的。红黑树是一种平衡有序的二叉树，具有二叉树所有的特性，TreeMap的插入删除查询都是依据红黑树的规则来进行的。可以参考：http://blog.****.net/chenssy/article/details/26668941
Hashtable
先说下，HashMap和TreeMap都是线程不安全的，多线程操作的时候可能会造成数据错误。Hashtable是线程安全的。其他内部实现，与HashMap都是一样的。
几个常用类的区别
1．ArrayList: 元素单个，效率高，多用于查询
2．Vector: 元素单个，线程安全，多用于查询
3．LinkedList:元素单个，多用于插入和删除
4．HashMap: 元素成对，元素可为空
5．HashTable: 元素成对，线程安全，元素不可为空
6. HashSet：元素单个，元素不可重复
Vector、ArrayList和LinkedList
大多数情况下，从性能上来说ArrayList最好，但是当集合内的元素需要频繁插入、删除时LinkedList会有比较好的表现，但是它们三个性能都比不上数组，另外Vector是线程同步的。所以： 如果能用数组的时候(元素类型固定，数组长度固定)，请尽量使用数组来代替List； 如果没有频繁的删除插入操作，又不用考虑多线程问题，优先选择ArrayList； 如果在多线程条件下使用，可以考虑Vector； 如果需要频繁地删除插入，LinkedList就有了用武之地：如果你什么都不知道，用ArrayList没错。