Android面試題數(shù)據(jù)結(jié)構(gòu)篇，如果喜歡請(qǐng)持續(xù)關(guān)注和推薦。

List,Set,Map的區(qū)別

Set是最簡(jiǎn)單的一種集合。集合中的對(duì)象不按特定的方式排序，并且沒(méi)有重復(fù)對(duì)象。 Set接口主要實(shí)現(xiàn)了兩個(gè)實(shí)現(xiàn)類：

HashSet： HashSet類按照哈希算法來(lái)存取集合中的對(duì)象，存取速度比較快
TreeSet ：TreeSet類實(shí)現(xiàn)了SortedSet接口，能夠?qū)现械膶?duì)象進(jìn)行排序。
List的特征是其元素以線性方式存儲(chǔ)，集合中可以存放重復(fù)對(duì)象。

ArrayList() :代表長(zhǎng)度可以改變得數(shù)組?？梢詫?duì)元素進(jìn)行隨機(jī)的訪問(wèn)，向ArrayList()中插入與刪除元素的速度慢。
LinkedList():在實(shí)現(xiàn)中采用鏈表數(shù)據(jù)結(jié)構(gòu)。插入和刪除速度快，訪問(wèn)速度慢。
Map 是一種把鍵對(duì)象和值對(duì)象映射的集合，它的每一個(gè)元素都包含一對(duì)鍵對(duì)象和值對(duì)象。Map沒(méi)有繼承于Collection接口 從Map集合中檢索元素時(shí)，只要給出鍵對(duì)象，就會(huì)返回對(duì)應(yīng)的值對(duì)象。

HashMap：Map基于散列表的實(shí)現(xiàn)。插入和查詢“鍵值對(duì)”的開銷是固定的。可以通過(guò)構(gòu)造器設(shè)置容量capacity和負(fù)載因子load factor，以調(diào)整容器的性能。
LinkedHashMap： 類似于HashMap，但是迭代遍歷它時(shí)，取得“鍵值對(duì)”的順序是其插入次序，或者是最近最少使用(LRU)的次序。只比HashMap慢一點(diǎn)。而在迭代訪問(wèn)時(shí)發(fā)而更快，因?yàn)樗褂面湵砭S護(hù)內(nèi)部次序。
TreeMap ： 基于紅黑樹數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。查看“鍵”或“鍵值對(duì)”時(shí)，它們會(huì)被排序(次序由Comparabel或Comparator決定)。TreeMap的特點(diǎn)在 于，你得到的結(jié)果是經(jīng)過(guò)排序的。TreeMap是唯一的帶有subMap()方法的Map，它可以返回一個(gè)子樹。
WeakHashMao ：弱鍵(weak key)Map，Map中使用的對(duì)象也被允許釋放: 這是為解決特殊問(wèn)題設(shè)計(jì)的。如果沒(méi)有map之外的引用指向某個(gè)“鍵”，則此“鍵”可以被垃圾收集器回收。

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ì)象，開銷很大。ArrayMap用的是copy數(shù)據(jù)，所以效率相對(duì)要高。
3、ArrayMap提供了數(shù)組收縮的功能，在clear或remove后，會(huì)重新收縮數(shù)組，是否空間
4、ArrayMap采用二分法查找；

HashMap和HashTable的區(qū)別

1 HashMap不是線程安全的，效率高一點(diǎn)、方法不是Synchronize的要提供外同步，有containsvalue和containsKey方法。
hashtable是，線程安全，不允許有null的鍵和值，效率稍低，方法是是Synchronize的。有contains方法方法。Hashtable 繼承于Dictionary 類

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ō)比較慢。

HashSet與HashMap怎么判斷集合元素重復(fù)？

HashSet不能添加重復(fù)的元素，當(dāng)調(diào)用add（Object）方法時(shí)候，首先會(huì)調(diào)用Object的hashCode方法判hashCode是否已經(jīng)存在，如不存在則直接插入元素；如果已存在則調(diào)用Object對(duì)象的equals方法判斷是否返回true，如果為true則說(shuō)明元素已經(jīng)存在，如為false則插入元素。

ArrayList和LinkedList的區(qū)別，以及應(yīng)用場(chǎng)景
ArrayList是基于數(shù)組實(shí)現(xiàn)的，ArrayList線程不安全。 LinkedList是基于雙鏈表實(shí)現(xiàn)的。 使用場(chǎng)景：
如果應(yīng)用程序?qū)Ω鱾€(gè)索引位置的元素進(jìn)行大量的存取或刪除操作，ArrayList對(duì)象要遠(yuǎn)優(yōu)于LinkedList對(duì)象；
如果應(yīng)用程序主要是對(duì)列表進(jìn)行循環(huán)，并且循環(huán)時(shí)候進(jìn)行插入或者刪除操作，LinkedList對(duì)象要遠(yuǎn)優(yōu)于ArrayList對(duì)象；

數(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)系）

HashMap的實(shí)現(xiàn)原理：

HashMap是基于哈希表的map接口的非同步實(shí)現(xiàn)，它允許使用null值作為key和value。在Java編程語(yǔ)言中最基本的結(jié)構(gòu)就是兩種，一種是數(shù)組，另一種是模擬指針（引用）。所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個(gè)基本的結(jié)構(gòu)來(lái)構(gòu)造，HashMap也不例外。HashMap實(shí)際上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)。即數(shù)組和鏈表的結(jié)合體。HashMap底層就是一個(gè)數(shù)據(jù)結(jié)構(gòu)，數(shù)組中的每一項(xiàng)又是一個(gè)鏈表。

沖突：
HashMap中調(diào)用Hashcode()方法計(jì)算Hashclde值，由于Java中兩個(gè)不同的對(duì)象可能有一樣的Hashcode。就導(dǎo)致了沖突的產(chǎn)生。

解決：
HashMap在put時(shí)候，底層源碼可以看出，當(dāng)程序試圖將一個(gè)key-value對(duì)象放入到HashMap中，首先根據(jù)該key的hashCode()返回值決定該Entry的存儲(chǔ)位置，如果兩個(gè)Entry的key的hashCode()方法返回值相同，那他們的存儲(chǔ)位置相同，如果這兩個(gè)Entry的key通過(guò)equals比較返回true，新添加的Entry的value將會(huì)覆蓋原來(lái)的Entry的value，但是key不會(huì)被覆蓋，反之，如果返回false，新添加的Entry將與集合中原有的Entry形成Entry鏈，新添加的位于頭部，舊的位于尾部。

原理

利用key的hashCode重新hash計(jì)算出當(dāng)前對(duì)象的元素在數(shù)組中的下標(biāo)。
存儲(chǔ)時(shí)如果出現(xiàn)hash值相同的key，分兩種情況：1、如果key相同，則覆蓋原來(lái)的值。2、如果key不同（出現(xiàn)沖突），則放在鏈表中。
獲取時(shí)，直接找到hash值對(duì)應(yīng)的下標(biāo)，再進(jìn)一步判斷key是否相同，從而拿到對(duì)應(yīng)的值。
Hashmap的核心就是使用數(shù)組進(jìn)行存儲(chǔ)，出現(xiàn)key沖突的時(shí)候，就存放在鏈表中。
ConcurrentHashMap內(nèi)部實(shí)現(xiàn)，HashTable的實(shí)現(xiàn)被廢棄的原因:
1.HashTable容器在競(jìng)爭(zhēng)激烈的并發(fā)環(huán)境下表現(xiàn)出效率低下的原因，是因?yàn)樗性L問(wèn)HashTable的線程都必須競(jìng)爭(zhēng)同一把鎖，那假如容器里有多把鎖，每一把鎖用于鎖容器其中一部分?jǐn)?shù)據(jù)，那么當(dāng)多線程訪問(wèn)容器里不同數(shù)據(jù)段的數(shù)據(jù)時(shí)，線程間就不會(huì)存在鎖競(jìng)爭(zhēng)，從而可以有效的提高并發(fā)訪問(wèn)效率，這就是ConcurrentHashMap所使用的鎖分段技術(shù)，首先將數(shù)據(jù)分成一段一段的存儲(chǔ)，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段數(shù)據(jù)的時(shí)候，其他段的數(shù)據(jù)也能被其他線程訪問(wèn)。
2.ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。Segment是一種可重入鎖ReentrantLock，在ConcurrentHashMap里扮演鎖的角色，HashEntry則用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)。一個(gè)ConcurrentHashMap里包含一個(gè)Segment數(shù)組，Segment的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)， 一個(gè)Segment里包含一個(gè)HashEntry數(shù)組，每個(gè)HashEntry是一個(gè)鏈表結(jié)構(gòu)的元素，每個(gè)Segment守護(hù)者一個(gè)HashEntry數(shù)組里的元素,當(dāng)對(duì)HashEntry數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須首先獲得它對(duì)應(yīng)的Segment鎖。

說(shuō)說(shuō) LruCache 底層原理

LruCache 使用一個(gè) LinkedHashMap 簡(jiǎn)單的實(shí)現(xiàn)內(nèi)存的緩存，沒(méi)有軟引用，都是強(qiáng)引用。如果添加的數(shù)據(jù)大于設(shè)置的最大值，就刪除最先緩存的數(shù)據(jù)來(lái)調(diào)整內(nèi)存。
maxSize 是通過(guò)構(gòu)造方法初始化的值，他表示這個(gè)緩存能緩存的最大值是多少。
size 在添加和移除緩存都被更新值，他通過(guò)safeSizeOf 這個(gè)方法更新值。safeSizeOf默認(rèn)返回1，但一般我們會(huì)根據(jù) maxSize重寫這個(gè)方法，比如認(rèn)為 maxSize 代表是 KB 的話，那么就以KB為單位返回該項(xiàng)所占的內(nèi)存大小。
除異常外首先會(huì)判斷size是否超過(guò)maxSize，如果超過(guò)了就取出最先插入的緩存，如果不為空就刪掉，并把size減去該項(xiàng)所占的大小。這個(gè)操作將一直循環(huán)下去，直到 size 比 maxSize 小或者緩存為空。

最后

喜歡的話可以關(guān)注一下哦，會(huì)每天更新android相關(guān)的文章。