什么是數(shù)據(jù)結(jié)構(gòu)？
簡(jiǎn)單說(shuō)就是以某種方式把一堆數(shù)據(jù)組織起來(lái)。通常不同的組織方式會(huì)有不同的特性坝茎。Java中常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組涤姊、鏈表、List嗤放、Map等等思喊。
為什么會(huì)有這么多數(shù)據(jù)結(jié)構(gòu)？
不同的數(shù)據(jù)結(jié)構(gòu)形式通常都有各自的使用場(chǎng)景次酌。比如常見(jiàn)的ArrayList恨课。使用ArrayList你可以方便添加和移除數(shù)據(jù)。但如果看過(guò)ArrayList源碼的話會(huì)知道ArrayList底層還是使用數(shù)組岳服。那為什么還要用ArrayList剂公？嚴(yán)格來(lái)說(shuō)Java最底層提供的數(shù)據(jù)結(jié)構(gòu)方式只有基本類型、引用類型和數(shù)組吊宋。其他任何類型都是由這些基本的數(shù)據(jù)結(jié)構(gòu)封裝起來(lái)的纲辽，或者說(shuō)其他任何Java數(shù)據(jù)結(jié)構(gòu)，一層層往下拆最終都會(huì)變成這幾個(gè)璃搜。比如ArrayList就是從數(shù)組封裝過(guò)來(lái)的拖吼。那問(wèn)題來(lái)了，數(shù)組能做到这吻，那為什么還要用ArrayList吊档？主要是因?yàn)锳rrayList進(jìn)行增刪改查使用起來(lái)非常方便，但數(shù)組處理起來(lái)就要復(fù)雜多了唾糯。所以把這些常用的需求封裝起來(lái)就出現(xiàn)了ArrayList怠硼。
List
大家在使用List的時(shí)候可能通常都會(huì)寫下面這樣的代碼
List<String> list = new ArrayList<>();
Java中List是個(gè)接口，所以需要用它的實(shí)現(xiàn)類來(lái)實(shí)例化趾断。那當(dāng)你寫下上面代碼的時(shí)候有沒(méi)有思考過(guò)一個(gè)問(wèn)題拒名，為什么要用ArrayList。Java里有沒(méi)有其他的List實(shí)現(xiàn)類芋酌？當(dāng)然有增显。AndroidStudio或者Intelij Idea可以找到List實(shí)現(xiàn)類，然后通過(guò)Ctrl+H看到所有的繼承自List的類和接口脐帝。你可能會(huì)看到非常多同云，但比較常用的主要就是ArrayList，LinkedList和Vector堵腹。這三個(gè)都是List實(shí)現(xiàn)類炸站。有沒(méi)有想過(guò)一個(gè)問(wèn)題，如果你需要用到List了疚顷，那么究竟應(yīng)該用什么哪個(gè)類旱易？就比如你寫了一個(gè)RecyclerView的Adapter禁偎。有Adapter就一定會(huì)需要有個(gè)數(shù)據(jù)源。這時(shí)候應(yīng)該選哪個(gè)實(shí)現(xiàn)類阀坏？其實(shí)明白這三者區(qū)別就很容易選了如暖。
- ArrayList內(nèi)部實(shí)現(xiàn)是個(gè)數(shù)組、有序存儲(chǔ)忌堂。數(shù)組大家都知道長(zhǎng)度不可變盒至，那么append數(shù)據(jù)消耗可能會(huì)比較大，因?yàn)榭赡軙?huì)需要resize士修，如果是insert或者remove數(shù)據(jù)消耗就會(huì)比較大枷遂，因?yàn)樾枰獢?shù)組拷貝。但是get速度非称宄埃快酒唉，因?yàn)榭梢灾苯诱业綄?duì)應(yīng)位置。
private static List<String> add0(String[] array) {
List<String> list = new ArrayList<>();
for (String s : array) {
list.add(s);
}
return list;
}
private static List<String> add1(String[] array) {
List<String> list = new ArrayList<>();
list.addAll(Arrays.asList(array));
return list;
}
private static void remove0(List<String> list, int index, int count) {
for (int i = 0; i < count; i++) {
list.remove(index + i);
}
}
private static void remove1(List<String> list, int index, int count) {
list.subList(index, index + count).clear();
}
add0和add1哪個(gè)寫法好沸移？remove0和remove1哪個(gè)寫法好黔州？add0一個(gè)個(gè)把數(shù)據(jù)add到ArrayList，最多ArrayList可能會(huì)發(fā)生array.length次數(shù)組resize阔籽。但是add1就最多只會(huì)發(fā)生一次數(shù)組resize。remove0和remove1也是一樣牲蜀。
- LinkedList 看名字就知道這是一個(gè)鏈表實(shí)現(xiàn)的List笆制，內(nèi)部不再有數(shù)組。那么對(duì)于鏈表來(lái)說(shuō)添加數(shù)據(jù)就是打開(kāi)鏈條涣达，接上鏈條在辆，再鎖上鏈條的過(guò)程。如果是頻發(fā)插入數(shù)據(jù)度苔，比如數(shù)據(jù)從1條連續(xù)插入到10萬(wàn)條匆篓，效率可以認(rèn)為是一樣。但是要get數(shù)據(jù)就比較坑了寇窑，通過(guò)index并不能直接定位到數(shù)據(jù)鸦概，所以就需要遍歷數(shù)據(jù)了。remove數(shù)據(jù)也一樣甩骏，只要任何是設(shè)計(jì)到index的操作效率都會(huì)比較低窗市，除了頭和尾，因?yàn)長(zhǎng)inkedList針對(duì)頭尾做了緩存饮笛。
- Vector 平時(shí)見(jiàn)的會(huì)非常少咨察，它內(nèi)部實(shí)現(xiàn)也是用數(shù)組，但跟ArrayList不同的是它是線程安全的福青，你會(huì)發(fā)現(xiàn)它方法有synchronized關(guān)鍵字摄狱。除了這點(diǎn)其他特性可以認(rèn)為是等同于ArrayList脓诡。
好，又回到前面老問(wèn)題媒役，RecyclerView的Adapter應(yīng)該用什么數(shù)據(jù)結(jié)構(gòu)祝谚？我們思考下Adapter的應(yīng)用場(chǎng)景。通常Adapter不會(huì)非常頻繁的添加數(shù)據(jù)刊愚，每次滑過(guò)RecyclerView都會(huì)觸發(fā)onBindViewHolder踊跟，要bind就一定需要從數(shù)據(jù)源通過(guò)index取數(shù)據(jù)出來(lái)，取操作會(huì)比較頻繁鸥诽，那我們肯定不能用LinkedList了（但其實(shí)考慮到RecyclerView顯示數(shù)據(jù)都是連續(xù)的商玫，所以如果用鏈表來(lái)訪問(wèn)臨近數(shù)據(jù)效率反而會(huì)更高），又因?yàn)锳dapter基本上不會(huì)出現(xiàn)要去子線程操作數(shù)據(jù)源的情況牡借。所以也不需要線程安全拳昌。剩下的就當(dāng)然是ArrayList了，而且ArrayList取效率本來(lái)就非常高钠龙，完全符合需求炬藤。
Map
Map是一個(gè)鍵值對(duì)數(shù)據(jù)結(jié)構(gòu)。Map的實(shí)現(xiàn)類也非常多碴里，但主要是：HashMap沈矿、LinkedHashMap，TreeMap咬腋，HashTable羹膳，Android里又加了ArrayMap和SparseArray。Map跟List不一樣的是不光能存數(shù)據(jù)了根竿，還能額外多保存一個(gè)key陵像。那有個(gè)問(wèn)題，假如我新建一個(gè)下面這樣的Data類寇壳。然后把所有鍵值對(duì)通過(guò)Data對(duì)象保存到List里醒颖，那我不是一樣實(shí)現(xiàn)了鍵值對(duì)保存嗎？
public class Data<K,V>{
private K mKey;
private V mValue;
public Data(K key, V value) {
mKey = key;
mValue = value;
}
public K getKey() {
return mKey;
}
public void setKey(K key) {
mKey = key;
}
public V getValue() {
return mValue;
}
public void setValue(V value) {
mValue = value;
}
}
那我為什么要用各種Map實(shí)現(xiàn)類呢壳炎？還是同樣的問(wèn)題泞歉，雖然功能上確實(shí)能實(shí)現(xiàn)但是效率上不同的實(shí)現(xiàn)方式差別會(huì)非常大。
- HashMap
大家寫Map可能絕大部分情況下都是使用HashMap匿辩。HashMap底層是通過(guò)數(shù)組加鏈表（Java1.8新加了紅黑樹(shù)）來(lái)實(shí)現(xiàn)疏日。為什么要搞這么復(fù)雜呢？又是數(shù)組又是鏈表又是樹(shù)的撒汉？其實(shí)還是為了提高效率沟优。上面的把鍵值對(duì)封裝成Data，加到List中睬辐。get效率跟HashMap比就會(huì)非常慘了挠阁。因?yàn)間et只能一個(gè)個(gè)去遍歷宾肺，但是HashMap就可以通過(guò)key的hashcode非常高效的get數(shù)據(jù)。 - LinkedHashMap
看名字就知道多了個(gè)Linked侵俗，意思就是排序锨用。LinkedHashMap本身就是繼承自HashMap，所以增刪改查方面和HashMap基本是一致的隘谣。區(qū)別主要就是通過(guò)entrySet遍歷了增拥。LinkedHashMap會(huì)保存元素的添加順序然后按順序遍歷，但HashMap就是無(wú)序了寻歧。 - TreeMap
TreeMap內(nèi)部是個(gè)紅黑樹(shù)掌栅。從使用角度來(lái)看，它跟LinkedHashMap主要區(qū)別就LinkedHashMap保存的是元素的插入順序码泛，而TreeMap則是對(duì)key排序猾封。遍歷可以得到一個(gè)按key排序的結(jié)果。 - HashTable
內(nèi)部是個(gè)鏈表噪珊，另外就是線程同步晌缘。 - SparseArray
SparseArray內(nèi)部依然是使用數(shù)組來(lái)實(shí)現(xiàn)。但是限制了key只能int痢站，而且沒(méi)有裝箱磷箕，HashMap的key只能是Integer。所以Sparse性能會(huì)更好阵难，它內(nèi)部做了數(shù)據(jù)壓縮搀捷，來(lái)稀疏數(shù)組的數(shù)據(jù)，節(jié)省內(nèi)存多望。 - ArrayMap
ArrayMap內(nèi)部也是使用數(shù)組。查找數(shù)據(jù)會(huì)通過(guò)二分法來(lái)提高效率氢烘，Google推薦用ArrayMap來(lái)代替HashMap怀偷。
