本平臺的文章更新會有延遲闯两，大家可以關(guān)注微信公眾號-顧林海，包括年底前會更新kotlin由淺入深系列教程谅将，目前計劃在微信公眾號進行首發(fā)漾狼，如果大家想獲取最新教程，請關(guān)注微信公眾號饥臂，謝謝
在Android應(yīng)用開發(fā)中逊躁，HashMap使用最頻繁的容器之一，但它并不是最節(jié)約的容器隅熙，會占用大量內(nèi)存志衣。
HashMap是一個散列鏈表，向HashMap中put元素時猛们，先根據(jù)key的HashCode重新計算hash值，根據(jù)hash值得到這個元素在數(shù)組中的位置狞洋，如果該位置已經(jīng)存放了其他元素弯淘，那么在這個位置上的元素將以鏈表的形式存放，新加入的放鏈頭吉懊，最先加入的放鏈尾庐橙。如果該位置上沒有元素假勿，就直接將該元素放到此數(shù)組中指定的位置。
也就是說态鳖，向HashMap插入一個對象前转培，會給一個通向Hash陣列的索引，在索引的位置中浆竭，保存了這個Key對象的值浸须。
這意味著需要考慮的一個最大問題是沖突，也就是Hash沖突邦泄，當多個對象散列于陣列相同位置時删窒，就會有散列沖突的問題。因此顺囊，HashMap會配置一個大的數(shù)組來減少潛在的沖突肌索，并且會有其他的邏輯防止鏈接算法和一些沖突的發(fā)生。
從節(jié)省內(nèi)存的角度來看特碳，使用HashMap不是一個正確的選擇诚亚，為此Android提供了一個替代容器，也就是ArrayMap午乓。
ArrayMap提供了和HashMap一樣的功能站宗，但能避免過多的內(nèi)存開銷，方法是使用兩個小數(shù)組硅瞧，而不是一個大數(shù)組份乒。其中一個數(shù)組記錄對象Key Hash過后的順序列表，另一個數(shù)組按Key的順序記錄Key-Value值腕唧，根據(jù)Key數(shù)組的順序或辖，交織在一起。
在需要獲取某個Value時枣接，ArrayMap會計算輸入Key轉(zhuǎn)換過后的hash值颂暇，然后使用二分查找法對Hash數(shù)組尋找到對應(yīng)的index，然后可以通過這個index在另外一個數(shù)組中直接訪問需要的鍵值對但惶。如果在第二個數(shù)組鍵值對中的key和前面輸入的查詢key不一致耳鸯，就認為發(fā)生了碰撞沖突。為了解決這個問題膀曾，ArrayMap會以該key為中心點县爬，分別上下展開，逐個對比查找添谊，直到找到匹配的值财喳。
因此會帶來一個問題，就是隨著ArrayMap中對象數(shù)量的增加，需要訪問單獨對象的時間也會變長耳高。
在ArrayMap中執(zhí)行插入或者刪除操作時扎瓶，從性能角度上看，比HashMap還要更差一些泌枪，但如果只涉及很小的對象數(shù)概荷，比如1000以下，就不需要擔心這個問題碌燕。當值特別小時误证，相比HashMap，ArrayMap能節(jié)省更多的內(nèi)存陆蟆。
使用ArrayMap總結(jié)如下：
當對象的數(shù)目非常欣壮А（1000以內(nèi)），但是訪問特別多叠殷，或者刪除和插入頻率不高時使用ArrayMap改鲫。
當有映射容器，有映射時林束，并且所有映射的容器也是ArrayMap時使用ArrayMap像棘。
LinkedHashMap 直接繼承自HashMap ，這也就說明了 HashMap 一切重要的概念 LinkedHashMap 都是擁有的壶冒，這就包括了缕题，hash 算法定位 hash 桶位置，哈希表由數(shù)組和單鏈表構(gòu)成胖腾，并且當單鏈表長度超過 8 的時候轉(zhuǎn)化為紅黑樹烟零，擴容體系，這一切都跟 HashMap 一樣咸作。那么除了這么多關(guān)鍵的相同點以外锨阿，LinkedHashMap 比 HashMap 更加強大，這體現(xiàn)在：
LinkedHashMap 內(nèi)部維護了一個雙向鏈表记罚，解決了 HashMap 不能隨時保持遍歷順序和插入順序一致的問題
LinkedHashMap 元素的訪問順序也提供了相關(guān)支持墅诡，也就是我們常說的 LRU（最近最少使用）原則。
LinkedHashMap 擁有與 HashMap 相同的底層哈希表結(jié)構(gòu)桐智，即數(shù)組 + 單鏈表 + 紅黑樹末早，也擁有相同的擴容機制。相比 HashMap 的拉鏈式存儲結(jié)構(gòu)说庭，內(nèi)部額外通過 Entry 維護了一個雙向鏈表然磷。HashMap 元素的遍歷順序不一定與元素的插入順序相同，而 LinkedHashMap 則通過遍歷雙向鏈表來獲取元素刊驴，所以遍歷順序在一定條件下等于插入順序样屠。LinkedHashMap 可以通過構(gòu)造參數(shù)accessOrder 來指定雙向鏈表是否在元素被訪問后改變其在雙向鏈表中的位置。
Android、Java痪欲、Python、Go攻礼、PHP业踢、IOS、C++礁扮、HTML等等技術(shù)文章知举，更有各種書籍推薦和程序員資訊，快來加入我們吧太伊！關(guān)注技術(shù)共享筆記雇锡。
搜索微信“顧林海”公眾號僚焦，定期推送優(yōu)質(zhì)文章锰提。
