? ? ?對于性能優(yōu)化朝扼，主要是從這幾個方面進行探討：數(shù)據(jù)結構，啟動速度霎肯，布局擎颖，電量和網絡，apk的大小等观游。本文從數(shù)據(jù)結構的角度進行舉例：
1.學習數(shù)據(jù)結構優(yōu)化的必要性：
? ? ?在我們開發(fā)過程中搂捧，選好一個合適的數(shù)據(jù)結構或者說一個數(shù)據(jù)容器是尤其重要的，根據(jù)其優(yōu)點懂缕，規(guī)避其缺點允跑。比如ArrayList的優(yōu)點是取元素快，但是存（這里指代替換某個元素）或者刪除則效率并不高提佣。所以當一個功能替換某個元素頻繁或者刪除某個元素頻繁時候吮蛹，則顯然不是一個好的選擇。一款app除了要有令人驚嘆的功能和令人發(fā)指的交互之外拌屏，在性能上也應該追求絲滑的要求潮针，這樣才能更好地提高用戶體驗。但是如何更好的理解或者說自己能寫出一個好的算法倚喂，則取決于我們對各個容器的特定認識每篷。并且這個東西一天兩天是講不清楚的，還需要長久的去刷題端圈，去練習焦读。這里提供一個刷題網站。-----------leetcode. ?相信每天刷幾道舱权，將會收獲很多矗晃。
本文將從這幾個點進行分析：ArrayList,LinkedList,HashMap,SparseArray,ArrayMap
首先我們從ArrayList看起：
它是一個線性數(shù)據(jù)結構，并且又是一個順序表宴倍。它的特點是：
優(yōu)點：它在物理上(內存)連續(xù),所以查找元素快张症。
缺點：刪除和增加元素需要大量移動元素仓技。增刪慢。
比如：(ArrayList內部實際上是一個數(shù)組)一個數(shù)組：int[] elementData. ? 如何能準確獲取elementData數(shù)組的第i個元素呢俗他？因為我們知道內存是連續(xù)的脖捻。elementData占四個字節(jié)，假設elementData的內存地址是0xfaff456 則第i的元素為：0xfaff456+I*4.
那如何解決這個缺點呢兆衅？這里就有一個LinkedList：
LinkedList是個什么地沮？它是一個鏈表結構的容器。
優(yōu)點：空間不連續(xù)羡亩，邏輯上連續(xù),刪除增加元素快
缺點：物理上不連續(xù)摩疑，查找要輪詢。查找慢畏铆。
LinkedList是一個雙鏈表未荒，內部有一個指向下一個節(jié)點和一個指向上一個節(jié)點的指針（ 如果第一個指向最后一個元素 最后一個指向第一個節(jié)點：形成了環(huán)，就是環(huán)形鏈表）,為什么說它刪除添加元素快呢及志？如下圖：
所以LinkedList不需要去重新移動元素（直接挪動指針）片排，從而讓添加和刪除元素性能得到提高，但是獲取元素就只能去遍歷了（內存不是連續(xù)的）速侈。
現(xiàn)在糾結一個問題率寡，有沒有一種數(shù)據(jù)結構能同時包含上面兩種優(yōu)點呢：HashMap
現(xiàn)在在面試上HashMap是面試大概率是會問的，所以在這里我們來探究一下HashMap.
HashMap是由什么構成的呢倚搬？
在1.7版本之前冶共，是由數(shù)組+鏈表構成的。
在1.8版本之后每界，是由數(shù)組+鏈表+紅黑樹組成的捅僵。
看一下HashMap是如何存放數(shù)據(jù)的：
存放：
? ? ? ? ?先計算hash的值，根據(jù)hash的值找到數(shù)組位置（下標）眨层，再往鏈表中添加元素庙楚。?
? ? ? （源碼里：h & (length-1)源碼里） == ? ??hashCode % length ?= 下標的位置： 這兩個公式其實是相等的。
? ? ? ? ?糾結：為什么源碼要用位運算,因為位運算效率是更高的趴樱。
? ? ? ? ?hash碰撞：當存入的兩個key值計算的hash是相同的馒闷，則就產生了hash碰撞，所以引入了鏈表解決hash碰撞叁征。
查找：?
? ? ? ? 先計算key的hash的值,根據(jù)hash值找到數(shù)組位置纳账，再進行遍歷數(shù)組，找到對應的元素捺疼。
刪除：
? ? ? ? ?先計算key的hash的值 ?疏虫，根據(jù)hash值找到數(shù)組位置，再從遍歷的鏈表中刪除節(jié)點。
HashMap 的擴容（請看源碼）：
? ? ? ? 加載因子：Default_load_factory = 0.75;
? ? ? ? 閾值：0.75 * 16 = 12;
? ? ? ? hash 的元素大于12的時候就擴容卧秘。超過百分之75容量的時候就擴容
源碼中有一個加載因子默認是0.75尤蛮，則其閾值位0.75 * 16 = 12 ,也就是說，當HashMap的元素個數(shù)大于12的時候就進行擴容斯议，這里有一個標準，就是擴容的大小是2的次冪醇锚。
擴容的意義：（默認的hashMap的大小 == 16）
數(shù)學家研究發(fā)現(xiàn)在0.6~0.75最合適哼御，因為避免hash值總是計算相同，這樣很多元素都放在了一個鏈表中焊唬，這樣形成了單鏈表恋昼，很顯然這樣會影響性能，這樣擴容是為了避免沖突成單鏈表.
糾結一個問題赶促，擴容肯定是會影響性能的液肌。因為在擴容的時候，原本長度變了鸥滨，所以hash值就變了嗦哆，原本的元素都要重新進行計算，則就影響了性能婿滓。 那么hashMap是如何進行初始化的老速，為了節(jié)省內存，hashmap的初始化操作是在put中進行的（在用到的時候才真正初始化hash表凸主，不用的時候就不初始化了）橘券；
那么為什么HashMap是2的次冪呢？
? ? ? ?是為了這個運算 ?h& (length-1)
如果是length = 16 ?則16-1: ? ?二進制為1111
如果不是2的次冪卿吐，如果是length =?10呢旁舰？ 10-1:二進制1001
現(xiàn)在有一個hash值為6 二進制為110
現(xiàn)在有一個hash值為7 二進制為111
現(xiàn)在6對length =??16求模運算： ??現(xiàn)在6對length = 10求模運算：
? 110. ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?110
1111 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??1001
結果：0110 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?結果：0000
現(xiàn)在7對length =??16求模運算： ? ?現(xiàn)在7對length = 10求模運算：?
? 111 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???111
1111 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???1001
結果：0111 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?結果：?0001
可以看出：只有最高位和最低為有用，如果都是1嗡官，則四位都可以得到不一樣的值箭窜，所以更可以大的避免hash碰撞,從這個細節(jié)上來說又進行優(yōu)化了一次。
在前面可以看到我們因為只有75%的空間可以使用衍腥，但是浪費了25%绽快，我們還有什么數(shù)據(jù)結構對這個空間進行優(yōu)化了嗎？
Android量身定制：sparseArray;
sparseArray ：
? ? ? ? ? ? ? ? ? ? ? 雙數(shù)組結構紧阔。 一個數(shù)組存key,一個存value坊罢。但是key值只能存放int型的數(shù)據(jù)。內部采用了二分查找的方法.
? ? 增加：
? ? ? ? ? ? ? ? ? ? ? 根據(jù)key值進行二分查找,找到可以添加元素的位置擅耽，然后插入數(shù)據(jù)并移動數(shù)據(jù)
? ? 查找：
? ? ? ? ? ? ? ? ? ? ? ?根據(jù)key值進行二分查找,找到數(shù)組下標,取出對應的value值
? ? 刪除：
? ? ? ? ? ? ? ? ? ? ? ? 根據(jù)key值進行二分查找, ?找到數(shù)組下標,?然后將value數(shù)組上的元素標記為delete活孩，并不是真的刪除，等下次再有有效的元素直接 ? ? ? ? ? ? ? ? ? ? 添加進來乖仇，不用進行移動數(shù)據(jù). ??
但是這個容器也是有缺點的因為key只能放入int型的數(shù)據(jù)憾儒。
ArrayMap: ? 任意類型的key
? ? ? hashmap + sparseMap.
這個也是有hash沖突的询兴，因為key值也要進行hash計算，當有hash沖突的時候起趾，則直接進行添加到第二個位置诗舰，比如在1的下標處有一個節(jié)點了，則直接追加到2的位置训裆。
