Android中一般使用的數據結構有java中的基礎數據結構List，Set，Map。還有一些Android中特有的幾個，SparseArray(使用Map時Key是int類型的時候可以用這個代替)等。

繼承關系：

Collection<–List<–ArrayList

Collection<–List<–Vector

Collection<–List<–LinkedList

Collection<–Set<–HashSet

Collection<–Set<–HashSet<–LinkedHashSet

Collection<–Set<–SortedSet<–TreeSet

Map<–HashMap （補充一個HashMap的子類LinkedHashMap：）

Map<–SortedMap<–TreeMap

注：這里的 Collection、List、Set和Map都是接口（Interface），其中Collection是所有集合類的接口，Set和List也都實現該接口。

下面分別來介紹List、Set、Map。

List

List是有序的Collection，使用此接口能夠精確的控制每個元素插入的位置。用戶能夠使用索引（元素在List中的位置，類似于數組下標）來訪問List中的元素，這類似于Java的數組。 List比較常用的有ArrayList和LinkedList，還有一個比較類似的Vector。

1、ArrayList

基于數組（Array）的List，ArrayList其實是對數組的動態擴充，底層的數據結構使用的是數組結構（數組長度是可變的百分之五十延長）。

特點：

對于數據的隨機get和set或是少量數據的插入或刪除，效率會比較高。ArrayList是線程不安全的，在不考慮線程安全的情況下速度也比較快的。ArrayList插入數據可以重復，也是有序的，按照插入的順序來排序。性能上要比Vector（是線程安全的）好一些。

Vector

基于數組（Array）的List，Vector其實是對數組的動態擴充，底層的數據結構使用的是數組結構（數組長度是可變的百分之百延長）。

特點：

Vector的使用方法和內部實現基本和ArrayList相同，只不過它在add(), remove(), get()等方法中都加了同步。所以Vector是線程同步(sychronized)的，線程安全的。但是使用效率上就不如ArrayList了。

LinkedList

LinkedList不同于前面兩個，是基于鏈表實現的雙向鏈表數據結構。
它每一個節點（Node）都包含三方面的內容：

1、節點本身的數據（data）

2、前一個節點的信息（previousNode）

3、下一個節點的信息（nextNode）

所以當對LinkedList做添加，刪除動作的時候就不用像基于數組的ArrayList一樣，必須進行大量的數據移動。
只要更改nextNode的相關信息就可以實現了，這是LinkedList的優勢。

LinkedList根據序號獲取數據，是根據二分法進行遍歷，如果序號小于總長度的一半，就從鏈表頭部開始往后遍歷，直到找到對應的序號。如果序號大于總長度的一半，就從鏈表尾部往前進行遍歷，直到找到對應的序號。拿到數據。

List總結

1、所有的List中只能容納單個不同類型的對象組成的表，而不是Key－Value鍵值對。例如：[ tom,1,c ]

2、所有的List中可以有相同的元素，例如Vector中可以有 [ tom,koo,too,koo ]

3、所有的List中可以有null元素，例如[ tom,null,1 ]

4、基于Array的List（Vector，ArrayList）適合查詢，而LinkedList 適合添加，刪除操作

Set

Set是一種不包含重復的元素的無序Collection。 一般使用的有HashSet和TreeSet。

雖然Set同List都實現了Collection接口，但是他們的實現方式卻大不一樣。List基本上都是以Array為基礎。但是Set則是在 HashMap的基礎上來實現的，這個就是Set和List的根本區別。

HashSet

HashSet是根據hashCode來決定存儲位置的，是通過HashMap實現的，所以對象必須實現hashCode()方法，存儲的數據無序不能重復，可以存儲null,但是只能存一個。

看看 HashSet的add（Object obj）方法的實現就可以一目了然了。

public boolean add(Object obj) {   return map.put(obj, PRESENT) == null;   
}

這個也是為什么在Set中不能像在List中一樣有重復的項的根本原因，因為HashMap的key是不能有重復的。

HashSet代碼示例：

public class Main {public static void main(String[] args) throws IOException {hashSet();}public static void hashSet(){Set<String> set = new HashSet<String>();set.add("2");set.add("1");set.add(null);set.add("1");for(String s : set){System.out.println(s);}}
}

運行結果：

null
1
2

LinkedHashSet

HashSet的一個子類，一個鏈表。

它和HashSet的區別就在于LinkedHashSet的元素嚴格按照放入順序排列。LinkedHashSet內部使用LinkedHashMap實現，所以它和HashSet的關系就相當于HashMap和LinkedHashMap的關系。如果你想讓取出元素的順序和插入元素的順序完全相同，那么就使用LinkedHashSet代替HashSet。

LinkedHashSet也不是線程安全的。

TreeSet

SortedSet的子類，它不同于HashSet的根本就是TreeSet是有序的。它是通過SortedMap來實現的。TreeSet是根據二叉樹實現的，也就是TreeMap,，放入數據不能重復且不能為null，可以重寫comparator()方法來確定元素大小，從而進行升序排序。

代碼示例：

public class Main {public static void main(String[] args) throws IOException {treeSet();}public static void treeSet(){//通過傳入MyComparator對象自定義的排序方法，來實現從大到小的排序。Set<Integer> treeSet = new TreeSet<>(new MyComparator());treeSet.add(1);treeSet.add(3);treeSet.add(4);treeSet.add(2);for(Integer i : treeSet){System.out.println(i);}}static class MyComparator implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {if(o1 < o2 ){return -1;}if(o1 == o2 ){return 0;}if(o1 > o2 ){return 1;}return 0;}}
}

運行結果：

1
2
3
4

Set總結

1、Set實現的基礎是Map（HashMap）

2、Set中的元素是不能重復的，如果使用add(Object obj)方法添加已經存在的對象，則會覆蓋前面的對象

Map

Map 是一種把鍵對象和值對象進行關聯的容器，而一個值對象又可以是一個Map，依次類推，這樣就可形成一個多級映射。

對于鍵對象來說，像Set一樣，一個 Map容器中的鍵對象不允許重復，這是為了保持查找結果的一致性；如果有兩個鍵對象一樣，那你想得到那個鍵對象所對應的值對象時就有問題了，可能你得到的并不是你想的那個值對象，結果會造成混亂，所以鍵的唯一性很重要，也是符合集合的性質的。

當然在使用過程中，某個鍵所對應的值對象可能會發生變化，這時會按照最后一次修改的值對象與鍵對應。對于值對象則沒有唯一性的要求，你可以將任意多個鍵都映射到一個值對象上，這不會發生任何問題（不過對你的使用卻可能會造成不便，你不知道你得到的到底是那一個鍵所對應的值對象）。

Map有兩種比較常用的實現：HashMap和TreeMap。

HashMap

HashMap是基于散列鏈表來實現的，簡單的來說，根據key算出一個hash值，確定一個存放index，但是hash值有可能會沖突重復，所以如果沖突的hash值就需要以鏈表的形式在同一個index存放了。詳情請看HashMap原理和代碼淺析這篇文章。

代碼示例：

    Map<String, String> hashMap = new HashMap<>();//存儲hashMap.put("1", "abc");hashMap.put("2", "bcd");//根據key來刪除hashMap.remove("1");//根據key獲取String value = hashMap.get("2");//map的遍歷,有很多方法遍歷,這里只列舉一種。for(Map.Entry<String, String> entry : hashMap.entrySet()){//獲取keyentry.getKey();//獲取valueentry.getValue();}

LinkedHashMap

LinkedHashMap繼承自HashMap，特點是內部存入數據是有順序的，增加了記住元素插入或者訪問順序的功能，這個是通過內部一個雙向的循環鏈表實現的。與 HashMap 一樣，它可以為基本操作（add、contains 和 remove）提供穩定的性能，假定哈希函數將元素正確分布到桶中。由于增加了維護鏈接列表的開支，其性能很可能比 HashMap 稍遜一籌，不過這一點例外：LinkedHashMap 的 collection 視圖迭代所需時間與映射的大小 成比例。HashMap 迭代時間很可能開支較大，因為它所需要的時間與其容量 成比例。

TreeMap

TreeMap的使用大致跟HashMap類似，但是內部實現是根據紅黑樹來實現的。紅黑樹是一種平衡有序的二叉樹，TreeMap的插入刪除查詢都是依據紅黑樹的規則來進行的。可以參考 Java提高篇（二七）—–TreeMap

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沒錯。

以上是java中的基礎的數據結構，下面來看下android中特有的數據結構。

SparseArray

SparseArray類型

SparseLongArray

SparseIntArray

SparseBooleanArray

SparseArray

SparseArray特點

1、SparseArray是android提供的一個工具類，它可以用來替代hashmap進行對象的存儲

2、SparseArray比HashMap更省內存，它對數據采取了矩陣壓縮的方式來表示稀疏數組的數據，從而節約內存空間

3、SparseArray只能存儲key為整型的數據

4、SparseArray在存儲和讀取數據時候，使用的是二分查找法，提高了查找的效率

5、SparseArray有自己的垃圾回收機制。（當數量不是很多的時候，這個不必關心。）

ArrayMap

官方對ArrayMap也有說明：它不是一個適應大數據的數據結構，相比傳統的HashMap速度要慢，因為查找方法是二分法，并且當你刪除或者添加數據時，會對空間重新調整，在使用大量數據時，效率并不明顯，低于50%。

所以ArrayMap是犧牲了時間換區空間。在寫手機app時，適時的使用ArrayMap，會給內存使用帶來可觀的提升。

HashMap和ArrayMap的區別

1、存儲方式不同

2、添加數據時擴容時的處理不同

詳情請參考Android內存優化：ArrayMap