1.ArrayMap 綜述
特點(diǎn)：
1).實(shí)現(xiàn)了Map接口，并使用int[]數(shù)來(lái)存儲(chǔ)key的hash值宅广，數(shù)組的索引用作index，而使用Object[]數(shù)組來(lái)存儲(chǔ)key<->value 包券，這還是比較新穎的首妖。
2).使用二分查找查找hash值在key數(shù)組中的位置，然后根據(jù)這個(gè)位置得到value數(shù)組中對(duì)應(yīng)位置的元素塔次。
3).和SparseArray類(lèi)似方篮，當(dāng)數(shù)據(jù)有幾百條時(shí)，性能會(huì)比HashMap低50%励负，因此ArrayMap適用于數(shù)據(jù)量很小的場(chǎng)景藕溅。
2.ArrayMap和HashMap的區(qū)別？
1).ArrayMap的存在是為了解決HashMap占用內(nèi)存大的問(wèn)題继榆，它內(nèi)部使用了一個(gè)int數(shù)組用來(lái)存儲(chǔ)元素的hashcode巾表，使用了一個(gè)Object數(shù)組用來(lái)存儲(chǔ)元素汁掠，兩者根據(jù)索引對(duì)應(yīng)形成key-value結(jié)構(gòu)，這樣就不用像HashMap那樣需要額外的創(chuàng)建Entry對(duì)象來(lái)存儲(chǔ)集币，減少了內(nèi)存占用考阱。但是在數(shù)據(jù)量比較大時(shí)，ArrayMap的性能就會(huì)遠(yuǎn)低于HashMap鞠苟，因?yàn)?ArrayMap基于二分查找算法來(lái)查找元素的乞榨，并且數(shù)組的插入操作如果不是末尾的話需要挪動(dòng)數(shù)組元素，效率較低偶妖。
2).而HashMap內(nèi)部基于數(shù)組+單向鏈表+紅黑樹(shù)實(shí)現(xiàn)姜凄，也是key-value結(jié)構(gòu)， 正如剛才提到的趾访，HashMap每put一個(gè)元素都需要?jiǎng)?chuàng)建一個(gè)Entry來(lái)存放元素态秧，導(dǎo)致它的內(nèi)存占用會(huì)比較大，但是在大數(shù)據(jù)量的時(shí)候扼鞋，因?yàn)镠ashMap中當(dāng)出現(xiàn)沖突時(shí)申鱼，沖突的數(shù)據(jù)量大于8，就會(huì)從單向鏈表轉(zhuǎn)換成紅黑樹(shù)云头，而紅黑樹(shù)的插入捐友、刪除、查找的時(shí)間復(fù)雜度為O(logn),相對(duì)于ArrayMap的數(shù)組而言在插入和刪除操作上要快不少溃槐，所以數(shù)據(jù)量上百的情況下匣砖，使用HashMap會(huì)有更高的效率。
3.如何解決沖突問(wèn)題昏滴？
在ArrayMap中猴鲫，假設(shè)存在沖突的話，并不會(huì)像HashMap那樣使用單向鏈表或紅黑樹(shù)來(lái)保留這些沖突的元素谣殊，而是全部key拂共、value都存儲(chǔ)到一個(gè)數(shù)組當(dāng)中，然后查找的話通過(guò)二分查找進(jìn)行姻几，這也就是當(dāng)數(shù)據(jù)量大時(shí)不宜用ArrayMap的原因了宜狐。
4.HashMap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)
數(shù)組+鏈表/紅黑樹(shù)
5.HashMap允許空鍵空值么？
HashMap最多只允許一個(gè)鍵為Null(多條會(huì)覆蓋)蛇捌，但允許多個(gè)值為Null抚恒。
6.影響HashMap性能的重要參數(shù)
初始容量：創(chuàng)建哈希表(數(shù)組)時(shí)的數(shù)量，默認(rèn)為16络拌。在不指定capacity情況下柑爸，初始化容量是16，但不是初始化的時(shí)候就創(chuàng)建了一個(gè)16大小的數(shù)組盒音，而是在第一次put的時(shí)候去判斷是否需要初始化表鳍。太小了就有可能頻繁發(fā)生擴(kuò)容，影響效率祥诽。太大了又浪費(fèi)空間譬圣，不劃算。所以雄坪，16就作為一個(gè)經(jīng)驗(yàn)值被采用了厘熟。
負(fù)載因子(擴(kuò)容因子,加載因子)：哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度，默認(rèn)為 0.75维哈。擴(kuò)容因子是用來(lái)判斷當(dāng)前數(shù)組(“哈希桶”)什么時(shí)候需要進(jìn)行擴(kuò)容绳姨，假設(shè)因子為0.5，那么HashMap的初始化容量是16阔挠，則16*0.5 = 8個(gè)元素的時(shí)候飘庄，HashMap就會(huì)進(jìn)行擴(kuò)容。
7.為什么擴(kuò)容因子是0.75购撼？
擴(kuò)容因子設(shè)置比較大的時(shí)候跪削，相當(dāng)于擴(kuò)容的門(mén)檻就變高了，發(fā)生擴(kuò)容的頻率變低了迂求，但此時(shí)發(fā)生Hash沖突的幾率就會(huì)提升碾盐，當(dāng)沖突的元素過(guò)多的時(shí)候，變成鏈表或者紅黑樹(shù)都會(huì)增加了查找成本（hash 沖突增加揩局，鏈表長(zhǎng)度變長(zhǎng)）毫玖。而擴(kuò)容因子過(guò)小的時(shí)候，會(huì)頻繁觸發(fā)擴(kuò)容凌盯，占用的空間變大付枫，比如重新計(jì)算Hash等，使得操作性能會(huì)比較高十气。
8.HashMap的工作原理
HashMap是基于hashing的原理励背，我們使用put(key, value)存儲(chǔ)對(duì)象到HashMap中，使用get(key)從HashMap中獲取對(duì)象砸西。
9.new HashMap()
在JDK 8中叶眉，在調(diào)用new HashMap()的時(shí)候并沒(méi)有分配數(shù)組堆內(nèi)存，只是做了一些參數(shù)校驗(yàn)芹枷，初始化了一些常量衅疙。
10.HashMap什么時(shí)候開(kāi)辟bucket數(shù)組占用內(nèi)存？
在HashMap第一次put的時(shí)候調(diào)用resize方法鸳慈，無(wú)論Java 8還是Java 7都是這樣實(shí)現(xiàn)的饱溢。
11.HashMap是線程不安全的
在jdk1.7中，在多線程環(huán)境下走芋，擴(kuò)容時(shí)會(huì)造成環(huán)形鏈或數(shù)據(jù)丟失绩郎，在jdk1.8中潘鲫，在多線程環(huán)境下，會(huì)發(fā)生數(shù)據(jù)覆蓋的情況肋杖。
12.HashMap在1.8中做了如下優(yōu)化：
①數(shù)組+鏈表改成了數(shù)組+鏈表或紅黑樹(shù)溉仑；
②鏈表的插入方式從頭插法改成了尾插法；
③擴(kuò)容的時(shí)候1.7需要對(duì)原數(shù)組中的元素進(jìn)行重新hash定位在新數(shù)組的位置状植，1.8采用更簡(jiǎn)單的判斷邏輯浊竟，位置不變或索引+舊容量大小津畸；
④在插入時(shí)振定，1.7先判斷是否需要擴(kuò)容，再插入肉拓，1.8先進(jìn)行插入后频，插入完成再判斷是否需要擴(kuò)容。
13.Java8中為什么要引進(jìn)紅黑樹(shù)帝簇，是為了解決什么場(chǎng)景的問(wèn)題徘郭？
引入紅黑樹(shù)是為了避免hash性能急劇下降，引起HashMap的讀寫(xiě)性能急劇下降的場(chǎng)景丧肴，正常情況下残揉，一般是不會(huì)用到紅黑樹(shù)的，在一些極端場(chǎng)景下芋浮，假如客戶端實(shí)現(xiàn)了一個(gè)性能拙劣的hashCode方法抱环，可以保證HashMap的讀寫(xiě)復(fù)雜度不會(huì)低于O(lgN)。
14.HashMap如何處理key為null的鍵值對(duì)
放置在桶數(shù)組中下標(biāo)為0的桶中纸巷。
15.桶中的元素鏈表何時(shí)轉(zhuǎn)換為紅黑樹(shù)镇草，什么時(shí)候轉(zhuǎn)回鏈表，為什么要這么設(shè)計(jì)瘤旨？
當(dāng)同一個(gè)桶中的元素?cái)?shù)量大于等于8的時(shí)候元素中的鏈表轉(zhuǎn)換為紅黑樹(shù)梯啤，反之，當(dāng)桶中的元素?cái)?shù)量小于等于6的時(shí)候又會(huì)轉(zhuǎn)為鏈表存哲，這樣做的原因是避免紅黑樹(shù)和鏈表之間頻繁轉(zhuǎn)換因宇，引起性能損耗。
16.ArrayList介紹
ArrayList是一個(gè)數(shù)組隊(duì)列祟偷，相當(dāng)于動(dòng)態(tài)數(shù)組察滑。與Java中的數(shù)組相比，它的容量能動(dòng)態(tài)增長(zhǎng)修肠。它繼承于AbstractList贺辰，實(shí)現(xiàn)了List，RandomAccess，Cloneable饲化，java.io.Serializable這些接口莽鸭。
17.ArrayList的線程安全性
對(duì)ArrayList進(jìn)行添加元素的操作的時(shí)候是分兩個(gè)步驟進(jìn)行的:
1).即第一步先在object[size]的位置上存放需要添加的元素；
2).第二步將size的值增加1吃靠。
由于這個(gè)過(guò)程在多線程的環(huán)境下是不能保證具有原子性的蒋川，因此ArrayList在多線程的環(huán)境下是線程不安全的。
18.ArrayList的數(shù)據(jù)結(jié)構(gòu)
ArrayList的底層數(shù)據(jù)結(jié)構(gòu)就是一個(gè)數(shù)組撩笆，數(shù)組元素的類(lèi)型為Object類(lèi)型，對(duì)ArrayList的所有操作底層都是基于數(shù)組的缸浦。
19.ArrayList常用優(yōu)化方案
1).如果事先能夠估算ArrayList需要的長(zhǎng)度夕冲，可在構(gòu)造時(shí)指定初始數(shù)組長(zhǎng)度，節(jié)省擴(kuò)容開(kāi)銷(xiāo)裂逐。
2).頻繁調(diào)用void add(int index, E element)函數(shù)且指定下標(biāo)位置靠前時(shí)歹鱼，考慮轉(zhuǎn)換為L(zhǎng)inkedList。
3).調(diào)用boolean contains(Object o) 函數(shù)比較頻繁時(shí)卜高，可以考慮把元素放入HashSet里進(jìn)行查詢(xún)弥姻。
20.ArrayList優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
1).ArrayList底層以數(shù)組實(shí)現(xiàn)，是一種隨機(jī)訪問(wèn)模式掺涛，再加上它實(shí)現(xiàn)了RandomAccess接口庭敦，因此查找也就是get的時(shí)候非常快薪缆。
2).ArrayList在順序添加一個(gè)元素的時(shí)候非常方便秧廉，只是往數(shù)組里面添加了一個(gè)元素而已。
3).根據(jù)下標(biāo)遍歷元素拣帽，效率高疼电。
4).根據(jù)下標(biāo)訪問(wèn)元素，效率高减拭。
5).可以自動(dòng)擴(kuò)容蔽豺，默認(rèn)為每次擴(kuò)容為原來(lái)的1.5倍。
6).修改元素和通過(guò)下標(biāo)查詢(xún)?cè)匦矢摺?/p>
7).集合是有順序的拧粪。
缺點(diǎn)：
1).插入和刪除元素的效率不高修陡。
2).根據(jù)元素下標(biāo)查找元素需要遍歷整個(gè)元素?cái)?shù)組，效率不高既们。
3).線程不安全濒析。
4).刪除元素效率低，因?yàn)橐ㄟ^(guò)拷貝數(shù)組來(lái)實(shí)現(xiàn)啥纸。
5).大量新增效率低号杏，因?yàn)榇罅啃略龅臅r(shí)候要不斷進(jìn)行擴(kuò)容和數(shù)組的拷貝。
6)清除集合效率低，因?yàn)榍宄δ苁峭ㄟ^(guò)循環(huán)數(shù)組進(jìn)行清除的盾致。
7).移除元素后主经，容量有大量剩余，需要手動(dòng)調(diào)用trimToSize進(jìn)行清理庭惜。
21.LinkedList()和ArrayList()
ArrayList() : 代表長(zhǎng)度可以改變得數(shù)組罩驻。可以對(duì)元素進(jìn)行隨機(jī)的訪問(wèn)护赊，向ArrayList()中插入與刪除元素的速度慢惠遏。
LinkedList()：在實(shí)現(xiàn)中采用鏈表數(shù)據(jù)結(jié)構(gòu)。插入和刪除速度快骏啰，訪問(wèn)速度慢节吮。
22.ArrayMap和HashMap的對(duì)比
1).存儲(chǔ)方式不同。
HashMap內(nèi)部有一個(gè)HashMapEntry<K, V>[]對(duì)象判耕，每一個(gè)鍵值對(duì)都存儲(chǔ)在這個(gè)對(duì)象里透绩，當(dāng)使用put方法添加鍵值對(duì)時(shí)，就會(huì)new一個(gè)HashMapEntry對(duì)象壁熄。
2).添加數(shù)據(jù)時(shí)擴(kuò)容時(shí)的處理不一樣帚豪，進(jìn)行了new操作，重新創(chuàng)建對(duì)象草丧，開(kāi)銷(xiāo)很大狸臣。ArrayMap用的是copy數(shù)據(jù)，所以效率相對(duì)要高方仿。
3).ArrayMap提供了數(shù)組收縮的功能固棚，在clear或remove后，會(huì)重新收縮數(shù)組仙蚜，是否空間此洲。
4).ArrayMap采用二分法查找。
23.HashMap和HashTable的區(qū)別委粉？
1).HashMap不是線程安全的呜师，效率高一點(diǎn)、方法不是Synchronize的要提供外同步贾节，有containsvalue和containsKey方法汁汗。
2).hashtable是線程安全，不允許有null的鍵和值栗涂，效率稍低知牌，方法是是Synchronize的。有contains方法方法斤程。Hashtable 繼承于Dictionary 類(lèi)角寸。
24.ArrayList和LinkedList的區(qū)別，以及應(yīng)用場(chǎng)景。
ArrayList是基于數(shù)組實(shí)現(xiàn)的扁藕，ArrayList線程不安全沮峡。
LinkedList是基于雙鏈表實(shí)現(xiàn)的。
使用場(chǎng)景：
1).如果應(yīng)用程序?qū)Ω鱾€(gè)索引位置的元素進(jìn)行大量的存取或刪除操作亿柑，ArrayList對(duì)象要遠(yuǎn)優(yōu)于LinkedList對(duì)象邢疙；
2).如果應(yīng)用程序主要是對(duì)列表進(jìn)行循環(huán)，并且循環(huán)時(shí)候進(jìn)行插入或者刪除操作望薄，LinkedList對(duì)象要遠(yuǎn)優(yōu)于ArrayList對(duì)象疟游。
25.HashMap與HashSet的區(qū)別？
hashMap:HashMap實(shí)現(xiàn)了Map接口,HashMap儲(chǔ)存鍵值對(duì),使用put()方法將元素放入map中,HashMap中使用鍵對(duì)象來(lái)計(jì)算hashcode值,HashMap比較快痕支，因?yàn)槭鞘褂梦ㄒ坏逆I來(lái)獲取對(duì)象乡摹。
HashSet實(shí)現(xiàn)了Set接口，HashSet僅僅存儲(chǔ)對(duì)象采转，使用add()方法將元素放入set中，HashSet使用成員對(duì)象來(lái)計(jì)算hashcode值瞬痘，對(duì)于兩個(gè)對(duì)象來(lái)說(shuō)hashcode可能相同故慈，所以equals()方法用來(lái)判斷對(duì)象的相等性，如果兩個(gè)對(duì)象不同的話框全，那么返回false察绷。HashSet較HashMap來(lái)說(shuō)比較慢。
26.數(shù)組和鏈表的區(qū)別津辩？
數(shù)組：是將元素在內(nèi)存中連續(xù)存儲(chǔ)的拆撼；它的優(yōu)點(diǎn)：因?yàn)閿?shù)據(jù)是連續(xù)存儲(chǔ)的，內(nèi)存地址連續(xù)喘沿，所以在查找數(shù)據(jù)的時(shí)候效率比較高闸度；它的缺點(diǎn)：在存儲(chǔ)之前，我們需要申請(qǐng)一塊連續(xù)的內(nèi)存空間蚜印，并且在編譯的時(shí)候就必須確定好它的空間的大小莺禁。在運(yùn)行的時(shí)候空間的大小是無(wú)法隨著你的需要進(jìn)行增加和減少而改變的，當(dāng)數(shù)據(jù)兩比較大的時(shí)候窄赋，有可能會(huì)出現(xiàn)越界的情況哟冬，數(shù)據(jù)比較小的時(shí)候，又有可能會(huì)浪費(fèi)掉內(nèi)存空間忆绰。在改變數(shù)據(jù)個(gè)數(shù)時(shí)浩峡，增加、插入错敢、刪除數(shù)據(jù)效率比較低翰灾。
鏈表：是動(dòng)態(tài)申請(qǐng)內(nèi)存空間，不需要像數(shù)組需要提前申請(qǐng)好內(nèi)存的大小，鏈表只需在用的時(shí)候申請(qǐng)就可以预侯，根據(jù)需要來(lái)動(dòng)態(tài)申請(qǐng)或者刪除內(nèi)存空間致开，對(duì)于數(shù)據(jù)增加和刪除以及插入比數(shù)組靈活。還有就是鏈表中數(shù)據(jù)在內(nèi)存中可以在任意的位置萎馅，通過(guò)應(yīng)用來(lái)關(guān)聯(lián)數(shù)據(jù)（就是通過(guò)存在元素的指針來(lái)聯(lián)系）双戳。
27.LinkedList
LinkedList本質(zhì)上是一個(gè)雙向鏈表的存儲(chǔ)結(jié)構(gòu)。
對(duì)于元素查詢(xún)來(lái)說(shuō)糜芳，ArrayList優(yōu)于LinkedList飒货，因?yàn)長(zhǎng)inkedList要移動(dòng)指針。對(duì)于新增和刪除操作峭竣，LinedList比較占優(yōu)勢(shì)塘辅，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)。
28.HashMap默認(rèn)的bucket數(shù)組是多大皆撩？
默認(rèn)是16扣墩，即時(shí)指定的大小不是2的整數(shù)次冪，HashMap也會(huì)找到一個(gè)最近的2的整數(shù)次冪來(lái)初始化桶數(shù)組扛吞。
小伙伴如果有興趣的話呻惕，歡迎來(lái)閱讀更多文章，搜索并關(guān)注公眾號(hào)“Android技術(shù)迷”關(guān)注后即可閱讀更多文章滥比，感謝關(guān)注亚脆。
